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

51–59 of 59 posts

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

#51

Post by mkirchner »

bionhoward wrote: post #42

Nice work! what were some of the biggest challenges getting this to work?

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

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

#52

Post by JonChesterfield »

mkirchner wrote: post #48
JonChesterfield wrote: post #40

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/v…

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

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

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

#53

Post by mkirchner »

cataphract wrote: post #44
thechao wrote: post #12

Earlier quoted context omitted.

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

Fair enough: struct hamt_allocator { void *(*realloc)(struct hamt_allocator *h, void *chk, size_t oldsize, size_t newsize); }; struct my_allocator { struct hamt_allocator parent; size_t used; char buffer[8192]; }; static void *alloc_func(struct hamt_allocator *h, void *chk, const size_t oldsize, const size_t newsize) { if (!newsize) { return NULL; } if (h && newsize sizeof(alloc->buffer) - alloc->used) { return NULL;…

Beautiful, thanks!

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

#54

Post by kazinator »

hgs3 wrote: post #26
kazinator wrote: post #18

Earlier quoted context omitted.

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've seen this type of API design in C before, but not with a context. I'm curious where HAMT would get the ctx instance to pass to hamt_malloc in this design?

If the macro doesn't use the argument, it doesn't have to exist.

Currently the code does use macros, e.g. mem_alloc(h->ator, size).

Firstly, I'd hide the detail of how the allocator is derived from h into the allocator wrapper routines and just make it mem_alloc(h, size). It's mem_alloc which can do h->ator.

Now the nice thing is that h always exists. So even mem_alloc ignores the first parameter, we don't have to pass something fictional as an argument:

  #define mem_alloc(h, size) malloc(size)
then remove the h->ator and related cruft. Someone who needs a context for their allocator can hack that in.

By the way, if you're going to have allocator providers, you want:

  #define mem_alloc(h, size) h->ator->alloc(h->ator, size)
                                            ^^^^^^^
and not:

  #define mem_alloc(h, size) h->ator->alloc(size)
like the code has it now.

Thou shalt not define a C callback interface without a context pointer.

Without a context pointer, you cannot have an allocator module where you can bind different allocator arenas to different objects.

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

#55

Post by naasking »

cbarrick wrote: post #11
nnx wrote: post #10

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

Swiss 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 impl…

> HAMTs are hash tries. O(log(n)) lookup, but persistent / cheep to copy.

O(LOG(k)) might be a clearer bound rather than n.

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

#56

Post by cataphract »

cataphract wrote: post #44
thechao wrote: post #12

Earlier quoted context omitted.

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

Fair enough: struct hamt_allocator { void *(*realloc)(struct hamt_allocator *h, void *chk, size_t oldsize, size_t newsize); }; struct my_allocator { struct hamt_allocator parent; size_t used; char buffer[8192]; }; static void *alloc_func(struct hamt_allocator *h, void *chk, const size_t oldsize, const size_t newsize) { if (!newsize) { return NULL; } if (h && newsize sizeof(alloc->buffer) - alloc->used) { return NULL;…

While this was not the point of the comment, one thing missing is that oldsize and newsize should be rounded for alignment purposes:

    struct my_allocator {
        struct hamt_allocator parent;
        size_t used;
        union {
            char buffer[8192];
            max_align_t _align;
        };
    };
    
    static inline size_t align_size(size_t value)
    {
        size_t alignment = _Alignof(max_align_t);
    
        // if (value % _Alignof(max_align_t) == 0) {
        //     return value;
        // } else {
        //     return ((value / alignment) + 1) * alignment;
        // }
    
        return value + (alignment - 1) & ~(alignment - 1);
    }
Even better, the allocator function should get the alignment so don't waste bytes unnecessarily.

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

#57

Post by torstenvl »

kazinator wrote: post #20
torstenvl wrote: post #6

Earlier quoted context omitted.

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

The pattern was never specified as fully working. Not in C99 and C90. It's due to the following reason: it was never specified that realloc(ptr, 0) behaves like free(ptr). The case of size == 0 is not separately discussed in the C99 description of realloc. realloc(ptr, 0) can behave like (free(ptr), malloc(0)), where malloc(0) doesn't necessarily behave like ((void *) 0). Malloc may return a unique object that may be…

I stand corrected! Thanks :)

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

#58

Post by cbarrick »

naasking wrote: post #55
cbarrick wrote: post #11

Earlier quoted context omitted.

Swiss 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 impl…

> HAMTs are hash tries. O(log(n)) lookup, but persistent / cheep to copy. O(LOG(k)) might be a clearer bound rather than n.

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

Post reply on HN