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!
aidenn0
In my experiments, tries easily win out only when comparisons are expensive. Tries struggle against optimized btrees e.g. when you have word-sized integers as the keys.
They do win in simplicity of implementation vs performace. A bog-standard critbit tree with no tricks is almost trivial to implement. Performace wise it stays in the running against anything not heavily optimized.
bollu
you seem to know a lot of data structures :) are there new ones in the 2010s and 2020s that are cool?
virtualritz
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):
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.
xiangpeng
Hi author here, thank you for testing bbtree, bbtree works best if you can implement the `InlinkeKey` trait, would love to see the workloads and check if I missed anything? feel free to create an issue in the repo!
virtualritz
TL;DR: whatever your agent told you it wrote and you then "confirmed" experimentally: there is a disconnect with reality ... somewhere.
I wasted more time on this, literally and figuratively.
InlinkeKey microbench results below.
Each row is one pass over n keys with three variants interleaved in one process:
The same pattern shows at 4k and 1M entries and for the (u32,u32) pair and a (u8,usize) tuple my crate uses. Adding InlineKey makes the narrow keys slower than bbtree without inline keys.
It only beats the trait-less version on the 24-byte edge key. But there it still trails std!
Your post's proven (?) u64 impl is possibly the ceiling for this mechanism on my CPU (Rhyzen 6800H, 8 cores/16 threads). It is at parity with std at 4k to 65k on this CPU and about 10 percent ahead at 1M.
Iteration is where bbtree genuinely wins, 5-15x, but my kernel's time is not in iteration. And I guess that is true for most applications.
You eventually need to add and/or get/read data.
hugmynutus
[flagged]
xiangpeng
Hi author here, first of all, thank you for taking time to read the AI slop, you probably already spend more time than I do on this repo, appreciated!
The inline key: yes, it applies to all kinds of integers and strings, and it exposes InlineKey traits that allow you to implement your own inline prefix.
The checklist items: I forget to cross them and they are all implemented, although I think the checklist item has nothing to do with bbtree. but this is definitely a flaw.
hugmynutus
writing a macro to implement most common integers would've been a time saving.
I also appreciate your paper/work on bf-tree, I started a hobbyist filesystem based on it.
ytxm
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.
jared_hulbert
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.
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.
tyilo
> No human can write better code than LLMs.
Bold claim...
ashkankiani
I had a feeling when I read the title and then started reading the post, "this person must be young, probably a student." I think it's ironic that they're using such unscientific terminology like "fastest" given their background https://xiangpeng.systems/. So clearly, it's in the interest of marketing. Maybe some kind of job advertising/resume thing.
I can almost guarantee that someone has built a custom btree for their specific domain which is faster than this; and that they probably have some or all of the techniques used in this library that are the main contributors to performance, as well. Prefetching is probably the main one they'll claim, and I know personally of some proprietary implementations which have it.
I would like to see some more humility, but I suppose that when you've already resigned your own potential to being below an LLM, then what's the point.
It's not possible or useful for them to grow anymore. Some new frontier model next week will outdo whatever ephemerally useful project this person writes, right? That's the logic?
0c3ca83
Especially since it's trivially proved wrong by inspecting the code. It's invariably awful.
This is only a statement that could be written by someone that doesn't read the code.
marci
I wish his llms included sanakirja* in the comparisons, which has some (human made) speed claims*.
No, he used verus, a rust tool.
And shuffle and ffs. See his docs
aw1621107
Sure. I didn't mean to say that the author used CBMC, only that it's an example of model checking.
Incidentally, the docs don't seem to say what model checker was used. I don't think any of verus, shuffle, or ffs are technically model checkers (or at the very least they don't describe themselves as such)
ozgrakkurt
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
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!
They do win in simplicity of implementation vs performace. A bog-standard critbit tree with no tricks is almost trivial to implement. Performace wise it stays in the running against anything not heavily optimized.
I tested this on a 3D boolean mesh kernel I am working on (this is swapping out std::BTreeMap, no other code changes):
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:
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.
I wasted more time on this, literally and figuratively.
InlinkeKey microbench results below.
Each row is one pass over n keys with three variants interleaved in one process:
The same pattern shows at 4k and 1M entries and for the (u32,u32) pair and a (u8,usize) tuple my crate uses. Adding InlineKey makes the narrow keys slower than bbtree without inline keys.It only beats the trait-less version on the 24-byte edge key. But there it still trails std!
Your post's proven (?) u64 impl is possibly the ceiling for this mechanism on my CPU (Rhyzen 6800H, 8 cores/16 threads). It is at parity with std at 4k to 65k on this CPU and about 10 percent ahead at 1M.
Iteration is where bbtree genuinely wins, 5-15x, but my kernel's time is not in iteration. And I guess that is true for most applications.
You eventually need to add and/or get/read data.
The inline key: yes, it applies to all kinds of integers and strings, and it exposes InlineKey traits that allow you to implement your own inline prefix.
The checklist items: I forget to cross them and they are all implemented, although I think the checklist item has nothing to do with bbtree. but this is definitely a flaw.
I also appreciate your paper/work on bf-tree, I started a hobbyist filesystem based on it.
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.
https://news.ycombinator.com/item?id=50218616
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.
Bold claim...
I can almost guarantee that someone has built a custom btree for their specific domain which is faster than this; and that they probably have some or all of the techniques used in this library that are the main contributors to performance, as well. Prefetching is probably the main one they'll claim, and I know personally of some proprietary implementations which have it.
I would like to see some more humility, but I suppose that when you've already resigned your own potential to being below an LLM, then what's the point.
It's not possible or useful for them to grow anymore. Some new frontier model next week will outdo whatever ephemerally useful project this person writes, right? That's the logic?
This is only a statement that could be written by someone that doesn't read the code.
* https://docs.rs/sanakirja-core
* https://pijul.org/posts/2021-02-06-rethinking-sanakirja#benc...
What does model checking mean here?
[0]: https://www.cprover.org/cbmc/
Incidentally, the docs don't seem to say what model checker was used. I don't think any of verus, shuffle, or ffs are technically model checkers (or at the very least they don't describe themselves as such)
The quote at the top isn't related to what any of this is so it is pretty funny while being obnoxious