Simple-Robotics / aligator

A versatile and efficient framework for constrained trajectory optimization
https://simple-robotics.github.io/aligator/
BSD 2-Clause "Simplified" License
144 stars 19 forks source link

Replace vector of CostPtr in CostStack objects by a map of CostPtr #195

Closed edantec closed 2 months ago

edantec commented 2 months ago

When creating a CostStack, the user must keep in mind the index of each Cost component they have defined, in order to be able to modify the Cost object later on. It would be more intuitive to use std::map<String,CostPtr> to retrieve each component, instead of using std::vector<CostPtr>.

ManifoldFR commented 2 months ago

We can be use boost::unordered_map for now. It is quite fast, faster than std::unordered_map in recent versions of Boost (> 1.80), and we depend on boost already.

https://martin.ankerl.com/2022/08/27/hashmap-bench-01/#boost__unordered_map

The benchmark in the above link also suggests well-balanced performance across the board. There is also the choice of allocator and hash function, but I don't think it's that important at this point.

One important aspect for MPC is having stable references (explained in the benchmark). We can't afford an insertion into the map moving other elements around because we want to be able to keep our own "book" of the components for e.g. on-the-fly modification.

ManifoldFR commented 2 months ago

Two other options are robin_hood maps and unordered_dense from the author the benchmark:

They're header only and drop-in replacements.