title: Python's Garbage Collector Increases Program Runtime Complexity
body: <p>I'm trying to understand why Python's garbage collector slows down my program <em>algorithmically</em>.</p>
  <p>I have a python program that processes a series of messages, each containing values for different metrics, and I store all of these metrics in a data structure of the format:</p>
  <pre><code>{
    &quot;metric_name1&quot;: {
      &quot;timestamps&quot;: [...],
      &quot;values&quot;: [...]
    },
    ...
  }
  </code></pre>
  <p>Every time a new value is encountered in the input messages, it is appended to the corresponding array. Each input message can contain many metrics. There are thousands of metrics and each metric can have millions of values.</p>
  <p>Recently, I have experienced inordinately high runtimes on some inputs. After doing some profiling, I noted that the runtime is quadratic in terms of input size, even though algorithm's complexity is linear (I just extract values and append them to an array).</p>
  <p>Interestingly, when I disable python's garbage collection via <code>gc.disable()</code>, the runtime becomes linear.</p>
  <p>I have read through <a href="https://devguide.python.org/garbage_collector/" rel="nofollow noreferrer">design docs</a> for python's garbage collector, but I'm having trouble understanding how it can cause this jump from linear to quadratic.</p>
  <p>What part of python's garbage collector could cause this complexity increase?</p>
  <p>For reference, I am using <code>Python 3.6.9</code>.</p>