1 7 goto die? 那個 goto 到底能不能用啊? - ianchen0119/AwesomeCS GitHub Wiki

是否要在 C 程式中使用 goto,一直都是工程師之間熱烈討論的話題之一。有人說使用 goto 會破壞程式結構、也有人說都有迴圈了,何必使用 goto 呢?

goto 於大型軟體專案的應用

因為工作的關係,筆者最近閱讀了一個大型的 c 語言專案,並且碰巧讀到了 Computed goto for efficient dispatch tables 這篇文章,讓我對 goto 有了更深入的認知。 一般來說,goto 如果出現在 C 語言專案,那它有很大的可能是被應用在:

  • exception handling
  • computed goto

前者可以方便開發者在 C 語言程式出錯時回收動態分配的記憶體,或是進行對應的錯誤處理以確保程式下次進入該函式時仍可以正常工作。 試想,如果一家公司需要開發一個高效能的網路程式,並且要確保該程式可以穩定且持續的工作,這時在軟體中可能發生的錯誤都不能被輕易放過。

以 2021 年 10 月初 Facebook 斷線的例子來看,Facebook 因長達六小時的斷線,連帶損失估計超過 9 億美元,由此可見商業化軟體的穩定性是非常重要的。

至於後者 computed goto,才是筆者想要在本文與大家分享的重點!

computed goto

在先前的淺談分支預測與 Hazards 議題一文中,我們可以歸納出一個重點: 如果分支預測失敗,會導致流水線中已經排序的指令流被清除,這也就表示我們的處理器不止做了白工,還要把正確的指令填充回流水線上面。

再談 branch prediction

現代處理器可能引入如上圖所示的分支預測方法,處理器會以 address 為索引,檢索 Pattern history table 上的歷史紀錄進一步的做出預測。

computed goto 的應用

computed goto 適用於取代 switch case 為基底的 dispatcher,因為 switch 僅會以一個基底作為分派任務的參考,這樣子說可能會有點抽象,讓我們用程式碼來進一步了解這個概念:

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;
        }
    }

如果以現代處理器的分支預測方式來看,同一段程式碼在不同的週期可能會 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 關鍵字可以使變數的生命週期延長至程式結束

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

  • unary operator && 是 gcc 提供的擴展,它可以搭配 label 使用以取得明確的跳轉位址。
  • 配合 goto 可以讓程式訪問 code[] 的結果直接跳轉到它對應的操作。

這樣做的好處顯而易見,computed goto 把 jump 的操作分成了好幾部分,只要正確的訪問 dispatch table,我們的處理器就能更精準的預測到正確的分支。

真實世界的例子

Computed goto for efficient dispatch tables 一文有提到 computed goto 被應用到了哪些知名的軟體上:

  • Ruby 1.9 (YARV): also uses computed goto.
  • Dalvik (the Android Java VM): computed goto
  • Lua 5.2: uses a switch

此外,由 Jserv 老師主導開發的 rv32emu-next 同樣引入了 computed goto 的實作,詳細手法可參考:

使用前請詳閱公開說明書

由於 unary operator 是 gcc 特別提供的擴展,如果你的 C 語言專案不是由 gcc 編譯,或是有人下載了你的原始碼且採用其他編譯器進行編譯就有可能會造成錯誤。 因此,在使用時可以考慮:

  • 寫好 makefile,避免有使用者做出超出預期的行為
  • 針對編譯器類別做偵測,如果目標編譯器非 gcc,則使用一般的 switch case

最後,可以在編譯時加入 -fno-gcse-fno-crossjumping,讓 gcc 優化你的原始碼。

Reference