摘要：我最近透過將直譯器從樹狀走訪直譯器改為位元組碼編譯器加上虛擬機器直譯器，大幅提升了 GoAWK 的速度。本文將說明它為何更快，以及新的直譯器如何運作。

更新：GoAWK 現在已原生支援 CSV 檔案。

幾年前我寫了 GoAWK，一個用 Go 撰寫的 AWK 直譯器，並寫了一篇文章說明它的運作原理、測試方式，以及我是如何讓它變得更快的。

GoAWK 一直是個有趣的 side project，而且至少被一個頗具規模的開源專案所採用，也就是 使用它的 Benthos 串流處理器。它甚至幫我拿到了現在在 Canonical 的工作。

GoAWK 之前使用的是樹狀走訪直譯器：要執行一個程式碼區塊時，它會遞迴地走訪已解析的語法樹。這種方式非常簡單，但速度並不快。我一直想改用位元組碼編譯器搭配虛擬機器直譯器，最近終於付諸實行了。

我早期的一個程式設計專案是 Third，一個給 DOS 用的 Forth 編譯器。大多數的 Forth 編譯器，包括 Third，都是使用一種位元組碼形式的簡單編譯器——在 Forth 的世界裡稱為直譯式程式碼（threaded code）。所以可以說，我對虛擬機器感興趣已經有 25 年了……這算是真正的 geek，還是只是老了呢？

為什麼虛擬機器比樹狀走訪更快？

為什麼編譯成虛擬指令、再用虛擬機器來執行，會比直接評估語法樹（「樹狀走訪」）更快，並不是那麼直觀。

實際上，前置作業反而更多：原本只需要做詞法分析和解析產生語法樹，現在還多了一個編譯步驟。不過，虛擬機器編譯器（包括 GoAWK 的）通常都非常簡單、也不做最佳化，所以這個步驟很快。

執行速度更快的原因之一是：RAM——也就是隨機存取記憶體（Random Access Memory）——在現代處理器上其實並非真正的隨機存取。記憶體區塊會依需求被載入到快速的 CPU 快取中，所以當你需要存取一個新的區塊時，花的時間會比已經在快取中的情況多上約 10 倍。Peter Norvig 在典型 CPU 上各種操作的耗時表格中顯示，從 L1 快取取值大約只需 0.5 奈秒，從 L2 快取取值則要多 14 倍，而從主記憶體取值又要再多 14 倍！

以此為前提來寫程式，被稱為「資料導向設計」。當我看到 Andrew Kelley 精彩的演講 A Practical Guide to Applying Data-Oriented Design 時，再次體會到這種設計帶來的巨大影響。Andrew 是 Zig 程式語言的創造者，他的演講描述了他如何透過應用資料導向設計技術大幅提升 Zig 編譯器的速度。這場演講促使我開始思考 GoAWK 的相關問題。但回到正題，為什麼虛擬機器會比樹狀走訪更快呢……

語法樹是由一堆指向其他節點的節點結構所組成。它們分散在記憶體各處，所以要評估子節點，就必須沿著指標在 RAM 中跳來跳去，很可能會把快取中原有的資料擠掉。

下圖是 GoAWK 中針對 print $1+$2 這個運算式所產生的語法樹，每個節點名稱上方以十六進位標示其記憶體位址：

PrintStmt 與 BinaryExpr 只相距 48 個位元組，但左邊的 FieldExpr 卻與後者相距 8KB，而它的 NumExpr 又與前者相距將近 120KB。快取區塊通常是 64 個位元組，所以每一個很可能都需要從主記憶體額外載入一個快取區塊。對快取一點也不友善。

使用虛擬機器直譯器時，指令位於一個漂亮的線性 opcode（操作碼）陣列中，很可能會一次就被載入到同一個快取區塊中。在 RAM 中跳來跳去的情況就少得多。以下是同一個程式在 GoAWK 虛擬機器中的指令樣貌（你可以用新增的除錯旗標 goawk -da 看到這種「組合語言清單」）：

$ echo 3 4 | goawk -da '{ print $1+$2 }'
        // { body }
0000    FieldInt 1
0002    FieldInt 2
0004    Add
0005    Print 1    // 1 is the number of values to print

7

