3 ms·
My understanding is that 4 is a relatively sweet spot for allowing efficient consing/deconsing of the finger nodes. I became fascinated by fingertrees a few yea
by asynchrony 12y ago
My understanding is that 4 is a relatively sweet spot for allowing efficient consing/deconsing of the finger nodes. I became fascinated by fingertrees a few years ago and created several toy implementations. I recall that the size of the fingers did impact the performance of various operations though I no longer remember.
Sadly I do recall that the constant factors were prohibitively high which made finger trees rather unsuited as an every day list/array data structure for most applications. It would certainly simplify programming to have one sequential collection type that is adequately performant at everything.
- 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.