[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [59487] trunk/blender/source/blender/ blenlib/intern/BLI_ghash.c: For pointer hashing use the same method as python, it gives better distribution.

[Campbell Barton]

Revision: 59487
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=59487
Author:   campbellbarton
Date:     2013-08-24 20:30:08 +0000 (Sat, 24 Aug 2013)
Log Message:
-----------
For pointer hashing use the same method as python, it gives better distribution.

some tests with high poly mesh data in hashes.
- empty buckets before 4-5%, after 1-2%
- speedup for hash lookups, in my tests lookups take approx ~60% of the time they did before.

Modified Paths:
--------------
    trunk/blender/source/blender/blenlib/intern/BLI_ghash.c

Modified: trunk/blender/source/blender/blenlib/intern/BLI_ghash.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/BLI_ghash.c	2013-08-24 20:16:14 UTC (rev 59486)
+++ trunk/blender/source/blender/blenlib/intern/BLI_ghash.c	2013-08-24 20:30:08 UTC (rev 59487)
@@ -408,10 +408,23 @@
 
 /***/
 
+#if 0
+/* works but slower */
 unsigned int BLI_ghashutil_ptrhash(const void *key)
 {
 	return (unsigned int)(intptr_t)key;
 }
+#else
+/* based python3.3's pointer hashing function */
+unsigned int BLI_ghashutil_ptrhash(const void *key)
+{
+	size_t y = (size_t)key;
+	/* 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 *) - 4));
+	return (unsigned int)y;
+}
+#endif
 int BLI_ghashutil_ptrcmp(const void *a, const void *b)
 {
 	if (a == b)