[インデックス 10810] ファイルの概要

このコミットは、Goコンパイラのガベージコレクタ（gc）におけるエスケープ解析の改善に関するものです。特に、ラベルのループ深度解析をより正確に行うことで、インライン化によって発生する余分なラベルが引き起こすパフォーマンスの低下を防ぎます。これにより、strconv.ftoa（FormatFloatの内部処理）のメモリ割り当てカウントのテストが壊れる問題が解決され、全体的なエスケープ解析の精度が向上します。

コミット

commit 9bf3478658a781d38ab0a71bb027d781b8ade14b
Author: Luuk van Dijk <lvd@golang.org>
Date:   Thu Dec 15 17:35:59 2011 +0100

    gc: better loopdepth analysis for labels
    
    This avoids degraded performance caused by extra labels
    emitted by inlining (breaking strconv ftoa alloc count unittest) and is better in any case.
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/5483071

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/9bf3478658a781d38ab0a71bb027d781b8ade14b

元コミット内容

gc: better loopdepth analysis for labels

This avoids degraded performance caused by extra labels
emitted by inlining (breaking strconv ftoa alloc count unittest) and is better in any case.

変更の背景

Goコンパイラは、プログラムのパフォーマンスを最適化するために、エスケープ解析とインライン化という2つの重要な技術を使用します。

• エスケープ解析（Escape Analysis）: 変数がスタックに割り当てられるべきか、それともヒープに「エスケープ」してガベージコレクションの対象となるべきかを決定するコンパイル時最適化です。スタック割り当てはヒープ割り当てよりも高速で効率的であり、ガベージコレクションのオーバーヘッドを削減します。コンパイラの目標は、可能な限り多くの変数をスタックに割り当てることです。
• インライン化（Function Inlining）: 関数呼び出しのオーバーヘッドを排除し、さらなる最適化の機会を露出させるために、呼び出される関数の本体を呼び出しサイトに直接挿入するコンパイラ最適化です。

これらの最適化は通常、パフォーマンス向上に寄与しますが、相互作用によって予期せぬ問題が発生することがあります。このコミットの背景には、インライン化によって生成される「余分なラベル」が、エスケープ解析におけるループ深度の計算を誤らせ、結果としてパフォーマンスの低下を引き起こすという問題がありました。特に、strconv.FormatFloat（浮動小数点数を文字列に変換する関数）の内部処理であるftoaのメモリ割り当てカウントの単体テストが、この問題によって失敗していました。

strconv.FormatFloatのような関数は、新しい文字列を返すため、通常はメモリ割り当てが発生します。しかし、ループ内で頻繁に呼び出される場合、これらの割り当てがパフォーマンスのボトルネックになる可能性があります。エスケープ解析がループ深度を誤って判断すると、本来スタックに割り当てられるべき変数がヒープに割り当てられてしまい、ガベージコレクションの頻度が増加し、全体的な実行速度が低下します。

このコミットは、エスケープ解析がラベルをより正確に処理し、真のループを形成するラベルとそうでないラベルを区別することで、この問題を解決しようとしています。

前提知識の解説

Goコンパイラ (gc)

Go言語の公式コンパイラはgcと呼ばれ、Goのソースコードを機械語に変換する役割を担っています。gcは、エスケープ解析、インライン化、デッドコード削除など、様々な最適化をコンパイル時に行い、生成されるバイナリのパフォーマンスを向上させます。

エスケープ解析 (Escape Analysis)

エスケープ解析は、コンパイラが変数の生存期間を分析し、その変数がスタックに割り当てられるべきか、ヒープに割り当てられるべきかを決定するプロセスです。

• スタック割り当て: 関数が呼び出されるたびに、その関数のローカル変数や引数を格納するためのメモリ領域がスタック上に確保されます。関数が終了すると、この領域は自動的に解放されます。スタック割り当ては非常に高速で、ガベージコレクションのオーバーヘッドがありません。
• ヒープ割り当て: 変数が関数のスコープを超えて生存する必要がある場合（例：ポインタが関数から返される場合、クロージャでキャプチャされる場合など）、その変数はヒープに割り当てられます。ヒープに割り当てられたメモリは、ガベージコレクタによって管理され、不要になった時点で解放されます。ヒープ割り当てはスタック割り当てよりもコストが高く、ガベージコレクションの実行はプログラムの実行を一時停止させる可能性があります。

