5 ms·
> 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 struc
by jules 12y ago
> 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.
- asynchrony 12y agoCopying 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.
- jules 12y agoNice 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.