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, IntervalTreeStatus: 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.
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.
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.
| Tree | Query width | Hits per query | overlap |
envelop |
overlaps (yes/no) |
|---|---|---|---|---|---|
| 12,000 intervals, length up to 2,000 | 5,000 | 71 | 1,383 → 12.5 (111x) | 1,390 → 14.0 (99x) | 10.5 → 3.3 (3.2x) |
| 100,000 intervals, length up to 2,000 | 5,000 | 59 | 1,540 → 19.1 (81x) | 1,572 → 18.9 (83x) | 14.3 → 5.8 (2.5x) |
| same tree | 100,000 | 1,013 | 30,640 → 119 (257x) | 31,879 → 378 (84x) | 14.1 → 2.7 (5.2x) |
| 100,000 intervals, length up to 200,000 | 5,000 | 1,027 | 69,981 → 654 (107x) | 61,706 → 1.3 | 277 → 134 (2.1x) |
| 450,000 intervals, length up to 400 | 5,000 | 52 | 896 → 17.4 (51x) | 939 → 22.7 (42x) | 2,973 → 4.1 (723x) |
| 450,000 short intervals with gaps | 200 | 0.2 | 12.5 → 4.2 (3.0x) | 11.6 → 1.6 (7.1x) | 57,613 → 2.2 |
| 12,000 intervals with endpoints in 0..63 | 8 | 4,686 | 33,516 → 5,074 (6.6x) | 32,832 → 1,839 (18x) | 13.9 → 5.3 (2.6x) |
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
envelopthat drops from 62 ms to 1.3 us returns 0.6 intervals per query, and theoverlapsthat 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 andaddcost 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.
- Many intervals with the same range.
Interval.__hash__uses onlybeginandend, so intervals that share a range and differ indataall 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 oneattook 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.Intervalis intervaltree's own class here, so its hash cannot be changed without breaking equality with intervals made elsewhere. - Building,
add,remove,merge_*,split_overlapsand the set operations are intervaltree's code.split_overlapson 100,000 sparse intervals took 29.7 s in one profiling run (results/profile_ops.txt).
Results are equal sets of the same Interval objects. Three things differ:
- Iteration order of a result set from
overlapandenvelopcan differ, because hits are found in a different order.atkeeps the original's order. Sinceremove_overlap(begin, end),remove_envelopandchopremove 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. copy,union,difference,intersection,symmetric_difference,from_tuplesand unpickling return this package'sIntervalTree. In intervaltree 3.2.1 a subclass gets plainIntervalTrees back from these; its development branch has already changed that.- 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.
- Parity tests (tests/test_parity.py): every query at every pair of points
against intervaltree, with int, float (including infinities and -0.0),
Fraction,stranddatetimeendpoints; 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.
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
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).