エスケープ解析の目的は、可能な限り多くの変数をスタックに割り当てることで、ヒープ割り当てとガベージコレクションの負荷を減らし、プログラムのパフォーマンスを向上させることです。

インライン化 (Inlining)

インライン化は、関数呼び出しのオーバーヘッド（引数のプッシュ、スタックフレームの作成、ジャンプ命令など）を削減するための最適化です。コンパイラは、小さな関数の場合、その関数のコードを呼び出し元に直接埋め込むことがあります。これにより、関数呼び出しのコストがなくなるだけでなく、インライン化されたコードに対してさらなる最適化（例：定数畳み込み、レジスタ割り当ての改善）が可能になることがあります。

インライン化はエスケープ解析に大きな影響を与えることがあります。関数がインライン化されると、そのローカル変数は呼び出し元の関数のスコープの一部となります。これにより、インライン化されなかった場合にはヒープにエスケープしていたであろう変数が、スタックに割り当てられるようになる可能性があります。

ループ深度 (Loop Depth)

エスケープ解析において、ループ深度は変数がループ内でどのように使用されるかを考慮するための情報です。ループ内で繰り返し割り当てられる変数は、その生存期間がループの反復に限定される場合、スタックに割り当てられる可能性があります。しかし、ループを抜けても生存する必要がある場合や、ループ内でヒープにエスケープするような操作が行われる場合、ヒープに割り当てられます。

このコミットでは、特にgoto文とラベルによって形成されるループの検出精度が問題となっていました。

strconv.FormatFloat とメモリ割り当て

strconv.FormatFloat関数は、float64型の数値を文字列に変換します。Goでは文字列は不変であり、FormatFloatが返す文字列は常に新しいメモリ割り当てを伴います。これは、FormatFloatが内部的にftoa（float to ASCII）のような関数を呼び出して数値の文字列表現を生成し、その結果を新しい文字列として返すためです。

ループ内でFormatFloatが頻繁に呼び出されると、大量の短い文字列が生成され、そのたびにヒープ割り当てが発生します。これにより、ガベージコレクションの頻度が増加し、パフォーマンスが低下する可能性があります。この問題を回避するためには、strconv.AppendFloatのように既存のバイトスライスに結果を追記する関数を使用することで、メモリ割り当てを削減できます。

このコミットで言及されている「strconv ftoa alloc count unittest」は、FormatFloatの内部処理が特定のメモリ割り当て回数を超えないことを検証するテストであったと考えられます。インライン化による余分なラベルがループ深度解析を誤らせ、不必要なヒープ割り当てを引き起こした結果、このテストが失敗したと推測されます。

技術的詳細

このコミットは、Goコンパイラのgcにおけるエスケープ解析のesc.cファイルに修正を加えています。主な変更点は、ラベルのループ深度解析を改善し、真のバックジャンプ（ループを形成するジャンプ）を持つラベルと、単なる前方ジャンプのターゲットであるラベルを区別することです。

以前の実装では、OLABEL（ラベルを表すノード）に遭遇すると、無条件にloopdepthをインクリメントしていました。これは、インライン化によって生成される余分なラベルが、実際にはループを形成しない場合でも、エスケープ解析が誤ってループ深度を増加させてしまう原因となっていました。その結果、変数が不必要にヒープにエスケープし、パフォーマンスが低下していました。

このコミットでは、以下の新しいアプローチが導入されています。

