aptos-core icon indicating copy to clipboard operation
aptos-core copied to clipboard

[move-stdlib] Introduce efficient OrderedMap implementation

Open igor-aptos opened this issue 4 months ago • 2 comments

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

igor-aptos avatar Oct 04 '24 18:10 igor-aptos