python / python/cpython

Use saturating counters for branch taken counters in `_POP_JUMP_IF_FALSE` and similar instructions.

未關閉
#151,499 1 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視

還沒有人認領這個 Issue。

interpreter-core performance topic-JIT
主要語言
Python
星號
77.2k
分支
36k
平均合併
1 天 9 小時
30 天內合併 PR
558

描述

Each conditional branch instruction contains a 16 bit field for recording the direction of the last 16 jumps.

    uint16_t *branches;
    uint16_t val = *branches;
    val = (val << 1) | direction;
    *branches =val;

This tells the direction of the last 16 branches.
When recording traces for the JIT, 16 branches is not a lot of information to guide region selection.

Instead, we could record the count of the two directions instead using a pair of saturating 8 bit counters.

    uint8_t branches[2];
    branches[direction] += (branches[direction] != 255);

Which is only one extra ALU instruction for most C compilers, and no extra memory accesses.

With a JIT warmup of up 500, we can get precise numbers of the branches taken.
With a warmup of a 1000, the saturating counters can still distinguish between branches that are rarely taken and those which are more balanced.

For example, if a branch switches direction every 20 times, the current counter might show a perfectly biased branch, but the saturating counter approach will show that the branch is roughly balanced.

貢獻指南

開啟貢獻指南

從這裡開始

  1. 先讀完整個 Issue,再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫,在一個分支上完成修改。
  4. 送出 Pull Request,並在描述裡引用這個 Issue 編號。

研究方向

_POP_JUMP_IF_FALSE 指令和類似的條件分支實作開始,接著追蹤它們的分支資料如何為 JIT 追蹤記錄。當方向計數使用兩個飽和計數器、上限為 255,並在不改變指令行為的情況下提供所提議的預熱資訊時,這項變更就完成了。

由索引模型根據 Issue 內容生成。

評估

技術堆疊
c, python
領域
compilers, performance
Issue 類型
功能
難度
4/5
預估耗時
3-5 天
活躍度
冷清
描述清晰度
基本清楚
新手友好度
48/100

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。