Optimize tree construction
Plan:
- [x] Benchmark current implementations of
from,prepend, andappend. - [ ] Implement
_from_arraysimilar to_from_small_listbut recurse whenarray.length >= 12. - [x] Implement
_from_iterableas 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
fromby_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)asthis.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.