search

blachlylab / intervaltree

Interval tree structures in D
MIT License
7 stars 0 forks source link

splay tree optimizations #11

Open jblachly opened 5 years ago

jblachly commented 5 years ago

  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 commented 5 years ago
  1. For hg19Tohg38.chain and splaytree, stackmax == 20
jblachly commented 5 years ago
  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 commented 5 years ago
  1. taken care of in latest update, can provide 10-20% speed boost
jblachly commented 3 years ago

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