Armin's method cache optimization updated for Python 2.6

[bioinformed]

BPO	1700288
Nosy	@arigo, @birkenfeld, @rhettinger, @jcea, @amauryfa
Files	python26-classattrcache.diff fastattr_test.py

^{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 = None
closed_at = <Date 2009-01-15.18:54:51.780>
created_at = <Date 2007-04-13.19:16:08.000>
labels = ['interpreter-core']
title = "Armin's method cache optimization updated for Python 2.6"
updated_at = <Date 2009-01-15.18:54:51.745>
user = 'https://bugs.python.org/bioinformed'

bugs.python.org fields:

activity = <Date 2009-01-15.18:54:51.745>
actor = 'collinwinter'
assignee = 'none'
closed = True
closed_date = <Date 2009-01-15.18:54:51.780>
closer = 'collinwinter'
components = ['Interpreter Core']
creation = <Date 2007-04-13.19:16:08.000>
creator = 'bioinformed'
dependencies = []
files = ['7940', '8887']
hgrepos = []
issue_num = 1700288
keywords = ['patch']
message_count = 23.0
messages = ['52431', '52432', '52433', '52434', '52435', '52436', '52437', '52438', '52439', '52440', '52441', '58262', '58263', '58932', '59818', '59854', '59855', '59857', '59874', '59875', '59876', '59881', '79912']
nosy_count = 11.0
nosy_names = ['nnorwitz', 'arigo', 'georg.brandl', 'collinwinter', 'rhettinger', 'jcea', 'amaury.forgeotdarc', 'peaker', 'bioinformed', 'jyasskin', 'ntoronto']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue1700288'
versions = ['Python 2.6']

[bioinformed]

I've forward ported and slightly cleaned up Armin's method cache patch (see bpo-1685986). I've attempted to clarify and tighten up several loose ends in the code, so hopefully I haven't mucked anything up.

My performance results are not quite as good as Armin's, though still very encouraging. I see a typical speed up of 10%, with heavily object oriented application code seeing speedups of 15-20%. Given these rather significant results, the major task is to verify correctness.

[nnorwitz]

I tried this test on parrotbench (b0.py in particular) and I'm not sure I could distinguish an improvement over the noise (best case was about 5%). The variability is pretty high on my box (dual amd64 opertons, ubuntu gcc 4.1.2-ish). At first it seemed a bit slower with the original patch which uses unsigned ints. I tried changing to unsigned longs. It seemed a little better, though not sure if it was really due to the change. I think unsigned longs should be used for 64-bit boxes.

Did you use a benchmark/program that is open source? I don't know that I have anything decent to test this with. Raymond probably does though. Also what platform did you test on?

[bioinformed]

I benchmarked using pystone, pybench, and a bunch of my local scientific applications that have tight computational kernels still in pure Python. I tested on a 64bit Linux box, defining the version_tag as either int or unsigned long with no appreciable difference in performance. I'm trying to get parrotbench to run, but it doesn't seem to have been updated for modern Python versions.

[arigo]

A further minor improvement could be achieved by
re-doing the inlining of _PyType_Lookup() in
object.c. Ideally, the fast path only could be
inlined, and the rest put in a separate function
or just using _PyType_Lookup().

[bioinformed]

I tried re-inlining the fast path from _PyType_Lookup() in object.c and found no measurable improvement on the simple benchmarks I tried. I've also stress-tested the patch by disabling the fast-path return, always performing the slow-path lookup, and asserting that the cached result matches the slow-path result. I then ran that modified interpreter on the Python test-suite, various benchmarks, and a range of my own applications. While not a formal proof of correctness, it was encouraging that the cache remained consistent.

[peaker]

Why is CPython copying functions to inline them?

This is not only code duplication that makes the code easy to break, it also bloats the caller function beyond readability.

I believe that using a private .c #include file with an inline keyword, or at worst, #include the function code directly is a better solution.

Is there any reason to use the method currently used by CPython?

[bioinformed]

First off, all versions of this patch do away with the rather aggressively repeated inline code. My previous comment about refactoring and testing an inlined form were purely an experiment with null results.

That aside, you do raise a good question. However, given the current patch, it is unfortunately off-topic and irrelevant to the consideration of this patch. Please feel free to pursue it elsewhere, since I worry that it will only serve as a negative distraction from the much more interesting aims of the mro optimization. Since you are clearly worried about the performance of attribute lookup, please try it out and report your findings. I'll be happy review the results from your benchmarks and any suggestions you have.

[rhettinger]

FWIW, I'm still reviewing this code.

[peaker]

I may be missing something trivial here, but why the cache global - and not per-typeobject?

As I saw it - the mro cache was supposed to be a mapping of (type,name)->(descriptor/classattr) that's based on the __mro__ of type, and all of the dicts in type and its bases.

I think the right way to do it is to use another Pythonic dict object in each type, that holds this cache (name->(descriptor/classattr)).
This cache dict should essentially be equivalent to a merge of all the dicts in the mro. and gets updated whenever any of the dicts of the types in the mro gets updated.
Not sure why to re-implement a fast-hashtable when one already exists.
Also - once it is associated with the type - it does not hold any references to any names that are not already referenced by someone in the type hierarchy, so there are no mm/gc issues either.

Am I missing something here?

[bioinformed]

The cache is global to make it fast, have a deterministic and low memory footprint, and be easy to invalidate. It is distinct from the standard Python dict implementation since it need not be as general nor fully associative, as cache collisions are not subject to re-probing. Neither does it even go through the motions of memory management, which would be rather hard to get the standard dict implementation to emulate. It is kept drastically minimal in the interests of performance and goes to great pains to hide and minimize the impact to the rest of the interpreter. In this regard it seems quite successful, as it even removes the need for the manually inlined code you commented on before. It also survives harsh stress-testing and presents no detectable performance regressions in any of my benchmarks (to the contrary, many operations are significantly faster).

While a per-type-object cache sounds feasible, it is hard for me to see how it could be as efficient in the general case -- for one, the dict look up fast path is just so much heavier. Please feel free to take that as a challenge to produce a patch that contradicts my intuition.

[arigo]

peaker: we tried several approaches (including ones similar to what you describe) in PyPy, and the one in this patch is the one that worked best there. There is of course no guarantee that the same experiments would have given exactly the same results in CPython, so feel free to try them all again - I won't :-)