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

Beating hash tables with trees? The ART-ful radix trie

the-paper-trail.org

Post reply on HN
Print view View original

11–20 of 42 posts

Re: Beating hash tables with trees? The ART-ful radix trie

#11

Post by jstimpfle »

saagarjha wrote: post #9
jstimpfle wrote: post #8

Earlier quoted context omitted.

You can implement most things with dynamically allocated vectors. Just use indices instead of pointers to link the elements. This can also bring advantage in space efficiency if you're able to do with 4 byte indices instead of 8 byte pointers.

You can consider the entire virtual memory space to be a big vector, where a pointer is just an index into it!

However that's a pretty poor vector. It's not homogeneous (you put things of different shapes inside). That also implies you need sophisticated memory management, leading to further overheads. You cannot meaningfully iterate it.

Re: Beating hash tables with trees? The ART-ful radix trie

#12

Post by saagarjha »

jstimpfle wrote: post #11
saagarjha wrote: post #9

Earlier quoted context omitted.

You can consider the entire virtual memory space to be a big vector, where a pointer is just an index into it!

However that's a pretty poor vector. It's not homogeneous (you put things of different shapes inside). That also implies you need sophisticated memory management, leading to further overheads. You cannot meaningfully iterate it.

I was mostly joking…

Re: Beating hash tables with trees? The ART-ful radix trie

#13

Post by photon-torpedo »

saagarjha wrote: post #9
jstimpfle wrote: post #8

Earlier quoted context omitted.

You can implement most things with dynamically allocated vectors. Just use indices instead of pointers to link the elements. This can also bring advantage in space efficiency if you're able to do with 4 byte indices instead of 8 byte pointers.

You can consider the entire virtual memory space to be a big vector, where a pointer is just an index into it!

Yes, that's exactly how we do it in Fortran 77.

Re: Beating hash tables with trees? The ART-ful radix trie

#14

Post by kccqzy »

jstimpfle wrote: post #8
faragon wrote: post #5

A good point for both RB trees and linear-addressing hash tables is that they can be implemented with vectors( [1], [2]), allowing the case of initial reservation for N elements, so with a tricky implementation you could even have the data structure with one or zero allocations (e. g. allocate the tree or the hash table in the stack). For tries you could use many memory pools for the different node sizes, apply path…

You can implement most things with dynamically allocated vectors. Just use indices instead of pointers to link the elements. This can also bring advantage in space efficiency if you're able to do with 4 byte indices instead of 8 byte pointers.

I tend to use C++'s std::deque as a poor man's arena allocator. I find it works even better than vectors with indices: indeed C++ says pushing at the end will validate iterators but not pointers to the elements themselves. This gets rid of the infrequent resizing in vectors.

Re: Beating hash tables with trees? The ART-ful radix trie

#15

Post by jstimpfle »

saagarjha wrote: post #12
jstimpfle wrote: post #11

Earlier quoted context omitted.

However that's a pretty poor vector. It's not homogeneous (you put things of different shapes inside). That also implies you need sophisticated memory management, leading to further overheads. You cannot meaningfully iterate it.

I was mostly joking…

Yes and I'm serious :-)

Re: Beating hash tables with trees? The ART-ful radix trie

#16

Post by jstimpfle »

kccqzy wrote: post #14
jstimpfle wrote: post #8

Earlier quoted context omitted.

You can implement most things with dynamically allocated vectors. Just use indices instead of pointers to link the elements. This can also bring advantage in space efficiency if you're able to do with 4 byte indices instead of 8 byte pointers.

I tend to use C++'s std::deque as a poor man's arena allocator. I find it works even better than vectors with indices: indeed C++ says pushing at the end will validate iterators but not pointers to the elements themselves. This gets rid of the infrequent resizing in vectors.

I think you have a typo in there, "validate iterators" -> "invalidate iterators".

It should be easy to build a non-invalidating version of the iterator that has a pointer to the chunk and an offset within that chunk. That's more like 12 or 16 bytes, though.

What I like about vectors is that an index is not really about the storage that the vector holds at that position. The index is a mathematical identity of an object. It's the object itself. The vector is only a materialized function that holds some attribute for each object. The nice thing is we can have multiple independent vectors for each object type. This is true modularity.

We can get an address from a simple index with deques, too. But only with significant indirection. So I think if (1) no movement cost on reallocation is allowed, and/or (2) stable pointers are needed, deques are a fine choice. But vectors are my first choice.

Given that we have huge address spaces nowadays we could also consider preallocating large global vectors at stable addresses, and expanding them with mmap(). This way the copying when growing the vector is not needed.

Re: Beating hash tables with trees? The ART-ful radix trie

#17

Post by vbezhenar »

jstimpfle wrote: post #8
faragon wrote: post #5

A good point for both RB trees and linear-addressing hash tables is that they can be implemented with vectors( [1], [2]), allowing the case of initial reservation for N elements, so with a tricky implementation you could even have the data structure with one or zero allocations (e. g. allocate the tree or the hash table in the stack). For tries you could use many memory pools for the different node sizes, apply path…

You can implement most things with dynamically allocated vectors. Just use indices instead of pointers to link the elements. This can also bring advantage in space efficiency if you're able to do with 4 byte indices instead of 8 byte pointers.

You can also use vector of vectors. Reallocating would be cheaper. But access would incur extra indirection.

Re: Beating hash tables with trees? The ART-ful radix trie

#19

Post by jules »

namibj wrote: post #18

Just a friendly reminder that B-trees are often faster on modern microprocessors than RB-trees. See kbtree.h for a simple, yet fast example. I didn't test it, but I'd assume B-tries would be rather efficient.

Red-Black trees are isomorphic to B-trees of node size 4. If you take a Red-Black tree and put each black node together with all its red children into a single node then you get a B-tree of node size 4. An insertion/deletion algorithm for Red-Black trees gives a corresponding insertion/deletion algorithm for B-trees of size 4 and vice versa. Putting those nodes together in a single node probably improves performance already because you have fewer pointers, and you can improve performance further by increasing the size of the B-tree nodes to, say, 32 instead of 4.

Re: Beating hash tables with trees? The ART-ful radix trie

#20

Post by acidx »

Nice article and analysis! I'm actually considering scrapping the trie used in my project to something based off of this one, with some modifications:

For instance, find_node(c, Node48) could avoid the branch if a non-existing index points to an additional entry in child_ptrs that's always NULL. Lookup would be comparable to the Node256 version.

Another thing that could be done, is to scrap the Node48 entirely, and implement two new structs to replace it: Node32 and Node64, and use respectively AVX2 and AVX512. These can be based off of the Node16 version. It remains to be seen if these will yield better performance than the branchless Node48 above, especially if power management kicks in when mixing AVX512 with older SIMD generations.

The trie in Lwan (https://lwan.ws) does an interesting trick to reduce the amount of memory used in the equivalent of a Node256: instead of 256 pointers to a node, it has only 8 pointers. Characters are hashed (MOD 8). The leaf node contains a linked list of key/value pair, and an actual string comparison is performed at the end. (Lwan cheats here by avoiding a string comparison if the linked list contains only 1 element.) Works pretty well, as it's part of the URL routing mechanism.

One other experiment I've been making with tries, is to use the idea of key compression and use it in a different way: slice it every 4 or 8 bytes, consider those bytes as an arbitrary integer, and add every chunk of it to a hashmap, building a chain for the next lookup in some_struct. The prototype I wrote works pretty well.

Post reply on HN