title: Why does subclassing in Python slow things down so much?
body: <p>I was working on a simple class that extends <code>dict</code>, and I realized that key lookup and use of <code>pickle</code> are <em>very</em> slow.</p>
  
  <p>I thought it was a problem with my class, so I did some trivial benchmarks:</p>
  
  <pre class="lang-sh prettyprint-override"><code>(venv) marco@buzz:~/sources/python-frozendict/test$ python --version
  Python 3.9.0a0
  (venv) marco@buzz:~/sources/python-frozendict/test$ sudo pyperf system tune --affinity 3
  [sudo] password for marco: 
  Tune the system configuration to run benchmarks
  
  Actions
  =======
  
  CPU Frequency: Minimum frequency of CPU 3 set to the maximum frequency
  
  System state
  ============
  
  CPU: use 1 logical CPUs: 3
  Perf event: Maximum sample rate: 1 per second
  ASLR: Full randomization
  Linux scheduler: No CPU is isolated
  CPU Frequency: 0-3=min=max=2600 MHz
  CPU scaling governor (intel_pstate): performance
  Turbo Boost (intel_pstate): Turbo Boost disabled
  IRQ affinity: irqbalance service: inactive
  IRQ affinity: Default IRQ affinity: CPU 0-2
  IRQ affinity: IRQ affinity: IRQ 0,2=CPU 0-3; IRQ 1,3-17,51,67,120-131=CPU 0-2
  Power supply: the power cable is plugged
  
  Advices
  =======
  
  Linux scheduler: Use isolcpus=&lt;cpu list&gt; kernel parameter to isolate CPUs
  Linux scheduler: Use rcu_nocbs=&lt;cpu list&gt; kernel parameter (with isolcpus) to not schedule RCU on isolated CPUs
  (venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '                    
  x = {0:0, 1:1, 2:2, 3:3, 4:4}
  ' 'x[4]'
  .........................................
  Mean +- std dev: 35.2 ns +- 1.8 ns
  (venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
  class A(dict):
      pass             
  
  x = A({0:0, 1:1, 2:2, 3:3, 4:4})
  ' 'x[4]'
  .........................................
  Mean +- std dev: 60.1 ns +- 2.5 ns
  (venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
  x = {0:0, 1:1, 2:2, 3:3, 4:4}
  ' '5 in x'
  .........................................
  Mean +- std dev: 31.9 ns +- 1.4 ns
  (venv) marco@buzz:~/sources/python-frozendict/test$ python -m pyperf timeit --rigorous --affinity 3 -s '
  class A(dict):
      pass
  
  x = A({0:0, 1:1, 2:2, 3:3, 4:4})
  ' '5 in x'
  .........................................
  Mean +- std dev: 64.7 ns +- 5.4 ns
  (venv) marco@buzz:~/sources/python-frozendict/test$ python
  Python 3.9.0a0 (heads/master-dirty:d8ca2354ed, Oct 30 2019, 20:25:01) 
  [GCC 9.2.1 20190909] on linux
  Type "help", "copyright", "credits" or "license" for more information.
  &gt;&gt;&gt; from timeit import timeit
  &gt;&gt;&gt; class A(dict):
  ...     def __reduce__(self):                 
  ...         return (A, (dict(self), ))
  ... 
  &gt;&gt;&gt; timeit("dumps(x)", """
  ... from pickle import dumps
  ... x = {0:0, 1:1, 2:2, 3:3, 4:4}
  ... """, number=10000000)
  6.70694484282285
  &gt;&gt;&gt; timeit("dumps(x)", """
  ... from pickle import dumps
  ... x = A({0:0, 1:1, 2:2, 3:3, 4:4})
  ... """, number=10000000, globals={"A": A})
  31.277778962627053
  &gt;&gt;&gt; timeit("loads(x)", """
  ... from pickle import dumps, loads
  ... x = dumps({0:0, 1:1, 2:2, 3:3, 4:4})
  ... """, number=10000000)
  5.767975459806621
  &gt;&gt;&gt; timeit("loads(x)", """
  ... from pickle import dumps, loads
  ... x = dumps(A({0:0, 1:1, 2:2, 3:3, 4:4}))
  ... """, number=10000000, globals={"A": A})
  22.611666693352163
  </code></pre>
  
  <p>The results are really a surprise. While key lookup is 2x slower, <code>pickle</code> is <em>5x</em> slower.</p>
  
  <p>How can this be? Other methods, like <code>get()</code>,<code>__eq__()</code> and <code>__init__()</code>, and iteration over <code>keys()</code>, <code>values()</code> and <code>items()</code> are as fast as <code>dict</code>.</p>
  
  <hr>
  
  <p><strong>EDIT</strong>: I took a look at the source code of Python 3.9, and in <code>Objects/dictobject.c</code> it seems that the <code>__getitem__()</code> method is implemented by <code>dict_subscript()</code>. And <code>dict_subscript()</code> slows down subclasses only if the key is missing, since the subclass can implement <code>__missing__()</code> and it tries to see if it exists. But the benchmark was with an existing key.</p>
  
  <p>But I noticed something: <code>__getitem__()</code> is defined with the flag <code>METH_COEXIST</code>. And also <code>__contains__()</code>, the other method that is 2x slower, has the same flag. From the <a href="https://docs.python.org/3.9/c-api/structures.html#METH_COEXIST" rel="nofollow noreferrer">official documentation</a>:</p>
  
  <blockquote>
    <p>The method will be loaded in place of existing definitions. Without
    METH_COEXIST, the default is to skip repeated definitions. Since slot
    wrappers are loaded before the method table, the existence of a
    sq_contains slot, for example, would generate a wrapped method named
    <strong>contains</strong>() and preclude the loading of a corresponding PyCFunction with the same name. With the flag defined, the PyCFunction will be
    loaded in place of the wrapper object and will co-exist with the slot.
    This is helpful because calls to PyCFunctions are optimized more than
    wrapper object calls.</p>
  </blockquote>
  
  <p>So if I understood correctly, in theory <code>METH_COEXIST</code> should speed things up, but it seems to have the opposite effect. Why?</p>
  
  <hr>
  
  <p><strong>EDIT 2</strong>: I discovered something more.</p>
  
  <p><code>__getitem__()</code> and <code>__contains()__</code> are flagged as <code>METH_COEXIST</code>, because they are declared in PyDict_Type <strong>two</strong> times.</p>
  
  <p>They are both present, one time, in the slot <code>tp_methods</code>, where they are explicitly declared as <code>__getitem__()</code> and <code>__contains()__</code>. But the <a href="https://docs.python.org/3/c-api/typeobj.html#c.PyTypeObject.tp_methods" rel="nofollow noreferrer">official documentation</a> says that <code>tp_methods</code> are <strong>not</strong> inherited by subclasses.</p>
  
  <p>So a subclass of <code>dict</code> does not call <code>__getitem__()</code>, but calls the subslot <code>mp_subscript</code>. Indeed, <code>mp_subscript</code> is contained in the slot <code>tp_as_mapping</code>, that permits a subclass to inherit its subslots.</p>
  
  <p>The problem is that both <code>__getitem__()</code> and <code>mp_subscript</code> use the <strong>same</strong> function, <code>dict_subscript</code>. Is it possible that it's only the way it was inherited that slows it down?</p>