| msg81269 - (view) |
Author: Chema Cortés (chemacortes) |
Date: 2009-02-06 14:16 |
| Sometimes, the default hash for user-defined object is not equal to the id of the object: In [1]: class A: ...: pass In [2]: a=A() In [3]: id(a),hash(a) Out[3]: (3082955212L, -1212012084) The test box has an AMD Sempron, a 64bit CPU archictecture emulating a 32bit one. This following relation can be deduced: hash(a)=id(a)-2**32 |
|
|
| msg81270 - (view) |
Author: Antoine Pitrou (pitrou) *  |
Date: 2009-02-06 15:50 |
| I wouldn't qualify this as a bug. hash() doesn't need to be equal to the id() even in the default case. Actually, it may be better for hash() to be equal to id()/4 or id()/8, depending on the standard alignment of the memory allocator. |
|
|
| msg81277 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2009-02-06 16:24 |
| It looks like this is a platform with sizeof(long) == 4 and sizeof(void *) == 8. Is that right? As Antoine says, I can't see any problem here. Why do you think that hash(a) should be equal to id(a) in this case? Antoine, in what way would id()/4 be better than id()? |
|
|
| msg81282 - (view) |
Author: Antoine Pitrou (pitrou) * |
Date: 2009-02-06 16:53 |
| Because with hash() == id() == address of the PyObject, the hash is always a multiple of 4 or 8 (I think it's 8), so (hash() % dict_or_set_table_size) is non-uniformly distributed in most cases. |
|
|
| msg81283 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2009-02-06 17:06 |
| Hah. Good point. I'd forgotten about the taking-the-low-order-bits thing. Should probably do some timings (and possibly also number-of- collisions measurements) to find out whether using id() >> 3 actually makes any significant difference (either way) for dicts of objects. |
|
|
| msg81292 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2009-02-06 19:21 |
| Some preliminary timings indicate that it may well be worth replacing 'return (long)p' with 'return (long)p >> 3' in _Py_HashPointer (in Objects/object.c): I'm getting a 10% speedup in dict-building and dict-lookup for dicts of plain objects. I'll open a separate issue for this and post details of the timings. In the meantime, I think this issue can be closed as invalid: there's no reason that id(a) and hash(a) have to be equal. (chemacortes, if you disagree then please do comment; we'll still see the comments even though the issue is closed). |
|
|
| msg81307 - (view) |
Author: Jesús Cea Avión (jcea) * |
Date: 2009-02-06 22:09 |
| The issue is trivially reproductible in any 32 bits platform, simply allocating objects until you go up the 2GB mark. Since __hash__() wants to take advantage of every bit in a 32 bit platform, and we don't have unsigned integers in python, I vote for "invalid" too. There is no promise of "id(obj)==hash(obj)": you can overload "__hash__()" anytime, and that is already done for strings, integers, tuples, etc. The speed advantage is interesting, though. |
|
|
| msg81333 - (view) |
Author: Chema Cortés (chemacortes) |
Date: 2009-02-07 04:41 |
| I also agree to close this bug as invalid. Indeed, there is not any reason to make equal id(a) and hash(a), but the description of "hashable" object from the documentation (but this is a different issue). 'hash' and 'id' returns the same-wordsize integer (32bit): 'id' as unsigned long (Py_uintptr_t), and 'hash' as signed long casted from 'id'. Thanks for your time, Chema |
|
|
| msg81480 - (view) |
Author: Jesús Cea Avión (jcea) * |
Date: 2009-02-09 19:55 |
| Marc, please post the bugid for the "hash>>3" issue. It is interesting enough to pursue it. |
|
|
| msg81481 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2009-02-09 20:03 |
| See issue 5186 for using id()/8 for the hash. |
|
|
| msg81482 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2009-02-09 20:06 |
| Tim, any thoughts? |
|
|
| msg81964 - (view) |
Author: Terry J. Reedy (terry.reedy) * |
Date: 2009-02-13 19:13 |
| Chema, thank you for bringing this semi-conscious assumption to light. Intentionally breaking it significantly speeds up set and dict creation. |
|
|