GoAWK 編譯器所做的（相對少數的）最佳化之一就在這裡展現：當 $i 中的 i 是整數常數時，它會將其轉成單一的 FieldInt i 指令，而不是 Num i 加上 Field 的兩指令序列。這表示大多數的欄位查詢只需經過一次 opcode 解碼迴圈，而不是兩次。

虛擬機器做法更快的另一個原因，是因為函式呼叫更少，而函式呼叫相對較慢。在評估語法樹時，eval 函式會遞迴地再次呼叫 eval 來評估子節點。使用虛擬機器時，這一切都被攤平成單一的 opcode 陣列並用迴圈遍歷——分派 opcode 時不需要任何函式呼叫。

編譯器與虛擬機器的細節

GoAWK 的虛擬機器使用 32 位元的 opcode。一開始我打算使用 8 位元的 opcode（「bytecode」中的「byte」就是由此而來），但 32 位元的 opcode 一樣快，而且使用 32 位元就不需要可變長度的跳躍位移：較大的 AWK 腳本可能會需要超過 -128 到 +127 的跳躍位移，而沒有人會需要超過 32 位元所能提供的二十億位移量。64 位元的 opcode 則不必要地太大，而且速度也稍微慢一些。

以下是前 10 個 opcode（總共有 85 個——你可以在 internal/compiler/opcodes.go 看到完整清單）：

// Opcode represents a single virtual machine instruction (or argument).
// The comments beside each opcode show any arguments that instruction
// consumes.
type Opcode int32

const (
    Nop Opcode = iota

    // Stack operations
    Num // numIndex
    Str // strIndex
    Dupe
    Drop
    Swap

    // Fetch a field, variable, or array item
    Field
    FieldInt    // index
    Global      // index
    Local       // index
    ...
)

就像你在上面 print $1+$2 的組合語言清單中所看到的，我使用的是堆疊式虛擬機器。這種方式實作起來比較簡單，因為編譯器不需要處理暫存器配置，只需對堆疊進行 push 和 pop。堆疊式虛擬機器可能會稍微慢一些——像 Lua 這類非常快的虛擬機器是基於暫存器的。

GoAWK 的編譯器相當簡單，基本上是從語法樹到指令的直接轉換。我針對不同作用域的變數存取做了一些特化：例如，取得全域變數使用 Global 指令，取得區域變數則使用 Local。（如你所見，我的指令命名方式極具創意。）

以下是將 1 到 10 的數字加總的簡單程式的組合語言清單：

$ goawk -da 'BEGIN { for (i=1; i<=10; i++) sum += i; print sum }'
        // BEGIN
0000    Num 1 (0)
0002    AssignGlobal i
0004    Global i
0006    Num 10 (1)
0008    JumpGreater 0x0018
000a    Global i
000c    AugAssignGlobal AugOpAdd sum
000f    IncrGlobal 1 i
0012    Global i
0014    Num 10 (1)
0016    JumpLessOrEqual 0x000a
0018    Global sum
001a    Print 1

55

這裡展示了一個我從 Python 抄來的小巧最佳化，Python 的直譯器在 3.10 版中加入了它（不過我確定這不是什麼新點子）。要編譯 for 或 while 迴圈，最簡單的做法就是在頂端做測試，然後在迴圈底部使用無條件的 Jump。但這表示每次迴圈都要執行兩個跳躍指令：一個在頂端，一個在底部。

相反地，我們把條件編譯兩次：一次在迴圈前反向判斷（JumpGreater），一次在迴圈底部（JumpLessOrEqual）。整體程式碼會稍微多一點，因為條件被重複了，但迴圈本身——也就是關鍵所在——少了一個跳躍指令。

我們幾乎肯定可以進一步改進指令集，或許可以在事先知道運算型別時，為整數或字串加入專門的指令。不過這會增加複雜度，就目前而言我還是想保持簡單。

GoAWK 編譯器所做的另一項最佳化是針對指派。AWK 中的指派是運算式，所以預設情況下你會把它的值推到堆疊上……結果在大多數情況下又馬上丟棄掉。而你很少會用到指派運算式的值。

以下是一個經過最佳化的指派運算式的組合語言：

$ ./goawk -da 'BEGIN { x=42; print x }'
        // BEGIN
0000    Num 42 (0)
0002    AssignGlobal x
0004    Global x
0006    Print 1

42

而如果沒有這個最佳化，它看起來會像這樣：

0000    Num 42 (0)
0002    Dupe              # unnecessary
0003    AssignGlobal x
0005    Drop              # unnecessary
0006    Global x
0008    Print 1

下面是編譯陳述句的程式碼，展示了用於此最佳化的特例。我也一併附上我們如何編譯 if 陳述句，以展示截然不同的情況。請注意編譯器如何大量使用 Go 的 type switch：

func (c *compiler) stmt(stmt ast.Stmt) {
    switch s := stmt.(type) {
    case *ast.ExprStmt:
        // Optimize assignment expressions to avoid extra Dupe and Drop
        switch expr := s.Expr.(type) {
        case *ast.AssignExpr:
            c.expr(expr.Right)
            c.assign(expr.Left)
            return

        case *ast.IncrExpr:
            ... // similar optimization for i++ and i--

        case *ast.AugAssignExpr:
            ... // similar optimization for i+=2 (for example)
        }

        // Non-optimized ExprStmt: push value and then drop it
        c.expr(s.Expr)
        c.add(Drop)

    ...

    case *ast.IfStmt:
        if len(s.Else) == 0 {
            jumpOp := c.condition(s.Cond, true)
            ifMark := c.jumpForward(jumpOp)
            c.stmts(s.Body)
            c.patchForward(ifMark)
        } else {
            jumpOp := c.condition(s.Cond, true)
            ifMark := c.jumpForward(jumpOp)
            c.stmts(s.Body)
            elseMark := c.jumpForward(Jump)
            c.patchForward(ifMark)
            c.stmts(s.Else)
            c.patchForward(elseMark)
        }

    ...
    }
}

虛擬機器的 execute 函式是一個單一的 for 迴圈搭配一個大型的 switch 陳述句——每個 opcode 一個 case。以下是擷取指令以及處理其中幾個 opcode 的程式碼片段：

func (p *interp) execute(code []compiler.Opcode) error {
    for ip := 0; ip < len(code); {
        op := code[ip]
        ip++

        switch op {
        case compiler.Num:
            index := code[ip]
            ip++
            p.push(num(p.nums[index]))

        case compiler.Str:
            index := code[ip]
            ip++
            p.push(str(p.strs[index]))

        case compiler.Dupe:
            v := p.peekTop()
            p.push(v)

        ...

        case compiler.FieldInt:
            index := code[ip]
            ip++
            v, err := p.getField(int(index))
            if err != nil {
                return err
            }
            p.push(v)

        ...
        }
    }
}

Go 的 switch 陳述句

如上所示，虛擬機器被實作為一個大型的 switch 陳述句，每個 opcode 一個 case（大約有 80 個 case）。Go 的 switch 陳述句目前是以對「case 空間」進行二分搜尋的方式來實作的。你可以把它想成編譯成類似這樣的東西——為求簡潔，這裡只完整展示了樹狀結構中的少數幾個分支：

if op < 40 {
    if op < 20 {
        if op < 10 {
            if op < 5 {
                if op < 2 {
                    if op < 1 {
                        // handle opcode 0
                    } else {
                        // handle opcode 1
                    }
                } else {
                    // cases for opcodes 2-4
                }
            } else {
                // cases for opcodes 5-9
            }
        } else {
            // cases for opcodes 10-19
        }
    } else {
        // cases for opcodes 20-39
    }
} else {
    if op < 60 {
        // cases for opcodes 40-59
    } else {
        // cases for opcodes 60-79
    }
}

如你所見，你需要進行 O(log₂ N) 次比較與跳躍，才能找到你感興趣的 case。對於 80 個 opcode 來說，每解碼一個指令就要經過 6 到 7 個分支。

隨著指令數量的增加，分支數量也會跟著增加（不過幸好這種成長是對數性的，而非線性的）。當我最初為 GoAWK 寫出概念驗證的虛擬機器、只實作了展示所需的 7 或 8 個指令時，它帶來了巨大的效能提升，幾乎快了 40%，因為 switch 只有少數幾個 case。但現在我已經把所有 opcode 都補齊，速度就「只」快了 18%。

當我大約有 100 個 opcode 時，速度實際上比現在更慢。我移除了一些原本以為會加快速度的特化，但 opcode 變少後意味著少了一個二分搜尋的分支，結果平均反而快了 12%。

如果有一種方法能實現常數時間的指令分派，無論有多少指令都一樣，那就太好了。為什麼 Go 不能把 switch 實作為一個跳躍位址表：直接在表中查詢程式碼位址並跳過去呢？結果，Go 團隊的 Keith Randall 正在做這件事，所以我們可能會在 Go 1.19 中看到這個功能。

我在 GoAWK 上試用了 Keith 的分支（目前只支援 int64 型別），它讓一個簡單的微基準測試速度提升了 10%。所以我非常期待 Go 編譯器學會「跳躍表（jump table）」。

我們能自己做這個最佳化嗎？用函式陣列如何？我試過把分派迴圈改成以下形式：

func (p *interp) execute(code []compiler.Opcode) error {
    for ip := 0; ip < len(code); {
        op := code[ip]
        ip++

        n, err := vmFuncs[op](p, code, ip)
        if err != nil {
            return err
        }
        ip += n
    }
    return nil
}

// Type of function called for each instruction. Each function returns
// the number of arguments the instruction read from code[ip:].
type vmFunc func(p *interp, code []compiler.Opcode, ip int) (int, error)

var vmFuncs [compiler.EndOpcode]vmFunc

func init() {
    vmFuncs = [compiler.EndOpcode]vmFunc{
        compiler.Nop: vmNop,
        compiler.Num: vmNum,
        compiler.Str: vmStr,
        ...
    }
}

func vmNop(p *interp, code []compiler.Opcode, ip int) (int, error) {
    return 0, nil
}

func vmNum(p *interp, code []compiler.Opcode, ip int) (int, error) {
    index := code[ip]
    p.push(num(p.nums[index]))
    return 1, nil
}

func vmStr(p *interp, code []compiler.Opcode, ip int) (int, error) {
    index := code[ip]
    p.push(str(p.strs[index]))
    return 1, nil
}

這在 GoAWK 的微基準測試上只帶來了 1-2% 的速度提升（查看結果與程式碼）。最後我決定還是堅持使用較簡單的 switch 程式碼，另外再想其他提升速度的方法。而且當 Go 編譯器支援 switch 的跳躍表時，我什麼都不用做就能獲得 10% 的提升！

gcc 編譯器有一個稱為「computed goto（計算式 goto）」的非標準功能，它讓你可以在每個 opcode 的程式碼結尾寫類似 goto *dispatch_table[code[ip++]] 這樣的東西，直接跳到下一個 opcode 的程式碼。Eli Bendersky 寫了一篇關於 computed goto 的精彩文章，所以我就不在這裡多做贅述。大多數用 C 寫的虛擬機器都使用這種技巧，包括 CPython 以及許多其他專案。不幸的是 Go 沒有 computed goto，不過話說回來，當 switch 被編譯成跳躍表時，就已經算是完成一半了。

如果你對編譯器如何最佳化 switch 的學術性內容有興趣，可以閱讀 Roger Sayle 的論文「A Superoptimizer Analysis of Multiway Branch Code Generation [PDF]」，這篇論文發表於 2008 年的 GCC 開發者高峰會。

其他最佳化（以及一個反最佳化）

除了從樹狀走訪轉換為虛擬機器之外，我最近還加入了一些其他最佳化：

• 將導向至命令的輸出做緩衝，這讓重新導向的 print 速度提升了 10 倍。我當初在為 stdout 加入緩衝時，所有 print 輸出就已獲得類似的提升，但我當時漏掉了重新導向的版本。
• 只有在需要時才將數字字串轉為數值。以前我是急切地做轉換，現在只有在值需要在數值語境中使用時才轉換。這對那些將 $i 欄位當作字串使用的真實腳本有明顯的改善，不過它確實讓比較操作變慢了。它讓我一個相當貼近真實世界的文字計數腳本快了 40%。
• 我對 strings.TrimSpace 的最佳化被納入 Go 1.13，所以我得以在 GoAWK 要求至少 Go 1.13 後移除我自訂的 TrimSpace 版本。

一個有問題的修正是我將 GoAWK 的字串函式，例如 length() 和 substr()，改為使用 Unicode 字元索引而非位元組索引。我知道這會讓這些操作從 O(1) 變成 O(N)（N 為字串長度），但我以為影響不大，因為「N 通常很小」。

結果這個假設並不成立：Volodymyr Gubarkov 的 gron.awk 腳本在處理大型 JSON 檔案時，處理時間從 1 秒變成了超過 8 分鐘——意外地變成二次方複雜度。這實在無法接受，所以我決定暫時 revert 這個修正，未來再想辦法用 O(1) 的方式來處理。Gawk 的長期維護者 Arnold Robbins 也留言說明了 Gawk 為了讓字串處理更有效率所做的諸多努力。

我希望未來能進一步最佳化 GoAWK，並已開了一個統合議題（umbrella issue）來追蹤後續的效能工作。以下是一些想法：

虛擬機器的改進。 以下是一些我考慮用來加速虛擬機器的做法：

• 最佳化或減少堆疊操作。interp.push 方法特別慢，原因是其中的 append 檢查（而在一般的 AWK 程式中 append 幾乎從未需要）。如果你有關於如何事先判斷最大堆疊大小的好點子，請告訴我。在可能出現遞迴函式呼叫的情況下，這甚至可行嗎？
• 有沒有可以加入的專門 opcode，例如一個能在引數中直接推入整數常數的 Int 指令？加入 Int 可以省去對 interp.nums 切片的一次記憶體查詢。
• 想必 JumpLess 和類似的 opcode 並不常在字串上使用。是否應該將它們替換為 JumpLessNum，以避免至少對其中一個運算元做型別檢查？（對於字串，我們會使用較長的指令序列。）

字串串接也因為在串接超過兩個字串時過多的配置與複製而不必要地昂貴。目前像 first_name " " last_name 這樣的多重串接運算式會被編譯成兩個二元的 Concat 指令：

Global first_name
Str " "
Concat
Global last_name
Concat

讓編譯器偵測這種情況並輸出新的 Concat numArgs 指令會更有效率，例如：

Global first_name
Str " "
Global last_name
Concat 3

這少了一個指令，但更重要的是，它可以避免配置一個暫時字串，結果又得重新配置一個新的並複製位元組。串接超過兩個值在 AWK 中相當常見，而這個最佳化的效益會隨著串接的值越多而越大。

正規表示式也很適合加速。GoAWK 目前使用 Go 的 regexp 套件，但不幸的是它相當慢。這使得大量使用正規表示式的 AWK 腳本速度大約只有 Gawk 的一半，幾乎只有 Mawk 的四分之一。

有兩種方法可以改進：

1. 自己寫一個正規表示式引擎（可能會嘗試直接將 Mawk 的移植到 Go）。這大概需要花很多功夫，而且由於 Go 的邊界檢查和較少的編譯器最佳化，可能仍然不會很快。
2. 提升 Go 正規表示式引擎的速度。這無疑是更好的方法，因為所有使用 Go regexp 套件的人都會受益。這也很可能相當困難。我可能會把這件事留給比我更聰明的人——或許 這些議題中的一些會隨著時間被修復。

虛擬機器的成果

那麼，虛擬機器直譯器到底快了多少呢？微基準測試——坦白說其中大多數並不是你平常會用 AWK 寫的腳本——整體快了約 18%。這些是執行時間，所以數字越小越好（你可以在原始提交中看到，或使用 benchmark.sh 自行測量，再接著用 benchstat.sh 來顯示這些差異）：

name                    old time/op  new time/op  delta
NativeFunc-8            10.7µs ± 0%  10.8µs ± 0%   +0.67%
BuiltinGsub-8           16.2µs ± 0%  16.2µs ± 0%   +0.36%
BuiltinGsubAmpersand-8  16.2µs ± 0%  16.2µs ± 0%   +0.29%
BuiltinSub-8            13.6µs ± 0%  13.6µs ± 0%     ~   
BuiltinSubAmpersand-8   13.5µs ± 0%  13.6µs ± 0%     ~   
SimplePattern-8          133ns ± 1%   134ns ± 0%     ~   
ConcatLarge-8           8.43ms ± 1%  8.35ms ± 2%     ~   
BuiltinSplitRegex-8     87.9µs ± 0%  87.7µs ± 0%   -0.21%
BuiltinSplitSpace-8     35.4µs ± 0%  35.1µs ± 0%   -0.70%
GetField-8               445ns ± 1%   435ns ± 2%   -2.42%
FuncCall-8              2.84µs ± 0%  2.76µs ± 2%   -2.65%
BuiltinSprintf-8        9.67µs ± 0%  9.23µs ± 0%   -4.58%
RecursiveFunc-8         15.7µs ± 0%  14.9µs ± 0%   -4.95%
ConcatSmall-8            735ns ± 0%   691ns ± 1%   -5.98%
BuiltinMatch-8          2.91µs ± 0%  2.71µs ± 1%   -7.02%
BuiltinIndex-8          1.23µs ± 1%  1.11µs ± 1%   -9.51%
RegexMatch-8            1.24µs ± 1%  1.11µs ± 4%  -10.07%
SetField-8               905ns ± 0%   810ns ± 0%  -10.45%
ForInLoop-8             2.04µs ± 2%  1.78µs ± 4%  -12.86%
ArrayOperations-8        657ns ± 0%   565ns ± 0%  -13.94%
BinaryOperators-8        493ns ± 0%   413ns ± 0%  -16.15%
BuiltinSubstr-8          975ns ± 0%   765ns ± 0%  -21.50%
Comparisons-8            417ns ± 0%   321ns ± 0%  -22.98%
SimpleBuiltins-8        1.00µs ± 0%  0.75µs ± 0%  -25.61%
CondExpr-8               203ns ± 0%   151ns ± 0%  -25.62%
BuiltinLength-8          607ns ± 0%   429ns ± 0%  -29.34%
IfStatement-8            219ns ± 0%   152ns ± 0%  -30.65%
AugAssign-8             1.50µs ± 0%  0.98µs ± 0%  -34.74%
LocalVars-8              479ns ± 0%   300ns ± 2%  -37.32%
Assign-8                 446ns ± 0%   261ns ± 0%  -41.55%
ForLoop-8               4.34µs ± 0%  2.50µs ± 0%  -42.39%
GlobalVars-8             468ns ± 0%   269ns ± 1%  -42.48%
IncrDecr-8               448ns ± 0%   148ns ± 0%  -66.87%
[Geo mean]              2.36µs       1.94µs       -17.90%

遞增、遞減和複合指派之所以快這麼多，是因為虛擬機器為它們提供了專用的 opcode。變數存取也有了相當大的改進，for 迴圈、if 陳述句、二元運算子以及許多其他基準測試也是如此。

我更「貼近真實世界」的基準測試套件——其中大多數取自原始 AWK 原始碼——整體快了 13%。在這個表格中，goawk 是新的虛擬機器直譯器，orig 是舊的樹狀走訪版本。有些違反直覺的是，這裡的數字是它比原始 awk 快幾倍，所以數字越大越好。

結論

我確實很喜歡這次帶來的效能提升。雖然不如我期望的那麼多，但 GoAWK 現在在許多 CPU 密集的操作上比 Gawk 更快，這點相當不錯。它仍然永遠比不上追求極致效能的 Mawk。而對於 AWK 通常的用途——字串處理和正規表示式——GoAWK 仍有很大的改進空間。

老實說，我不確定這額外的 2500 行程式碼是否值得（對於一個包含測試在內只有 15,000 行程式碼的專案來說）。如果有工程主管在監督，我大概會遭到反對（「這對真實世界的工作負載有幫助嗎？」）。不過，GoAWK 自始至終都是一個熱情驅動的專案——我很享受製作與分享它的過程，這對我來說就足夠了。

我已經合併了編譯器與虛擬機器，並在 GoAWK v1.15.0 中發布。Go API 和 goawk 指令應該是 100% 向下相容的。它已經透過我的直譯器測試以及來自原始 AWK 和 Gawk 相關測試的充分驗證，但如果你發現任何問題，請提交一個 issue。

希望你喜歡或從這篇文章中有所收穫。歡迎隨時與我聯繫，提供你的回饋或想法。