6 ms·
Show HN: A hash array-mapped trie implementation in C
Long-simmering side project that is finally ready to see the light. HAMTs are a cool persistent data structure and implementing one has been a lot of fun. Beyond the code, there is likely some value in the extensive and largely complete implementation docs; basic benchmarks are linked in the README, too.
Kind of aiming to be "the libavl for HAMTs". That is obviously a high and aspirational bar but a distinct possibility if it stirs up a little interest and/or contribution.
Anyways, it's time for this to go out, collect feedback and maybe even some use outside of toy projects. Let me know how it goes.
- tombert 3y agoI discovered HAMTs first when Erlang added support for first-class maps, and it was sort of a "holy shit!" moment for me. They felt like the "holy grail" of data structures for me; I can treat any updates as "copies" without the cost of a copy. About a year later, I learned Clojure, and fell even more in love with the data structure; when the language fully embraces a useful data structure, it changes the way you think about the entire program, and now it's sort of hard for me to go back to languages that don't have a good HAMT implementation. I mean, I still do it, but I do think that having a "go to standard" in C really has the potential to set a great precedent.
- thechao 3y agoJust a note about your 'exported memory allocation' API: struct hamt_allocator { void *(*malloc)(const size_t size); void *(*realloc)(void *chunk, const size_t size); void (*free)(void *chunk); }; This whole thing could just be: struct hamt_allocator { void *cookie; void* (*realloc) (struct hamt_allocator* h, void* chk, const size_t size); }; With the following constraints: 1. `realloc(H, nullptr, N)` -- allocated N bytes 2. `realloc(H, p, 0)` -- frees the pointer p 3. `realloc(H, p, N)` -- resizes the pointer p And, the user has access to a 'context' (`cookie`) so they can use a (for instance) pool allocation scheme. Personally, I like a slightly different API: struct hamt_allocator { void *cookie; void* (*realloc) (struct hamt_allocator* h, void* chk, const size_t oldsize, const size_t newsize); }; With the following constraints: 1. `realloc(H, nullptr, 0, N)` -- allocated N bytes 2. `realloc(H, p, N, 0)` -- frees the pointer p 3. `realloc(H, p, N, M)` -- resizes the pointer p But I know a lot of people get confused and/or don't like having to pass (& thus keep) so much information to the allocator.
- david2ndaccount 3y agoI generally like this pattern, but why pass the allocator instead of the cookie?
- thechao 3y agoIf you want to "shim" the API, then it's easier to have the whole previous object, rather than just the cookie.
- cataphract 3y agoYou don't need the cookie then. You can just allocate a larger struct (sort of subclassing it). You save a pointer indirection.
- thechao 3y agoThere's a limit to what can be crammed into a HN comment!
- pixelpoet 3y agoI have discovered a truly marvelous allocator pattern which this HN comment is too small to contain.
- jjgreen 3y ago[350 years later] I have confirmed the optimality of the allocator pattern as a special case in my proof of the Inter-universal Teichmüller theorem (Springer, 879pp).
- inopinatus 3y agoThe solution is obviously to realloc the comment.
- cataphract 3y ago
- vinkelhake 3y agoIf you're interested in persistent data structures for C++, then I highly recommend Immer. High quality and easy to work with. https://github.com/arximboldi/immer https://github.com/arximboldi/immer
- nnx 3y agohow does HAMTs compare with more recent designs like Swiss Tables? [1] [1] https://abseil.io/about/design/swisstables https://abseil.io/about/design/swisstables
- cbarrick 3y agoSwiss Tables are hash tables. O(1) lookup, but expensive to copy. HAMTs are hash tries. O(log(n)) lookup, but persistent / cheep to copy. They are not really comparable, since hash tables are not persistent. In functional languages, persistent data structures are MUCH more natural to work with. HAMTs we're originally created for the Clojure standard library, IIRC. HAMTs lend themselves to more elegant/performant implementations than self-balancing trees, since they don't need to rebalance as long as your hash function is good. Also, HAMTs generally have a high branching factor, so the search can be as fast as a hash table for small-to-medium maps. Though I don't know of any HAMTs using SIMD tricks like Swiss Table. (EDIT: I guess the popcnt thing that HAMTs do would be considered a SIMD trick. Larger registers would allow the branching factor to be raised.) Like hash tables, HAMTs don't require intermediate key comparison for lookup. The original HAMT paper is a good read: http://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf http://infoscience.epfl.ch/record/64398/files/idealhashtrees...
- naasking 3y ago> HAMTs are hash tries. O(log(n)) lookup, but persistent / cheep to copy. O(LOG(k)) might be a clearer bound rather than n.
- cbarrick 3y agoFor a hash trie, the depth is bounded by the log of the number of elements: O(log(n)). I think O(log(k)) would mean that the bound is based on the size of the largest key. This may be true of regular tries, but not of hash tries.
- masklinn 3y agoCompletely unrelated. The primary advantage of hamt is that they’re persistent, so they’re immutable with cheap update, but with efficient lookup & good cache behaviour thanks to the dense nodes and high branching factor.
- ghotli 3y agoNot much to add other than this is cool and the README was very informative. Nice work!
- erichocean 3y agoHow does this compare to https://github.com/arximboldi/immer https://github.com/arximboldi/immer (other than the C/C++ difference)? Also, it's my understanding that, in practice, persistent data structures require a garbage collector in order to handle deallocation when used in a general-purpose way. How does your implementation handle that? Also, have you seen https://github.com/cnuernber/ham-fisted https://github.com/cnuernber/ham-fisted ? I think there are a few other Java-based persistent collections as well in the overall Clojure ecosystem that also improve on Hickey's original implementation, but I can't recall them now…
- magicalhippo 3y ago> How does your implementation handle that? This is explained in the readme[1]. You can pass custom allocation functions (mallic, realloc, free), so you can plug in Boehm fex. [1]: https://github.com/mkirchner/hamt#memory-management https://github.com/mkirchner/hamt#memory-management
- dumdumchan 3y agoSo refcounting?
- aidenn0 3y agoBeohm is not refcounting, it's a tracing GC.
- vkazanov 3y agoBoehm is not tracing, it's a conservative GC. PS admittedly, terminology is not precise enough in this space.
- aidenn0 3y agoI would say that the terminology is pretty good in this space, and BDWGC is a conservative tracing GC. A tracing GC determines reachability by following (i.e. tracing) chains of references. A precise GC will retain exactly the set of reachable objects, a conservative GC will retain potentially more. Tracing GCs might be precise (or not), they might handle internal-pointers (or not), they might move the data (or not), they might handle variable sized allocations (or not).
- kazinator 3y agoDoc fix: Iterators section repeats a code block with these declaration from the previous section: size_t hamt_size(const struct hamt *trie); const void *hamt_get(const struct hamt *trie, void *key);
- commandersaki 3y agoAre these the same as Crit-bit trees [0]? [0]: https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html Edit: I think I understand now from the design section on your page, they are both tries, but the HAMT uses the hash of the key to locate the node whereas Crit-bit uses the key itself.
- silasdavis 3y agoCrit bit tries are also, therefore, sorted. They can be iterated in order. See also https://dotat.at/prog/qp/README.html https://dotat.at/prog/qp/README.html
- commandersaki 3y agoVery cool!
- robbintt 3y agoThat's cool! I recently had GPT-4 write me a HAMT in C++, and it somewhat works, a lot of the basics are there. I ran out of time but am planning on fixing it up with instruct. It missed a lot of stuff and its tests run but they aren't very good.
- deleted 3y ago[deleted]
- query2 3y agoIs enum { N = 5; }; legal C now with the semiclolon inside the braces?
- spacechild1 3y agoNice! I think you should really add a userdata member to hamt_allocator. Not every memory allocator is global!
- mkirchner 3y agoAgree. I was trying to mostly mimick the libavl API, hence the design decision.
- JonChesterfield 3y agoGood datastructure, code looks quite clean for C. Your API is missing some of the advantages relative to hash tables though. Because it's a tree, operations like union and difference of two instances can be sublinear in the size of the instances. E.g. union can copy subtrees when the other instance has empty at the corresponding position. You're also missing a batch construction call, create a new tree out of N key/value pairs. That's much faster than inserting one at a time because you can sort the array up front and then create the tree without any temporary nodes. The function pointers in the interface are probably difficult for the compiler to devirtualise. Changing that in C means macros or code generators though, does some damage to ease of use. Thanks for sharing it
- mkirchner 3y agoThank you, happy to share. These are excellent pointers. Regarding the batch construction, it's not immediately clear to me how to implement sorting since the order is implicit through the hash function (it seems one would need to construct a trie to build a trie?) but I might be wrong...
- JonChesterfield 3y agoHash the keys before/while sorting. The repeated hashing with different seeds is an interesting approach to collisions but would add some annoyance here. Roughly do just enough work to put the key/values in the same order that you would see them in when iterating through the corresponding trie. Other way to go would be to implement merge then do the batch construction by partitioning the initial array, building tries out of the pieces then merging them. That could also be the fallback for when the first hash collides. If the partitioning was by the first five bits of the hash you'd get a reasonable approximation to doing the sort.
- fanf2 3y agoI have spotted a couple of ways to improve performance: Increase the size of the bitmap in each node from 32 bits to 64 bits. You are wasting 4 bytes per node, and wider nodes mean fewer indirections for each lookup. Change the recursion in the lookup to iteration. You used iteration in other traversals, and it should be much more efficient.
- mkirchner 3y agoThanks! Yes, basically log_64(n) vs. log_32(n) and it would also require to switch to a 64 bit hash function and adjust hash exhaustion and bit fiddling arithmetic accordingly. Re the impact of the recursion, that's actually zero for the search code since clang does a tail call optimization; it's a fair point for the removal code.
- bionhoward 3y agoNice work! what were some of the biggest challenges getting this to work?
- mkirchner 3y ago#1 doing it in many 20-30min batches with little kids #2 see #1 Jokes aside, IMHO there was not a single challenge standing out in terms of implementation; getting the pieces to work together and finding residual bugs was hard. LLDB was my friend but still missing valgrind on Mac. Writing (and re-writing) the docs really helped with mental clarity and not having to stress about a deadline was not hurting either. I often just closed the lid and made it my future self's problem with good success ;-) Oh, and one thing I am proud of: how well the recursive search generalized to path copying. That came together very nicely.
- fsloth 3y agoBagwell’s HAMT paper is one of my favourite data structure papers! Thanks for sharing! In case this is unfamiliar topic - immutable value based programming is super cool because it simplifies the cognitive load of reasoning about your program - hence enabling you to write better programs per-unit-of-effort consumed.
- pkkm 3y agoI like how readable the code and docs are. Thanks for sharing.
- photon_lines 3y agoI just did a bit of a write-up on HAMTs and you can find it here: https://photonlines.substack.com/p/grokking-hash-array-mapped-tries https://photonlines.substack.com/p/grokking-hash-array-mappe... I actually included your repo as well in the mentions at the end of the article so hopefully it helps :)