finger-tree

finger-tree copied to clipboard

Plan:

• [x] Benchmark current implementations of from, prepend, and append.
• [ ] Implement _from_array similar to _from_small_list but recurse when array.length >= 12.
• [x] Implement _from_iterable as an iterative version of _from_array (see https://github.com/functional-data-structure/finger-tree/issues/108#issuecomment-927101262).
• [ ] ~See if replacing push loop in from by _from_array([...iterable]) is faster (optimize?).~ NO (because we do not want to keep two copies of the data simultaneously)
• [x] See if implementing this.append(iterable) as this.concat(from(..., iterable)) improves performance.
• [x] Similar for prepend.

Maybe point 2 should be recurse when array.length >= 13, see #120.

The first draft implementation is twice slower than repeated pushes (after forcing the entire tree by calling .measure()). Not forcing the tree makes the operation run twice faster than repeated pushes. Removing the delay calls wins between 1/4 and 1/3 of the whole runtime making it only 1.5 times slower than repeated pushes.

This merging approach does not seem to make sense if we want to gain speed because it causes too many structure changes*. A better approach comes to mind: do repeated pushes but batch them to skip one level of structure changes.

* while not efficient, this implementation constitues a good benchmark for the underlying operations.