Hacker News Reader

> My understanding is that 4 is a relatively sweet spot for allowing efficient consing/deconsing of the finger nodes.

I doubt it. For the persistent data structures I've implemented a branching factor of 32 or 64 worked best (persistent hash maps, vectors, and b+ trees). A high branching factor keeps the depth of the tree very small. Copying a block of memory a few times is cheaper than copying a little memory block a lot of times.

View on HN

Copying the fingers is the most common operation. Every cons/decons requires copying one of the fingers. Operations that propagate deeper into the tree are lazy, so the primary factor affecting performance of common operations is time required to copy one of the fingers. The result of using a higher branching factor would be copying a larger memory block many times.

Nice in theory, but my benchmarks show otherwise :) Copying a 32 words of memory doesn't take much more time than copying 1 word of memory.

Reply on news.ycombinator.com