Add `__length_hint__` methods to `itertools` helpers

[KowalskiThomas]

Following-up on #145333, I would like to add more __length_hint__ methods to itertools helper iterators. Not all of them can have such a method (those that are not finite, like count or unknown like takewhile) but I think we could at least add them for starmap, batched, and possibly others like product, pairwise etc that will require some more attention.

I plan to work on this in the next few days.

[picnixz]

Please, wait before working on it. We need @rhettinger or a maintainer's consensus on that one. I think it's fine but would it be really useful in general cases?

[cmaloney]

Some background bits: __length_hint__ was added in PEP-424, discussed at https://mail.python.org/pipermail/python-dev/2012-July/120920.html, and implemented in gh-60352.

I think it's goood reading overall, some points that seem relevant to this:

• Enables a performance optimization: Replace continual re-allocation with an up front (over-)allocation reducing or eliminating copies and reallocations resulting in a significant speedup.
• There are interesting cases to consider from test_iterlen: https://mail.python.org/pipermail/python-dev/2012-July/120966.html
• How well passing through / calling __length_hint__ on underlying may work in various cases.

With that in mind I suspect for these would be useful to measure the performance tradeoff between having another function vs. how many elements are in the iterable. My intuition says small iterables (ex. 1-4 items) will be slightly slower while mid to long will see significant speedups. Being explicit about that cost/benefit tradeoff I think will be very useful. Most useful is if there are cases in pyperformance or well used public code bases which will speedup; pyperf microbenchmarks also potentially useful.

That definitely takes work to measure for a proposal and doesn't guarantee acceptance but will likely help get consensus. Significant performance gains in real-world code bases are very motivating :)

[KowalskiThomas]

Thanks so much for that comment, it's extremely helpful. I'll take some time to unravel that, read the things you recommended and eventually have a go at measuring the impact when I get a chance.

Anecdotally, I was wondering before making the PR whether this would be useful at all so I made some very basic benchmarks on just building lists where I saw noticeable improvement (order of 10-15%), but that was just one specific example.

I'll update this ticket with my progress !

[rhettinger]

I explored this path at one point and mostly found it to be a dead-end. I wrote-up some of my findings in Lib/test/test_iterlen.py.

[KowalskiThomas]

To follow-up on this...

I checked in some of the bigger repos (using GitHub Code Search) for usage of itertools.islice (which was the first helper I looked into) and overall, it seems like they either don't use it in a way that would benefit from adding __length_hint__ (e.g. they do next(islice(...)) which doesn't materialise the iterator) or use it in contexts where it would be useful, but the workload is already heavily I/O bound (e.g. Django batching database operations if I remember correctly).

For completeness' sake, I also checked usages in the standard library and while there are some, there aren't a lot and most importantly they're on lower-sized inputs as far as I can tell (which, I've noticed in benchmarks, aren't benefitting from the optimisation).

---

After that, I figured microbenchmarks might be the logical next step.

I had already written some previously (just to check that my changes were actually somewhat useful, before opening my PR) and they confirmed what Cody said: on smaller-sized iterators (up to 10 items, I'd say), there is a performance hit (coming I assume from one additional call). We're talking ~10% of O(100ns) calls so it's not huge, but it's there.

On larger iterators, there's a significant performance boost (~15-25% as early as 100 items), then eventually on even larger ones (100k+), it seems like the performance gains from making islice more efficient are less and less significant compared to the overall cost of allocating.

---

Since I was interested in knowing more about other helpers as well, I implemented a __length_hint__ for starmap, and accumulate. The bottomline for starmap and accumulate is that they show the same results approximately as islice.

---

So long story short... I'm not sure those changes are worth making, after all. Happy to hear(/read) your thoughts if you think otherwise but I'm especially not a fan of that fact it makes performance worse in some probably common cases (few items).

---

For future reference, my benchmark for islice was the following. The only "benchmarked variable" is stop because that's the one that varying has the most effect on performance (since it directly has an impact on the number of resulting items).

Details

import pyperf
from itertools import islice
from typing import Callable, Iterator

pool = list(range(5_000_000))


def make_list(n: int) -> Callable[[], list[int]]:
    data = pool[:n]
    return lambda: data


def make_iter(n: int) -> Callable[[], Iterator[int]]:
    data = pool[:n]
    return lambda: iter(data)


def make_generator(n: int) -> Callable[[], Iterator[int]]:
    def gen() -> Iterator[int]:
        yield from range(n)
    return gen


def make_range(n: int) -> Callable[[], range]:
    return lambda: range(n)


source_factories: list[tuple[str, Callable]] = [
    ("list",       make_list),
    ("iter_list",  make_iter),
    ("generator",  make_generator),
    ("range",      make_range),
]

sizes = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 100, 1_000, 10_000, 100_000, 500_000, 1_000_000, 5_000_000]

runner = pyperf.Runner()
for src_name, src_factory in source_factories:
    for n in sizes:
        make_src = src_factory(n)
        bench_name = f"list(islice({src_name}, {n}))"
        runner.bench_func(bench_name, lambda src=make_src, stop=n: list(islice(src(), stop)))

[rhettinger]

Thank you for the research effort.

I'm not sure those changes are worth making, after all.

I agree. Let's close this.