Repository files navigation

An implementation ofHAMT(Hash Array Mapped Trie, Bagwell) in Swift.Eonil, May 2019.

UseHAMT type. This type provides these features.

• Hash-based key-value storage.
• All of read/write/copyamortized O(log(n)) time up to certain number of elements(seePerformance section), andO(n) at worst.
• Full"Copy-on-Write" behaviorwith minimal amount of copying.

The type provides these dictionary-like interfaces.

• Conformance toSequence protocol.
• Conformance toEquatable protocol.
• isEmpty: Bool
• count: Int
• subscript(Key) -> Value? { get set }
• subscript(Key, default: @autoclosure () -> Value) -> Value { get set }
• keys: Sequence
• values: Sequence

These features are not supported (maybe yet).

• Index and index based look-up and iteration.
• Any other collection protocol conformance.

As like most Swift datastrctures,HAMT is also fully CoW compliant. This meanseach copy of same HAMT tree shares data as much as much possible. Regardlesof how many copies you make, HAMT shares most portion of tree with all othercopies.

HAMT type in this library is designed to be used aspersistent datastructure.

In copy-persistent scenario under 64-bit environment,HAMT provides near constant time (O(log(n)) & max depth=10, -> O(10)) single element read/write/copyperformance up to hash resolution limit ((2^6)^10 items) regardless of contained itemcount if hash function is well distributed. Also new copy does not take extra space unlessgets mutated. Copy with single element mutation takesO(log(n)) extra time and space.On the other hand, copyingSwift.Dictionary takesO(n) time and extra space.

Instead, single element read/write ofHAMT is about 2x/50x times slowerthan ephemeralSwift.Dictionary for random 64-bit integer keys and values.

Note that "operation count" in above graph is accumulated number.

Here's another performance comparison with copying B-Tree.NaiveSwift.Dictionary is not drawn here because read/write performanceis same with ephemeral one, and copying it takes too much time and didn't finish.

For small dataset, naive copying ofSwift.Dictionary works better, but ascopying cost increases linearly, it is no longer efficient after 1,000 items.

Therefore,HAMT is better if you need a hash-based persistent associative arraydata structure that can grow more than several thousands.

B-Tree shows better write performance overall. HAMT performs better after 100Kitems, but it doesn't seem to be really practical numbers. And it requires keysto beComparable. By the way, as B-Tree doesn't have hash collision, it'll showmore reliable performance.

HAMT type is implemented usingPD5Bucket64 internally.PD5Bucket64 type provides all additional properties for testing andvalidation.PD4 type was an implementation of hash-trie, and deprecated due tohigh rate of wasted memory.PD5 implements HAMT and shows nearlysame performance withPD4 with far less memory consumption.

I usedPD5 prefix for convenience only for internals. Public major typename isHAMT, and internal types all usePD5 prefixed. If I implementa next version of algorithm, it'll be named asPD6.

If once implementation gets stabilized, maybe I'll rename allPDx prefixestoHAMT someday.

At this point, only 64-bit platforms are considered. It should work on32-bit platforms but less performance and have not been tested.

If you link this library, you'll notice the performance is not good as shownin the graph.As like Károly Lőrentey clarified,it's because Swift compiler does not inline and optimize over externallylinked functions.You can compile HAMT source code with your code together in samemodule to archive best possible performance.

• See also"B-Tree for Swift" by Károly Lőrenteyif you need sorted associative array.

• Here's anice explanation of how HAMT works by Marek.

• For more information about HAMT, seethe paper by Phil Bagwell.

Sending contribution means implicit agreement to redistributeyour contribution under "MIT License".

This code is licensed under "MIT License".Copyright Eonil, Hoon H.. 2019.All rights reserved.