5 ms·

Interesting, Abseil's btree claims to use a larger value: ... for absl::btree_set<int32_t>, nodes currently have 62 children ... https://abseil.io/about/desig

• vlovich123 2y ago
  From the looks of it Rust [1] uses a constant branching factor based on number of items whereas ABSEIL generally uses a target of 256 bytes [3] for branching and fits however many elements fit within that [2]. Rust’s approach seems to be more primitive as ABSEIL is optimizing for cache line usage (not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing?) [1] https://github.com/rust-lang/rust/blob/master/library/alloc/src/collections/btree/node.rs https://github.com/rust-lang/rust/blob/master/library/alloc/... [2] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/internal/btree.h#L428-L443 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724... [3] https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724595912afefc9a567fcaaf5/absl/container/btree_map.h#L93 https://github.com/abseil/abseil-cpp/blob/74f8c1eae915f90724...
  • masklinn 2y ago
    > not sure why it’s several multiples of a cache line - maybe to help the prefetcher or to minimize cache line bouncing? The AMD64 cache line is only 64 bytes, that would make for very low branching factors given interior nodes need a pointer per child, plus key, plus record pointer if b-tree (as opposed to b+tree).
    • vlovich123 2y ago
      To be clear, I was examining only leaf nodes. I’m not sure if interior nodes use the same logic. Still, ABSEIL generally uses a larger branching factor than Rust for some undocumented reason.