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" ?

[dellaert]

@ProfFan please approve #1408 when you have a moment. It is the same as #1407 but for 4.3, where a lot of boost iterator code is simply removed from Values, making our work a bit easier.

I experimented with Any and I think this is a good 4.3. solution. Here is an incomplete prototype:

class Values {
 public:
  /// @name Testable
  /// @{

  /** print method for testing and debugging */
  void print(const std::string& str = "",
             const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;

  /** Test whether the sets of keys and values are identical */
  bool equals(const Values& other, double tol = 1e-9) const;

  /// @}
  /// @name Standard Interface
  /// @{

  /** The number of variables in this config */
  size_t size() const { return values_.size(); }

  /** whether the config is empty */
  bool empty() const { return values_.empty(); }

  // Store the values in a map of std::Any:
  std::map<Key, std::any> values_;

  // Insert without checking key.
  template <typename T>
  void _insert(Key key, const T& value) {
    values_.emplace(key, value);
  }

  /**
   * Templated version to add a variable with the given j,
   * throws KeyAlreadyExists<J> if j is already present
   */
  template <typename T>
  void insert(Key key, const T& value) {
    // Check if the key already exists
    if (values_.find(key) != values_.end()) {
      throw ValuesKeyAlreadyExists(key);
    }
    // Insert the value
    _insert(key, value);
  }

  // Update without checking key, but does check type.
  template <typename T>
  void _update(Key key, T value) {
    // Check if the type is correct
    // TODO(dellaert): handle matrix conversions
    try {
      std::any_cast<T>(values_.at(key));
      values_[key] = value;
    } catch (const std::bad_any_cast&) {
      throw ValuesIncorrectType(key, typeid(values_.at(key)), typeid(T));
    }
  }

  /**
   * Templated version to update a variable with the given key,
   * throws KeyDoesNotExist<J> if key is not present.
   */
  template <typename T>
  void update(Key key, T value) {
    // Check if the key exists
    if (values_.find(key) == values_.end()) {
      throw ValuesKeyDoesNotExist("Values::at", key);
    }
    _update(key, value);
  }

  /// Templated version to insert_or_assign a variable with the given key.
  template <typename ValueType>
  void insert_or_assign(Key key, const ValueType& val) {
    // Check if the key exists
    if (values_.find(key) == values_.end()) {
      _insert(key, val);
    } else {
      _update(key, val);
    }
  }

  /** Add a set of variables, throws KeyAlreadyExists<J> if a key is already
   * present */
  void insert(const Values& values);

  /**
   * Check if a value exists with key \c key.  See exists<>(Key key)
   * and exists(const TypedKey& key) for versions that return the value if it
   * exists. */
  bool exists(Key key) const;

  /** Retrieve a variable by key \c key.  The type of the value associated with
   * this key is supplied as a template argument to this function.
   * @param key Retrieve the value associated with this key
   * @tparam T The type of the value stored with this key, this method
   * Throws
   * - ValuesKeyDoesNotExist if the key does not exist
   * - ValuesIncorrectType if the requested type is not correct
   * - DynamicValuesIncorrectType if a stored matrix/vector cannot be returned.
   * @return The stored value
   */
  template <typename T>
  const T& at(Key key) const {
    // Check if the key exists
    if (values_.find(key) == values_.end()) {
      throw ValuesKeyDoesNotExist("Values::at", key);
    }
    // Check if the type is correct
    // TODO(dellaert): handle matrix conversions
    try {
      return std::any_cast<const T&>(values_.at(key));
    } catch (const std::bad_any_cast&) {
      throw ValuesIncorrectType(key, typeid(values_.at(key)), typeid(T));
    }
  }

  /** Retrieve a variable by key \c j.  This version returns a reference
   * to the base Value class, and needs to be casted before use.
   * @param j Retrieve the value associated with this key
   * @return A const reference to the stored value
   */
  template <typename T>
  T& at(Key key) {
    // Check if the key exists
    if (values_.find(key) == values_.end()) {
      throw ValuesKeyDoesNotExist("Values::at", key);
    }
    // Check if the type is correct
    // TODO(dellaert): handle matrix conversions
    try {
      return std::any_cast<T&>(values_.at(key));
    } catch (const std::bad_any_cast&) {
      throw ValuesIncorrectType(key, typeid(values_.at(key)), typeid(T));
    }
  }

  /// @}
};

Comments?

[jlblancoc]

Yes, I think std::any may be the best solution. 👍
std::variant is good, but requires a fixed enumeration of types. With any plus your templated at<> method, things should move on great.
The only downside was the lack of info on the actually stored type, but you already added a typeid() in the exception, so users will have a hint in the case of errors. For me, it's probably the best option!

[dellaert]

See #1411 for getting rid of boost completely. I could not make Values work with std::any. Turns out our GenericValue mechanism from back in the day is pretty nifty, and allows the trait-based Retract/dim/print etc. Open to suggestions to use fancy c++17 features, but ChatGPT could not give me a good answer :-)