From 79eee6ba6bfde635bed0992e230d22af2e1e8478 Mon Sep 17 00:00:00 2001 From: Antoine Pitrou Date: Fri, 13 Feb 2009 14:01:05 +0000 Subject: Merged revisions 69582-69583 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ........ r69582 | antoine.pitrou | 2009-02-13 14:52:33 +0100 (ven., 13 févr. 2009) | 4 lines Issue #5186: Reduce hash collisions for objects with no __hash__ method by rotating the object pointer by 4 bits to the right. ........ r69583 | antoine.pitrou | 2009-02-13 14:57:40 +0100 (ven., 13 févr. 2009) | 3 lines Fix compiler warning (gcc) ........ --- Misc/NEWS | 3 +++ Objects/object.c | 22 +++++++--------------- 2 files changed, 10 insertions(+), 15 deletions(-) diff --git a/Misc/NEWS b/Misc/NEWS index 33a1c98..3aa3b49 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -12,6 +12,9 @@ What's New in Python 3.1 alpha 0 Core and Builtins ----------------- +- Issue #5186: Reduce hash collisions for objects with no __hash__ method by + rotating the object pointer by 4 bits to the right. + - Issue #4575: Fix Py_IS_INFINITY macro to work correctly on x87 FPUs: it now forces its argument to double before testing for infinity. diff --git a/Objects/object.c b/Objects/object.c index ee18bc3..8583797 100644 --- a/Objects/object.c +++ b/Objects/object.c @@ -699,23 +699,15 @@ _Py_HashDouble(double v) long _Py_HashPointer(void *p) { -#if SIZEOF_LONG >= SIZEOF_VOID_P - return (long)p; -#else - /* convert to a Python long and hash that */ - PyObject* longobj; long x; - - if ((longobj = PyLong_FromVoidPtr(p)) == NULL) { - x = -1; - goto finally; - } - x = PyObject_Hash(longobj); - -finally: - Py_XDECREF(longobj); + size_t y = (size_t)p; + /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid + excessive hash collisions for dicts and sets */ + y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4)); + x = (long)y; + if (x == -1) + x = -2; return x; -#endif } long -- cgit v0.12