Oh, not much, just reimplementing std::vec::Vec for better cache locality on a Sunday afternoon, what's up with you?
Conversation
RRB vector at 2x speed of native Vec at size < branching factor even before head/tail chunking, guess that's a good sign.
Comically, Vec can still do 1000 push_fronts faster than RRB, even though that's essentially O(n²). Cache locality is a hell of a drug.
1
1
28
Replying to
Very curious about the tradeoffs one makes with persistent data structures (eg. in im) vs the simpler std ones when it comes to cache locality. Do the complexity properties make up for slowdowns from all that pointer chasing? Could be handy for helping folks choose between them.
Replying to
In principle, yes, they're all trees so cache locality mostly isn't a thing. The trick us to ameliorate this as much as possible with chunking - basically just having unusually large tree nodes.
1