Some form of inline cache for C API attribute/method loading

[Fidget-Spinner]

Watching Kevin's PyCon talk on modern code for interpreters made me learn that Python method/attribute loads are now faster in Python than in the C API.

All the CallMethod C API functions need to lookup the names of the methods. This is also the case for PyObject_GetAttr and attributes.

I wonder if we can implement some sort of "inline cache" infrastructure for C API attribute/method loads. The cache would behave similarly to the current _Py_ID macros and would mimic the behavior and logic of its LOAD_METHOD/LOAD_ATTR PEP 659 cousin. However, it would only specialize for one "form". Ideally, we should only use this at call sites where there's largely only one "specialization" form that is well known. The specialization will thus be simpler than the Python counterpart as we have much more information in C.

I plan to try this out for _PySys_GetAttr first because its basically just one form (LOAD_ATTR_MODULE). Following that we can then try methods because the majority of those are two forms.

My wishful thinking end goal is that eventually we can have something for the public C API to boost the performance of C extensions, rather than C extension authors having to rewrite large swathes of code. However, I think that's too far out there for now.

[brandtbucher]

One big difference is that the same C-API can have many diverse call sites, while the current bytecode caches are extremely localized. I'm not sure that there are typically many identical calls to PyObject_GetAttr all back-to-back, so a caching mechanism would likely either take two forms:

• Something like the current _PyType_Lookup cache that can "remember" more than one recent lookup.
• An alternate API/macro form where a static local cache is passed as part of the call:

static _PyAttrCache cache = {0};
attr = _PyObject_GetAttrCached(&cache, o, name);

I'm not sure I'm a huge fan of either option, since the first one adds a large-ish maintenance burden for every API we cache, and the second still requires C-extension authors to modify their code.

(I personally believe that code that makes heavy use of the Python object model (PyObject_GetAttr, PyObject_GetItem, etc...) from C code is probably better off being written in Python anyways. I cringe a bit every time I see somebody convert perfectly good Python code line-by-line to "Python-but-in-C" for speed alone.)

[Fidget-Spinner]

Yep I was thinking of form 2. Form 1 won't have any benefit over the current PyType_Lookup cache for most methods.

I have a suspicion that with form 2, any abstraction we do will become macro hell, but if it works it may be worth it.

Allowing C extensions to use this is probably a pipe dream. Even then if we just keep it to CPython only it'll pay for itself. There are many builtin functions that could use this. (E.g. just print has two call sites that can benefit from this)

[gvanrossum]

I dunno. I agree that neither option is that attractive, but as an API user I'd rather have the API automatically do the caching for me without me changing my code (not even recompiling, assuming it's in the stable ABI). I think this is what made _PyType_Lookup so successful (IIRC it didn't always have a cache, and I was pleasantly surprised when I discovered it had grown a cache while I was doing other stuff.)

[Fidget-Spinner]

I agree regarding neither option being attractive.

I quickly abandoned the idea of a _PyType_Lookup style cache because it's comparatively slower than the current inline cache. I also don't see how it'd be much faster in certain cases. Say for module attribute loads currently using _PyDict_GetItem(module, module_attr). In that case a lookup into a table is required. _PyType_Lookup effectively has to do the same. So it's a competition between who has the faster table implementation (I don't think it's easy to beat the one in Python :).

I hope I can shrink the change down to something minimally invasive like:

PyObject *file = CACHE_LOAD_ATTR_MODULE(tstate, &_Py_ID(stdout));

Then we can use it internally to boost performance of internal functions.

[gvanrossum]

Sure, give it a try. What would be in that macro?

[Fidget-Spinner]

Roughly:

def CACHE_LOAD_ATTR_MODULE(tstate, attr):
    interp_state = get_interp_state(tstate)
    # This works similarly to _Py_ID. We can auto generate these and attach them to interpreter state struct.
    _PyLoadAttrCache *cache = interp_state.inline_cache.__FILE__.__LINE__
    # Do LOAD_ATTR_MODULE things
    ...
    # on DEOPT, fall back to _PyDict_GetItem(module) and return that

[Fidget-Spinner]

Update: I tried it and it's not worth it. It's only a 5% improvement when I removed one lookup from print().

# main, no PGO, release build
python.exe -m timeit "print(end='')"
1000000 loops, best of 5: 233 nsec per loop
python.exe -m timeit "print(end='')"
1000000 loops, best of 5: 236 nsec per loop

# C API inline caching, no PGO, release build
python.exe -m timeit "print(end='')"
1000000 loops, best of 5: 221 nsec per loop
python.exe -m timeit "print(end='')"
1000000 loops, best of 5: 220 nsec per loop

Branch: https://github.com/Fidget-Spinner/cpython/tree/inca_capi

[brandtbucher]

To be fair, I’d be very surprised if looking up sys.stdout was the bottleneck for any print call. If we did implement this sort of caching, I don’t think this would be the best place to use it. Maybe the lookup of newlist.sort in sorted, but the time of that routine is likely bound by the actual sort (and there are better ways of performing that move anyways).

In fact, I don’t really see any good candidates in the builtins where this sort of caching would be a clear, meaningful win.

[Fidget-Spinner]

Yeap. That's why I'm abandoning this idea. It will probably net us at maximum a 5% win across the builtin functions. But at this rate, it might be better for us to wait for the interpreter to speed up, then implement these smaller functions in Python to make use of the specialization there (I remember Mark talking about this in another issue).

[ericsnowcurrently]

FYI, this got me thinking more generally about the C-API. I wrote up my thoughts in #410.

[kmod]

We did this sort of thing a bit in Pyston v1, though mechanically it worked a bit differently, where the runtime could invoke the jit. We did find some cases where it made sense, such as map() and sum(), but we didn't go too far with the idea.

[brandtbucher]

See also #131.

[kmod]

These functions are highly polymorphic so you would need something in addition to #131 to be useful beyond microbenchmarks