What information do we need to gather during "adaptive" interpretation?

[markshannon]

An optimizer of regions larger than a single instruction is going to want information about the values seen during prior execution.

What values should we gather?
What sort of API should we provide, so that optimizers don't need to probe the interpreter's internal data structures?

For which operations should we record the actual value, and for which should we record the class of that value?
This is fairly clear in most cases. E.g. we want the value for calls, but the types for binary operations.
What do we need to record that isn't obvious?

What other things should we record?
E.g. reference counts for binary operations (#380 (reply in thread))

We already gather quite a lot of information, but often in the form of version numbers, which makes it tricky to get the original value.
We could record the actual values, which would be expensive, or we could use the type cache to lookup types, which would be cheaper but probabilistic.

What information do Pyston and Cinder record?

@undingen
@kmod
@carljm
@DinoV

[This subject was brought several times up in #375 and #380]

[carljm]

We currently collect and use the type of every input (used stack element) of every bytecode. At the moment we don't collect specific objects at all.

[swtaarrs]

I haven't been in any of these discussions before but I work on Cinder with @carljm 👋 . I can add some context on how we handle this for our type specialization work in the JIT (which is mostly orthogonal to shadowcode, our version of an adaptive interpreter).

We have mildly concrete plans to collect specific object data in the future. In addition to values for calls like @markshannon mentioned, we'd also like to profile truthy/falsey singletons when they're operands to conditional branches (things like True, False, whether an int is zero or non-zero. None is already covered by the type profiling we have).

We also might profile the mortality of objects, although that isn't relevant to builds without immortalization support.

One factor that affects the type of profile data we can collect/use is that due to Instagram's deployment setup and forked worker model, we collect and use the data in different processes. The exact format we use is here, but for the moment it mostly boils down to "a bunch of type names, stored as strings".

[markshannon]

we'd also like to profile truthy/falsey singletons when they're operands to conditional branches

How useful is it to know the actual values seen in a conditional branch, rather than a history of which way the branch went (which can be kept in a small bit vector)?

[swtaarrs]

It's very useful for JIT specialization. If, for example, our profile data shows that the operand to a POP_JUMP_IF_FALSE is always a singleton like int(0), we can compile the whole instruction to a few cheap machine instructions:

1. Compare TOS with the fixed value of PyLong_FromLong(0).
2. If it's equal, jump to the bytecode target (which will often mean just falling through to the next machine instruction), otherwise deopt to the interpreter.

And I have a commit in progress to ensure that all small ints and other singletons are immortal, so in the fast path when we know TOS is int(0), we also know that we don't have to decref it when popping off the stack. I have no data to support this yet, but I suspect that enough optimizations like this could make immortalization a net win even on single-process workloads.

This does rely on small ints in a certain range being interned, but we're comfortable taking dependencies on straightforward implementation details like that for performance.

[markshannon]

I understand that you want to compile highly biased branches differently from unbiased branches. We will want to do the same.

But, are highly biased branches that aren't type tests and tests against None common enough to warrant the considerable extra overhead of tracking values rather than just the (one bit) direction?

My guess is the most common form is the implicit test against None, if x: where x is either an instance of an always truthy class, or None.

[swtaarrs]

are highly biased branches that aren't type tests and tests against None common enough to warrant the considerable extra overhead of tracking values rather than just the (one bit) direction?

We don't know yet, since we haven't collected the data. In our case, though, the overhead isn't that much: we're already profiling the types of all operands to most bytecode instructions, and expanding that to also profile certain values wouldn't be much more work.

We intend to collect some initial data on this in the next month or two, and the results of that will guide whether or not we actually implement anything in the JIT.