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.

Sign up for GitHub

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

Jump to bottom

[optimization] MapStack lookup optimization #9

Open
bddap opened this issue Feb 12, 2021 · 0 comments
Open

[optimization] MapStack lookup optimization #9

bddap opened this issue Feb 12, 2021 · 0 comments

Comments

@bddap
Copy link
Contributor

bddap commented Feb 12, 2021

MapStack is in a hot path but is uses BTreeMap under the hood.

This optimization will make MapStack insertions and deletions O(1) rather than O(log n).

Let's change MapStack to be less generic, forcing key to be usize. Next let's make sure to only use small numbers for keys.
If we ensure both of those things, we can change the BTreeMap<K, V> in mapstack to Vec<Option<V>>.
@bddap bddap mentioned this issue Apr 8, 2021
Open
@bddap bddap mentioned this issue Apr 22, 2021
Merged
4 tasks
bddap added a commit that referenced this issue Apr 23, 2021
@bddap
MapStack Optimization
65766a9 
impl the optimization described in #9

Results are good.
```
test ancestry::infer_          ... bench:   1,201,454 ns/iter (+/- 20,579)
test ancestry::infer_30        ... bench:   3,758,380 ns/iter (+/- 76,535)
test ancestry::prove_          ... bench:   1,342,813 ns/iter (+/- 31,824)
test ancestry::prove_30        ... bench:   4,210,072 ns/iter (+/- 46,268)
test recursion_minimal::infer_ ... bench:      12,014 ns/iter (+/- 232)
test recursion_minimal::prove_ ... bench:      16,378 ns/iter (+/- 357)
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@bddap