Masstree: A cache-friendly mashup of tries and B-trees
the-paper-trail.org
Masstree: A cache-friendly mashup of tries and B-trees
1–10 of 24 posts
Re: Masstree: A cache-friendly mashup of tries and B-trees
#2Related: qp-tries and critbit tries: https://dotat.at/prog/qp/README.html, https://cr.yp.to/critbit.html
Re: Masstree: A cache-friendly mashup of tries and B-trees
#3can't you better hash the keys and match hashes? They arent variable length, and will be unique per unique string regardless of the length.
Re: Masstree: A cache-friendly mashup of tries and B-trees
#4Masstree is one of the DBs Berkeley used when comparing the performance of Anna [1] (now Fluent [2]):
Re: Masstree: A cache-friendly mashup of tries and B-trees
#5can't you better hash the keys and match hashes? They arent variable length, and will be unique per unique string regardless of the length.
That won't give you range queries / ordered iteration, which were the point of using a tree rather than a hash table in the first place.
Re: Masstree: A cache-friendly mashup of tries and B-trees
#6can't you better hash the keys and match hashes? They arent variable length, and will be unique per unique string regardless of the length.
[deleted]
Re: Masstree: A cache-friendly mashup of tries and B-trees
#7Masstree is one of the DBs Berkeley used when comparing the performance of Anna [1] (now Fluent [2]): [1] https://rise.cs.berkeley.edu/blog/anna-kvs/ [2] https://github.com/fluent-project/fluent
[deleted]
Re: Masstree: A cache-friendly mashup of tries and B-trees
#8So what are the advantages over adaptive radix trees or good old judy-dict/array?
Apart from judy being too damn complicated, and too old to be optimized for vector-compare instructions (I think the fancy hand-coded x86 vector-comparisons are the main reason for ART being competitive with judy, considering that it misses at least key compression and the clever allocator, and that ART is not as optimized for using every byte out of every fetched cache-line).
Re: Masstree: A cache-friendly mashup of tries and B-trees
#9So what are the advantages over adaptive radix trees or good old judy-dict/array? Apart from judy being too damn complicated, and too old to be optimized for vector-compare instructions (I think the fancy hand-coded x86 vector-comparisons are the main reason for ART being competitive with judy, considering that it misses at least key compression and the clever allocator, and that ART is not as optimized for using eve…
Here's a recent comparison of Masstree to ART: https://twitter.com/andy_pavlo/status/986647389820747776?s=2...
ART looks to be better in most cases. It's on my list of K-V stores to review: https://www.the-paper-trail.org/page/reading-list/
Re: Masstree: A cache-friendly mashup of tries and B-trees
#10So what are the advantages over adaptive radix trees or good old judy-dict/array? Apart from judy being too damn complicated, and too old to be optimized for vector-compare instructions (I think the fancy hand-coded x86 vector-comparisons are the main reason for ART being competitive with judy, considering that it misses at least key compression and the clever allocator, and that ART is not as optimized for using eve…
Here's a recent comparison of Masstree to ART: https://twitter.com/andy_pavlo/status/986647389820747776?s=2... ART looks to be better in most cases. It's on my list of K-V stores to review: https://www.the-paper-trail.org/page/reading-list/
Cool, looking forward. Please put Judy in as well :)
Seriously, the 17 year old judy is still pretty good, despite it's lack of use of cool vector load / compare / etc instructions for quickly traversing tree nodes that are too small for a full radix search (ART does "simultaneous search", i.e. compares to all stored keys in a single instruction, while judy afaik runs a linear search).
It would be pretty cool if someone vectorized that in judy, and replaced null-terminated strings by a binary-safe representation. Unfortunately, all implementations are old and very hard to read.