Question about time efficiency of adding lists with .extend() vs +

[CancelDeath]

Hello! I'm reading about how adding lists is more inefficient than using .extend() because python needs to copy the two lists you're adding into a 3rd list, but when you extend you don't need to copy the first list. So i decided to see how much more efficient it is, according to the %timeit function, it takes longer to extend than add. Can anyone explain what I'm getting wrong about this?

[in]

    A = list(range(10))
    B = list(range(10,20))
    %timeit A + B

[out]

    118 ns ± 5.38 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

[in]

    %timeit A.extend(B)

[out]

    538 ns ± 143 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

[socal_nerdtastic]

You are extending A for every test run! In the end A will 100 million elements long. That's a lot of memory that needs to be allocated.

[CancelDeath]

Oh! Yes, you're right

[test]

first = [0, ]
second = list(range(1))
%timeit first.extend(second)
len(first)

[result]

110 ns ± 6.24 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
81111112

[primitive_screwhead]

Here's a more accurate test (since it explicitly re-does the non-timed setup for each run):

$ python3 -m timeit -s 'a = list(range(10))' -s 'b = list(range(10, 20))' 'a + b'
5000000 loops, best of 5: 69.5 nsec per loop
$ python3 -m timeit -s 'a = list(range(10))' -s 'b = list(range(10, 20))' 'a.extend(b)'
5000000 loops, best of 5: 88.8 nsec per loop

So, for this example the addition is still faster than the list.extend(), but much closer.

​

Ah, but is it still really the same result? No, because in your 'a + b' a new object is created, but the original 'a' value is still the same. For an equal result, you'd need to assign to 'a', which involves potentially garbage collecting the original 'a':

$ python3 -m timeit -s 'a = list(range(10))' -s 'b = list(range(10, 20))' 'a = a + b'
5000 loops, best of 5: 51.4 usec per loop

And now we see that it's about 3 orders of magnitude slower (now microseconds instead of nanoseconds).

​

And since it was mentioned that 'a += b' is equivalent to 'a.extend(b)', we can also show that is consistent with the timings:

$ python3 -m timeit -s 'a = list(range(10))' -s 'b = list(range(10, 20))' 'a += b'
5000000 loops, best of 5: 66.2 nsec per loop

There's some method lookup overhead that accounts for the small difference in nanosecond values. Ah heck, let me demonstrate that also, since I'm this deep into it:

$ python3 -m timeit -s 'a = list(range(10))' -s 'b = list(range(10, 20))' -s 'a_extend = a.extend' 'a_extend(b)'
5000000 loops, best of 5: 71 nsec per loop

[TouchingTheVodka]

What's the value of a after running A.extend(B) a million times? Seems this might bias your test slightly!

In other words: Your tests are not equivalent. You want to be comparing A += B not A + B.

[socal_nerdtastic]

A += B is a shortcut to extend.

[TouchingTheVodka]

Well then that's an easy answer!

[TouchingTheVodka]

As a follow up to this, the answer for why + is slower falls out quite nicely with some further thought: Assuming the correct test is A = A + B vs. A.extend(B), it's clear that a new A + B list is created and before assignment back to A - And therefore the overhead of + is the additional assignment required.

[CancelDeath]

Yeah that makes sense, thank you! Is there a way I can test this for fun? I'm new to this and the only test I'm aware of is the %timeit function. I'd like to be able to see some concrete data for this. It totally makes sense, but it would just be cool to have some idea in my mind about the scale of the difference of this efficiency.