fastintervaltree

A drop-in subclass of intervaltree's IntervalTree whose range queries walk the tree once. It returns the same sets as intervaltree 3.2.1, and is pure Python.

# before
from intervaltree import Interval, IntervalTree
# after: nothing else changes
from fastintervaltree import Interval, IntervalTree

Status: version 0.1.0, working and tested. The overlap and envelop change has also been offered to intervaltree itself as pull request #166; if that is merged and released, most of the reason for this package goes away.

Why

intervaltree answers overlap(begin, end) with one point search for begin and then one more for every interval boundary inside the range. On a tree of 12,000 intervals a query that returns 71 of them takes about 1.4 ms. Users have reported this on intervaltree's tracker (#120, #127). envelop works the same way, and overlaps with a range scans the whole table of boundaries when the answer is not found at once.

Here each of these is a single descent that skips a subtree the range cannot reach. The tree, its nodes and every operation that changes the tree are intervaltree's own code, inherited unchanged.

Numbers

Microseconds per query, intervaltree 3.2.1 against this package on identical trees, random integer intervals. Python 3.13.5, Windows, one laptop; process pinned, 5 rounds with the two variants alternating, best round of each. Full output: results/bench_queries.txt.

How to read it:

• The gain grows with the number of boundaries inside the query range. Narrow queries on sparse trees gain about 3x; wide ones gain 50x to 250x.
• Rows where the original took tens of milliseconds were timed on few queries (5 to 20 per round), so those ratios are rough. Two cells have no ratio because it would mislead: the envelop that drops from 62 ms to 1.3 us returns 0.6 intervals per query, and the overlaps that drops from 58 ms to 2.2 us is the case where the original scans all of the roughly 900,000 boundaries.
• The last row is the shape reported in issue #120, and it gains least. See "What is not faster".
• Point queries (at, tree[p]) are 1.0x to 1.5x. Building a tree and add cost 0% to 5% more than the original in two runs, which is within this machine's noise.

remove_overlap, remove_envelop, chop and tree[a:b] call these queries and get faster with them. They were not timed separately.

What is not faster

• Many intervals with the same range. Interval.__hash__ uses only begin and end, so intervals that share a range and differ in data all land in one hash bucket, and every set that holds k of them costs on the order of k squared comparisons. With 1,000 such intervals one at took 129 ms in the original; with 5,000 it took 3.0 s. This package does not change that (#126), and it is why the 0..63 row above gains only 6.6x. Interval is intervaltree's own class here, so its hash cannot be changed without breaking equality with intervals made elsewhere.
• Building, add, remove, merge_*, split_overlaps and the set operations are intervaltree's code. split_overlaps on 100,000 sparse intervals took 29.7 s in one profiling run (results/profile_ops.txt).

Differences from intervaltree

Results are equal sets of the same Interval objects. Three things differ:

1. Iteration order of a result set from overlap and envelop can differ, because hits are found in a different order. at keeps the original's order. Since remove_overlap(begin, end), remove_envelop and chop remove hits in iteration order, the internal layout of the tree afterwards can differ from what intervaltree would have built. Its contents, and the answers to every query, do not.
2. copy, union, difference, intersection, symmetric_difference, from_tuples and unpickling return this package's IntervalTree. In intervaltree 3.2.1 a subclass gets plain IntervalTrees back from these; its development branch has already changed that.
3. NaN. If a query endpoint or any endpoint in the tree is NaN, the call is passed to intervaltree's own code, so the answer is whatever intervaltree gives.

Endpoints are assumed to be totally ordered apart from NaN. Types with a partial order (sets, for example) are not supported and not tested.

Evidence

• Parity tests (tests/test_parity.py): every query at every pair of points against intervaltree, with int, float (including infinities and -0.0), Fraction, str and datetime endpoints; trees built at once and one interval at a time; and again after every step of random sequences drawn from 28 operations. Exception types are compared as well as results. Hypothesis generates the cases.
• The fast path is the code under test (tests/test_fast_path.py): a counter on intervaltree's two search routines reads zero for ordinary trees, and non-zero when NaN forces the fallback.
• Mutation check (tools/mutation_check.py): 37 deliberate one-line breakages; the tests catch 33. The other 4 cannot change any answer, and the reasons are printed in results/mutation_check.txt.
• intervaltree's own test suite at tag 3.2.1 passes with this class swapped in (tools/swap_in_fast.py): 99 tests, the same count as without the swap.

CI runs the tests on Linux, Windows and macOS with Python 3.10, 3.13 and 3.15, and on Linux with Python 3.9, always against intervaltree 3.2.1. Python 3.11 was run once by hand.

Install

pip install fastintervaltree

It needs Python 3.9 or newer and installs intervaltree 3.2.x as a dependency.

To run the checks, from a clone:

pip install -e ".[test]"
python -m pytest                      # about 2 minutes
python tools/mutation_check.py        # several minutes, 6 processes
python research/bench_queries.py      # a few minutes; needs a quiet machine

Licence

Apache-2.0, the same as intervaltree, from which this is derived. See NOTICE. Written with the help of an AI coding assistant (Claude Code).