Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
edantec opened this issue Sep 16, 2024 · 2 comments · Fixed by #199
Closed

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

edantec opened this issue Sep 16, 2024 · 2 comments · Fixed by #199

Comments

@edantec
Copy link
Collaborator

edantec commented Sep 16, 2024

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
Copy link
Member

ManifoldFR commented Sep 17, 2024

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
Copy link
Member

ManifoldFR commented Sep 17, 2024

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

They're header only and drop-in replacements.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants