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

このコミットは、Goランタイムのメモリ管理における mcentral のアロケーション（割り当て）処理を高速化することを目的としています。具体的には、個々のオブジェクトのハンドリングを減らし、一度に提供可能なオブジェクトの量を予測することで、ボトルネックを解消し、全体的なパフォーマンスを向上させています。

コミット

commit d8626ef128bb5e9e13a8f8659481067f12dd23cc
Author: Sébastien Paolacci <sebastien.paolacci@gmail.com>
Date:   Fri Jan 18 16:39:22 2013 -0500

    runtime: faster mcentral alloc.
    
    Reduce individual object handling by anticipating how much of them are servable.
    
    Not a chunked transfer cache, but decent enough to make sure the bottleneck is not here.
    
    Mac OSX, median of 10 runs:
    
    benchmark                 old ns/op    new ns/op    delta
    BenchmarkBinaryTree17    5358937333   4892813012   -8.70%
    BenchmarkFannkuch11      3257752475   3315436116   +1.77%
    BenchmarkGobDecode         23277349     23001114   -1.19%
    BenchmarkGobEncode         14367327     14262925   -0.73%
    BenchmarkGzip             441045541    440451719   -0.13%
    BenchmarkGunzip           139117663    139622494   +0.36%
    BenchmarkJSONEncode        45715854     45687802   -0.06%
    BenchmarkJSONDecode       103949570    106530032   +2.48%
    BenchmarkMandelbrot200      4542462      4548290   +0.13%
    BenchmarkParse              7790558      7557540   -2.99%
    BenchmarkRevcomp          831436684    832510381   +0.13%
    BenchmarkTemplate         133789824    133007337   -0.58%
    
    benchmark                  old MB/s     new MB/s  speedup
    BenchmarkGobDecode            32.82        33.33    1.02x
    BenchmarkGobEncode            53.42        53.86    1.01x
    BenchmarkGzip                 43.70        44.01    1.01x
    BenchmarkGunzip              139.09       139.14    1.00x
    BenchmarkJSONEncode           42.69        42.56    1.00x
    BenchmarkJSONDecode           18.78        17.91    0.95x
    BenchmarkParse                 7.37         7.67    1.04x
    BenchmarkRevcomp             306.83       305.70    1.00x
    BenchmarkTemplate             14.57        14.56    1.00x
    
    R=rsc, dvyukov
    CC=golang-dev
    https://golang.org/cl/7005055

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

https://github.com/golang/go/commit/d8626ef128bb5e9e13a8f8659481067f12dd23cc

元コミット内容

runtime: faster mcentral alloc.

Reduce individual object handling by anticipating how much of them are servable.

Not a chunked transfer cache, but decent enough to make sure the bottleneck is not here.

Mac OSX, median of 10 runs:

benchmark                 old ns/op    new ns/op    delta
BenchmarkBinaryTree17    5358937333   4892813012   -8.70%
BenchmarkFannkuch11      3257752475   3315436116   +1.77%
BenchmarkGobDecode         23277349     23001114   -1.19%
BenchmarkGobEncode         14367327     14262925   -0.73%
BenchmarkGzip             441045541    440451719   -0.13%
BenchmarkGunzip           139117663    139622494   +0.36%
BenchmarkJSONEncode        45715854     45687802   -0.06%
BenchmarkJSONDecode       103949570    106530032   +2.48%
BenchmarkMandelbrot200      4542462      4548290   +0.13%
BenchmarkParse              7790558      7557540   -2.99%
BenchmarkRevcomp          831436684    832510381   +0.13%
BenchmarkTemplate         133789824    133007337   -0.58%

benchmark                  old MB/s     new MB/s  speedup
BenchmarkGobDecode            32.82        33.33    1.02x
BenchmarkGobEncode            53.42        53.86    1.01x
BenchmarkGzip                 43.70        44.01    1.01x
BenchmarkGunzip              139.09       139.14    1.00x
BenchmarkJSONEncode           42.69        42.56    1.00x
BenchmarkJSONDecode           18.78        17.91    0.95x
BenchmarkParse                 7.37         7.67    1.04x
BenchmarkRevcomp             306.83       305.70    1.00x
BenchmarkTemplate             14.57        14.56    1.00x

R=rsc, dvyukov
CC=golang-dev
https://golang.org/cl/7005055

変更の背景

Goランタイムのメモリ管理において、mcentral は重要な役割を担っています。mcentral は、異なるサイズのオブジェクトクラスに対応するメモリ領域（mspan）の中央フリーリストを管理するコンポーネントです。各プロセッサごとのキャッシュである mcache がローカルキャッシュを使い果たした際に、mcentral からメモリを要求します。

このコミットの背景には、mcentral におけるオブジェクトの割り当て処理がボトルネックとなっていたという問題があります。特に、個々のオブジェクトを一つずつ処理するオーバーヘッドがパフォーマンスに影響を与えていました。このコミットは、このボトルネックを解消し、より効率的なメモリ割り当てを実現することで、Goプログラム全体の実行速度を向上させることを目指しています。コミットメッセージに記載されているベンチマーク結果からも、特に BenchmarkBinaryTree17 などで顕著な改善が見られることから、この最適化が効果的であったことが伺えます。

前提知識の解説

Goのランタイムにおけるメモリ管理は、主に以下のコンポーネントによって構成されています。

• mspan (Memory Span): 連続したページ（通常は8KB）の集まりで、特定のサイズのオブジェクトを格納するために使用されます。mspan は、その中に含まれるオブジェクトのサイズクラス（例えば、8バイト、16バイトなど）によって分類されます。
• mcache (Memory Cache): 各ゴルーチン（またはP: Processor）にローカルに割り当てられるキャッシュです。ゴルーチンがメモリを割り当てる際、まず自身の mcache からメモリを要求します。これにより、ロックの競合を減らし、高速な割り当てを可能にします。mcache は、様々なサイズのオブジェクトに対応する mspan のリストを保持しています。
• mcentral (Memory Central): mcache が自身のローカルキャッシュを使い果たした際に、メモリを要求する中央のフリーリストです。mcentral は、mspan のリストを管理しており、まだ空きオブジェクトを持つ mspan のリスト（nonempty）と、完全に割り当て済みの mspan のリスト（empty）を保持しています。mcentral は、特定のサイズのオブジェクトクラスごとに存在します。
• mheap (Memory Heap): Goランタイムが管理するヒープ領域全体です。mheap は、mspan を mcentral に提供したり、大きなオブジェクトのために直接メモリを割り当てたりします。

メモリ割り当ての基本的な流れは以下のようになります。

1. ゴルーチンがメモリを要求すると、まず自身の mcache を確認します。
2. mcache に適切なサイズの空き mspan があれば、そこからオブジェクトが割り当てられます。
3. mcache に空き mspan がない場合、対応する mcentral に新しい mspan を要求します。
4. mcentral は、nonempty リストから空きのある mspan を mcache に提供します。
5. mcentral の nonempty リストが空の場合、mheap から新しい mspan を取得し、それを初期化して mcentral の nonempty リストに追加し、mcache に提供します。

このコミットは、特に mcentral から mcache へオブジェクトを割り当てる際の効率を改善することに焦点を当てています。

技術的詳細

このコミットの主要な最適化は、mcentral から複数のオブジェクトを割り当てる runtime·MCentral_AllocList 関数における処理の変更です。以前の実装では、MCentral_Alloc というヘルパー関数をループ内で呼び出し、一つずつオブジェクトを割り当てていました。これは、個々のオブジェクトごとにロックの取得と解放、およびリスト操作を行うため、オーバーヘッドが大きくなる可能性がありました。

新しい実装では、このアプローチが変更されています。

1. 利用可能なオブジェクト数の事前計算: MCentral_AllocList 関数内で、まず現在の mspan (s) が持つオブジェクトの総容量 (cap) と、まだ割り当てられていないオブジェクトの数 (avail) を計算します。そして、要求されたオブジェクト数 n と avail を比較し、実際に割り当て可能なオブジェクト数に n を調整します。これにより、ループの回数を事前に決定し、不要なイテレーションを避けることができます。
2. フリーリストの直接操作: s->freelist から直接 n 個のオブジェクトを連続して取得するように変更されています。以前のように MCentral_Alloc を繰り返し呼び出すのではなく、last = last->next; のようにポインタを辿ることで、一度のロック内で複数のオブジェクトを効率的に取得します。
3. MCentral_Alloc の削除: 個々のオブジェクトを割り当てるためのヘルパー関数 MCentral_Alloc が削除されました。これは、MCentral_AllocList 内でより効率的な一括割り当てロジックが導入されたため、その必要がなくなったことを意味します。
4. s->ref の更新: 割り当てられたオブジェクトの数 n を s->ref に加算することで、mspan 内の参照カウンタを正確に更新します。
5. mcentral の nfree の更新: c->nfree (中央フリーリストの総オブジェクト数) から割り当てられた n を減算します。
6. mspan の状態遷移の最適化: n == avail (要求された数だけオブジェクトを割り当て、かつそれが mspan 内の残りの全オブジェクトであった場合) の条件が追加され、この場合に mspan を nonempty リストから empty リストへ移動させる処理がより効率的に行われるようになりました。これにより、mspan が完全に使い果たされた際のリスト操作が最適化されます。

