Title: Improve method cache efficiency
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.5, Python 2.7
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: benjamin.peterson Nosy List: Arfrever, arigo, benjamin.peterson, gregory.p.smith, koobs, pitrou, python-dev, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2014-11-11 16:13 by pitrou, last changed 2016-02-07 06:36 by python-dev. This issue is now closed.

File name Uploaded Description Edit
methcache.patch pitrou, 2014-11-11 16:13 review
Messages (14)
msg231031 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-11-11 16:13
The method cache is currently very small. Attached patch bumps the size a bit and improves the hash computation formula.
msg231032 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-11-11 16:19
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.
msg231034 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-11-11 17:41
Current hashing algorithm takes middle bits, proposed code takes low bits. Doesn't this make the hash worse?
msg231036 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2014-11-11 18:09
FYI method cache optimization was added in issue1700288.
msg231038 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-11-11 18:44
The low bits of the unicode hash should be as good as the middle bits.
msg231040 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-11-11 19:04
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.
msg231163 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2014-11-14 17:21
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.
msg231196 - (view) Author: Roundup Robot (python-dev) Date: 2014-11-15 00:35
New changeset 97dc64adb6fe by Antoine Pitrou in branch 'default':
Issue #22847: Improve method cache efficiency.
msg231197 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2014-11-15 00:55
Now pushed. Thanks for the comments!
msg259583 - (view) Author: Gregory P. Smith (gregory.p.smith) * (Python committer) Date: 2016-02-04 17:49
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.
msg259633 - (view) Author: Roundup Robot (python-dev) Date: 2016-02-05 06:23
New changeset 6357d851029d by Antoine Pitrou in branch '2.7':
Issue #22847: Improve method cache efficiency.
msg259634 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2016-02-05 06:24
I suppose we've backported scarier things.
msg259764 - (view) Author: Kubilay Kocak (koobs) Date: 2016-02-07 06:12
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
msg259766 - (view) Author: Roundup Robot (python-dev) Date: 2016-02-07 06:36
New changeset 04424651f76c by Benjamin Peterson in branch '2.7':
fix hash member name (closes #22847)
Date User Action Args
2016-02-07 06:36:14python-devsetstatus: open -> closed
resolution: fixed
messages: + msg259766
2016-02-07 06:27:19koobssetresolution: fixed -> (no value)
2016-02-07 06:12:33koobssetstatus: closed -> open
nosy: + koobs
messages: + msg259764

2016-02-05 06:24:08benjamin.petersonsetstatus: open -> closed
resolution: fixed
messages: + msg259634
2016-02-05 06:23:35python-devsetmessages: + msg259633
2016-02-04 17:49:23gregory.p.smithsetstatus: closed -> open

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

messages: + msg259583
resolution: fixed -> (no value)
2014-11-15 00:55:35pitrousetstatus: open -> closed
resolution: fixed
messages: + msg231197

stage: resolved
2014-11-15 00:35:12python-devsetnosy: + python-dev
messages: + msg231196
2014-11-15 00:16:05Arfreversetnosy: + Arfrever
2014-11-14 17:21:43rhettingersetnosy: + rhettinger
messages: + msg231163
2014-11-11 19:04:18pitrousetmessages: + msg231040
2014-11-11 18:44:31pitrousetmessages: + msg231038
2014-11-11 18:09:59serhiy.storchakasetnosy: + arigo
messages: + msg231036
2014-11-11 17:41:01serhiy.storchakasetmessages: + msg231034
2014-11-11 16:19:14pitrousetmessages: + msg231032
2014-11-11 16:13:46pitroucreate