This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: Reduce hash collisions for objects with no __hash__ method
Type: performance Stage:
Components: Interpreter Core Versions: Python 3.1, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: pitrou Nosy List: LambertDW, Rhamphoryncus, chemacortes, jcea, mark.dickinson, pitrou, rhettinger
Priority: normal Keywords: patch

Created on 2009-02-08 16:36 by mark.dickinson, last changed 2022-04-11 14:56 by admin. This issue is now closed.

Files
File name Uploaded Description Edit
pointer_hash.patch mark.dickinson, 2009-02-08 16:36
pointer_hash2.patch mark.dickinson, 2009-02-11 12:28
pointer_hash3.patch pitrou, 2009-02-11 22:52
time_object_hash.py pitrou, 2009-02-11 22:53
pointer_hash4.patch pitrou, 2009-02-11 23:27
linux_x86_64_timings.txt mark.dickinson, 2009-02-13 13:32
pointer_hash5_xor.patch mark.dickinson, 2009-02-13 13:33
pointer_hash5_rotate.patch mark.dickinson, 2009-02-13 13:34
Messages (43)
msg81389 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-08 16:36
In the issue 5169 discussion, Antoine Pitrou suggested that for an object 
x without a __hash__ method, id()/8 might be a better hash value than 
id(), since dicts use the low order bits of the hash as initial key, and 
the 3 lowest bits of an id() will always be zero.

Here's a patch.
msg81390 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-08 17:03
Here are some timings for dict creation, created with the attached script.  
They're not particularly scientific, but they at least show that this one-
line optimization can make a significant difference.

Typical results on my machine (OS X 10.5.6/Intel), 32-bit non-debug build 
of the trunk (r69442):  before

dict creation (selected):  1.95572495461
dict creation (shuffled):  1.98964595795
dict creation:  1.78589916229

and after:

dict creation (selected):  1.7055079937   # (14% speedup)
dict creation (shuffled):  1.5843398571   # (25% speedup)
dict creation:  1.32362794876             # (34% speedup)

BTW, all tests pass on my machine with this patch applied.
msg81396 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-08 17:56
The code path for SIZEOF_LONG < SIZEOF_VOID_P could probably also
benefit from this optimization by casting the pointer to a size_t (this
will effect 64-bit Windows, where long is 32 bits but pointers are 64 bits).

(unfortunately it seems the 64-bit Windows buildbot has disappeared)
msg81398 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-08 18:06
Benchmark results on my machine (64-bit Linux, gcc 4.3.2, AMD X2 3600+):

Before:
dict creation (selected):  5.09600687027
dict creation (shuffled):  5.66548895836
dict creation:  3.72823190689

After:
dict creation (selected):  4.57248306274   (10% speedup)
dict creation (shuffled):  4.81948494911   (15% speedup)
dict creation:  2.43905687332              (35% speedup)
msg81400 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-08 18:13
I observe even greater speedups (15%/20%/37%) on set creation. Here is
the updated benchmark script.
msg81599 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-10 21:00
Some comments, while I remember:

* the argument to _Py_HashPointer is not always divisible by 8.  It's
called to create hashes for various objects, including methodobjects; see 
the line:

	y = _Py_HashPointer((void*)(a->m_ml->ml_meth));

in meth_hash in methodobject.c, for example; here ml_meth is a C function 
pointer.  I can't see how this could be a problem, though, especially as 
is seems very unlikely that two function pointers could be less than 8 
bytes apart.

* following from the above, it's also pretty unlikely that any two object 
pointers will be less than 16 bytes apart, so it might be worth seeing if 
performance with >>4 is noticeably any different from with >>3.

