Report on performance for 1.10.0 versus 2.0.0

[AlexandreDecan]

2.0.0 is still under development, but we already observed a huge performance increase for interval creation/union, intersection, difference and complement (except for intersection of very small intervals, but we are talking about µs!).

TL;DR: speed-up observed, details below.

                                        Union  Intersection  Difference  Complement
large intervals: ~500 atomics        1.854881     36.768802  117.073171  234.741784
medium intervals: ~50 atomics        1.637532      4.327869   12.640000  349.353050
small intervals: ~5 atomics          1.349882      0.463259    1.505017    3.898305

Time in milliseconds (5K atomics not reported for 1.10.0: too slow):

                                          v     Union  Intersection  Difference  Complement
index                                                                                      
small intervals: ~5 atomics          1.10.0   0.00571        0.0145      0.0450     0.02990
medium intervals: ~50 atomics        1.10.0   0.06370       13.2000     31.6000    18.90000
large intervals: ~500 atomics        1.10.0   7.03000     1320.0000   2880.0000  1500.00000
small intervals: ~5 atomics           2.0.0   0.00423        0.0313      0.0299     0.00767
medium intervals: ~50 atomics         2.0.0   0.03890        3.0500      2.5000     0.05410
large intervals: ~500 atomics         2.0.0   3.79000       35.9000     24.6000     6.39000
very large intervals: ~5000 atomics   2.0.0  69.20000      258.0000    205.0000    50.50000

To quantify this, we ran the following snippet in both versions (in a Jupyter console, hence the use of %timeit). Please note that there is no scientific or rigorous process here ;-)

import intervals as I

sm = [
    I.Interval(*(I.closed(i, i+1) for i in range(0, 10, 2))),
    I.Interval(*(I.closed(i, i+1) for i in range(1, 10, 2)))
]

md = [
    I.Interval(*(I.closed(i, i+1) for i in range(0, 100, 2))),
    I.Interval(*(I.closed(i, i+1) for i in range(1, 100, 2)))
]

xl = [
    I.Interval(*(I.closed(i, i+1) for i in range(0, 1000, 2))),
    I.Interval(*(I.closed(i, i+1) for i in range(1, 1000, 2)))
]

xxl = [
    I.Interval(*(I.closed(i, i+1) for i in range(0, 10000, 2))),
    I.Interval(*(I.closed(i, i+1) for i in range(1, 10000, 2)))
]


for i, label in zip([sm, md, xl, xxl], ['small', 'medium', 'large', 'very large']):
    print(label, 'intervals: ~'+str(len(i[0])), 'atomics')
    print('Union:')
    %timeit -r5 -n10 I.Interval(*i)

    print('Intersection:')
    %timeit -r5 -n10 i[0] & i[1]

    print('Difference:')
    %timeit -r5 -n10 i[0] - i[1]

    print('Complement:')
    %timeit -r5 -n10 ~i[0]

    print()

Here are the resulting outputs for both versions. Notice that we killed the execution of "very large intervals" in 1.10.0 as it took too much time.

1.10.0 :

small intervals: ~5 atomics
Union:
57.1 µs ± 3.14 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Intersection:
145 µs ± 19.6 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Difference:
450 µs ± 26.1 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Complement:
299 µs ± 34.9 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)

medium intervals: ~50 atomics
Union:
637 µs ± 36.2 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Intersection:
13.2 ms ± 777 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Difference:
31.6 ms ± 4.05 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)
Complement:
18.9 ms ± 2.46 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)

large intervals: ~500 atomics
Union:
7.03 ms ± 577 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Intersection:
1.32 s ± 53.7 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)
Difference:
2.88 s ± 53.3 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)
Complement:
1.5 s ± 37.3 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)

2.0.0 :

small intervals: ~5 atomics
Union:
42.3 µs ± 1.07 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Intersection:
313 µs ± 9.13 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Difference:
299 µs ± 15.1 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Complement:
76.7 µs ± 1.34 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)

medium intervals: ~50 atomics
Union:
389 µs ± 19.5 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Intersection:
3.05 ms ± 128 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Difference:
2.5 ms ± 308 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Complement:
541 µs ± 15.4 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)

large intervals: ~500 atomics
Union:
3.79 ms ± 202 µs per loop (mean ± std. dev. of 5 runs, 10 loops each)
Intersection:
35.9 ms ± 4.81 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)
Difference:
24.6 ms ± 3.56 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)
Complement:
6.39 ms ± 1.11 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)

very large intervals: ~5000 atomics
Union:
69.2 ms ± 10.3 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)
Intersection:
258 ms ± 11.3 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)
Difference:
205 ms ± 10.7 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)
Complement:
50.5 ms ± 3.75 ms per loop (mean ± std. dev. of 5 runs, 10 loops each)