Running index-microbenchmarks now to see which is faster :)
Single threaded random lookups: 1.4M/sec for bcachefs, 2M/sec for masstree.
Anna is on my list of systems to include in this review (see https://www.the-paper-trail.org/reading-list/). Looking forward to it!
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).
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/
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.
Something gets bonus points for not needing other libraries or static data, so I could put it in a kernel, but usually I don't really need this.
For example, Judy is LGPL. Darn. That alone is trouble, but Judy makes it more questionable due to non-trivial code in *.h files.
Any good options?
Reason: Ordered access or range queries need a (radix-)tree.
So insertion and removal need to pay for the comparatively slow tree search and rebalancing.
Lookups or mutations could use a hash table that references the same data, especially if no key compression is used for storage.
edit: oh, it's because it's a link and they have some background coloring or something on links.
