Issue 5186: Reduce hash collisions for objects with no hash method (original) (raw)
Created on 2009-02-08 16:36 by mark.dickinson, last changed 2022-04-11 14:56 by admin. This issue is now closed.
Messages (43)
Author: Mark Dickinson (mark.dickinson) * 
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.
Author: Mark Dickinson (mark.dickinson) *
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.
Author: Antoine Pitrou (pitrou) *
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)
Author: Antoine Pitrou (pitrou) *
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)
Author: Antoine Pitrou (pitrou) *
Date: 2009-02-08 18:13
I observe even greater speedups (15%/20%/37%) on set creation. Here is the updated benchmark script.
Author: Mark Dickinson (mark.dickinson) *
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...
Author: Antoine Pitrou (pitrou) *
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).
Author: Antoine Pitrou (pitrou) *
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)
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.
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
Author: Raymond Hettinger (rhettinger) *
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.
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.
Author: Mark Dickinson (mark.dickinson) *
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,
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.
But I agree that mixing the bottom bits back in (via rotate, or xor, or whatever) doesn't seem likely to help.
Author: Antoine Pitrou (pitrou) *
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.
Author: Mark Dickinson (mark.dickinson) *
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 ) = 2sizeof(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 ) != 2sizeof(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
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.
Author: Mark Dickinson (mark.dickinson) *
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.
Author: Raymond Hettinger (rhettinger) *
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.
Author: Antoine Pitrou (pitrou) *
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?
Author: Mark Dickinson (mark.dickinson) *
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.
Author: Antoine Pitrou (pitrou) *
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).
Author: Antoine Pitrou (pitrou) *
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.
Author: Raymond Hettinger (rhettinger) *
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)))
62515Author: Antoine Pitrou (pitrou) *
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)
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.
Author: Raymond Hettinger (rhettinger) *
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
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" ?
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.
Author: Raymond Hettinger (rhettinger) *
Date: 2009-02-12 03:43
David, yes, I did mean x ^= x>>4; How embarrassing.
Author: Mark Dickinson (mark.dickinson) *
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.
Author: Antoine Pitrou (pitrou) *
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 () 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.
Author: Mark Dickinson (mark.dickinson) *
Date: 2009-02-12 11:54
Well, I had memories of a weird signed/unsigned problem () 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.
Author: Antoine Pitrou (pitrou) *
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?
Author: Mark Dickinson (mark.dickinson) *
Date: 2009-02-12 12:14
+1 for checking in pointer_hash4.patch, provided Raymond approves.
Author: Raymond Hettinger (rhettinger) *
Date: 2009-02-12 12:51
Consider it approved. Though I prefer you switch to x ^= x >> 4.
Author: Mark Dickinson (mark.dickinson) *
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...)
Author: Antoine Pitrou (pitrou) *
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?
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.
Author: Mark Dickinson (mark.dickinson) *
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.
Author: Antoine Pitrou (pitrou) *
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).
Author: Mark Dickinson (mark.dickinson) *
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. :-)
Author: Antoine Pitrou (pitrou) *
Date: 2009-02-13 14:04
pointer_hash5_rotate.patch has been committed to trunk and py3k. Thanks!
Author: Raymond Hettinger (rhettinger) *
Date: 2009-02-13 20:23
Sweet!