Issue 21744: itertools.islice() goes over all the pre-initial elements even if the iterable can seek (original) (raw)

If L is a big sequence and I do "itertool.islice(L, 1000000, None)", islice will go over a million elements before returning the first that I actually cared.

Since L is a sequence, islice could go directly to the element 1000000.

My program performance improved hugely replacing a "for i in L[p:]" for "for i in (L[p] for p in range(p, len(L)))".

Using itertools and doing "for i in itertools.islice(L, p, None)" is massively inefficient.

I would think that allowing the special case optimization would be a good idea. As is, if you want to take slices of buffers without making copies, you can use memoryview and get O(1) views of a slice of the memory. But there's nothing built-in that's even remotely equivalent for large lists/tuples. If I have list (we'll call it mylist) with one million items, and I'd like to iterate/operate on the last 100,000, my choices are:

  1. mylist[-100000:] # Copies 100,000 pointers; on x64, that's 800KB of memory copied, and 100,000 increfs and decrefs performed en masse, before I even iterate
  2. itertools.islice(mylist, 900000, None) # Uses no additional memory, but performs a solid million increfs/decrefs as it iterates, 90% of which are unnecessary
  3. Write a custom sequence view class that explicitly indexes to simulate a "listview" or a "tupleview" in a style similar to a memoryview. Minimal memory overhead, and it doesn't process stuff you don't care about, but you actually have to write the thing, and any pure Python implementation is going to add a lot of mathematical overhead to maintain a slice or range in parallel so you can index the wrapped sequence appropriately.

#3 is the only fully generalizable way to do this, but I see no reason not to make it possible to handle simple cases with islice. Either you write a custom iterator that uses higher level Python constructs to index on behalf of the user (slower, but generalizes to anything with a len and getitem), and/or a high performance custom iterator that is basically just iterating a C array from PySequence_FAST_ITEMS; only works with lists/tuples, but would be blazing fast (alternatively, just let itertools.islice directly muck with the tuple/list iterator internals to fast forward them to the correct index, which reduces the need for extra code, at the expense of a tighter dependency between itertools and tuple/list internals).

If people are opposed to making islice do this sort of work, I may be forced to start considering a dedicated sequenceview class. Either that, or propose an extension to the iterator protocol to request fast-forwarding, where non-specialized iterators act like islice does now, and specialized iterators skip ahead directly. :-)

I will admit, on further consideration, a dedicated sequenceview might work more nicely. islice's interface is limited by its generality; since it doesn't assume a length, you can't use a negative value for end.

Does anyone think a general sequenceview class would make sense (or a sequenceview function that returns either a general sequenceview or a memoryview, depending on what the underlying type is)? Might make an interesting project, whether or not islice is improved.