Weird speed differences for iterating lists

Question

I create two long lists repeating two different values. In the first list the values alternate, in the second list one value's occurrences come before the other's:

a1 = [object(), object()] * 10**6
a2 = a1[::2] + a1[1::2]

Then I iterate them, doing nothing with them:

for _ in a1: pass
for _ in a2: pass

Which of the two gets iterated faster? Depends on how I measure! I did 50 races with each timing method:

timing method: timeit.timeit
  list a1 won 50 times
  list a2 won 0 times

timing method: timeit.default_timer
  list a1 won 0 times
  list a2 won 50 times

Why do the two timing methods give me completely opposite results? And why are there speed differences between the two lists at all? I'd expect something more like 25-25 twice, instead of 50-0 and 0-50.

Reasons from previous similar questions and why I don't think they're responsible here:

branch prediction: I don't have any branching that could make a difference.
cache misses: Shouldn't happen, as I only have two values (and I don't even do anything with them).
garbage collection: Not involved here.
None of these would explain the opposite speed differences between the timing methods anyway.

I'm using Python 3.10, same results on a weak Windows laptop and a strong Linux Google Compute Engine instance.

Full code:

from timeit import timeit, default_timer

a1 = [object(), object()] * 10**6
a2 = a1[::2] + a1[1::2]

for method in 'timeit', 'default_timer':
    wins1 = wins2 = 0

    for _ in range(50):

        time1 = time2 = float('inf')
        for _ in range(5):

            if method == 'timeit':
                t1 = timeit('for _ in a1: pass', 'from __main__ import a1', number=1)
                t2 = timeit('for _ in a2: pass', 'from __main__ import a2', number=1)
            else:
                start = default_timer();
                for _ in a1: pass
                end = default_timer()
                t1 = end - start

                start = default_timer();
                for _ in a2: pass
                end = default_timer()
                t2 = end - start

            time1 = min(time1, t1)
            time2 = min(time2, t2)

        wins1 += time1 < time2
        wins2 += time2 < time1

    print(f'timing method: timeit.{method}')
    print(f'  list a1 won {wins1} times')
    print(f'  list a2 won {wins2} times')
    print()

user_2705542 · Answer

Not "an answer", but a clue: add

def f(a):
    for _ in a: pass

and then in the default_timer branch replace

for _ in a1: pass

with f(a1), and similarly for the iteration over a2.

Two things I see then:

Output changes to more uniform

timing method: timeit.timeit

  list a1 won 50 times
  list a2 won 0 times

timing method: timeit.default_timer
  list a1 won 50 times
  list a2 won 0 times

It's no longer the case that timeit runs faster than default_timer,

#2 is so obvious it may be hard to notice why ;-) In the original, the for-loop target _ is a module global, so updating it on each iteration requires a dict lookup and store. But timeit builds a function out of the stuff passed to it, so in the code timeit runs, _ is a local variable instead, and a faster STORE_FAST indexed store suffices.

Function f() was introduced so that the "heavy lifting" is done in both cases on local variables.

The code being timed here does so very little that the difference between a dict lookup and an index-a-vector-with-an-int operation can be highly significant

Weird speed differences for iterating lists

1 Answers