aptos-core
aptos-core copied to clipboard
[move-stdlib] Introduce efficient OrderedMap implementation
Description
Implement efficient OrderedMap implementation in move-stdlib, to replace/deprecate SimpleMap. It is an in-memory datastructure - i.e. doesn't store anything in separate resources.
Implementation is a SortedVectorMap, but given the efficiency improvements of vector operations with memcpy, it's performance characteristics are extremely good.
Running different sizes tests (these are full results), we get milliseconds needed for 100 inserts and 100 removals on maps of different sizes:
num elements SimpleMap OrderedMap::SortedVectorMap
10 6.4 6.8
100 25.4 10.3
1000 673.9 12.8
10000 too long 19.5
Basically achieving log(n) performance, with very simple implementation.
How Has This Been Tested?
provided unit tests
Key Areas to Review
Type of Change
- [x] New feature
Which Components or Systems Does This Change Impact?
- [x] Aptos Framework
Checklist
- [x] I have read and followed the CONTRIBUTING doc
- [x] I have performed a self-review of my own code
- [x] I have commented my code, particularly in hard-to-understand areas
- [x] I identified and added all stakeholders and component owners affected by this change as reviewers
- [x] I tested both happy and unhappy path of the functionality
- [ ] I have made corresponding changes to the documentation