* we should make sure that the value returned by _Py_HashPointer isn't the 
illegal hash value -1 (though it's difficult to see how it could be).  One 
safe way to do this that shouldn't cost any CPU cycles would be to cast to 
unsigned long before the right shift, to be sure that the right shift 
zero-extends instead of sign-extending, so that the result is guaranteed 
nonnegative.

* It *would* be nice to do something about the SIZEOF_LONG < SIZEOF_VOID_P 
case: the current conversion to a PyLong seems like quite an expensive way 
to go.  And I've just ordered a computer with 64-bit Windows installed...
msg81602 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-10 21:18
Some tests on py3k (32-bit build):

>>> l = [object() for i in range(20)]
>>> [id(l[i+1]) - id(l[i]) for i in range(len(l)-1)]
[16, -96, 104, 8, 8, 8, 8, 8, -749528, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]
>>> class C(object):
...    __slots__ = ()
... 
>>> l = [C() for i in range(20)]
>>> [id(l[i+1]) - id(l[i]) for i in range(len(l)-1)]
[-104, 24, 8, 8, 8, 8, 8, 8, 8, 8, 8, 16, 8, 8, 8, 8, 16, -8, 16]
>>> class C(object):
...    __slots__ = ('x')
... 
>>> l = [C() for i in range(20)]
>>> [id(l[i+1]) - id(l[i]) for i in range(len(l)-1)]
[432, 24, -384, 408, 24, 24, -480, 528, 24, 24, 24, 24, 48, -360, 504,
24, -480, 552, 24]

So, as soon as an user-defined type isn't totally trivial, it is
allocated in at least 24-byte memory units. Shifting by 4 shouldn't be
detrimental performance-wise, unless you allocate lots of purely empty
object() instances...

Note: a 64-bit build shows an even greater allocation unit:

>>> class C(object):
...    __slots__ = ('x')
... 
>>> l = [C() for i in range(20)]
>>> [id(l[i+1]) - id(l[i]) for i in range(len(l)-1)]
[56, -112, 168, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
56, 56]

I wonder why the allocation unit is 56 and not 48 (2*24).
msg81606 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-10 21:46
Le mardi 10 février 2009 à 21:18 +0000, Antoine Pitrou a écrit :
> Note: a 64-bit build shows an even greater allocation unit:
> 
> >>> class C(object):
> ...    __slots__ = ('x')
> ... 
> >>> l = [C() for i in range(20)]
> >>> [id(l[i+1]) - id(l[i]) for i in range(len(l)-1)]
> [56, -112, 168, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
> 56, 56]
> 
> I wonder why the allocation unit is 56 and not 48 (2*24).

I have found the answer. The PyGC_Head forces its own alignment using a
"long double" dummy, which in 64-bit mode (Linux / gcc) wastes 8 bytes
between the end of the PyGC_Head and the PyObject itself.
(SIZEOF_LONG_DOUBLE is 16 in pyconfig.h)
msg81619 - (view) Author: Adam Olsen (Rhamphoryncus) Date: 2009-02-11 03:31
On my 64-bit linux box there's nothing in the last 4 bits:

>>> [id(o)%16 for o in [object() for i in range(128)]]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0]

And with a bit more complicated functions I can determine how much shift
gives us the lowest collision rate:

def a(size, shift):
    return len(set((id(o) >> shift) % (size * 2) for o in [object() for
i in range(size)]))

def b(size):
    return [a(size, shift) for shift in range(11)]

def c():
    for i in range(1, 9):
        size = 2**i
        x = ', '.join('% 3s' % count for count in b(size))
        print('% 3s: %s' % (size, x))

>>> c()
  2:   1,   1,   1,   2,   2,   1,   1,   1,   2,   2,   2
  4:   1,   1,   2,   3,   4,   3,   2,   4,   4,   3,   2
  8:   1,   2,   4,   6,   6,   7,   8,   6,   4,   3,   2
 16:   2,   4,   7,   9,  12,  13,  12,   8,   5,   3,   2
 32:   4,   8,  14,  23,  30,  25,  19,  12,   7,   4,   2
 64:   8,  16,  32,  55,  64,  38,  22,  13,   8,   4,   2
128:  16,  32,  64, 114, 128,  71,  39,  22,  12,   6,   3
256:  32,  64, 128, 242, 242, 123,  71,  38,  20,  10,   5

The fifth column (ie 4 bits of shift, a divide of 16) works the best. 
Although it varies from run to run, probably more than half the results
in that column have no collisions at all.

.. although, if I replace object() with list() I get best results with a
shift of 6 bits.  Replacing it with dict() is best with 8 bits.

We may want something more complicated.
msg81620 - (view) Author: Adam Olsen (Rhamphoryncus) Date: 2009-02-11 03:53
Upon further inspection, although a shift of 4 (on a 64-bit linux box)
isn't perfect for dict, it's fairly close to it and well beyond random
hash values.  Mixing things more is just gonna lower it towards random
values.

>>> c()
  2:   1,   1,   1,   2,   2,   1,   1,   1,   1,   1,   2
  4:   1,   1,   2,   3,   4,   3,   3,   2,   2,   2,   3
  8:   1,   2,   4,   7,   8,   7,   5,   6,   7,   5,   5
 16:   2,   4,   7,  11,  16,  15,  12,  14,  15,   9,   7
 32:   3,   5,  10,  18,  31,  30,  30,  30,  31,  20,  12
 64:   8,  14,  23,  36,  47,  54,  59,  59,  61,  37,  21
128:  16,  32,  58,  83, 118, 100, 110, 114, 126,  73,  41
256:  32,  64, 128, 195, 227, 197, 203, 240, 253, 150,  78
msg81625 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-02-11 04:29
Instead of a shift, how about a rotate or byteswap in case the lower
bits ever become significant again in some build.
msg81635 - (view) Author: Adam Olsen (Rhamphoryncus) Date: 2009-02-11 09:02
The alignment requirements (long double) make it impossible to have
anything in those bits.

Hypothetically, a custom allocator could lower the alignment
requirements to sizeof(void *).  However, rotating to the high bits is
pointless as they're the least likely to be used — impossible in this
case, as only the 2 highest bits would contain anything, and for that
you'd need a dictionary with at least 2 billion entries on 32bit, which
is more than the 32bit address space.  64-bit is similar.

Note that mixing the bits back in, via XOR or similar, is actually more
likely to hurt than help.  It's just like ints and strings, who's hash
values are very sequential, a simple shift tends to get us sequential
hashes.  This gives us a far lower collision rate than a statistically
random hash.
msg81637 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-11 10:53
[Adam Olsen]
> The alignment requirements (long double) make it impossible to have
> anything in those bits.

Not necessarily, since not all pointers passed to _Py_HashPointer come
from a PyObject_Malloc.  _Py_HashPointer is used for function pointers
as well.  For example, on 64-bit linux I get:

