Improve method cache efficiency

[pitrou]

BPO	22847
Nosy	@arigo, @rhettinger, @gpshead, @pitrou, @benjaminp, @serhiy-storchaka, @koobs
Files	methcache.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/benjaminp'
closed_at = <Date 2016-02-07.06:36:14.320>
created_at = <Date 2014-11-11.16:13:46.877>
labels = ['interpreter-core', 'performance']
title = 'Improve method cache efficiency'
updated_at = <Date 2016-02-07.06:36:14.318>
user = 'https://github.com/pitrou'

bugs.python.org fields:

activity = <Date 2016-02-07.06:36:14.318>
actor = 'python-dev'
assignee = 'benjamin.peterson'
closed = True
closed_date = <Date 2016-02-07.06:36:14.320>
closer = 'python-dev'
components = ['Interpreter Core']
creation = <Date 2014-11-11.16:13:46.877>
creator = 'pitrou'
dependencies = []
files = ['37176']
hgrepos = []
issue_num = 22847
keywords = ['patch']
message_count = 14.0
messages = ['231031', '231032', '231034', '231036', '231038', '231040', '231163', '231196', '231197', '259583', '259633', '259634', '259764', '259766']
nosy_count = 9.0
nosy_names = ['arigo', 'rhettinger', 'gregory.p.smith', 'pitrou', 'benjamin.peterson', 'Arfrever', 'python-dev', 'serhiy.storchaka', 'koobs']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue22847'
versions = ['Python 2.7', 'Python 3.5']

[pitrou]

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

[pitrou]

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.

[serhiy-storchaka]

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

[serhiy-storchaka]

FYI method cache optimization was added in bpo-1700288.

[pitrou]

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

[pitrou]

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.

[rhettinger]

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.

[python-dev]

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

[pitrou]

Now pushed. Thanks for the comments!

[gpshead]

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.