1. escloopdepthlist と escloopdepth 関数の導入:

   • これらの関数は、実際のesc関数が実行される前に、コードツリーを事前に走査します。
   • 目的は、各ラベルがバックジャンプのターゲットであるかどうかを判断することです。
   • OLABELノードに遭遇すると、そのラベルのシンボル（n->left->sym->label）に一時的に&nonloopingという特別なマーカーを設定します。これは、現時点ではそのラベルがループを形成しないと仮定していることを示します。
   • OGOTOノードに遭遇すると、そのジャンプ先のラベルのシンボルをチェックします。
     • もしジャンプ先のラベルが既に&nonloopingとマークされていれば、それはこのgotoがそのラベルへのバックジャンプであることを意味します（つまり、ラベルがgotoよりも前に定義されている）。この場合、ラベルのシンボルを&loopingという別のマーカーに更新し、そのラベルがループを形成することを示します。
     • もしジャンプ先のラベルが未初期化（nil）であれば、それは前方ジャンプであり、ループを形成しないと判断されます。

2. esc関数におけるOLABELの処理の変更:

   • 実際のesc関数がOLABELノードに遭遇した際、事前に設定されたラベルのシンボルをチェックします。
   • もしシンボルが&nonloopingであれば、そのラベルはループを形成しないため、loopdepthは増加させません。
   • もしシンボルが&loopingであれば、そのラベルはループを形成するため、loopdepthをインクリメントします。
   • 処理後、ラベルのシンボルはnilにリセットされます。

この変更により、エスケープ解析は、真にループを形成するラベル（バックジャンプのターゲットとなるラベル）に対してのみループ深度を増加させるようになります。これにより、インライン化によって生成される余分なラベルが誤ってループ深度を増加させることを防ぎ、より正確なエスケープ解析が可能になります。結果として、不必要なヒープ割り当てが減少し、パフォーマンスが向上します。

コアとなるコードの変更箇所

src/cmd/gc/esc.c

• 新しい関数の追加:
  • static void escloopdepthlist(NodeList *l);
  • static void escloopdepth(Node *n);
  • static Label looping;
  • static Label nonlooping; これらの関数と変数は、ラベルのループ深度を事前に分析するために導入されました。
• escfunc関数の変更:
  • escloopdepthlist(curfn->nbody); が esclist(curfn->nbody); の前に呼び出されるようになりました。これにより、エスケープ解析の前にループ深度の事前分析が行われます。
• escloopdepth関数の実装:
  • OLABELの場合、n->left->sym->labelを&nonloopingに設定します。
  • OGOTOの場合、ジャンプ先のラベルが&nonloopingであれば、&loopingに更新します。これはバックジャンプを検出するためです。
• esc関数におけるOLABELの処理の変更:
  • 以前は無条件にloopdepth++していましたが、n->left->sym->labelの値に基づいて条件付きでloopdepthを増加させるようになりました。
  • &nonloopingであればloopdepthは増加せず、&loopingであれば増加します。
  • 処理後、n->left->sym->labelはnilにリセットされます。

src/cmd/gc/fmt.c

• stmtfmt関数の変更:
  • OLABELのケースが追加され、ラベルのフォーマット方法が定義されました。これはデバッグ出力の改善のためと考えられます。
• opprec配列の変更:
  • OLABELがopprec配列に追加されました。これは、コンパイラがノードの優先順位を扱う際にOLABELを認識できるようにするためです。

test/escape2.go

• 新しいテストケースの追加:
  • func foo122(): 無害な前方ジャンプの例。new(int)がエスケープしないことを確認します。
  • func foo123(): バックジャンプ（ループを形成するジャンプ）の例。new(int)がエスケープすることを確認します。 これらのテストケースは、新しいループ深度解析が正しく機能し、前方ジャンプとバックジャンプを区別できることを検証するために追加されました。

コアとなるコードの解説

このコミットの核心は、src/cmd/gc/esc.cにおけるescloopdepth関数と、esc関数内のOLABEL処理の変更です。

escloopdepth関数

static void
escloopdepth(Node *n)
{
    if(n == N)
        return;

    escloopdepthlist(n->ninit);

    switch(n->op) {
    case OLABEL:
        if(!n->left || !n->left->sym)
            fatal("esc:label without label: %+N", n);
        // Walk will complain about this label being already defined, but that's not until
        // after escape analysis. in the future, maybe pull label & goto analysis out of walk and put before esc
        // if(n->left->sym->label != nil)
        //    fatal("escape analysis messed up analyzing label: %+N", n);
        n->left->sym->label = &nonlooping; // 初期状態では非ループと仮定
        break;
    case OGOTO:
        if(!n->left || !n->left->sym)
            fatal("esc:goto without label: %+N", n);
        // If we come past one that's uninitialized, this must be a (harmless) forward jump
        // but if it's set to nonlooping the label must have preceded this goto.
        if(n->left->sym->label == &nonlooping) // ジャンプ先が既に非ループとマークされていれば
            n->left->sym->label = &looping;    // それはバックジャンプなのでループとマーク
        break;
    }

    escloopdepth(n->left);
    escloopdepth(n->right);
    escloopdepthlist(n->list);
    escloopdepth(n->ntest);
    escloopdepth(n->nincr);
    escloopdepthlist(n->nbody);
    escloopdepthlist(n->nelse);
    escloopdepthlist(n->rlist);
}

この関数は、コードツリーを再帰的に走査し、OLABELとOGOTOノードを特別に処理します。

• OLABELの場合: ラベルノードに遭遇すると、そのラベルのシンボル（n->left->sym->label）を&nonloopingという特別なポインタに設定します。これは、現時点ではそのラベルがループを形成しないと仮定していることを示します。
• OGOTOの場合: gotoノードに遭遇すると、そのジャンプ先のラベルのシンボルをチェックします。もしジャンプ先のラベルが既に&nonloopingとマークされていれば、それはこのgotoがそのラベルへのバックジャンプであることを意味します（つまり、ラベルがgotoよりも前に定義されている）。この場合、ラベルのシンボルを&loopingという別のポインタに更新し、そのラベルがループを形成することを示します。もしジャンプ先のラベルがnilであれば、それは前方ジャンプであり、ループを形成しないと判断されます。

この事前走査によって、各ラベルが実際にループを形成するバックジャンプのターゲットであるかどうかの情報が、ラベルのシンボルに埋め込まれます。

esc関数におけるOLABELの処理

    case OLABEL:
        if(n->left->sym->label == &nonlooping) {
            if(debug['m'] > 1)
                print("%L:%N non-looping label\n", lineno, n);
        } else if(n->left->sym->label == &looping) {
            if(debug['m'] > 1)
                print("%L: %N looping label\n", lineno, n);
            loopdepth++; // ループを形成するラベルの場合のみloopdepthを増加
        }
        // See case OLABEL in escloopdepth above
        // else if(n->left->sym->label == nil)
        //    fatal("escape anaylysis missed or messed up a label: %+N", n);

        n->left->sym->label = nil; // 処理後、シンボルをリセット

実際のesc関数がOLABELノードに遭遇した際、escloopdepthによって設定されたラベルのシンボルをチェックします。

• もしシンボルが&nonloopingであれば、そのラベルはループを形成しないため、loopdepthは増加させません。
• もしシンボルが&loopingであれば、そのラベルはループを形成するため、loopdepthをインクリメントします。

この条件付きのloopdepth増加により、エスケープ解析は真にループを形成するラベルに対してのみループ深度を考慮するようになり、インライン化によって生成される余分なラベルが誤ってエスケープ解析に影響を与えることを防ぎます。

関連リンク

• https://golang.org/cl/5483071

参考にした情報源リンク

• Go Escape Analysis - goperf.dev
• Go: Escape Analysis - medium.com
• Go Escape Analysis - devgenius.io
• Go Escape Analysis - syntactic-sugar.dev
• Go: Inlining - seagin.me
• Go: Inlining - lemire.me
• Go: Inlining - medium.com
• Go: Inlining - withcodeexample.com
• Go 1.11 Release Notes - github.io
• Go: Escape Analysis and Inlining - go.dev
• strconv.FormatFloat - go.dev
• strconv.AppendFloat - golinuxcloud.com