<div dir="ltr"><div><div><div><div>Hi Raymond,<br><br></div>Thanks for taking the time to respond, I appreciate that!  Please note that I'm not attempting to be deceptive.  I'm not looping over a list of length one; I'm just timing the creation of the iterator object.  In doing this, I've shown that, in a micro-benchmark, creating an iterator object can be made 15% faster with a freelist.<br>
<br></div>Yes, in one loop this is focusing on an O(1) setup of an O(n) operation.  I think the main benefit of this would be for inner loops.  (Which is what my benchmark tested, no?)  In our case, we tend to have a large list to iterate over (n) where each item has a couple containers that we also need to iterate over (size m).  In this case, I'm focusing on the O(n) setup of the O(n*m) operation where n is large.  Surely this isn't completely wasteful?<br>
<br></div>I'm not completely sure what the best way to exercise the case where the freelist misses.  Create one more than the number of freelisted iterators, perhaps?  I'm not sure if that would be reflective of real-world uses though.  Ignoring threads or other spontaneous iterator creation, either a particular loop is going to have its iterator in the freelist or not.  In the case not, we'll just check an iterator and fall back to the default freelist.<br>
<br></div>In regards to your second paragraph, would a more real-world benchmark help?  I don't want to put too many more resources into a bad idea, but I know in our app we tend to iterate over things a lot, so my hunch is that the iterator freelist would be in cache more often than not.  Forgive my ignorance, but is there a macro-benchmark suite I could try this against?  Even if the iterator freelist isn't in first-level cache, I'm almost certain it would exist within last-level cache.  Do you know what the cost of fetching from this is compared to grabbing a lock like the current _Py_Malloc does?<br>
<div><div> <div><div>Again, thanks for the time.  This is literally the first thing I've tried hacking into Python because it seemed like a cheap, easy (albeit, minor) improvement to a very common operation.  <br></div>
<div><br></div><div>Best,<br></div><div>-Kyle<br></div><div><br></div><div>P.S. I would like to put some effort into aligned memory allocations!  I've been casually browsing the issue on the bug tracker over the last week or so; I'm somewhat surprised this isn't already the case for the numerical types!<br>
</div></div></div></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Sep 15, 2013 at 10:38 AM, Raymond Hettinger <span dir="ltr"><<a href="mailto:raymond.hettinger@gmail.com" target="_blank">raymond.hettinger@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><div><div class="h5"><br><div><div>On Sep 14, 2013, at 11:26 PM, Kyle Fisher <<a href="mailto:anthonyfk@gmail.com" target="_blank">anthonyfk@gmail.com</a>> wrote:</div>
<br><blockquote type="cite"><div style="font-family:Arial;font-size:medium;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:-webkit-auto;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">
<div><div>I've realized that my original example is far too complex, so I've simplified it:<br><br></div>Status quo:<br>./python -m timeit -r 100 -s "a=[1]" "iter(a)"<br>10000000 loops, best of 100: 0.0662 usec per loop<br>
<br></div>With patch:<br>./python -m timeit -r 100 -s "a=[1]" "iter(a)"<br>10000000 loops, best of 100: 0.0557 usec per loop<br>List iter allocations: 6<br>List iter reuse through freelist: 1011111554<br>
100.00% reuse rate<br><br></div><span style="font-family:Arial;font-size:medium;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:-webkit-auto;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline!important;float:none">Which seems to show a 15% speedup.  I'd be curious what others get.</span></blockquote>
</div><br></div></div><div>This 15% claim is incredibly deceptive.  You're looping over a list of length one and the "benefits" fall away immediately for anything longer.  It seems like it is intentionally ignoring that you're optimizing an O(1) setup step in an O(n) operation.  And the timing loop does not exercise the cases where the freelist misses.</div>
<div><br></div><div>More important effects are being masked by the tight timing loop that only exercises the most favorable case.  In real programs, your patch may actually make performance worse.  The default freelisting scheme is heavily used and tends to always be in cache.  In contrast, a freelist for less frequently used objects tend to not be in cache when you need them.   Similar logic applies to branch prediction here as well. (In short, I believe that the patch serves only to optimize an unrealistic benchmark and would make actual programs worse-off).</div>
<div><br></div><div>I'm -1 on adding freelisting to iterators.  I recently removed the freelist scheme from Objects/setobject.c because it provided no incremental benefit over the default freelisting scheme.</div><div>
<br></div><div>Please focus your optimization efforts elsewhere in the code.  There are real improvements to be had for operations that matter.  The time to create an iterator is one of the least important operations in Python.   If this had been a real win, I would have incorporated it into itertools long ago. </div>
<span class="HOEnZb"><font color="#888888"><div><br></div><div><br></div><div>Raymond</div></font></span><div><br></div><div><br></div><div>P.S.  If you want to help benchmark the effects of aligned versus unaligned memory allocations, that is an area this likely to bear fruit (for example, if integer objects with 32 byte aligned, it would guarantee that the object head and body would be in the same cache line).</div>
<div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div>
</div></blockquote></div><br></div>