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

31–40 of 42 posts

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

#31

Post by bradleyjg »

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…

> or when faced with a query distribution that prefers locality

Isn't this a fairly common pattern? How would we go about quantifying the preferring locality-ness of a query distribution?

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

#32

Post by ltta_code »

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…

Funny enough, even that paper seems biased as well to me.

This paper probably applies best when you use the HT or tree as a DB index data-structure without constant updates for huuuge datasets, probably not as well when used as an updated associative map in your average program. I'd guess hash-tables (HT) are still faster in day-to-day programmer use but not as much as pointed out here.

Caveats:

- HTs pre-allocated: In the two experiments that show those detailed bar-charts, the hash-tables are completely pre-allocated, so no re-allocation and re-hashing on inserts.

- Charts: The workloads IV-C and IV-E get by far the most attention (3/4 page, 9 bar charts - each), these best support the paper's statements that HTs are much faster and consume less mem than ART. The mixed-use case IV-D is reported with only a single small chart, the whole write-up is just about 1/4 page combined and ART does better (comparable, but still slower than fastest HT) - arguably IV-D is probably most realistic use-case for how most people use hashmaps day-to-day.

- The keys are 64-bit ints so aren't all that long, again maybe common in a DB index but not really what you use hashmaps for mostly in the real world. So ART can't play out some of its strengths.

- The data set skews large, larger than the original paper (16M to 1,000,000,000 (1Billion) keys), and most people probably foremost look at the charts on the right with the huge numbers that make HT look best. Again, makes the results not super applicable to day-to-day hashmap use imo.

- They only look up existing keys, probably not great for either ART nor HT but could hurt their CH*Bucket performance.

Most of these caveats are explained in the test, but some are kind of buried. You can't just look at the charts and conclude hash-tables are 5x as fast as ART, always.

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

#33

Post by leiroigh »

fulafel wrote: post #30
leiroigh wrote: post #29

Earlier quoted context omitted.

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.

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

I'm not sure I agree. When faced with potentially adversarial input, a hash should be keyed. And, depending on the specific tree, you can probably cause a lot of havoc by causing repeated tree reorganizations. Even worse, you have a timing side-channel, because node-split and node-merge are expensive, likely measurable over the network. This can leak info about existing adjacent keys in the database.

This kind of attack is afaik not as researched or well-known as hash collision based attacks, but in my book that is a point in favor of hash tables with keyed hashes.

On the other hand, both approaches shouldn't play in the same league: If you need to support range queries, then you need to support range queries.

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

This is true for scenarios where trees save cache misses (e.g. if there is a correlation between order of queries and location of keys). The linked comparison explicitly compared L3 misses between various trees and various hash tables for various scenarios, and the hash tables come out better in that metric.

All that being said, ART is pretty cool and node16's branch-free SIMD search is amazing.

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

#34

Post by leiroigh »

bradleyjg wrote: post #31
leiroigh wrote: post #29

Earlier quoted context omitted.

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…

> or when faced with a query distribution that prefers locality Isn't this a fairly common pattern? How would we go about quantifying the preferring locality-ness of a query distribution?

>Isn't this a fairly common pattern?

Depends on the application. It is certainly not uncommon that queries fired at close times share a prefix.

>How would we go about quantifying the preferring locality-ness of a query distribution?

I know it when I see it?

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

#35

Post by whatshisface »

bradleyjg wrote: post #31
leiroigh wrote: post #29

Earlier quoted context omitted.

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…

> or when faced with a query distribution that prefers locality Isn't this a fairly common pattern? How would we go about quantifying the preferring locality-ness of a query distribution?

>How would we go about quantifying the preferring locality-ness of a query distribution?

For each level of the tree, treat the incoming stream of queries as a markov process where each state is a query that involves a certain node. So, if I have 7 nodes on level 2, I can build up a table of transition probabilities between vertices like "query involved node 3 on level 2" and "query involved node 7 on level 2." When the transitions between these vertices and themselves have high probability, the queries prefer locality. You can see which scale the locality is preferred on by doing this at each level of the tree.

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

#36

Post by BeeOnRope »

repsilat wrote: post #28

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

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

Sure you can, although at reduced efficiency the "deeper" you go.

For example, while searching a range of size N, you know your next probe point will be at N/2. You also know the probe point after that will be at N/4 or 3N/4, and so on. You know up-front all the possible probe points. Of course, only one out of the two probe points N/4 or 3N/4 or will actually be useful, depending on the N/2 result - but that doesn't stop you from comparing all three in parallel.

You can get a reasonable speedup this way: the extra comparisons happen in parallel and for a moderate depth the unnecessary probes are more than compensated by doing comparisons in parallel.

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

#37

Post by jules »

saagarjha wrote: post #23
jules wrote: post #19

Earlier quoted context omitted.

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.

That's what I said.

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

#38

Post by jules »

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…

Another standard trick to reduce memory is to store a bitfield telling you which pointers are not null, and then store an array of only the pointers that are non null. For example for a Node64 you store a 64 bits bitfield plus only the pointers that are not null, so if that node has only 3 children you store 64 bits plus 3 pointers instead of 64 pointers. You can index that structure by doing a shift + popcount: if you want to find the pointer at index n you first check the n-th bit in the bitfield to see if the pointer is null, and if it isn't you count the number of set bits in bitfield[0..n] to find the index into the pointer array.

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

#39

Post by HenryR »

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…

Authors try to compare their work against hash tables because, usually, HT represent an upper bound on the performance of point-lookups; we don't know how to do much better in general.

So if your data structure supports range queries _and_ point lookups, you should measure against hash tables to understand how far off the ideal you are. If it's not far, and your data structure is strictly more general, that's compelling.

Post reply on HN