この変更により、mcentral からのオブジェクト割り当てがバッチ処理のようになり、特に多数の小さなオブジェクトが頻繁に割り当てられるようなシナリオで、ロックの競合や関数呼び出しのオーバーヘッドが削減され、パフォーマンスが向上します。

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

変更は src/pkg/runtime/mcentral.c ファイルに集中しています。

--- a/src/pkg/runtime/mcentral.c
+++ b/src/pkg/runtime/mcentral.c
@@ -34,12 +34,13 @@ runtime·MCentral_Init(MCentral *c, int32 sizeclass)
 // Allocate up to n objects from the central free list.
 // Return the number of objects allocated.
 // The objects are linked together by their first words.
-// On return, *pstart points at the first object and *pend at the last.
+// On return, *pstart points at the first object.
 int32
 runtime·MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
 {
-\tMLink *first, *last, *v;\n-\tint32 i;\n+\tMSpan *s;\n+\tMLink *first, *last;\n+\tint32 cap, avail, i;\n \n \truntime·lock(c);\n \t// Replenish central list if empty.\n@@ -50,41 +51,34 @@ runtime·MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
 \t\t\treturn 0;\n \t\t}\n \t}\n+\ts = c->nonempty.next;\n+\tcap = (s->npages << PageShift) / s->elemsize;\n+\tavail = cap - s->ref;\n+\tif(avail < n)\n+\t\tn = avail;\n \n-\t// Copy from list, up to n.\n \t// First one is guaranteed to work, because we just grew the list.\n-\tfirst = MCentral_Alloc(c);\n+\tfirst = s->freelist;\n \tlast = first;\n-\tfor(i=1; i<n && (v = MCentral_Alloc(c)) != nil; i++) {\n-\t\tlast->next = v;\n-\t\tlast = v;\n+\tfor(i=1; i<n; i++) {\n+\t\tlast = last->next;\n \t}\n+\ts->freelist = last->next;\n \tlast->next = nil;\n-\tc->nfree -= i;\n-\n-\truntime·unlock(c);\n-\t*pfirst = first;\n-\treturn i;\n-}\n+\ts->ref += n;\n+\tc->nfree -= n;\n \n-// Helper: allocate one object from the central free list.\n-static void*\n-MCentral_Alloc(MCentral *c)\n-{\n-\tMSpan *s;\n-\tMLink *v;\n-\n-\tif(runtime·MSpanList_IsEmpty(&c->nonempty))\n-\t\treturn nil;\n-\ts = c->nonempty.next;\n-\ts->ref++;\n-\tv = s->freelist;\n-\ts->freelist = v->next;\n-\tif(s->freelist == nil) {\n+\tif(n == avail) {\n+\t\tif(s->freelist != nil || s->ref != cap) {\n+\t\t\truntime·throw(\"invalid freelist\");\n+\t\t}\n \t\truntime·MSpanList_Remove(s);\n \t\truntime·MSpanList_Insert(&c->empty, s);\n \t}\n-\treturn v;\n+\n+\truntime·unlock(c);\n+\t*pfirst = first;\n+\treturn n;\n }

コアとなるコードの解説

変更の核心は runtime·MCentral_AllocList 関数にあります。

変更前:

int32
runtime·MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
{
    MLink *first, *last, *v;
    int32 i;

    runtime·lock(c);
    // ... (リストの補充ロジック) ...

    // Copy from list, up to n.
    // First one is guaranteed to work, because we just grew the list.
    first = MCentral_Alloc(c); // 1つ目を割り当て
    last = first;
    for(i=1; i<n && (v = MCentral_Alloc(c)) != nil; i++) { // 残りをループで1つずつ割り当て
        last->next = v;
        last = v;
    }
    last->next = nil;
    c->nfree -= i;

    runtime·unlock(c);
    *pfirst = first;
    return i;
}

// Helper: allocate one object from the central free list.
static void*
MCentral_Alloc(MCentral *c)
{
    MSpan *s;
    MLink *v;

    if(runtime·MSpanList_IsEmpty(&c->nonempty))
        return nil;
    s = c->nonempty.next;
    s->ref++; // 参照カウンタをインクリメント
    v = s->freelist; // フリーリストから1つ取得
    s->freelist = v->next; // フリーリストを更新
    if(s->freelist == nil) { // フリーリストが空になったら
        runtime·MSpanList_Remove(s);
        runtime·MSpanList_Insert(&c->empty, s); // emptyリストへ移動
    }
    return v;
}

変更前は、MCentral_Alloc 関数が個々のオブジェクトをフリーリストから取得し、mspan の参照カウンタを更新し、必要に応じて mspan を empty リストに移動させる役割を担っていました。MCentral_AllocList は、この MCentral_Alloc をループで n 回呼び出すことで、複数のオブジェクトを割り当てていました。

変更後:

int32
runtime·MCentral_AllocList(MCentral *c, int32 n, MLink **pfirst)
{
    MSpan *s;
    MLink *first, *last;
    int32 cap, avail, i;

    runtime·lock(c);
    // ... (リストの補充ロジック) ...

    s = c->nonempty.next; // 現在のmspanを取得
    cap = (s->npages << PageShift) / s->elemsize; // mspanの総容量
    avail = cap - s->ref; // 利用可能なオブジェクト数
    if(avail < n)
        n = avail; // 要求数を調整

    first = s->freelist; // フリーリストの先頭を取得
    last = first;
    for(i=1; i<n; i++) { // n個のオブジェクトをポインタを辿って取得
        last = last->next;
    }
    s->freelist = last->next; // フリーリストの先頭を更新
    last->next = nil; // 取得したリストの末尾をnilに設定
    s->ref += n; // 参照カウンタを一括更新
    c->nfree -= n; // 中央フリーリストの総オブジェクト数を一括更新

    if(n == avail) { // mspanが完全に使い果たされた場合
        if(s->freelist != nil || s->ref != cap) {
            runtime·throw("invalid freelist"); // エラーチェック
        }
        runtime·MSpanList_Remove(s);
        runtime·MSpanList_Insert(&c->empty, s); // emptyリストへ移動
    }

    runtime·unlock(c);
    *pfirst = first;
    return n; // 実際に割り当てたオブジェクト数を返す
}

// MCentral_Alloc 関数は削除された

変更後では、MCentral_Alloc 関数が削除され、そのロジックが runtime·MCentral_AllocList に統合されました。

• s = c->nonempty.next; で、現在利用可能な mspan を取得します。
• cap と avail を計算し、実際に割り当てるオブジェクト数 n を決定します。
• first = s->freelist; でフリーリストの先頭を取得し、for(i=1; i<n; i++) { last = last->next; } のループで、n 個のオブジェクトをポインタを辿って一括で取得します。これにより、ループ内で関数呼び出しやロックの取得・解放が不要になります。
• s->freelist = last->next; で、mspan のフリーリストの先頭を、取得したオブジェクトの次の要素に更新します。
• last->next = nil; で、取得したオブジェクトのリストの末尾を nil に設定し、独立したリンクリストとして扱えるようにします。
• s->ref += n; と c->nfree -= n; で、mspan の参照カウンタと中央フリーリストの総オブジェクト数を一括で更新します。
• if(n == avail) の条件で、mspan が完全に使い果たされた場合に、nonempty リストから empty リストへの移動を効率的に行います。

この変更により、mcentral からのオブジェクト割り当て処理が大幅に効率化され、特に多数の小さなオブジェクトを一度に割り当てる際のパフォーマンスが向上しました。

関連リンク

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

参考にした情報源リンク

• Go runtime mcentral allocation optimization CL 7005055 - Web Search Results
• The Go Memory Model - andrestc.com
• Go's Memory Allocator - medium.com
• Go runtime: improve mcentral scalability - github.com
• Go Memory Management - github.io
• Go's runtime memory allocator - go-language.org