Branch prediction design for Tier 2 (uops) interpreter #109039
Comments
11 tasks
7 tasks
gvanrossum
added a commit
that referenced
this issue
Sep 11, 2023
This adds a 16-bit inline cache entry to the conditional branch instructions POP_JUMP_IF_{FALSE,TRUE,NONE,NOT_NONE} and their instrumented variants, which is used to keep track of the branch direction.
Each time we encounter these instructions we shift the cache entry left by one and set the bottom bit to whether we jumped.
Then when it's time to translate such a branch to Tier 2 uops, we use the bit count from the cache entry to decided whether to continue translating the "didn't jump" branch or the "jumped" branch.
The counter is initialized to a pattern of alternating ones and zeros to avoid bias.
The .pyc file magic number is updated. There's a new test, some fixes for existing tests, and a few miscellaneous cleanups.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I'm splitting this topic off gh-106529, notably see this comment: #106529 (comment).
The design we've arrived at adds a "counter" to all branch (== conditional jump) instructions in Tier 1, i.e., to
POP_JUMP_IF_{TRUE,FALSE,NONE,NOT_NONE}. This counter is managed differently than most other counter cache entries. It should be initialized to a pattern of alternating ones and zeros. Whenever we execute a branch instruction, we shift the counter left by one position (losing the leftmost bit), and set the bottom bit to one if we jump, or zero if we don't.When we get to the point where we're constructing a superblock, we look at the cache entry, and decide which is the more likely branch based on the number of bits in the counter (
_Py_popcount32()). We then continue projecting along the more likely branch.We can even get fancy and predict a percentage of correct predictions, and multiply the percentages together as we project through branches, and stop projecting altogether if the probability gets too low. E.g. after two branches with 50%, the probability would be 25%, which is probably too low to bother, so we stop. OTOH after one branch with 80% and one with 25%, we multiply together 0.8 and 0.75 (!), giving 0.6, which is still likely enough to keep going.
Linked PRs
The text was updated successfully, but these errors were encountered: