Try unordered

[Frank Dellaert]

A possible performance improvement to ExpressionFactor is to make JacobianMap into an unordered instead of a map, and find a way to reserve space on the heap to avoid a bunch of mallocs. @stan84 might you try that and report on result of timeCameraExpression before/after?

[Sungtae An]

Yes, I will try to do that. Is there a kind of deadline you think about?

[Frank Dellaert]

Should not take more than half an hour...

[Sungtae An]

I have changed the type of JacobianMap as boost::unordered_map, but the performance is not too different, rather slightly worse than before using std::map. Is it due to the small number of factors?

Should I commit this?

std::map

GeneralSFMFactor2<Cal3_S2>  : 1.11 musecs/call
Bin(Leaf,Un(Bin(Leaf,Leaf))): 0.834 musecs/call
Ternary(Leaf,Leaf,Leaf)     : 0.806 musecs/call
GenericProjectionFactor<P,P>: 0.859 musecs/call
Bin(Cnst,Un(Bin(Leaf,Leaf))): 0.728 musecs/call
Binary(Leaf,Leaf)           : 0.711 musecs/call

boost::unordered_map

GeneralSFMFactor2<Cal3_S2>  : 1.07 musecs/call
Bin(Leaf,Un(Bin(Leaf,Leaf))): 0.871 musecs/call
Ternary(Leaf,Leaf,Leaf)     : 0.871 musecs/call
GenericProjectionFactor<P,P>: 0.844 musecs/call
Bin(Cnst,Un(Bin(Leaf,Leaf))): 0.801 musecs/call
Binary(Leaf,Leaf)           : 0.777 musecs/call

[Frank Dellaert]

Thanks!! How about putting it in a branch, say feature/BAD_unordered and check it in. But then do one more commit with

• make sure it's unordered provided by boost, as std might be c++11 ?
• make sure you reserve the size with the max number of keys (= number of leaves). Or do you do this already?

The create a pull request with me and @ptf as reviewers...

[Frank Dellaert]

BTW, I'm impressed by your coding speed! :-) And, what machine/OD do you run this on? Obviously much faster than mine :-)

[Sungtae An]

I used boost::unordered_map not the STL one. However, I found out that when I firstly built the 'feature/BAD' branch, there was a compile error:

In file included from /usr/include/c++/4.6/type_traits:35:0,
                 from /home/stan/workspace/gtsam/gtsam/base/Manifold.h:23,
                 from /home/stan/workspace/gtsam/gtsam/base/Lie.h:22,
                 from /home/stan/workspace/gtsam/gtsam/base/LieScalar.h:22,
                 from /home/stan/workspace/gtsam/gtsam/base/LieScalar.cpp:11:
/usr/include/c++/4.6/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the upcoming ISO C++ standard, C++0x. This support is currently experimental, and must be enabled with the -std=c++0x or -std=gnu++0x compiler options.
In file included from /home/stan/workspace/gtsam/gtsam/base/Lie.h:22:0,
                 from /home/stan/workspace/gtsam/gtsam/base/LieScalar.h:22,
                 from /home/stan/workspace/gtsam/gtsam/base/LieScalar.cpp:11:

I had no idea what the problem is because it did not occur when I built the 'develop' branch. Thus, I just built it temporarily with a CXX_FLAG '-std=c++0x' which is used for c++11 standard which we do not want to use for now.

[Sungtae An]

I had JacobianMap reserve the size with the max number of keys. There is no method like reserve() in std::map, so I used some kind of trick which has same effect with the reserve() method.

I have created a pull request, please review it.

[Sungtae An]

In fact, I just changed or added a few lines of code...(did I do correctly?)

I am working on Macbook Pro (late 2013) with 2.3GHZ i7 but on Ubuntu 14.04 as a virtual machine with 6 cores and 8GB RAM. I currently went back to Ubuntu 12.04 due to the compile or test issues.

[Sungtae An]

I have tried std::vector version and the comparison is:

std::map

GeneralSFMFactor2<Cal3_S2>  : 1.14 musecs/call
Bin(Leaf,Un(Bin(Leaf,Leaf))): 0.86 musecs/call
Ternary(Leaf,Leaf,Leaf)     : 0.85 musecs/call
GenericProjectionFactor<P,P>: 0.92 musecs/call
Bin(Cnst,Un(Bin(Leaf,Leaf))): 0.78 musecs/call
Binary(Leaf,Leaf)           : 0.73 musecs/call

boost::unordered_map

GeneralSFMFactor2<Cal3_S2>  : 1.15 musecs/call
Bin(Leaf,Un(Bin(Leaf,Leaf))): 0.98 musecs/call
Ternary(Leaf,Leaf,Leaf)     : 0.93 musecs/call
GenericProjectionFactor<P,P>: 0.91 musecs/call
Bin(Cnst,Un(Bin(Leaf,Leaf))): 0.87 musecs/call
Binary(Leaf,Leaf)           : 0.84 musecs/call

std::vector

GeneralSFMFactor2<Cal3_S2>  : 1.11 musecs/call
Bin(Leaf,Un(Bin(Leaf,Leaf))): 0.78 musecs/call
Ternary(Leaf,Leaf,Leaf)     : 0.73 musecs/call
GenericProjectionFactor<P,P>: 0.88 musecs/call
Bin(Cnst,Un(Bin(Leaf,Leaf))): 0.71 musecs/call
Binary(Leaf,Leaf)           : 0.68 musecs/call

It is slightly better.

[Frank Dellaert]

That's great. Could you add the code changes into a branch/pull-request on BAD so I can look at it?

[Sungtae An]

I have created a pull request. Please review it.

[Frank Dellaert]

This has been superseded by VerticalBlockMatrix wrapper...