LOAD_METHOD_WITH_DICT misses in bm_go

[sweeneyde]

99.7% of LOAD_METHOD_WITH_DICT instructions deoptimize in bm_go. All bm_go stats are here. Some LOAD_METHOD_WITH_DICT stats by benchmark are here.

It seems bm_chaos, bm_regex_compile, and bm_sympy make good use of this opcode, while bm_2to3, bm_go, and bm_tornado_http all have miss rates of 95% or more. Most others benchmarks have a miss rate of 16-17%, presumably from pyperf/pyperformance overhead.

Most of the bm_go deoptimization seems to occur at the following line in ceval.c (the last DEOPT_IF):

DEOPT_IF(dict->ma_keys->dk_version != read_u32(cache->keys_version), LOAD_METHOD);

From what I've gathered, most of the misses occur when loading the method Square.find, and Square instances get assigned extra attributes after __init__ finishes. This maybe gives some insight into why the miss rate is what it is, but I don't know if there's any way to improve this. Is there some way to be more particular at specialization time?

I wonder if there's any benefit to adding a more dynamic ADAPTIVE_CACHE_BACKOFF. Instead of one _Py_CODEUNIT that always starts at 64, there could be two uint8_t, one for the current counter and another for a counter start value that starts small (11 or something?) and then gets incremented at every miss, with a cap at 255.

[sweeneyde]

I tried that change and measure the stats before and after. Some miss percentages went down significantly (e.g. 36.9% --> 22.9%), others increased a bit.

[brandtbucher]

I wonder if there's any benefit to adding a more dynamic ADAPTIVE_CACHE_BACKOFF. Instead of one _Py_CODEUNIT that always starts at 64, there could be two uint8_t, one for the current counter and another for a counter start value that starts small (11 or something?) and then gets incremented at every miss, with a cap at 255.

@markshannon has been discussing something similar offline. His design uses "exponential backoff" instead.

As I understand it, we would use 4 bits of the counter as an exponent, and the other 12 as the counter value. Each time we un-specialize (or a fail to specialize) and convert back to the adaptive form, we increment the exponent. Then we treat the maximum counter value as 2 ** exponent.

So each time we convert back to the adaptive form, we cut the amount of churn in half.

[Fidget-Spinner]

I'm a little lost. If you're referring to the part where it dynamically sets reference in bm_go, that seems like a slight anti-pattern. The code should set it to None in __init__. PyCharm usually complains if you modify a variable that wasn't initialised in __init__, but I'm not too sure about other linters.

Then again, this pattern happens in the real-world, so I can't just dismiss it :). In this case shouldn't it de-optimize immediately and not bother specializing again? Seems like Cinder possibly does that.

[markshannon]

Yes, bm_go is particularly bad for LOAD_METHOD, as it creates a lot of objects for a class, before fully initializing any of them.
Each instance then gets its own unshared keys with different version.

Having said that, it still performs well and the misses are a very small fraction of the overall instruction count.

Exponential back off would be nice, but we don't want to back off for low miss rates.
Without a hit counter, we don't what the miss rate is, we just know the absolute number of misses.

One scheme would be to increment the exponent every time we fail to specialize and reduce (down to the minimum) when we specialize successfully. The problem is that we keep succeeding here, and then missing because different object have different keys.

Which makes me wonder, why does LOAD_METHOD_WITH_DICT work at all?
We would expect LOAD_METHOD for regular instances to be specialized to LOAD_METHOD_WITH_VALUES or LOAD_METHOD_NO_DICT. Given that LOAD_METHOD_WITH_DICT is for irregular instances each of which will have differing dict-keys, how does it work at all?

[markshannon]

Hmm, is LOAD_METHOD_WITH_DICT effective for objects with a split keys dict, where the shared keys is the same as that cached on the class? And ineffective in all other cases?

Should be easy to test, just add a check when specializing that obj->dict->keys == obj->class->shared_keys

[brandtbucher]

Hmm, is LOAD_METHOD_WITH_DICT effective for objects with a split keys dict, where the shared keys is the same as that cached on the class? And ineffective in all other cases?

We handle two different cases here, right? 0 < tp_dictoffset, and managed dictionaries. Do the former ever share keys? I don't know off the top of my head.

Separately, I wonder if the first case is really common enough to specialize for? We could shrink this huge cache by one slot and clean things up a bit if it turns out it's not. (We could also just split this into two specializations, and stop caching the value that way.)

[sweeneyde]

It seems one fundamental issue is that it's hard to tell based on one call to _Py_Specialize_LoadMethod whether or not the keys version will be stable.

So can we base the decision on two consecutive calls? If it gets to the point where it's possible to specialize to LOAD_METHOD_WITH_DICT, we could store all the appropriate cache data, but not actually change the opcode. Then on the next call to _Py_Specialize_LoadMethod where it's possible to do so, check whether the data matches, and if so, actually change the opcode this time.

I'm not sure how much faster the adaptive opcode is than the DEOPT_IF path, but since the DEOPT_IF in question is rather late in the opcode, it might be worth it. But then again, maybe shrinking the cache is more worth it.

[markshannon]

I'm puzzled as to how LOAD_METHOD_DICT works at all.
For it to work, the following must be true:

1. The object must have a dictionary
2. The dict's keys' version must be the same as the object specialized for.

This can only happen if either:

1. The object has managed dict/values and the object's __dict__ has been accessed, forcing creating of the object's dictionary, or
2. The object is exactly same one as specialized for.

Case 1 seems highly unlikely, so maybe we are seeing case 2 in the benchmarks where this works.

If we were to allow shared-key dicts for non-managed classes (which might make sense) then LOAD_METHOD_DICT might be more useful.

[brandtbucher]

This could also happen for a bunch of objects that all have an empty __dict__ too, right? They would all share the empty keys, in that case.

[markshannon]

I would expect them to mainly share the class cached keys (which would be empty, but not the same as the common empty keys), or for the dict to not exist at all. Dicts are lazily allocated for a lot of objects.

I am guessing here, I don't have any data.