Shrinking the inline caches

[markshannon]

Currently inline caches take up about two thirds of the space used by the bytecode.
We get good performance from inline caches, so obviously we want to keep them, but they could be smaller.

For hardware reasons caches must be a power-of-two size, which is a bit unfortunate as we often don't need that much data.

We should look into ways to reduce the amount of information needed in the cache to fit into a smaller power-of-two.
We can do that by merging two values into a single cache entry, or by accepting that some things won't get cached.

Some examples

Pointers

We currently store pointers as 64bit values. We could store pointers as 32bit offsets. That would prevent caching any pointers more than 2Gb away from the base pointer. For the vast majority of applications that should be a win, if we are caching objects created early like functions or classes.

Combining function version and minimum args in _PyCallCache

Currently we store the function version in 32 bits, where 26 bits should be enough. The minimum args is given 16 bits, when 6 bits is enough; functions with 64 or more parameters are extremely rare. 26 + 6 == 32.

LOAD_METHOD

The LOAD_METHOD instruction has a 20 byte cache.
We can reduce its size to 12 bytes by changing the pointer to an offset, ditching the LOAD_METHOD_WITH_DICT which is mostly ineffective and shrinking the cached keys version from 32 bits to 16 bits.

[markshannon]

We can further shrink the LOAD_METHOD cache by taking advantage of the fact that the cached keys on a class can never have keys deleted, only added. So, if it is the same size then it holds the same keys. The size fits into 5 bits.

[markshannon]

Another way to shrink the LOAD_METHOD cache is to change the object pointer cache to a single index into a per-class cache.

We probably don't want to use the global type cache, as we need to recheck the version, perform a redundant check on the name and handle misses due to collisions.
We could add a per-class array (either fixed or variably sized) that contains borrowed references to cached objects. No need for a mapping or to store the names, as we can do a linear search when specializing, and constant-time lookup when executing.
As usual, the cache would only be valid when the version numbers match.

If this is effective, we could claim back some memory by shrinking the global method cache.

[Fidget-Spinner]

Before shrinking the global method cache, we'd also need to ensure _PyType_Lookup doesn't slow down. That function is still really important for C-API method lookups.

If I understand you correctly, you're saying LOAD_METHOD will get the cached method from a per-class cache. Would _PyType_Lookup also search through that cache?

[gvanrossum]

How do we ensure that the borrowed references remain valid? (Especially in the light of all of the discussion about changes to refcounting.)

[markshannon]

They are borrowed references, so they are always invalid by themselves. It is only the combination of use and cache that may be valid.

The references are only valid at point of use if the type versions match, as that means there is a strong reference to the attribute in the class or one of its superclasses. The type cache used in _PyType_Lookup works this way.