Optimization

[dcjones]

Revisiting my old hobby of optimizing IntervalTrees.

So far:

• Avoid using isless, since depending on the interval type it can unnecessarily compare things other than first and last, e.g. sequence name.
• Store leaf entries in a plain array, avoiding some overhead from Slice.
• Faster nextintersection! function for iterative intersection.

My simple benchmark goes from:

• successive intersection: 5.9s -> 5.3s 5.4s
• iterative intersection: 8.4s -> 7.3s 5.8s

TODO:

• [x] Better cost analysis of successive versus iterative intersection. Often it chooses incorrectly and runs the empirically slower algorithm.
• [ ] Implement a third algorithm: run successive B vs A instead of successive A vs B, which is O(|B| log |A|) instead of O(|A| log |B|).
• [x] Store leaf keys redundantly in contiguous memory. Uses more memory, but it looks like cache misses from having to follow leaf entry pointers slows things down a lot.
• [ ] Investigate using StaticArrays to store keys.
• [ ] Anything else that may occur to me along the way.

[codecov-io]

Codecov Report

Merging #25 into master will decrease coverage by 1.58%. The diff coverage is 92.39%.

@@            Coverage Diff             @@
##           master      #25      +/-   ##
==========================================
- Coverage    93.2%   91.62%   -1.59%     
==========================================
  Files           3        3              
  Lines         692      776      +84     
==========================================
+ Hits          645      711      +66     
- Misses         47       65      +18

Impacted Files	Coverage Δ
src/slice.jl	93.22% <75%> (-6.78%)	:arrow_down:
src/IntervalTrees.jl	92.72% <94.19%> (-1.53%)	:arrow_down:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 1f1bb8b...5da2d2d. Read the comment docs.

[bicycle1885]

Cool! I'm interested in the performance impact of simple iteration over all intervals in a tree, because when I tried it before it was much slower than I expected.

[dcjones]

Curiously iteration is about the same on julia 0.5, but significantly slower with this change on master. I'll look into that. :frowning: