<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; "><br><div><div>On Dec 11, 2012, at 1:13 AM, Antoine Pitrou <<a href="mailto:solipsis@pitrou.net">solipsis@pitrou.net</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><blockquote type="cite" style="font-family: Helvetica; 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>On Dec 10, 2012, at 2:48 AM, Christian Heimes <<a href="mailto:christian@python.org">christian@python.org</a>><br>wrote:<br><br><blockquote type="cite">On the other hand every lookup and collision checks needs an<br>additional multiplication, addition and pointer dereferencing:<br><br>entry = entries_baseaddr + sizeof(PyDictKeyEntry) * idx<br></blockquote><br><br>Currently, the dict implementation allows alternative lookup<br>functions based on whether the keys are all strings.<br>The choice of lookup function is stored in a function pointer.<br>That lets each lookup use the currently active lookup<br>function without having to make any computations or branches.<br></blockquote><br style="font-family: Helvetica; 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: Helvetica; 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; ">An indirect function call is technically a branch, as seen from the CPU</span><br style="font-family: Helvetica; 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: Helvetica; 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; ">(and not necessarily a very predictable one, although recent Intel</span><br style="font-family: Helvetica; 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: Helvetica; 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; ">CPUs are said to be quite good at that).</span></blockquote></div><br><div>FWIW, we already have an indirection to the lookup function.</div><div>I would piggyback on that, so no new indirections are required.</div><div><br></div><div>My plan now is to apply the space compaction idea to sets.</div><div>That code is less complex than dicts, and set operations </div><div>stand to benefit the most from improved iteration speed.</div><div><br></div><div>The steps would be:</div><div><br></div><div>* Create a good set of benchmarks for set operations</div><div> for both size and speed.</div><div><br></div><div>* Start with the simplest version of the idea: separate the</div><div> entries table from the hash table. Keep the hash table at</div><div> Py_ssize_t, and pre-allocate the entry array to two-thirds the size</div><div> of the hash table. This should give about a 25% space savings</div><div> and speed-up iteration for all the set-to-set operations.</div><div><br></div><div>* If that all works out, I want to trim the entry table for frozensefs</div><div> so that the entry table has no over-allocations. This should</div><div> give a much larger space savings.</div><div><br></div><div>* Next, I want to experiment with the idea of using char/short/long</div><div> sizes for the hash table. Since there is already an existing</div><div> lookup indirection, this can be done with no additional overhead.</div><div> Small sets will get the most benefit for the space savings and</div><div> the cache performance for hash lookups should improve nicely</div><div> (for a hash table of size 32 could fit in a single cache line).</div><div><br></div><div>At each step, I'll run the benchmarks to make sure the expected</div><div>speed and space benefits are being achieved.</div><div><br></div><div>As a side-effect, sets without deletions will retain their insertion</div><div>order. If this is of concern, it would be no problem to implement</div><div>Antoine's idea of scrambling the entries during iteration.</div><div><br></div><div><br></div><div>Raymond</div><div><br></div><div><br></div><div>P.S. I've gotten a lot of suggestions for improvements to the</div><div>proof-of-concept code. Thank you for that. The latest version</div><div>is at: <a href="http://code.activestate.com/recipes/578375/">http://code.activestate.com/recipes/578375/</a></div><div>In that code, entries are stored in regular Python lists</div><div>and inherit their over-allocation characteristics (about</div><div>12.5% overallocated for large lists). There are many</div><div>other possible allocation strategies with their own</div><div>respective speed/space trade-offs.</div><div><br></div></body></html>