為什麼這個爭議還沒結束#

是否該在 C 程式中使用 goto，一直都是工程師之間熱烈討論的話題。有人說使用 goto 會破壞程式結構，呼應 Edsger Dijkstra（艾茲赫爾·戴克斯特拉）著名的 “Go To Statement Considered Harmful”；也有人認為都有迴圈了，何必使用 goto？

但在大型 C 專案與虛擬機（VM）實作中，goto 仍然有它合理且高效的用法。本章從兩個典型場景說起：例外處理與 computed goto。

goto 於大型軟體專案的應用#

實務上，goto 出現在 C 語言專案時，大致用於下面兩個情境：

  • exception handling（例外處理）：方便開發者在 C 語言程式出錯時集中釋放動態分配的記憶體，或進行對應的錯誤處理，確保程式下次進入該函式時仍能正常工作。
  • computed goto：搭配 GCC 擴展，做高效率的 dispatch table。

商業化軟體的穩定性非常重要。以 2021 年 10 月初 Facebook 斷線為例，長達 6 小時的斷線連帶損失估計超過 9 億美元，由此可見可能發生的錯誤都不能被輕易放過。

例外處理用法常見於 Linux kernel 與大型 C 專案，模式類似：

int do_something(...) {
    if (!alloc_a()) goto err_a;
    if (!alloc_b()) goto err_b;
    if (!alloc_c()) goto err_c;
    return 0;

err_c:
    free_b();
err_b:
    free_a();
err_a:
    return -1;
}

集中、線性、易於閱讀，比層層 if 巢狀清爽得多。

computed goto：本章重點#

在前一章「淺談分支預測與 Hazards 議題」中，我們歸納出一個重點：如果分支預測失敗，會導致流水線中已經排序的指令被清除，處理器不止做了白工，還要把正確的指令填充回流水線上。

再談 branch prediction#

現代處理器引入的分支預測方法，會以指令的 address 為索引，檢索 Pattern History Table 上的歷史紀錄進一步做出預測。換句話說，預測精準度取決於每個分支點本身的歷史。

switch-based dispatcher 的痛點#

computed goto 適用於取代 switch case 為基底的 dispatcher。switch 在底層通常會編譯成「同一個分支點 + 跳轉表」，所有 case 共用一個跳轉指令：

while (1) {
    switch (code[pc++]) {
        case OP_HALT:
            return val;
        case OP_INC:
            val++;
            break;
        case OP_DEC:
            val--;
            break;
        case OP_MUL2:
            val *= 2;
            break;
        case OP_DIV2:
            val /= 2;
            break;
        case OP_ADD7:
            val += 7;
            break;
        case OP_NEG:
            val = -val;
            break;
        default:
            return val;
    }
}

問題在於：以現代 CPU 的分支預測方式來看，這段程式碼在不同週期可能會 jump 到不同的地方，導致分支預測的成功率下降，並且需要反覆把正確指令填充回流水線。

computed goto 怎麼做？#

int interp_cgoto(unsigned char* code, int initval) {

    static void* dispatch_table[] = {
        &&do_halt, &&do_inc, &&do_dec, &&do_mul2,
        &&do_div2, &&do_add7, &&do_neg};
    #define DISPATCH() goto *dispatch_table[code[pc++]]

    int pc = 0;
    int val = initval;

    DISPATCH();
    while (1) {
        do_halt:
            return val;
        do_inc:
            val++;
            DISPATCH();
        do_dec:
            val--;
            DISPATCH();
        do_mul2:
            val *= 2;
            DISPATCH();
        do_div2:
            val /= 2;
            DISPATCH();
        do_add7:
            val += 7;
            DISPATCH();
        do_neg:
            val = -val;
            DISPATCH();
    }
}

幾個重點：

  • 在 function 內宣告變數時加入 static 關鍵字，可以使該變數的生命週期延長至程式結束。
  • unary operator && 是 GCC 提供的擴展，搭配 label 可以取得明確的跳轉位址。
  • 配合 goto *ptr，可以讓程式根據 code[] 直接跳轉到對應的 handler。

在 C/C++ 中，在不同的地方使用 static 可能會帶來不同的效果，使用上需要特別注意！

為什麼會比較快#

關鍵在於：computed goto 把 jump 操作分散到每個 handler 末端，每個 DISPATCH() 都是一個獨立的間接跳轉點。如此一來：

  • 每個 handler 末端的跳轉點都有自己的歷史紀錄
  • 分支預測器更容易學到「執行 OP_INC 後常接 OP_MUL2」這類常見的指令序列特徵
  • 預測命中率上升，流水線被清空的次數下降

只要正確存取 dispatch table，處理器就能更精準地預測到正確的分支。

真實世界的例子#

知名軟體中採用 computed goto 的例子：

  • Ruby 1.9（YARV）：使用 computed goto
  • Dalvik（Android Java VM）：使用 computed goto
  • Lua 5.2：使用 switch（對比組）

此外，由 Jserv 老師主導開發的 rv32emu-next 同樣引入了 computed goto 的實作。

使用前請詳閱公開說明書#

由於 &&label 是 GCC 特別提供的擴展：

  • 如果你的 C 語言專案不是由 GCC 編譯，或是使用其他編譯器，就有可能造成錯誤。
  • 因此使用上可以考慮：
    • 寫好 Makefile，避免使用者超出預期的編譯方式
    • 對編譯器類別做偵測，若目標編譯器非 GCC 則 fallback 到 switch case

最後，可以在編譯時加入 -fno-gcse 與 -fno-crossjumping，讓 GCC 不要把多個 dispatch 點合併回單一跳轉，保留 computed goto 的效能優勢。

重點整理#

  • goto 並非萬惡之首，在「集中錯誤處理」與「VM dispatcher」這兩種場景反而是合理選擇。
  • computed goto 透過分散跳轉點，提升分支預測命中率，是直譯器/VM 內常見的最佳化手法。
  • 使用前確認編譯器支援與最佳化選項；要寫得可移植，記得保留 switch fallback 路徑。

原文出處#

  • 原書/iThome：https://ithelp.ithome.com.tw/articles/10283072
Backward 淺談分支預測與 Hazards 議題 IEEE-754 與浮點數運算 Forward