Bbtree: Fastest Ordered Map

The real competitors to a Btree like data structure are trie based structures, such as burst tries, (optimised) q-fast and p-fast tries, level compressed tries, bucketed tries, path compressed tries, etc

Also optimised stratified trees (van emde boas) implementations where key length permits.

Full comparison based structures are rarely necessary: ints, floats, strings, etc can be dealt with by lexicographic structures

Tries in particular work outrageously well on (unrealistic) uniform random data with log-logarithmic operation times

As a result, I’m skeptical of “fastest” here

B trees are great though, good work!

Your mileage may vary.

I tested this on a 3D boolean mesh kernel I am working on (this is swapping out std::BTreeMap, no other code changes):

  ┌────────────────────────────────────┬──────────────────────┐
  │       bench 96..1536 faces         │        change        │
  ├────────────────────────────────────┼──────────────────────┤
  │ union/difference,                  │ +11% to +21% slower  │
  ├────────────────────────────────────┼──────────────────────┤
  │ intersection stage,                │ +16% to +34% slower  │
  └────────────────────────────────────┴──────────────────────┘

Then I thought, maybe this shines when you use big maps. I.e. more dense/complext meshes.

So I used one of my test fixtures, a Nefretiti bust scan with a million vertex IDs:

  ┌──────────────────────────────────────┬───────┬────────┐
  │     cage op (seconds, best of 3)     │  std  │ bbtree │
  ├──────────────────────────────────────┼───────┼────────┤
  │ difference                           │ 84.2  │ 83.0   │
  ├──────────────────────────────────────┼───────┼────────┤
  │ union                                │ 83.2  │ 85.6   │
  ├──────────────────────────────────────┼───────┼────────┤
  │ intersection                         │ 61.3  │ 67.1   │
  ├──────────────────────────────────────┼───────┼────────┤
  │ limit-surface difference (best of 2) │ 123.9 │ 147.2  │
  └──────────────────────────────────────┴───────┴────────┘

I.e. a lot of the claims the post makes probably only hold under a specific and possibly narrow set of use cases the author tested agains.

std::BTreeMap must hold ideally hold up well under any use case for such a map. That always means compromises must be made.

  ┌──────────────────────┬────────┬────────┬─────────┐
  │     n = 65536,       │  std   │ bbtree │ bbtree  │
  │    VertexId(u32)     │ BTree- │  Auto  │ Inline- │
  │                      │  Map   │        │   Key   │
  ├──────────────────────┼────────┼────────┼─────────┤
  │ insert               │ 18.3ms │ 12.3ms │ 20.8ms  │
  ├──────────────────────┼────────┼────────┼─────────┤
  │ get                  │ 14.0ms │  9.2ms │ 16.6ms  │
  ├──────────────────────┼────────┼────────┼─────────┤
  │ iterate              │ 0.74ms │ 0.05ms │ 0.10 ms │
  ├──────────────────────┼────────┼────────┼─────────┤
  │ entry().or_default() │ 52ms   │ 47ms   │ 54 ms   │
  │ .push                │        │        │         │
  └──────────────────────┴────────┴────────┴─────────┘

[flagged]

The dynamic web-paper format is nice for expository instructional articles, but here as much time is spent skipping over dynamic stuff in search of human involvement, of which there is thankfully plenty, than reading about the invention itself. It has at least been copyedited by someone even if the structure feels somewhat robotic.

For a map<String, usize> of /usr/share/dict/words (with the value being the dict offset), measuring this consistently using 40% more RAM than std::collections::BtreeMap. Their claim of less memory usage was specifically for integers, so this is more a data point than a refutation.

Very nice work. I'm working on stuff... adjacent to this I guess. I've been harping on the ideas that we have to be much more willing to reach for intrinsics, be laser focused on the cache lines, treat DRAM more like an async block device, but I can't believe I haven't thought to show the impact of coherence traffic! When I get some time I might try to apply some of my tricks to bbtree. DM me. I'd love to be able to reach out when I do.

https://news.ycombinator.com/item?id=50218616

This looks great.

We have smart batching in Dip where we deduplicate work received in what we call a "batched" request. We use BTreeMap to deduplicate work in the preprocessing "scatter" phase.

This deduplication in smart batching is the slowest phase on most bulk write workloads (200k+ inserts in a single request) and takes sometimes up to 3x the time taken for the combined fanout + db writes + db commits + gather.

Will try out with Bbtree and see how it goes.

> No human can write better code than LLMs.

Bold claim...

> Production-ready by formal verification, model checking, deterministic simulation, fuzzing, and lots of testing.

What does model checking mean here?

AI slop alert after reading just the first section on the website.

The quote at the top isn't related to what any of this is so it is pretty funny while being obnoxious

source ?

[flagged]

[dead]

[flagged]