Why is creating a collection from a concatenated list faster than using `.update`?

Question

When trying to answer What is the preferred way to create a multiple-list set in Python , I did some performance analysis and came up with a somewhat surprising conclusion.

Using

python -m timeit -s ' import itertools import random n=1000000 random.seed(0) A = [random.randrange(1<<30) for _ in xrange(n)] B = [random.randrange(1<<30) for _ in xrange(n)] C = [random.randrange(1<<30) for _ in xrange(n)]' 

for customization, I timed the following snippets:

 > $TIMEIT 'set(A+B+C)' 10 loops, best of 3: 872 msec per loop > $TIMEIT = set(A); s.update(B); s.update(C)' 10 loops, best of 3: 930 msec per loop > $TIMEIT = set(itertools.chain(A,B,C))' 10 loops, best of 3: 941 msec per loop 

To my surprise, set(A+B+C) is the fastest, despite the fact that it creates an intermediate list containing 3,000,000 items. .update and itertools.chain are slower, although none of them copy lists.

What's going on here?

---

EDIT: on the second computer (OS X 10.10.5, Python 2.7.10, 2.5GHz Core i7) I ran the following script (which runs tests back and forth to avoid sequencing effects):

 SETUP='import itertools import random n=1000000 random.seed(0) A = [random.randrange(1<<30) for _ in xrange(n)] B = [random.randrange(1<<30) for _ in xrange(n)] C = [random.randrange(1<<30) for _ in xrange(n)]' python -m timeit -s "$SETUP" 'set(A+B+C)' python -m timeit -s "$SETUP" = set(A); s.update(B); s.update(C)' python -m timeit -s "$SETUP" = set(itertools.chain(A,B,C))' python -m timeit -s "$SETUP" = set(itertools.chain(A,B,C))' python -m timeit -s "$SETUP" = set(A); s.update(B); s.update(C)' python -m timeit -s "$SETUP" 'set(A+B+C)' 

and got the following results:

 10 loops, best of 3: 579 msec per loop 10 loops, best of 3: 726 msec per loop 10 loops, best of 3: 775 msec per loop 10 loops, best of 3: 761 msec per loop 10 loops, best of 3: 737 msec per loop 10 loops, best of 3: 555 msec per loop 

Now set(A+B+C) clearly faster, and the results are pretty stable - it's hard to complement this with a simple measurement error. Running this script several times produces similar results.

Answer 1

I get different, not surprising results than you do in my Win 7 SP1, with a similar processor with Python 2.7.10, where set(A+B+C) seems to be the slowest way to do this, as you might expect. Similar results were obtained with reactivation of garbage and with Python 3.4.3.

I used my own timeit based timeit and got the following results:

 fastest to slowest execution speeds (Python 2.7.10) (10 executions, best of 3 repetitions) set(A); s.update(B); s.update(C) : 4.787919 secs, rel speed 1.00x, 0.00% slower set(A).update(B,C) : 6.463666 secs, rel speed 1.35x, 35.00% slower set(itertools.chain(A,B,C)) : 6.743028 secs, rel speed 1.41x, 40.83% slower set(A+B+C) : 8.030483 secs, rel speed 1.68x, 67.72% slower 

Benchmarking Code:

 from __future__ import print_function import sys from textwrap import dedent import timeit N = 10 # Number of executions of each "algorithm" R = 3 # number of Repeations of executions # common setup for all algorithms (not timed) setup = dedent(""" import itertools import gc import random try: xrange except NameError: xrange = range random.seed(0) n = 1000000 # number of elements in each list A = [random.randrange(1<<30) for _ in xrange(n)] B = [random.randrange(1<<30) for _ in xrange(n)] C = [random.randrange(1<<30) for _ in xrange(n)] # gc.enable() # to (re)enable garbage collection if desired """) algorithms = { "set(A+B+C)": dedent(""" s = set(A+B+C) """), "set(A); s.update(B); s.update(C)": dedent(""" s = set(A); s.update(B); s.update(C) """), "set(itertools.chain(A,B,C))": dedent(""" s = set(itertools.chain(A,B,C)) """), "set(A).update(B,C)": dedent(""" s = set(A).update(B,C) """), } # execute and time algorithms, collecting results timings = [ (label, min(timeit.repeat(algorithms[label], setup=setup, repeat=R, number=N)), ) for label in algorithms ] print('fastest to slowest execution speeds (Python {}.{}.{})\n'.format( *sys.version_info[:3]), ' ({:,d} executions, best of {:d} repetitions)\n'.format(N, R)) longest = max(len(timing[0]) for timing in timings) # length of longest label ranked = sorted(timings, key=lambda t: t[1]) # ascending sort by execution time fastest = ranked[0][1] for timing in ranked: print("{:>{width}} : {:9.6f} secs, rel speed {:4.2f}x, {:6.2f}% slower". format(timing[0], timing[1], round(timing[1]/fastest, 2), round((timing[1]/fastest - 1) * 100, 2), width=longest))