Optimize chunked_even itertool #815
Description
Intro
Increases the performance of the chunked_even itertool by removing looped slicing and combining online and finite methods.
As n gets large running islice in a loop becomes unsustainable as it has to chew through more and more elements to get to the appropriate slice.
We could check if the list is finite and copy to a list to perform slicing, and it is slightly faster but if you run something like chunked_even(range(1, 1000000000), 100) you will get an out of memory exception which can be avoided by using an iterator. So I decided to forgo that method as I couldn't find a good way to always avoid that out of memory exception when copying.
Testing
Test:
# test online
from more_itertools import chunked_even, consume
print('online n=3')
%timeit -n 10000 consume(chunked_even(iter(range(1, 8)), 3))
%timeit -n 10000 consume(chunked_even(iter(range(1, 20)), 3))
%timeit -n 10000 consume(chunked_even(iter(range(1, 60)), 3))
%timeit -n 10000 consume(chunked_even(iter(range(1, 120)), 3))
print('online')
%timeit -n 10000 consume(chunked_even(iter(range(1, 20)), 10))
%timeit -n 10000 consume(chunked_even(iter(range(1, 60)), 30))
%timeit -n 10000 consume(chunked_even(iter(range(1, 120)), 50))
%timeit -n 10000 consume(chunked_even(iter(range(1, 500)), 50))
%timeit -n 10000 consume(chunked_even(iter(range(1, 1000)), 100))
%timeit -n 1000 consume(chunked_even(iter(range(1, 10000)), 100))
%timeit -n 100 consume(chunked_even(iter(range(1, 100000)), 100))
print()
# test finite list
from more_itertools import chunked_even, consume
print('finite list n=3')
%timeit -n 10000 consume(chunked_even(list(range(1, 8)), 3))
%timeit -n 10000 consume(chunked_even(list(range(1, 20)), 3))
%timeit -n 10000 consume(chunked_even(list(range(1, 60)), 3))
%timeit -n 10000 consume(chunked_even(list(range(1, 120)), 3))
print('finite list')
%timeit -n 10000 consume(chunked_even(list(range(1, 20)), 10))
%timeit -n 10000 consume(chunked_even(list(range(1, 60)), 30))
%timeit -n 10000 consume(chunked_even(list(range(1, 120)), 50))
%timeit -n 10000 consume(chunked_even(list(range(1, 500)), 50))
%timeit -n 10000 consume(chunked_even(list(range(1, 1000)), 100))
%timeit -n 1000 consume(chunked_even(list(range(1, 10000)), 100))
%timeit -n 100 consume(chunked_even(list(range(1, 100000)), 100))
print()
# test finite range
from more_itertools import chunked_even, consume
print('finite range n=3')
%timeit -n 10000 consume(chunked_even(range(1, 8), 3))
%timeit -n 10000 consume(chunked_even(range(1, 20), 3))
%timeit -n 10000 consume(chunked_even(range(1, 60), 3))
%timeit -n 10000 consume(chunked_even(range(1, 120), 3))
print('finite range')
%timeit -n 10000 consume(chunked_even(range(1, 20), 10))
%timeit -n 10000 consume(chunked_even(range(1, 60), 30))
%timeit -n 10000 consume(chunked_even(range(1, 120), 50))
%timeit -n 10000 consume(chunked_even(range(1, 500), 50))
%timeit -n 10000 consume(chunked_even(range(1, 1000), 100))
%timeit -n 1000 consume(chunked_even(range(1, 10000), 100))
%timeit -n 100 consume(chunked_even(range(1, 100000), 100))
print()Before:
online n=3
2.42 µs ± 16 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
3.68 µs ± 29 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
7.61 µs ± 148 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
13.9 µs ± 387 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
online
3.19 µs ± 19.2 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
5.77 µs ± 35.9 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
10.6 µs ± 172 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
45.8 µs ± 346 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
92.5 µs ± 1.44 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
1.82 ms ± 13.6 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
25.6 ms ± 140 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
finite list n=3
1.91 µs ± 18.7 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.85 µs ± 24.7 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
6.6 µs ± 59.4 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
14.6 µs ± 472 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
finite list
1.84 µs ± 18.7 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.3 µs ± 13 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
3.28 µs ± 27.7 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
14.1 µs ± 143 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
28.5 µs ± 292 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
1.21 ms ± 5.06 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
104 ms ± 923 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
finite range n=3
1.83 µs ± 50.6 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.84 µs ± 11.3 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
7.02 µs ± 61.8 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
16.2 µs ± 77.5 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
finite range
1.73 µs ± 23.1 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.16 µs ± 14.2 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
3.06 µs ± 27.5 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
18 µs ± 328 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
46.9 µs ± 1.54 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
4.62 ms ± 138 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
423 ms ± 1.92 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)
After:
online n=3
1.84 µs ± 11.7 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.59 µs ± 27.4 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
4.95 µs ± 39.9 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
8.37 µs ± 78.8 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
online
1.79 µs ± 27.8 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.2 µs ± 10.9 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
3.25 µs ± 22.8 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
10.1 µs ± 88.3 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
19.8 µs ± 311 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
173 µs ± 3.99 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
3.36 ms ± 43.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
finite list n=3
1.93 µs ± 34.6 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.68 µs ± 23.7 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
5.13 µs ± 102 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
8.65 µs ± 74.7 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
finite list
1.9 µs ± 18.6 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.35 µs ± 41.4 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
3.63 µs ± 62.1 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
10.8 µs ± 88.9 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
20.5 µs ± 218 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
182 µs ± 3.22 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
3.92 ms ± 44.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
finite range n=3
1.89 µs ± 118 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.57 µs ± 10.2 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
4.88 µs ± 41.4 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
8.37 µs ± 110 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
finite range
1.76 µs ± 8.96 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.18 µs ± 10.5 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
3.2 µs ± 26.9 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
10.2 µs ± 140 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
19.6 µs ± 317 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
174 µs ± 5.88 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
3.11 ms ± 30.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)