Skip to content
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

splay tree optimizations #11

Open
jblachly opened this issue Mar 18, 2019 · 4 comments
Open

splay tree optimizations #11

jblachly opened this issue Mar 18, 2019 · 4 comments

Comments

@jblachly
Copy link
Member

  1. reduce use of updateMax (may not need to bubble up since we update on the way down on insert)

  2. templatize zig, ziz-zig, and zig-zag by direction to factor out if/else (although these if/else may be branch predicted well already)

  3. findOverlapsWith: static array stack. Will need to instrument this to see how deep an unbalanced tree we have after loading chain file.

  4. findOverlapsWith: static array ret. (would also want to change IntervalAVLTree to match)

  5. (Benchmark) When # overlapping intervals > 1, splay once or more

@jblachly
Copy link
Member Author

  1. For hg19Tohg38.chain and splaytree, stackmax == 20

@jblachly
Copy link
Member Author

  1. Splay calls zig, zig-zig, zig-zig, or else zig-zag. Only the 2 zig-zig calls have else ifs prior to the call and therefore have redundant if/else in function body.

Templated version of zigZig Does not seem to improve performance much if at all. This is in branch template-zigzag.

@jblachly
Copy link
Member Author

  1. taken care of in latest update, can provide 10-20% speed boost

@jblachly
Copy link
Member Author

jblachly commented Dec 5, 2020

This issue should be moved to https://github.com/blachlylab/intervaltree

@jblachly jblachly transferred this issue from blachlylab/swiftover Mar 26, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant