Rethinking the Values interface

[ProfFan]

The current GTSAM Values Value and GenericValue is largely a cascade of workarounds when we migrated from GTSAM 3 to 4. In light of moving in the direction of retiring Boost and having a generic Values container that is (most likely) just a STL container, we need to figure out a way of cleaning up these classes.

The Values object uses boost::ptr_map and clone_-deallocate pairs for memory pool/arena support, which is totally unused by the GenericValue mechanism. Thus the "fast allocators" are kinda nonsense-they never allocate real objects from the custom allocator, only the pair<Key, Value*> since 2014...

The interface of Values, i.e. the iterators (boost::transform_iterator) has few users and in my opinion can be replaced by just returning the interior iterators of the map.

For custom allocation, a great reference is https://www.youtube.com/watch?v=kSWfushlvB8, which covered all the details of making a container allocator-aware, and how to brew your own arena/pools.

CC @dellaert @jlblancoc @varunagrawal

[dellaert]

Yes, I'd love to drastically simplify Values. Not sure whether 4.3 or 5.0, but the evolution I have in mind is that there is only one Values type that can hold everything (discrete, nonlinear, vectors), and only one FactorGraph and BayesNet type. And, indeed, STL containers with zero wrapping costs.

It can't go in 4.2, need to land that now.

[jlblancoc]

If C++17 is an option, here's one possibility:

• std::variant with the most common cases (stored by value) + one wildcard case with a shared_ptr to a virtual interface. Implemented it here for a project: https://github.com/MOLAorg/mola-kernel/blob/9e26fecaaec76126a1fb7172a2a5aa0994be053e/include/mola-kernel/Entity.h#L21-L36
• It would need a helper like this to write code like this to handle the different stored types.

I think that keeping Pose3, etc. and the most common cases as "values" might lead to a compact solution in memory footprint, few memory allocations, etc.

The std::visit idiom is a bit weird at first sight, but OTOH, it's standard C++17.

An alternative would be std::any, too, but I slightly prefer variant since the possible types are all clearly enumerated in its declaration (for good and for bad...).

[ProfFan]

A few pieces here:

1. We probably want the overall API to be similar, so Values should look like a random-access map from Key to Value
2. in any case, a real map is not cheap to access
3. we do not need the values to be ordered, and linearization is not dependent on the order

For an optimization run (no iSAM/iSAM2), the usual step is like this:

1. User add some bunch of values
2. User add some bunch of factors
3. Loop
   1. Linearize
   2. Elimination
   3. Retract
4. Output result

1 and 2 are user-facing but is only a tiny fraction of the compute, so they can be slower.
3.x is the hotspot for the Values and FactorGraph containers. Removal of factors and values are rare.

In the iSAM case we add and remove very often, but the size of (3.2) elimination is relatively small.

So I think we should hide the implementation details of Values to the API. We can provide a default backend to Values that is maybe just a unordered_map<Key, std::variant<T...>>, but also allow this backend to be replaced with something else according to the actual usage.

Same idea goes to FactorGraph. Factor is usually inserted in a sequential manner, and the error functions access (logically) contiguous Values. Factor themselves require some storage for measurements, and access to this storage is also regular. If similar factors can be stored together, we will be able to detect this and vectorize linearization.

In the future, we can even allow optimizers to analyze the structure of the graph and apply solving strategies based on the backend in use. Hiding the implementation from the API allows us to safely rewrite everything without having to worry about API stability.

---

On std::variant: I looked at this extensively: it seems that std::variant is still a bit unfriendly to the compiler codegen. See https://github.com/groundswellaudio/swl-variant and https://www.reddit.com/r/cpp/comments/ktyxqa/variants_suck_but_you_can_get_good_performance/

In godbolt indeed the std::variant is adding some complexity, a large amount of which is doing type checking and exception handling, still probably better than a std::shared_ptr indirection. Main problem is that std::variant lacks an unchecked accessor (I tried a lot of solutions, using undefined behavior I can get rid of the check in clang, but not in GCC: https://godbolt.org/z/Mx65zjb3v). You can tell that the clang codegen is vectorizing the loop if I use the nullptr trick, while gcc is not.

[dellaert]

I looked at Values, and it is a right mess :-) I don't think since switching to 4.0 we need Value and GenericValue anymore, anyway? Perhaps I should add that to the things deprecated in GTSAM 4.2.

@jlblancoc the variant idea is interesting but a bit complex. Is it worth the complexity? Do you see a big speedup, for example?

@ProfFan on factors: I was thinking of "batched factors" as a potentially better solution, because we might not get away easily from shared pointers.

PS, should we convert this to a "discussion" ?