StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>"Dictionary creation" is really a red herring here. What the dictionary creation does in this case that's <em>relevant</em> is that it creates a hundred thousand new 125-element lists. Because lists can be involved in reference cycles, that creates 12.5 million list elements CPython's cyclic garbage collection has to examine whenever it scans a generation containing a dict. It doesn't matter that these lists are in dictionaries, it only matters that they exist.</p> <p>So what you're timing is largely the time consumed by Python's cyclic garbage collection. It doesn't particularly matter that you keep on creating more dicts, it only matters that you're creating new mutable objects (which can be involved in cycles) much faster than you're destroying old mutable objects. That (an excess of allocations over deallocations) is what triggers CPython's cyclic gc).</p> <p>Not much you can do about it, alas. Programs that go through well-delineated <em>phases</em> of creating mounds of new objects can benefit by disabling cyclic gc <em>for the duration</em>. Can't guess whether that applies to you, though.</p> <p>Ah, forgot one: the dict in <code>Foo</code> makes such a big difference because <code>Foo</code> "sticks around". All the other dicts you create are thrown away immediately after being constructed (CPython's reference counting is responsible for that), so don't add to the time consumed by cyclic gc. But the dict in <code>Foo</code> does, because <em>that</em> dict doesn't go away. Change your loop to append the new dicts to a list, and you'll see that the time goes up for each dict, then drops a lot, then goes up again, etc. That reflects dicts moving to older generations inside Python's cyclic gc, so getting scanned by cyclic gc less frequently. It gets complicated ;-)</p> <h2>More details?</h2> <p>It's hard to be more precise, because the performance of cyclic gc in specific cases depends on mountains of implementation details that can - and do - change across releases.</p> <p>The general advice to use "immutable objects" when possible is based on a rather deep ;-) understanding of how cyclic gc is implemented in CPython, and how it's evolved over the years.</p> <p>It so happens that <em>today</em> (most recent versions of Python 2 and Python 3), strong efforts are made to exempt certain tuples and dicts from cyclic gc. That may change. Special-casing such things isn't free, so deciding whether to add more tricks like this is always a difficult balancing act. It's an easier decision for immutable objects, hence the advice to move towards those.</p> <p>Tuples and dicts weren't special-cased at all until very late 2008, as detailed <a href="http://bugs.python.org/issue4688">in this from the Python issue tracker</a>.</p> <p>And - surprise ;-) - that turned out to have horrible performance consequences in <em>some</em> rare cases, which were fixed by <a href="http://bugs.python.org/issue14775">more special-casing in this issue</a> in mid 2012.</p> <p>Some good news is that a <code>gc.is_tracked()</code> function was added so you can at least investigate whether cyclic gc is going to scan a specific object. Here are some examples under Python 2.7.5. There's no guarantee they'll always work this way:</p> <p>"Scalar" objects (no internal pointers) are never tracked - it's impossible for them to be in a cycle:</p> <pre><code>>>> import gc >>> gc.is_tracked(4) False >>> gc.is_tracked("2323") False </code></pre> <p>Tuples are <em>initially</em> tracked:</p> <pre><code>>>> t1 = ([1],) >>> t2 = ((1.),) >>> gc.is_tracked(t1), gc.is_tracked(t2) (True, True) </code></pre> <p>However, if cyclic gc runs and determines that a tuple is immutable "all the way down", it untracks that tuple:</p> <pre><code>>>> gc.collect() 0 >>> gc.is_tracked(t1), gc.is_tracked(t2) (True, False) </code></pre> <p>There's nothing that can be done to <code>t2</code> to make it participate in a cycle, because it, and all its components (on & on, all the way down) are immutable. But <code>t1</code> still needs to be tracked! Because <code>t1[0]</code> is mutable, <code>t1</code> <em>may</em> be part of a cycle later:</p> <pre><code>>>> t1 ([1],) >>> t1[0][0] = t1 >>> t1 ([([...],)],) </code></pre> <p>A different policy happens to be used for dicts. They're <em>created</em> untracked, if possible:</p> <pre><code>>>> d = {1: [2]} >>> gc.is_tracked(d) True </code></pre> <p>Because that dict has a mutable value, it <em>could</em> become part of a cycle later, so must be tracked by cyclic gc.</p> <pre><code>>>> d[1][0] = d >>> d {1: [{...}]} </code></pre> <p>But a dict with untracked keys and values is created untracked:</p> <pre><code>>>> d = {1: 2} >>> gc.is_tracked(d) False </code></pre> <p>This is tricky, because such a dict can still become part of a cycle later!</p> <pre><code>>>> d[2] = d >>> gc.is_tracked(d) True </code></pre> <p>It's not free to detect such changes.</p> <p>Then there are combinations of the above:</p> <pre><code>>>> d = {(1, 2): (4, "abc", 5)} >>> gc.is_tracked(d) True >>> gc.collect() 3 >>> gc.is_tracked(d) False </code></pre> <p>In this case, <code>d</code> is tracked at first, because its keys and values (the tuples) are created tracked at first. But after cyclic gc runs the first time, it determines that the keys and values are "immutable all the way down", so untracks the dict.</p> <p>Like I said, it gets complicated ;-)</p> <p>BTW,</p> <blockquote> <p>I understand that tuple creation is much faster than list creation</p> </blockquote> <p>It should be only slightly slower to create a list. Lists and tuples have very similar implementations in CPython. tuples require a little less memory (which can be significant, in percentage terms, for very short sequences), and it can be a little faster to index a tuple than a list. But creation time? It's the difference between one <code>malloc()</code>-like function (for a tuple) versus two (for a list), independent of the number of elements. That can be significant for very short sequences, but not for large ones.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload