<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Aug 31, 2013 at 9:29 PM, raymond.hettinger <span dir="ltr"><<a href="mailto:python-checkins@python.org" target="_blank">python-checkins@python.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><a href="http://hg.python.org/cpython/rev/d40a65658ff0" target="_blank">http://hg.python.org/cpython/rev/d40a65658ff0</a><br>
changeset: 85486:d40a65658ff0<br>
parent: 85482:4d604f1f0219<br>
user: Raymond Hettinger <<a href="mailto:python@rcn.com">python@rcn.com</a>><br>
date: Sat Aug 31 21:27:08 2013 -0700<br>
summary:<br>
Further reduce the cost of hash collisions by inspecting an additional nearby entry.<br></blockquote><div><br><br></div><div>Hi Raymond,<br><br>I'm curious about the benchmarks used to test such micro-optimizations. Do you use one of the existing Python benchmark suites or do you have a particular set of micro-benchmarks you're running this on?<br>
<br>Eli<br><br></div><div><br> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
files:<br>
Objects/setobject.c | 43 +++++++++++++++++++++++++++++---<br>
1 files changed, 39 insertions(+), 4 deletions(-)<br>
<br>
<br>
diff --git a/Objects/setobject.c b/Objects/setobject.c<br>
--- a/Objects/setobject.c<br>
+++ b/Objects/setobject.c<br>
@@ -65,10 +65,11 @@<br>
The initial probe index is computed as hash mod the table size. Subsequent<br>
probe indices are computed as explained in Objects/dictobject.c.<br>
<br>
-To improve cache locality, each probe is done in pairs.<br>
-After the probe is examined, an adjacent entry is then examined as well.<br>
-The likelihood is that an adjacent entry is in the same cache line and<br>
-can be examined more cheaply than another probe elsewhere in memory.<br>
+To improve cache locality, each probe inspects nearby entries before<br>
+moving on to probes elsewhere in memory. Depending on alignment and the<br>
+size of a cache line, the nearby entries are cheaper to inspect than<br>
+other probes elsewhere in memory. This probe strategy reduces the cost<br>
+of hash collisions.<br>
<br>
All arithmetic on hash should ignore overflow.<br>
<br>
@@ -130,6 +131,26 @@<br>
if (entry->key == dummy && freeslot == NULL)<br>
freeslot = entry;<br>
<br>
+ entry = &table[j ^ 2];<br>
+ if (entry->key == NULL)<br>
+ break;<br>
+ if (entry->key == key)<br>
+ return entry;<br>
+ if (entry->hash == hash && entry->key != dummy) {<br>
+ PyObject *startkey = entry->key;<br>
+ Py_INCREF(startkey);<br>
+ cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);<br>
+ Py_DECREF(startkey);<br>
+ if (cmp < 0)<br>
+ return NULL;<br>
+ if (table != so->table || entry->key != startkey)<br>
+ return set_lookkey(so, key, hash);<br>
+ if (cmp > 0)<br>
+ return entry;<br>
+ }<br>
+ if (entry->key == dummy && freeslot == NULL)<br>
+ freeslot = entry;<br>
+<br>
i = i * 5 + perturb + 1;<br>
j = i & mask;<br>
perturb >>= PERTURB_SHIFT;<br>
@@ -190,6 +211,17 @@<br>
if (entry->key == dummy && freeslot == NULL)<br>
freeslot = entry;<br>
<br>
+ entry = &table[j ^ 2];<br>
+ if (entry->key == NULL)<br>
+ break;<br>
+ if (entry->key == key<br>
+ || (entry->hash == hash<br>
+ && entry->key != dummy<br>
+ && unicode_eq(entry->key, key)))<br>
+ return entry;<br>
+ if (entry->key == dummy && freeslot == NULL)<br>
+ freeslot = entry;<br>
+<br>
i = i * 5 + perturb + 1;<br>
j = i & mask;<br>
perturb >>= PERTURB_SHIFT;<br>
@@ -258,6 +290,9 @@<br>
entry = &table[j ^ 1];<br>
if (entry->key == NULL)<br>
break;<br>
+ entry = &table[j ^ 2];<br>
+ if (entry->key == NULL)<br>
+ break;<br>
i = i * 5 + perturb + 1;<br>
j = i & mask;<br>
perturb >>= PERTURB_SHIFT;<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
Repository URL: <a href="http://hg.python.org/cpython" target="_blank">http://hg.python.org/cpython</a><br>
</font></span><br>_______________________________________________<br>
Python-checkins mailing list<br>
<a href="mailto:Python-checkins@python.org">Python-checkins@python.org</a><br>
<a href="http://mail.python.org/mailman/listinfo/python-checkins" target="_blank">http://mail.python.org/mailman/listinfo/python-checkins</a><br>
<br></blockquote></div><br></div></div>