What is the point of defining seen_add = seen.add in this itertools recipe?

user_3498910 0
Viewed 641

I am reading the itertools recipe for unique_everseen:

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

What is the point of defining seen_add = seen.add in the code above?

itertools python
2 Answers

Performance. Using a local name to dereference the method is much faster than an attribute lookup (which has to bind a new method object each time):

>>> import timeit
>>> timeit.timeit('s.add', 's = set()', number=10**7)
0.4227792940218933
>>> timeit.timeit('seen_add', 's = set(); seen_add = s.add', number=10**7)
0.15441945398924872

Using a local reference is almost 3 times as fast. Because the set.add is used in a loop, it is worth optimising away the attribute lookup.

user_1002970

That's a technique called "hoisting" or "Loop-invariant code motion". In essence you do an operation that is executed multiple times but always returns the same value outside the loop instead of in the loop body.

In this case the loop would repeatedly lookup the add attribute of your seen set and create a "bound method". That's actually pretty fast but still an operation that is performed several times inside a loop and always gives the same result. So you can look up the attribute (in this case the bound method) once and store it in a variable to gain some performance.

Note that while this provides a speed-up it's by no means "much". I removed the second branch for this timing to make the code shorter:

from itertools import filterfalse

def unique_everseen(iterable):
    seen = set()
    seen_add = seen.add
    for element in filterfalse(seen.__contains__, iterable):
        seen_add(element)
        yield element

def unique_everseen_without(iterable):
    seen = set()
    for element in filterfalse(seen.__contains__, iterable):
        seen.add(element)
        yield element

Some exemplaric timings:

# no duplicates
a = list(range(10000))
%timeit list(unique_everseen(a))
# 5.73 ms ± 279 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit list(unique_everseen_without(a))
# 6.81 ms ± 396 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# some duplicates
import random
a = [random.randint(0, 100) for _ in range(10000)]
%timeit list(unique_everseen(a))
# 1.64 ms ± 12.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit list(unique_everseen_without(a))
# 1.66 ms ± 16.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# only duplicates
a = [1]*10000
%timeit list(unique_everseen(a))
# 1.64 ms ± 78.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit list(unique_everseen_without(a))
# 1.63 ms ± 24.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

So while you get ~10% speedup in the no duplicates case it's actually almost useless in case you got lots of duplicates.

Actually this recipe shows another example of "hoisting", more specifically the filterfalse(seen.__contains__, iterable). This looks up the __contains__ method of your seen set once and repeatedly calls it inside the filterfalse.

Maybe the take-away should be: Hoisting method lookups is a micro-optimization. It reduces the constant factor of your loop. The speedup may be worth it in certain operations but personally I think it should be used sparingly and only in combination with profiling/benchmarking.

user_53933810
Related