copy.copy vs copy.deepcopy performance on tuples

Question

%python -m timeit -s "import copy" "x = (1, 2, 3)" "copy.deepcopy(x)"
100000 loops, best of 3: 10.1 usec per loop

%python -m timeit -s "import copy" "x = (1, 2, 3)" "copy.copy(x)"
1000000 loops, best of 3: 0.609 usec per loop

Why is deepcopy 15 times slower than copy?

Each function has to iterate through the elements of the tuple. During that iteration, copy creates another reference to each element; deepcopy deepcopies each element.

But each element is an int, and deepcopying an int simply creates another reference to it. In other words, the two functions seem to perform precisely the same steps, the same number of times.

Here's the verification that no new instances are created in the process:

ActivePython 3.2.1.2 (ActiveState Software Inc.) based on
Python 3.2.1 (default, Jul 18 2011, 14:31:09) [MSC v.1500 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> x = (1,2,3)
>>> import copy
>>> y = copy.copy(x)
>>> z = copy.deepcopy(x)
>>> x is y
True
>>> x is z
True
>>> x[1] is z[1]
True

Answer 1

Tuples are immutable, but they can contain mutable elements:

>>> a = (1, 2, [])
>>> a[2].append(1000)
>>> a
(1, 2, [1000])

Note that the tuple doesn't change: it's the list the one that does; the tuple still contains the exact same list.

deepcopy should recurse copying those mutable elements. copy just copies the references to them.

>>> from copy import copy, deepcopy

>>> a = (1, 2, [])
>>> c = copy(a)
>>> d = deepcopy(a)

>>> a[2].append(1000)

>>> c
(1, 2, [1000])
>>> d
(1, 2, [])