title: Why is a deep copy so much slower than a shallow copy for lists of the same size?
body: <p>I've been working on a performance critical application which requires frequently requires making copies of a 2D list of integers and modifying the copy (I'm implementing the minimax algorithm).</p>
  
  <p>I've noticed there is a <em>huge</em> difference in performance between a copy, and a deepcopy on lists with the same number of elements, and I'd like to understand if my thinking is correct.</p>
  
  <p>To reproduce my problem, run the following code: </p>
  
  <pre><code>import numpy as np
  
  np.random.seed(0)
  lst1 = np.random.randint(100, size=1000 * 1000).tolist()
  lst2 = np.random.randint(100, size=(1000, 1000)).tolist()
  </code></pre>
  
  <p>Now, timing the statements below, you should see timings similar to mine.</p>
  
  <pre><code>%timeit copy.copy(lst1)
  %timeit lst1.copy()
  %timeit copy.deepcopy(lst2)
  
  5 ms ± 49.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
  5.47 ms ± 551 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
  1.61 s ± 112 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  </code></pre>
  
  <p>Both <code>lst1</code> and <code>lst2</code> have a million elements, but reliably copying the former is 200x faster than a nested list with the same number of elements. I thought this would have to do with the fact that making deep copies of nested lists might require some recursive implementation that is slow, so I tried</p>
  
  <pre><code>%timeit copy.deepcopy(lst1)
  1.43 s ± 90.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 
  </code></pre>
  
  <p>And the timings still show a massive slowdown. I've checked the <a href="https://docs.python.org/3/library/copy.html#copy.deepcopy" rel="nofollow noreferrer">docs</a>  but not much explanation was offered. However, from the timings, I suspect that <code>deepcopy</code> is copying each <em>int</em> as well, creating new integers. But this seems like a wasteful thing to do. </p>
  
  <p>Am I right in my thinking here? What is deepcopy doing here that <code>list.copy</code> and shallow copy don't?</p>
  
  <p>I've seen <a href="https://stackoverflow.com/questions/24756712/deepcopy-is-extremely-slow">deepcopy() is extremely slow</a> but it seems that question is asking for an alternative rather than an explanation (it wasn't clear to me). </p>