Map v8.0.0, it's finally here

Developers Language Support
12

Map V9 is out!

It is 2.25 times more space efficient than V7

It is 4.00 times more space efficient than V8

The primary goal of this release is to fix the issue some people started experiencing some time ago which can prevent canister upgrades when your map grows too big.

V9 reverts its internal structure to the one that is more similar to V7 (as linked nature on V8 was the subject of upgrade issues) but keeps all the improvements described in the original post (like DEQ methods, improved iterators, bidirectionality). The only things that were taken out (impossible to support with the current internal structure) are:

  • putBefore and putAfter are no longer present
  • mutation during iteration is no longer supported
  • (not a direct functionality downgrade) a shift in internal structure makes rehashes necessary again, decreasing the worst case complexity of some methods to linear

V8 map is moving to another repo (Motoko Hash Tree) and will be supported in the future. Its algorithm still has some advantages that can not be achieved with more common hash map algorithms. Though, its usage will be discouraged until we get a motoko compiler that fully fixes serialization/deserialization on upgrades for linked data structures.

On top of fixing the upgrade issue V9 provides huge improvements in terms of consumed space. On average it will consume 1.7 times less space than V7 and 2.7 times less space than V8. In the best case scenario these differences jump up to 2 and 3.5 times respectively. V9 also does not experience an increase in space consumption with Incremental GC enabled (unlike V7 and V8) which will further increase the multipliers to 2.25 and 4. Here I need to note that although V8 seems terrible in terms of space consumption looking at those multipliers, its worst case scenario was always better than V7 (more testing below).

Here is a performance comparison between recent Map versions using 100_000 (Nat32, Nat32) entries.

Structure Insert Get Update Delete Delete Desc Space + Garbage Space
V9 Map 100_565_493 31_135_243 32_997_376 93_732_517 91_153_853 6_292_948 2_097_264
V8 Map 78_535_383 54_324_546 73_834_132 109_237_393 93_839_974 8_000_016 5_600_016
V7 Map 78_533_461 27_591_504 37_182_651 66_453_451 64_171_242 18_706_608 3_448_676

Percentage table, comparing other versions to V9.

Structure Insert Get Update Delete Delete Desc Space + Garbage Space
V9 Map 1.000 1.000 1.000 1.000 1.000 1.000 1.000
V8 Map 0.781 1.745 2.238 1.165 1.029 1.271 2.670
V7 Map 0.781 0.886 1.127 0.709 0.704 2.973 1.644

The next table shows the amount of bytes each map version occupies per single (Nat32, Nat32) entry. Both the default GC and incremental GC were tested.

Structure Min Max Incremental Min Incremental Max
V9 Map 16.00 42.66 16.00 42.66
V8 Map 56.00 56.00 64.00 64.00
V7 Map 32.00 63.50 36.00 67.50

Upgrade strategy

  • Motoko compiler v0.9.8 (or higher) is required for Map V9
  • Add HashUtils as a second parameter to pop and cycle methods
  • The new method no longer requires HashUtils as a first param
  • Migrate all your stable maps using let newMap = Map_9.fromIter(Map_8.entries(oldMap), Map_9.x_hash)
  • Custom HashUtils no longer needs its third compound getNullKey which was a point of misunderstanding for some people (it also no longer requires to exclude 0xffffffff hash value)
11 Likes