Python 2.7a0 (trunk:69516, Feb 11 2009, 10:43:51)
[GCC 4.2.1 (SUSE Linux)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from hashlib import sha224
>>> hash(sha224)
47100514454970
>>> hash(sha224) % 16
10

> for that you'd need a dictionary with at least 2 billion entries
> on 32bit,

<nitpick> If I recall correctly, the higher bits of the hash value also
get used in collision resolution: they're mixed in to the algorithm
that's used to produce the probing sequence when looking for an empty
slot.  So the dictionary wouldn't necessarily have to be quite that
large for the top bits to come into play. </nitpick>

But I agree that mixing the bottom bits back in (via rotate, or xor, or
whatever) doesn't seem likely to help.
msg81639 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-11 12:18
Le mercredi 11 février 2009 à 03:31 +0000, Adam Olsen a écrit :
> 
> .. although, if I replace object() with list() I get best results with a
> shift of 6 bits.  Replacing it with dict() is best with 8 bits.

But list() and dict() don't use id() for hash.
msg81640 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-11 12:27
Here's an updated patch, that errs on the conservative side:

- rotate instead of shifting, as suggested by Raymond.  This costs
  very little, and I admit to feeling uncomfortable about the
  possibility of just throwing bits away 

- explicit check for -1

- special case for sizeof(void *) = 2*sizeof(long)

All tests pass with the patch applied.  I've left the 'convert to
PyLong' code in as a safety net: it's used on platforms where
sizeof(void *) > sizeof(long) but sizeof(void *) != 2*sizeof(long).  I
don't know of any such platforms in current use.

Sample timings on 64-bit linux (non-debug trunk build, Core 2 Duo).  

before:

dict creation (selected):  1.18751096725
dict creation (shuffled):  1.21234202385
dict creation:  1.00831198692
set creation (selected):  0.869561910629
set creation (shuffled):  0.867420911789
set creation:  0.77153301239

and after:

dict creation (selected):  1.06817317009
dict creation (shuffled):  0.987659931183
dict creation:  0.662216901779
set creation (selected):  0.735805034637
set creation (shuffled):  0.659453868866
set creation:  0.445232152939
msg81670 - (view) Author: Adam Olsen (Rhamphoryncus) Date: 2009-02-11 20:59
Antoine, I only meant list() and dict() to be an example of objects with
a larger allocation pattern.  We get a substantial benefit from the
sequentially increasing memory addresses, and I wanted to make sure that
benefit wasn't lost on larger allocations than object().

Mark, I concede the point about rotating; I believe the cost on x86 is
the same regardless.

Why are you still only rotating 3 bits?  My results were better with 4
bits, and that should be the sweet spot for the typical use cases.

Also, would the use of size_t make this code simpler?  It should be the
size of the pointer even on windows.
msg81672 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-11 21:18
I'm fine with rotating 4 bits instead of 3, especially if the timings look 
good on 32-bit as well as 64-bit.

We should really benchmark dict lookups (and set membership tests) as well 
as dict creation.
msg81678 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-02-11 22:04
At four bits, you may be throwing away information and I don't think
that's cool.  Even if some selected timings are better with more bits
shifted, all you're really showing is that there is more randomness in
the upper bits than the lower ones.  But that doesn't mean than the
lower one contribute nothing at all.

I'm *much* more comfortable with a byte-swap, rotation, or xoring-in
upper bits than with shifts that potentially destroy entropy. 
Otherwise, your taxing apps that build giant sets/dicts and need all
distinguishing bits to avoid collision pile-ups.
msg81679 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-11 22:22
> I'm *much* more comfortable with a byte-swap, rotation, or xoring-in
> upper bits than with shifts that potentially destroy entropy. 
> Otherwise, your taxing apps that build giant sets/dicts and need all
> distinguishing bits to avoid collision pile-ups.

Would (id() >> 4) + (id() & 15) be ok?
msg81681 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-11 22:29
> At four bits, you may be throwing away information and I don't think
> that's cool.

The current patch *does* do a rotation:  it doesn't throw away any 
information.
msg81682 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-11 22:52
Here is an updated patch. It uses a 4-bit shift and an addition. We
should avoid the use of logical or, because it makes the outputs
non-uniformly distributed ('1' bits are more likely).
msg81683 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-11 22:53
Here is an updated benchmark script, for both object() and an
user-defined class, and adding dict lookup, set lookup and set difference.
Set difference is massively faster: up to 60% faster.
msg81685 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-02-11 23:00
Guys, let's be careful.  Make sure that efforts to randomize lower bits
don't destroy information.   Something like x |= x>>8 is reversible and
fast.  Other fun looking transformations are not:

    >>> len(set((x >> 4) + (x & 15) for x in range(10**6)))
    62515
msg81689 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-11 23:27
Ok, updated patch:
- uses a 4-bit rotate (not shift)
- avoids comparing an unsigned long to -1
- tries to streamline the win64 special path (but I can't test)
msg81700 - (view) Author: Adam Olsen (Rhamphoryncus) Date: 2009-02-12 01:07
> At four bits, you may be throwing away information and I don't think
> that's cool.  Even if some selected timings are better with more bits
> shifted, all you're really showing is that there is more randomness in
> the upper bits than the lower ones.  But that doesn't mean than the
> lower one contribute nothing at all.

On the contrary, the expected collision rate for a half-full dictionary
is about 21%, whereas I'm getting less than 5%.  I'm taking advantage of
the sequentiality of addresses, just as int and str hashes do for their
values.

However, you're right that it's only one use case.  Although creating a
burst of objects for a throw-away set may itself be common, it's
typically with int or str, and doing it with custom objects is
presumably fairly rare; certainly not a good microbenchmark for the rest
of the interpreter.

Creating a list of 100000 objects, then shuffling and picking a few
increases my collision rate back up to 21%.  That should more accurately
reflect a long-running program using custom objects as keys in a dict.

That said, I still prefer the simplicity of a rotate.  Adding an
arbitrary set of OR, XOR, or add makes me uneasy; I know enough to do
them wrong (reduce entropy), but not enough to do them right.
msg81705 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-02-12 02:08
[Antoine]
> Ok, updated patch:
> - uses a 4-bit rotate (not shift)
> - avoids comparing an unsigned long to -1
> - tries to streamline the win64 special path (but I can't test)

pointer_hash4.patch looks fine to me.  Still, I think it's worth
considering the simpler and faster:  x |= x>>4.  The latter doesn't
require any special-casing for various pointer sizes.  It just works.

[Adam]
> Adding an arbitrary set of OR, XOR, or add makes me uneasy;
> I know enough to do them wrong (reduce entropy), but not 
> enough to do them right.

It's easy enough to prove (just show that the function is reversible)
and easy enough to test:

   assert len(set(ids)) == len(set(map(f, set(ids)))) # for any large
group of ids
msg81709 - (view) Author: David W. Lambert (LambertDW) Date: 2009-02-12 02:40
"x |= x>>4"

Are you (Ray) sure you didn't mean

"x ^= x>>4"    ?
msg81714 - (view) Author: Adam Olsen (Rhamphoryncus) Date: 2009-02-12 03:19
Testing with a large set of ids is a good demonstration, but not proof.
 Forming a set of *all* possible values within a certain range is proof.

However, XOR does work (OR definitely does not) — it's a 1-to-1
transformation (reversible as you say.)

Additionally, it still gives the unnaturally low collision rate when
using sequential addresses, so there's no objection there.
msg81718 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-02-12 03:43
David, yes, I did mean x ^= x>>4;
How embarrassing.
msg81734 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-12 08:57
> > - avoids comparing an unsigned long to -1

Just out of interest, why?  The cast is unnecessary:  there's no ambiguity 
or undefinedness (the int -1 gets promoted to unsigned long, with 
wraparound semantics), and neither gcc nor MSVC complains.

Other than that, the patch looks fine to me;  x ^= x >> 4 would be fine  
too.  I really don't see that it makes much difference either way, since 
both transformations are reversible and fast enough.
msg81737 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-12 11:09
Mark:
> Just out of interest, why?  The cast is unnecessary:  there's no ambiguity 
> or undefinedness (the int -1 gets promoted to unsigned long, with 
> wraparound semantics), and neither gcc nor MSVC complains.

Well, I had memories of a weird signed/unsigned problem (issue4935) and
I wasn't sure whether it could raise its head in the present case or
not.

Raymond:
> The latter doesn't
> require any special-casing for various pointer sizes.

The special casing is just there so as to make all pointer bits
participate in the final hash (which is what the original implementation
does). Otherwise we could just unconditionally cast to unsigned long.
msg81744 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-12 11:54
> Well, I had memories of a weird signed/unsigned problem (issue4935) and
> I wasn't sure whether it could raise its head in the present case or
> not.

I'm 99.9% sure that it's not a problem here.  If it is a problem then it
needs to be fixed in long_hash in longobject.c as well, which uses
exactly the same code.

The relevant section of the C99 standard is 6.3.1.8, para. 1 (try
googling for 'n1256' if you don't have a copy of the standard).  The
only really nasty cases are those of the form unsigned_int +
signed_long, or more generally,

low_rank_unsigned_integer binary_op higher_rank_signed_integer

where the type of the expression depends on the relative sizes (not just
ranks) of the integer types, giving potential portability problems.  And
there are similar problems with the integer promotions (6.3.1.1, para. 2).

I guess it comes down to personal taste, but my own preference is to
leave out casts where the conversion they describe is already implied by
the C language rules, adding them back in to silence compiler warnings
if necessary.  I find it reduces noise in the code and makes the
important casts more visible, but chacun à son goût.
msg81750 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-12 12:09
> Other than that, the patch looks fine to me;  x ^= x >> 4 would be fine  
> too.

I've just tried x ^= x >> 4 and the speedup is smaller on our
microbenchmark (time_object_hash.py). I conjecture that trying to
maintain the sequentiality of adresses may have beneficial cache
locality effects. Should we care?
msg81755 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-12 12:14
+1 for checking in pointer_hash4.patch, provided Raymond approves.
msg81759 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-02-12 12:51
Consider it approved.  Though I prefer you switch to x ^= x >> 4.
msg81768 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-12 14:55
> Though I prefer you switch to x ^= x >> 4.

Okay, how about this one?  Short and sweet.  No loss of information
except when sizeof(void *) > sizeof(long) (unavoidable until someone
finds a way to fit all 64-bit pointers into a 32-bit integer type...)
msg81778 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-12 16:58
> Okay, how about this one? 

Apart from the misindentation (the file should use tabs not spaces),
have you run the benchmark script with it?
msg81822 - (view) Author: Adam Olsen (Rhamphoryncus) Date: 2009-02-12 21:33
Antoine, x ^= x>>4 has a higher collision rate than just a rotate. 
However, it's still lower than a statistically random hash.

If you modify the benchmark to randomly discard 90% of its contents this
should give you random addresses, reflecting a long-running program.

Here's the results I got (I used shift, too lazy to rotate):
XOR, sequential:      20.174627065692999
XOR, random:          30.460708379770004
shift, sequential:    19.148091554626003
shift, random:        30.495631933229998
original, sequential: 23.736469268799997
original, random:     33.536177158379999

Not massive, but still worth fixing the hash.
msg81921 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-13 13:32
> Apart from the misindentation 

Apologies.  My fault for editing Python files while at work, with a
substandard editor configuration...

> have you run the benchmark script with it?

I have now.  See attached file for 3 sets of results (original, xor
version, and rotate) on 64-bit Linux/Core 2 Duo.

Summary: rotate is uniformly and significantly faster than xor;  xor is
uniformly and significantly faster than the unpatched version.
msg81923 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-13 13:38
Ok, so the rotate version is really significantly faster (and, as Adam
pointed out, it's also theoretically better).
msg81927 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2009-02-13 13:44
Antoine, please check in a patch of your choice.  I think we've beaten
this issue to death already. :-)
msg81929 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-02-13 14:04
pointer_hash5_rotate.patch has been committed to trunk and py3k. Thanks!
msg81970 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2009-02-13 20:23
Sweet!
History
Date User Action Args
2022-04-11 14:56:45adminsetgithub: 49436
2009-02-13 20:23:29rhettingersetmessages: + msg81970
2009-02-13 19:13:14terry.reedylinkissue5169 superseder
2009-02-13 14:04:34pitrousetstatus: open -> closed
resolution: accepted -> fixed
2009-02-13 14:04:26pitrousetmessages: + msg81929
2009-02-13 13:46:38pitrousetassignee: pitrou
2009-02-13 13:44:52mark.dickinsonsetmessages: + msg81927
2009-02-13 13:38:48pitrousetmessages: + msg81923
2009-02-13 13:34:13mark.dickinsonsetfiles: - pointer_hash5.patch
2009-02-13 13:34:05mark.dickinsonsetfiles: + pointer_hash5_rotate.patch
2009-02-13 13:33:57mark.dickinsonsetfiles: + pointer_hash5_xor.patch
2009-02-13 13:32:25mark.dickinsonsetfiles: + linux_x86_64_timings.txt
messages: + msg81921
2009-02-13 12:32:09mark.dickinsonsetfiles: - time_object_hash.py
2009-02-12 21:33:32Rhamphoryncussetmessages: + msg81822
2009-02-12 16:58:35pitrousetmessages: + msg81778
2009-02-12 14:55:54mark.dickinsonsetfiles: + pointer_hash5.patch
messages: + msg81768
2009-02-12 12:51:13rhettingersetresolution: accepted
messages: + msg81759
2009-02-12 12:14:39mark.dickinsonsetmessages: + msg81755
2009-02-12 12:09:20pitrousetmessages: + msg81750
2009-02-12 11:54:24mark.dickinsonsetmessages: + msg81744
2009-02-12 11:09:24pitrousetmessages: + msg81737
2009-02-12 08:57:25mark.dickinsonsetmessages: + msg81734
2009-02-12 03:43:31rhettingersetmessages: + msg81718
2009-02-12 03:19:56Rhamphoryncussetmessages: + msg81714
2009-02-12 02:40:59LambertDWsetnosy: + LambertDW
messages: + msg81709
2009-02-12 02:08:46rhettingersetmessages: + msg81705
2009-02-12 01:07:10Rhamphoryncussetmessages: + msg81700
2009-02-11 23:27:07pitrousetfiles: + pointer_hash4.patch
messages: + msg81689
2009-02-11 23:00:26rhettingersetmessages: + msg81685
2009-02-11 22:53:59pitrousetfiles: - time_object_hash.py
2009-02-11 22:53:49pitrousetfiles: + time_object_hash.py
messages: + msg81683
2009-02-11 22:52:11pitrousetfiles: + pointer_hash3.patch
messages: + msg81682
2009-02-11 22:29:02mark.dickinsonsetmessages: + msg81681
2009-02-11 22:22:38pitrousetmessages: + msg81679
2009-02-11 22:04:16rhettingersetmessages: + msg81678
2009-02-11 21:18:49mark.dickinsonsetmessages: + msg81672
2009-02-11 20:59:38Rhamphoryncussetmessages: + msg81670
2009-02-11 13:01:28chemacortessetnosy: + chemacortes
2009-02-11 12:28:02mark.dickinsonsetfiles: + pointer_hash2.patch
messages: + msg81640
2009-02-11 12:18:50pitrousetmessages: + msg81639
2009-02-11 10:53:24mark.dickinsonsetmessages: + msg81637
2009-02-11 09:02:21Rhamphoryncussetmessages: + msg81635
2009-02-11 04:29:22rhettingersetmessages: + msg81625
2009-02-11 03:53:48Rhamphoryncussetmessages: + msg81620
2009-02-11 03:31:50Rhamphoryncussetnosy: + Rhamphoryncus
messages: + msg81619
2009-02-10 21:46:28pitrousetmessages: + msg81606
2009-02-10 21:18:32pitrousetmessages: + msg81602
2009-02-10 21:00:42mark.dickinsonsetmessages: + msg81599
2009-02-09 23:07:52jceasetnosy: + jcea
2009-02-08 18:13:45pitrousetfiles: + time_object_hash.py
messages: + msg81400
2009-02-08 18:06:58pitrousetmessages: + msg81398
2009-02-08 17:56:23pitrousetmessages: + msg81396
2009-02-08 17:03:10mark.dickinsonsetfiles: + time_object_hash.py
messages: + msg81390
2009-02-08 16:36:16mark.dickinsoncreate