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:
┌──────────────────────┬────────┬────────┬─────────┐
│ 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 │ │ │ │
└──────────────────────┴────────┴────────┴─────────┘
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.
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.