<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><br></div><div><div>On Jun 18, 2013, at 12:00 AM, Gregory P. Smith <<a href="mailto:greg@krypto.org">greg@krypto.org</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div>Why did you do this in the 2.7 branch?</div><div><br></div><div>It hasn't been done in 3.3 or default</div></blockquote><br></div><div>I worked on the 2.7 branch first because that was the one I had loaded</div><div>and the one where I did timings and code disassembly. I intended to</div><div>post it to 3.3 and 3.4 as well over the weekend. </div><div><br></div><div>Ideally, it makes maintenance simpler for me if I keep the branches</div><div>the same as possible. I viewed the one-line struct transposition,</div><div>comment correction, and one-line blocklen change as being somewhat </div><div>innocuous non-algorithmic changes. The struct change fixed an unintended</div><div>cache miss for left links and the blocksize change causes the</div><div>deque_index code to compile more efficiently (using a right-shift</div><div>and bitwise-and and rather than a measurably more expensive</div><div>division and modulo calculation).</div><div><br></div><div>I truly wasn't expecting the Spanish Inquisition :-)</div><div><br></div><br><div><div>On Jun 22, 2013, at 1:43 PM, Scott Dial <<a href="mailto:scott+python-dev@scottdial.com">scott+python-dev@scottdial.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; ">changeset 84248:f1dc30a1be72 2.7</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; ">Arrange structure to match the common access patterns.</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.1 --- a/Modules/_collectionsmodule.c</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.2 +++ b/Modules/_collectionsmodule.c</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.3 @@ -48,8 +48,8 @@</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.4</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.5 typedef struct BLOCK {</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.6 struct BLOCK *leftlink;</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.7 + PyObject *data[BLOCKLEN];</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.8 struct BLOCK *rightlink;</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.9 - PyObject *data[BLOCKLEN];</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.10 } block;</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.11</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; "> 1.12 #define MAXFREEBLOCKS 10</span><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><br style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span style="font-family: Arial; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; display: inline !important; float: none; ">, which seems like a strange micro-optimization, at best.</span><br></blockquote><div><br></div>Yes, this is a micro-optimization. In working on implementing</div><div>deque slicing for 3.4, I restudied the block access patterns. </div><div>On an appendleft(), popleft() or extendleft() operation, the left link is</div><div>accessed immediately before or after the leftmost entry in the data block. </div><div>The old struct arrangement can cause an unnecessary cache miss</div><div>when jumping leftward. This was something I overlooked when I</div><div>originally wrote the code almost a decade ago.</div><div><br></div><div><div>On Jun 23, 2013, at 11:38 AM, Benjamin Peterson <<a href="mailto:benjamin@python.org">benjamin@python.org</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">I've backed this one out, too.</blockquote><div><br></div><div>Really, you reverted my one-line change within 24 hours of it being posted?</div><div>I can't be on-line every day and sometimes it takes a little while to catch up</div><div>with python email.</div><div><br></div><div><div>On Jun 22, 2013, at 2:55 PM, Guido van Rossum <<a href="mailto:guido@python.org">guido@python.org</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">Actually the data buffer is an array of pointers too, so with the<br>original BLOCKLEN value of 62, sizeof(block) would be 64 times<br>sizeof(PyObject *). In the Py3 version of the source there's even a<br>comment explaining this right before the #define BLOCKLEN. Raymond,<br>can you explain?</blockquote><br></div><div>I also tried to fix that comment so it would stop emphasizing the blocklen</div><div>being a multiple of the cache line. Also long as there is a reasonably long</div><div>data block, it matters less whether the data block size is an exact multiple</div><div>of the cache line length (62 or 64 words of data versus a typical 8 byte</div><div>cache line).</div><div><br></div><div>The data block size does matter elsewhere though.</div><div>The benefit of the having the data block being a power-of-two</div><div>is that the deque_index computation can use bits shifts</div><div>rather division and modulo calculations. The benefit</div><div>of switching data block size from 62 to 64 was measurable</div><div>(a few percent) and observable in the disassembly of the code.</div><div><br></div><div>I experimented with one other ordering as well</div><div>(putting the data block first and the links afterwards).</div><div>That saved the scaled-index byte in the generated code</div><div>but produced no measureable speed-up.</div><div><br></div><div>In short, I believe the following should go in:</div><div><br></div><div>* The comment fix. (Incorrectly suggesting that a 64-bit </div><div> Py_ssize_t would overflow). The revised comment</div><div> is simpler, more general, and correct.</div><div><br></div><div>* Putting the leftlink before the data block in the structure.</div><div><br></div><div>The follow is up for debate:</div><div><br></div><div>Changing the BLOCKLEN from 62 to 64 is debatable.</div><div>It measureably improved deque_index without an</div><div>observable negative effect on the other operations.</div><div><br></div><div>Lastly, there was a change I just put in to Py 3.4 replacing</div><div>the memcpy() with a simple loop and replacing the</div><div>"deque->" references with local variables. Besides</div><div>giving a small speed-up, it made the code more clear</div><div>and less at the mercy of various implementations</div><div>of memcpy().</div><div><br></div><div>Ideally, I would like 2.7 and 3.3 to replace their use of</div><div>memcpy() as well, but the flavor of this thread suggests</div><div>that is right out.</div><div><br></div><div><br></div><div>Raymond</div><div><br></div><div><br></div><div><br></div></div></body></html>