changeset:   93487:97dc64adb6fe
user:        Antoine Pitrou <solipsis@pitrou.net>
date:        Sat Nov 15 00:56:27 2014 +0100
files:       Misc/NEWS Objects/typeobject.c
description:
Issue #22847: Improve method cache efficiency.


diff -r 44e77709daa4 -r 97dc64adb6fe Misc/NEWS
--- a/Misc/NEWS	Fri Nov 14 11:48:37 2014 -0800
+++ b/Misc/NEWS	Sat Nov 15 00:56:27 2014 +0100
@@ -10,6 +10,8 @@
 Core and Builtins
 -----------------
 
+- Issue #22847: Improve method cache efficiency.
+
 - Issue #22335: Fix crash when trying to enlarge a bytearray to 0x7fffffff
   bytes on a 32-bit platform.
 
diff -r 44e77709daa4 -r 97dc64adb6fe Objects/typeobject.c
--- a/Objects/typeobject.c	Fri Nov 14 11:48:37 2014 -0800
+++ b/Objects/typeobject.c	Sat Nov 15 00:56:27 2014 +0100
@@ -14,10 +14,11 @@
    MCACHE_MAX_ATTR_SIZE, since it might be a problem if very large
    strings are used as attribute names. */
 #define MCACHE_MAX_ATTR_SIZE    100
-#define MCACHE_SIZE_EXP         9
+#define MCACHE_SIZE_EXP         12
 #define MCACHE_HASH(version, name_hash)                                 \
-        (((unsigned int)(version) * (unsigned int)(name_hash))          \
-         >> (8*sizeof(unsigned int) - MCACHE_SIZE_EXP))
+        (((unsigned int)(version) ^ (unsigned int)(name_hash))          \
+         & ((1 << MCACHE_SIZE_EXP) - 1))
+
 #define MCACHE_HASH_METHOD(type, name)                                  \
         MCACHE_HASH((type)->tp_version_tag,                     \
                     ((PyASCIIObject *)(name))->hash)
@@ -35,6 +36,14 @@
 static struct method_cache_entry method_cache[1 << MCACHE_SIZE_EXP];
 static unsigned int next_version_tag = 0;
 
+#define MCACHE_STATS 0
+
+#if MCACHE_STATS
+static size_t method_cache_hits = 0;
+static size_t method_cache_misses = 0;
+static size_t method_cache_collisions = 0;
+#endif
+
 /* alphabetical order */
 _Py_IDENTIFIER(__abstractmethods__);
 _Py_IDENTIFIER(__class__);
@@ -165,6 +174,18 @@
     Py_ssize_t i;
     unsigned int cur_version_tag = next_version_tag - 1;
 
+#if MCACHE_STATS
+    size_t total = method_cache_hits + method_cache_collisions + method_cache_misses;
+    fprintf(stderr, "-- Method cache hits        = %zd (%d%%)\n",
+            method_cache_hits, (int) (100.0 * method_cache_hits / total));
+    fprintf(stderr, "-- Method cache true misses = %zd (%d%%)\n",
+            method_cache_misses, (int) (100.0 * method_cache_misses / total));
+    fprintf(stderr, "-- Method cache collisions  = %zd (%d%%)\n",
+            method_cache_collisions, (int) (100.0 * method_cache_collisions / total));
+    fprintf(stderr, "-- Method cache size        = %zd KB\n",
+            sizeof(method_cache) / 1024);
+#endif
+
     for (i = 0; i < (1 << MCACHE_SIZE_EXP); i++) {
         method_cache[i].version = 0;
         Py_CLEAR(method_cache[i].name);
@@ -2708,8 +2729,12 @@
         /* fast path */
         h = MCACHE_HASH_METHOD(type, name);
         if (method_cache[h].version == type->tp_version_tag &&
-            method_cache[h].name == name)
+            method_cache[h].name == name) {
+#if MCACHE_STATS
+            method_cache_hits++;
+#endif
             return method_cache[h].value;
+        }
     }
 
     /* Look in tp_dict of types in MRO */
@@ -2743,6 +2768,13 @@
         method_cache[h].version = type->tp_version_tag;
         method_cache[h].value = res;  /* borrowed */
         Py_INCREF(name);
+        assert(((PyASCIIObject *)(name))->hash != -1);
+#if MCACHE_STATS
+        if (method_cache[h].name != Py_None && method_cache[h].name != name)
+            method_cache_collisions++;
+        else
+            method_cache_misses++;
+#endif
         Py_DECREF(method_cache[h].name);
         method_cache[h].name = name;
     }