Optimize all_equal recipe #899

bbayles · 2024-08-15T14:12:38Z

This PR updates all_equal with @rhettinger's new version.

Closes #896

pochmann3 · 2024-08-15T14:34:38Z

Did you overlook my benchmark where this was slower than the current version for the case of one group? (Which is the most relevant one for the mentioned usage un iequals.) This does not look like an optimization to me.

bbayles · 2024-08-15T14:50:39Z

Thanks for the comment. To be totally transparent, I am going to favor Raymond's suggestions in almost every case – this library is a wrapper around his work, and unless I have a big disagreement with one of his ideas, I'm going to implement them. You have a good track record of contributing to this library as well, and as such I am very open to your suggestion too. That said, I generally discount microbenchmarks on a single machine with un-representative inputs, which is what appears to be the basis for the "this is slower" claim.

rhettinger · 2024-08-15T15:11:23Z

Pochmann later posted a for/for variant that is much better than his other proposals. After changing the variable name from groups to iterator, I'm happy with it:

def all_equal(iterable, key=None):
    iterator = groupby(iterable, key)
    for first in iterator:
        for second in iterator:
            return False
    return True

I don't think we can do better than this. It is short and relies only on the most basic of Python features. It is a little less straight-forward than the try/except variant but only has a small and tolerable bit of weirdness. This is the one I recommend.

pochmann3 · 2024-08-15T16:44:07Z

I generally discount microbenchmarks on a single machine with un-representative inputs, which is what appears to be the basis for the "this is slower" claim.

As shown in the issue, I also reproduced my findings on another machine. And reproduced Raymond's disagreeing findings on the same machine when measuring his command line way without a function. I still don't know why measuring that way gives such very different results, but that way isn't the realistic way. The real all_equal is a function.

About "un-representative inputs": They do represent all cases: No groups, one group, more than one group. And all solutions under consideration use groupby. So those inputs are fully representative for the differences of the solutions.

I also like the normal version of my "gross" hack:

def all_equal(iterable, key=None):
    seen_one = False
    for _ in groupby(iterable, key):
        if seen_one:
            return False
        seen_one = True
    return True

It's similarly fast:

iterable = ()
True  137 Â± 0.3 ns  Stefan_hack
True  140 Â± 0.3 ns  Stefan_seen
True  147 Â± 0.7 ns  Stefan_loops
True  306 Â± 0.9 ns  current
True  356 Â± 0.8 ns  Raymond

iterable = (1,)
True  205 Â± 0.3 ns  Stefan_hack
True  208 Â± 0.7 ns  Stefan_seen
True  221 Â± 0.8 ns  Stefan_loops
True  355 Â± 1.3 ns  current
True  435 Â± 1.0 ns  Raymond

iterable = (1, 2)
False  251 Â± 0.4 ns  Stefan_loops
False  252 Â± 0.9 ns  Stefan_seen
False  255 Â± 0.8 ns  Stefan_hack
False  329 Â± 1.1 ns  Raymond
False  396 Â± 0.9 ns  current

Python: 3.13.0rc1+ (heads/3.13:009f9efe658, Aug 15 2024, 14:30:32) [Clang 18.1.6 (Fedora 18.1.6-3.fc40)]

Benchmark script

def current(iterable, key=None):
    return len(list(islice(groupby(iterable, key), 2))) <= 1

def Raymond(iterable, key=None):
    iterator = groupby(iterable, key=key)
    try:
        next(iterator)
        next(iterator)
    except StopIteration:
        return True
    return False

def Stefan_hack(iterable, key=None):
    for _ in groupby(iterable, key):
        if iterable is None:
            return False
        iterable = None
    return True

def Stefan_loops(iterable, key=None):
    iterator = groupby(iterable, key)
    for first in iterator:
        for second in iterator:
            return False
    return True

def Stefan_seen(iterable, key=None):
    seen_one = False
    for _ in groupby(iterable, key):
        if seen_one:
            return False
        seen_one = True
    return True


funcs = [current, Raymond, Stefan_hack, Stefan_loops, Stefan_seen]

iterables = (), (1,), (1, 2)

from timeit import timeit
from statistics import mean, stdev
import sys
import random
from itertools import *

for iterable in iterables:
    print(f'{iterable = }')
    times = {f: [] for f in funcs}
    def stats(f):
        ts = [t * 1e9 for t in sorted(times[f])[:10]]
        return f' {mean(ts):3.0f} ± {stdev(ts):3.1f} ns '
    for _ in range(100):
        random.shuffle(funcs)
        for f in funcs:
            t = timeit(lambda: f(iterable), number=1000) / 1000
            times[f].append(t)
    for f in sorted(funcs, key=stats):
        print(f(iterable), stats(f), f.__name__)
    print()

print('Python:', sys.version)

Attempt This Online!

rhettinger · 2024-08-16T14:40:36Z

Stefan, take the key=key out of the "Raymond" variant. Also we really don't care about the empty iterator case, it is a distractor. (Side note: passing in a lambda : is possibly the worst way to use timeit. Instead, prefer the setup="from __main__ import test" style shown in the examples at the bottom of the timeit docs.)

Bo, aside from the two other hacky variants proposed, I don't think there are any wrong choices here. My order of preference is 1) the try/next/next proposed in the issue, 2) the for first/for second in the current PR, or 3) just leaving it as-is.

Though not currently the fastest, the try/next/next most clearly expresses the algorithmic intent and doesn't ask the interpreter for anything beyond that. As the interpreter evolves, try/next/next will become the fastest (looking up builtins will be as fast as looking up globals/locals , catching exceptions will become cheaper, can catching StopIteration may be special cased). That said, we're only talking a few tens of nanoseconds outside the inner loop, so none of this really matters much. I don't care about it enough to endlessly joust with Stefan.

Optimize all_equal recipe

b4f7911

Use loops

fa05e90

rhettinger approved these changes Aug 15, 2024

View reviewed changes

bbayles merged commit 390a3db into master Aug 16, 2024
12 checks passed

bbayles deleted the issue-896-all-equal branch August 16, 2024 14:50

bbayles mentioned this pull request Sep 5, 2024

Version 10.5.0 #906

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Optimize all_equal recipe #899

Optimize all_equal recipe #899

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Optimize all_equal recipe #899

Optimize all_equal recipe #899

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!