4 ms·

Anyone who does too much C would know that manually implementing associative array (dictionary) is not fun. I started to use two implementations for my work, bo

by liuliu 7y ago

Anyone who does too much C would know that manually implementing associative array (dictionary) is not fun. I started to use two implementations for my work, both worked pretty well for the things they are good at (and all of them are as "generic" as you can get from C): khash: https://github.com/attractivechaos/klib/blob/master/khash.h https://github.com/attractivechaos/klib/blob/master/khash.h The interface I really liked, and you can customize the hash equality functions. rb from jemalloc: https://github.com/jemalloc/jemalloc/blob/dev/include/jemalloc/internal/rb.h https://github.com/jemalloc/jemalloc/blob/dev/include/jemall... The interface is a bit wacky, but it is flexible enough for my needs. rb shines when you need range queries (keys less than, more than etc.)

codr7 7y ago
I prefer ordered sets with value semantics (which allows using as maps without overhead) to hash tables since I find the performance easier to reason about and often want ordering anyway. The easiest one to implement would be a binary searched vector, but comes with the disadvantage of unstable pointers because of reallocations. rbtrees are definitely trickier, though this one is left leaning which reduces the complexity somewhat (see PDF linked from README).
- liuliu 7y ago
  The rbtree implementation from jemalloc allows you to maintain the value semantics (it is an intrusive design as well). I believe it is also a left-leaning 2-3 red-black tree to be exact. The API is a bit harder to understand but once you get use to it, can be pretty easy to use. It also implemented one trick that embeds the color bit into the right child node pointer, otherwise you are paying a full 8-byte size penalty.
  - codr7 7y ago
    Yeah, that's usually where I draw the line, embedding data in pointers :) Bitfields and packed structs is another angle that I usually don't bother with. Too many details to keep in mind for my feeble brain.

by liuliu 7y ago

codr7 7y ago

I prefer ordered sets with value semantics (which allows using as maps without overhead) to hash tables since I find the performance easier to reason about and often want ordering anyway. The easiest one to implement would be a binary searched vector, but comes with the disadvantage of unstable pointers because of reallocations. rbtrees are definitely trickier, though this one is left leaning which reduces the complexity somewhat (see PDF linked from README).

liuliu 7y ago
The rbtree implementation from jemalloc allows you to maintain the value semantics (it is an intrusive design as well). I believe it is also a left-leaning 2-3 red-black tree to be exact. The API is a bit harder to understand but once you get use to it, can be pretty easy to use. It also implemented one trick that embeds the color bit into the right child node pointer, otherwise you are paying a full 8-byte size penalty.
- codr7 7y ago
  Yeah, that's usually where I draw the line, embedding data in pointers :) Bitfields and packed structs is another angle that I usually don't bother with. Too many details to keep in mind for my feeble brain.