Skip to content

Optimize tree construction #108

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
4 of 6 tasks
make-github-pseudonymous-again opened this issue Nov 30, 2020 · 2 comments
Open
4 of 6 tasks

Optimize tree construction #108

make-github-pseudonymous-again opened this issue Nov 30, 2020 · 2 comments
Labels
perf This issue is about improving performance of the implementation in general

Comments

@make-github-pseudonymous-again
Copy link
Member

make-github-pseudonymous-again commented Nov 30, 2020

Plan:

  • Benchmark current implementations of from, prepend, and append.
  • Implement _from_array similar to _from_small_list but recurse when array.length >= 12.
  • Implement _from_iterable as an iterative version of _from_array (see Optimize tree construction #108 (comment)).
  • 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)
  • See if implementing this.append(iterable) as this.concat(from(..., iterable)) improves performance.
  • Similar for prepend.
@make-github-pseudonymous-again
Copy link
Member Author

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

@make-github-pseudonymous-again
Copy link
Member Author

make-github-pseudonymous-again commented Sep 25, 2021

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.

make-github-pseudonymous-again added a commit that referenced this issue Sep 28, 2021
This is progress on #108 and #120 but must be split.
make-github-pseudonymous-again added a commit that referenced this issue Oct 14, 2021
This is progress on #108 and #120 but must be split.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
perf This issue is about improving performance of the implementation in general
Projects
None yet
Development

No branches or pull requests

1 participant