Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: A hash array-mapped trie implementation in C

github.com

Post reply on HN
Print view View original

31–40 of 59 posts

Re: Show HN: A hash array-mapped trie implementation in C

#31

Post by flohofwoe »

thechao wrote: post #3

Just 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…

The advantage of the alloc/realloc/free interface is that you can simply plug in the standard functions malloc, realloc and free though, and any other allocator implementation which follows this convention without your own wrapper function inbetween.

Re: Show HN: A hash array-mapped trie implementation in C

#32

Post by flohofwoe »

kazinator wrote: post #18
thechao wrote: post #3

Just 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…

I would drop the API directly and concentrate on the algorithm. If users integrating HAMT need a different allocator situation, they can solve that problem by themselves, without a run-time indirection shim. You can help those users by providing some macros somewhere like #define hamt_malloc(ctx, x) malloc(x) and so forth, so it can be retargeted in one place. Leave an ignored context argument in place for those who…

I used macros in my libraries for overriding the allocation functions before, but have switched to runtime callbacks later, same for logging btw (I'd need to look through the issues list for the exact reasons which led to this decision though). In any case, passing callbacks as part of the initialization "feels" right and I didn't hear any complaints since the switch (and it's definitely a lot more convenient for the library user).

Also, if the library calls those function so frequently that the pointer indirection would be a performance problem, then there's arguably something very wrong with the library's design.

Re: Show HN: A hash array-mapped trie implementation in C

#35

Post by jjgreen »

pixelpoet wrote: post #15
thechao wrote: post #12

Earlier quoted context omitted.

There's a limit to what can be crammed into a HN comment!

I have discovered a truly marvelous allocator pattern which this HN comment is too small to contain.

[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).

Re: Show HN: A hash array-mapped trie implementation in C

#36

Post by masklinn »

nnx wrote: post #10

how does HAMTs compare with more recent designs like Swiss Tables? [1] [1] https://abseil.io/about/design/swisstables

Completely 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.

Re: Show HN: A hash array-mapped trie implementation in C

#37

Post by spacechild1 »

torstenvl wrote: post #6
thechao wrote: post #3

Just 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…

Sadly, this pattern doesn't work with standard realloc() anymore. C23 makes this undefined behavior due to existing non-conforming implementations. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2464.pdf

> Sadly, this pattern doesn't work with standard realloc() anymore

It never really did and it wasn't supposed to.

Re: Show HN: A hash array-mapped trie implementation in C

#39

Post by commandersaki »

silasdavis wrote: post #23
commandersaki wrote: post #21

Are these the same as Crit-bit trees [0]? [0]: 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.

Crit bit tries are also, therefore, sorted. They can be iterated in order. See also https://dotat.at/prog/qp/README.html

Very cool!

Re: Show HN: A hash array-mapped trie implementation in C

#40

Post by JonChesterfield »

Good 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

Post reply on HN