Issue 22847: Improve method cache efficiency

The method cache is currently very small. Attached patch bumps the size a bit and improves the hash computation formula.

It's not easy to get stable benchmark runs, but here is an example:

Report on Linux fsol 3.16.0-24-generic #32-Ubuntu SMP Tue Oct 28 13:07:32 UTC 2014 x86_64 x86_64
Total CPU cores: 4

### 2to3 ###
7.083762 -> 6.904087: 1.03x faster

### formatted_logging ###
Min: 0.351515 -> 0.330884: 1.06x faster
Avg: 0.352954 -> 0.332422: 1.06x faster
Significant (t=62.94)
Stddev: 0.00120 -> 0.00197: 1.6382x larger

### mako_v2 ###
Min: 0.035797 -> 0.034659: 1.03x faster
Avg: 0.036427 -> 0.035378: 1.03x faster
Significant (t=50.65)
Stddev: 0.00032 -> 0.00034: 1.0668x larger

### richards ###
Min: 0.174242 -> 0.163918: 1.06x faster
Avg: 0.175643 -> 0.165689: 1.06x faster
Significant (t=58.69)
Stddev: 0.00086 -> 0.00084: 1.0168x smaller

### simple_logging ###
Min: 0.300215 -> 0.287112: 1.05x faster
Avg: 0.301957 -> 0.288785: 1.05x faster
Significant (t=80.08)
Stddev: 0.00086 -> 0.00078: 1.1052x smaller

The following not significant results are hidden, use -v to show them:
django_v2, silent_logging, tornado_http.

Current hashing algorithm takes middle bits, proposed code takes low bits. Doesn't this make the hash worse?

FYI method cache optimization was added in issue1700288.

The low bits of the unicode hash should be as good as the middle bits.

In addition, the tp_version_tag evolves incrementally, so the low bits should be better when the same name is looked up on different types.

Thanks for adding the instrumentation.  Otherwise, it would have been difficult to tell whether the xor hashing had a significant deleterious effect on collisions.

Also, +1 on bumping up the cache size.

New changeset 97dc64adb6fe by Antoine Pitrou in branch 'default':
Issue #22847: Improve method cache efficiency.
https://hg.python.org/cpython/rev/97dc64adb6fe

Now pushed. Thanks for the comments!

I'm reopening this and assigning it to benjamin as the 2.7 release manager.  This change is valuable to apply to 2.7.x as well.  It is very simple and is a clear performance improvement for realistic workloads.  No API change.

When you profile Python 2.7 applications today, the _PyType_Lookup function shows up in the ~3% of all CPU cycles range.  This reduces that for a small memory tradeoff.

We're raising our cache exponent to be even larger than the 12 in this patch at work as we've got some huge applications.  Regardless, 12 is a much better default than the existing 9.

New changeset 6357d851029d by Antoine Pitrou in branch '2.7':
Issue #22847: Improve method cache efficiency.
https://hg.python.org/cpython/rev/6357d851029d

I suppose we've backported scarier things.

It appears this change broke all FreeBSD builders (9: gcc, 10/11: clang) for the 2.7 branch with:

==== koobs-freebsd-current (clang 3.7.x)

cc -pthread -c -fno-strict-aliasing -OPT:Olimit=0 -g -O2 -g -O0 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include  -DPy_BUILD_CORE -o Objects/typeobject.o Objects/typeobject.c
Objects/typeobject.c:2568:44: error: no member named 'hash' in 'PyStringObject'
        assert(((PyStringObject *)(name))->hash != -1);
               ~~~~~~~~~~~~~~~~~~~~~~~~~~  ^
/usr/include/assert.h:54:21: note: expanded from macro 'assert'
#define assert(e)       ((e) ? (void)0 : __assert(__func__, __FILE__, \
                          ^
1 error generated.
*** Error code 1

==== koobs-freebsd10 (clang 3.4.x)

cc -pthread -c -fno-strict-aliasing -OPT:Olimit=0 -g -O2 -g -O0 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include -fPIC -DPy_BUILD_CORE -o Objects/unicodeobject.o Objects/unicodeobject.c
--- Objects/typeobject.o ---
Objects/typeobject.c:2568:18: error: use of undeclared identifier 'PyASCIIObject'
        assert(((PyASCIIObject *)(name))->hash != -1);
                 ^
/usr/include/assert.h:54:21: note: expanded from macro 'assert'
#define assert(e)       ((e) ? (void)0 : __assert(__func__, __FILE__, \
                          ^
Objects/typeobject.c:2568:33: error: expected expression
        assert(((PyASCIIObject *)(name))->hash != -1);
                                ^
/usr/include/assert.h:54:21: note: expanded from macro 'assert'
#define assert(e)       ((e) ? (void)0 : __assert(__func__, __FILE__, \
                          ^
--- Objects/unicodectype.o ---
cc -pthread -c -fno-strict-aliasing -OPT:Olimit=0 -g -O2 -g -O0 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include -fPIC -DPy_BUILD_CORE -o Objects/unicodectype.o Objects/unicodectype.c
--- Objects/typeobject.o ---
2 errors generated.
*** [Objects/typeobject.o] Error code 1


==== koobs-freebsd9 (gcc 4.2.1 + patches)

gcc -pthread -c -fno-strict-aliasing -g -O2 -g -O0 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include  -DPy_BUILD_CORE -o Objects/unicodeobject.o Objects/unicodeobject.c
Objects/unicodeobject.c: In function 'PyUnicode_DecodeUTF7Stateful':
Objects/unicodeobject.c:1694: warning: comparison is always true due to limited range of data type
gcc -pthread -c -fno-strict-aliasing -g -O2 -g -O0 -Wall -Wstrict-prototypes  -I. -IInclude -I./Include  -DPy_BUILD_CORE -o Objects/unicodectype.o Objects/unicodectype.c
Objects/typeobject.c: In function '_PyType_Lookup':
Objects/typeobject.c:2568: error: 'PyASCIIObject' undeclared (first use in this function)
Objects/typeobject.c:2568: error: (Each undeclared identifier is reported only once
Objects/typeobject.c:2568: error: for each function it appears in.)
Objects/typeobject.c:2568: error: expected expression before ')' token
*** [Objects/typeobject.o] Error code 1

New changeset 04424651f76c by Benjamin Peterson in branch '2.7':
fix hash member name (closes #22847)
https://hg.python.org/cpython/rev/04424651f76c

assignee: benjamin.peterson
versions: + Python 2.7
nosy: + benjamin.peterson, gregory.p.smith

messages: + msg259583
resolution: fixed -> (no value)

stage: resolved