Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does max(iterable) perform much slower than an equivalent loop?

I noticed a strange performance hit from a minor refactoring that replaced a loop with a call to the builtin max inside a recursive function.

Here's the simplest reproduction I could produce:

import time

def f1(n):
    if n <= 1:
        return 1
    best = 0
    for k in (1, 2):
        current = f1(n-k)*n
        if current > best:
            best = current
    return best

def f2(n):
    if n <= 1:
        return 1
    return max(f2(n-k)*n for k in (1, 2))


t = time.perf_counter()
result1 = f1(30)
print('loop:', time.perf_counter() - t) # 0.45 sec

t = time.perf_counter()
result2 = f2(30)
print('max:', time.perf_counter() - t) # 1.02 sec

assert result1 == result2

Both f1 and f2 calculate factorial using the standard recursion but with an unnecessary maximization added in (just so I get to use max in a recursion while still keeping the recursion simple):

# pseudocode
factorial(0) = 1
factorial(1) = 1
factorial(n) = max(factorial(n-1)*n, factorial(n-2)*n)

It's implemented without memoization, so there's an exponential number of calls.

The implementation with max(iterable) is more than twice slower than the one with the loop.

Oddly, a direct comparison of max vs loop did not demonstrate the effect (edit: never mind, see @TimPeters answer). Also, if I use max(a, b) instead of max(iterable) the performance mismatch disappears.

like image 313
max Avatar asked Jun 17 '17 17:06

max


1 Answers

Posting this as "an answer" because useful formatting is impossible in comments:

$ python -m timeit "max(1, 2)"  # straight
10000000 loops, best of 3: 0.148 usec per loop

$ python -m timeit "max([i for i in (1, 2)])" # list comp
1000000 loops, best of 3: 0.328 usec per loop

$ python -m timeit "max(i for i in (1, 2))" # genexp
1000000 loops, best of 3: 0.402 usec per loop

Which shows that the recursion is a red herring. It's generally true, as these results show, that a genexp is slower than a listcomp, which is in turn slower than using neither. Since your code is doing more than just a max, the timing differences aren't as extreme - but since it's doing little more than just a max, the speed of the max part is nevertheless highly significant.

like image 54
Tim Peters Avatar answered Sep 29 '22 10:09

Tim Peters