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

21–30 of 42 posts

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

#21

Post by amluto »

acidx wrote: post #20

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

The AVX512 power issues and startup latency likely mean that using it it will likely be a loss except in microbenchmarks or unusual workloads.

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

#22

Post by jamii »

My experience has been that the vast majority of papers on data-structures are at best misleading, and at worst deliberately biased.

For example:

> The hash table used by the authors of ART in their study was a chained hash table, but this kind of hash tables can be suboptimal in terms of space and performance due to their potentially high use of pointers.

> Our experiments strongly indicate that neither ART nor Judy are competitive to the aforementioned hashing schemes in terms of performance, and, in the case of ART, sometimes not even in terms of space.

https://www.victoralvarez.net/papers/A%20Comparison%20of%20A...

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

#23

Post by saagarjha »

jules wrote: post #19
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…

They are isomorphic, but B-Trees are more cache friendly. B-Trees store more in each node, while red-black trees require pointer chasing for each element.

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

#25

Post by jstimpfle »

jamii wrote: post #22

My experience has been that the vast majority of papers on data-structures are at best misleading, and at worst deliberately biased. For example: > The hash table used by the authors of ART in their study was a chained hash table, but this kind of hash tables can be suboptimal in terms of space and performance due to their potentially high use of pointers. > Our experiments strongly indicate that neither ART nor Judy…

Related: https://nothings.org/computer/judy/

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

#26

Post by jstimpfle »

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.

I believe RB-trees are preferred e.g. in the linux kernel because of pointer stability.

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

#27

Post by marknadal »

Radix trees are one of the most under utilized data structures.

They are great and have fantastic performance!

I implemented a custom on disk storage engine with a Radix format, and am getting on a low end MacBook Air 2015 about 3K/acked writes to disk/second! It is now the default at https://github.com/amark/gun the code is pretty short too.

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

#28

Post by repsilat »

> This is superior to binary-search: no branches (except for the test when bitfield is 0), and all the comparisons are done in parallel

Branchless binary search isn't hard to implement if you know (or can bound) the number of elements statically. You just use the comparison result arithmetically instead of branching on it, and you unroll the loop.

Obviously a binary search can't do comparisons in parallel, though.

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

#29

Post by leiroigh »

jamii wrote: post #22

My experience has been that the vast majority of papers on data-structures are at best misleading, and at worst deliberately biased. For example: > The hash table used by the authors of ART in their study was a chained hash table, but this kind of hash tables can be suboptimal in terms of space and performance due to their potentially high use of pointers. > Our experiments strongly indicate that neither ART nor Judy…

It is unsurprising that a structure designed for range queries loses out against hashes for random point look-ups.

Thanks for posting that addition and very nice link. It is completely unclear why authors in this field even attempt to compete with hash-tables for random point queries: Trees (whether comparison or radix) make only sense when using either range queries or when faced with a query distribution that prefers locality.

Something I'd like to see is benchmarks of batch-query performance: If we can queue a couple of queries, then trees should gain a lot from processing them in-order (then, the last query has already warmed the cache for the next; this probably can pay for approximately sorting the batch).

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

#30

Post by fulafel »

leiroigh wrote: post #29
jamii wrote: post #22

My experience has been that the vast majority of papers on data-structures are at best misleading, and at worst deliberately biased. For example: > The hash table used by the authors of ART in their study was a chained hash table, but this kind of hash tables can be suboptimal in terms of space and performance due to their potentially high use of pointers. > Our experiments strongly indicate that neither ART nor Judy…

It is unsurprising that a structure designed for range queries loses out against hashes for random point look-ups. Thanks for posting that addition and very nice link. It is completely unclear why authors in this field even attempt to compete with hash-tables for random point queries: Trees (whether comparison or radix) make only sense when using either range queries or when faced with a query distribution that prefe…

Some other good reasons to use trees/tries, besides the ones you mention:

- reasonable worst-case behaviour (think real-time apps, or adverserial scenarios)

- persistent data structures (eg HAMT), as used in Clojure, Scala & Immutable.js

And the speed boost from locality gets more dramatic every passing year as the memory gap keeps widening.

Post reply on HN