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

このコミットは、Goランタイムにおけるスライス（slice）の拡張（grow）メカニズムと、文字列（string）からバイトスライス（[]byte）への変換処理を最適化するものです。具体的には、メモリ割り当ての際に、要求されたサイズだけでなく、実際に割り当てられるメモリブロックのサイズを考慮に入れることで、メモリの利用効率とパフォーマンスを向上させています。これにより、特にappend操作や文字列変換における不要な再割り当てやコピーが削減され、ベンチマーク結果にも顕著な改善が見られます。

コミット

commit bace9523eed9bc695310cd327b19ecdf7aa44612
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Mon Jan 27 15:11:12 2014 +0400

    runtime: smarter slice grow
    When growing slice take into account size of the allocated memory block.
    Also apply the same optimization to string->[]byte conversion.
    Fixes #6307.
    
    benchmark                    old ns/op    new ns/op    delta
    BenchmarkAppendGrowByte        4541036      4434108   -2.35%
    BenchmarkAppendGrowString     59885673     44813604  -25.17%
    
    LGTM=khr
    R=khr
    CC=golang-codereviews, iant, rsc
    https://golang.org/cl/53340044

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

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

元コミット内容

このコミットは、Goランタイムにおけるスライスの拡張ロジックを改善し、より賢くメモリを割り当てるようにします。具体的には、スライスを拡張する際に、要求されたサイズだけでなく、実際にメモリマネージャが割り当てるメモリブロックのサイズを考慮に入れます。この最適化は、文字列からバイトスライスへの変換処理にも適用されます。

この変更は、Issue #6307 を修正するものであり、以下のベンチマーク結果が示すように、特に文字列関連の操作において大幅なパフォーマンス改善をもたらしています。

• BenchmarkAppendGrowByte: 2.35%の改善
• BenchmarkAppendGrowString: 25.17%の改善

変更の背景

Goのスライスは、動的な配列のようなデータ構造であり、要素を追加する際に容量が不足すると、より大きな新しい配列を割り当てて既存の要素をコピーするという「拡張（grow）」処理が行われます。この拡張処理は、Goプログラムのパフォーマンスに大きな影響を与える可能性があります。

従来のGoランタイムでは、スライスを拡張する際に、新しい容量を計算する際に「要求された要素数」に基づいていました。しかし、Goのメモリマネージャ（GC）は、メモリを割り当てる際に、要求された正確なバイト数ではなく、特定の「サイズクラス」に丸められたブロック単位でメモリを割り当てます。例えば、100バイトを要求しても、実際には128バイトのブロックが割り当てられることがあります。

このミスマッチにより、スライスが拡張されるたびに、実際に割り当てられたメモリブロックにはまだ未使用の領域があるにもかかわらず、論理的な容量が不足したと判断され、不必要な再割り当てとデータコピーが発生する可能性がありました。これは特に、小さな要素を頻繁に追加するようなシナリオでパフォーマンスのボトルネックとなっていました。

Issue #6307 は、この非効率性を指摘し、スライスの拡張ロジックを改善する必要があることを示していました。このコミットは、この問題に対処し、メモリマネージャが実際に割り当てるメモリブロックのサイズを考慮に入れることで、より効率的なメモリ利用とパフォーマンス向上を実現することを目的としています。同様の最適化は、文字列からバイトスライスへの変換時にも適用され、関連するパフォーマンス問題も解決しています。

前提知識の解説

このコミットの理解には、以下のGoの概念とランタイムの内部動作に関する知識が役立ちます。

1. Goのスライス (Slice): Goのスライスは、配列をラップしたデータ構造で、ptr（基底配列へのポインタ）、len（現在の要素数）、cap（基底配列の容量）の3つのフィールドを持ちます。append関数などで要素を追加し、lenがcapを超えると、Goランタイムはより大きな容量を持つ新しい基底配列を割り当て、既存の要素をコピーしてから新しい要素を追加します。この「拡張」の際に、新しい容量は通常、現在の容量の2倍（または1.25倍）に設定されますが、このコミットではその計算に加えて、実際に割り当てられるメモリブロックのサイズも考慮するようになります。

2. Goのメモリ割り当て (Memory Allocation): Goのランタイムは、独自のメモリマネージャ（GC）を持っています。メモリは、ヒープ上に「mspan」と呼ばれる連続したメモリブロックの単位で管理されます。mspanは、特定のサイズのオブジェクトを格納するために最適化された「サイズクラス」に分類されます。例えば、8バイトのオブジェクト用、16バイトのオブジェクト用など、様々なサイズクラスがあります。mallocgc関数は、Goランタイムがヒープからメモリを割り当てる際に使用する内部関数です。この関数は、要求されたサイズに最も適したサイズクラスのmspanからメモリブロックを割り当てます。この際、要求されたサイズよりも大きなブロックが割り当てられることがあります。

3. append関数: Goの組み込み関数であるappendは、スライスに要素を追加するために使用されます。appendは、スライスの容量が不足している場合、新しい基底配列を割り当ててデータをコピーし、その新しいスライスを返します。このコミットは、この内部的な容量拡張ロジックを改善します。

4. 文字列 (String) とバイトスライス ([]byte) の変換: Goの文字列はイミュータブルなバイトのシーケンスです。文字列からバイトスライスへの変換（例: []byte(myString)）は、文字列のバイトデータを新しいバイトスライスにコピーする操作を伴います。この際にも、新しいバイトスライスのためのメモリ割り当てが発生するため、スライスの拡張と同様の最適化が適用されます。

5. runtime·roundupsize関数: このコミットで導入または変更される重要な内部関数です。これは、要求されたバイト数に対して、Goのメモリマネージャが実際に割り当てるメモリブロックのサイズ（最も近いサイズクラスのサイズ）を返す役割を担います。この関数を使用することで、ランタイムは「論理的な容量」だけでなく「物理的に割り当てられる容量」を考慮に入れることができるようになります。

技術的詳細

このコミットの核心は、Goランタイムのメモリ割り当て戦略とスライスの容量拡張ロジックの間の連携を強化することにあります。

runtime·roundupsize関数の導入/改善

最も重要な変更は、src/pkg/runtime/msize.c に runtime·roundupsize(uintptr size) 関数が追加（または既存のロジックが改善）されたことです。この関数は、mallocgcがsizeバイトを要求された場合に実際に割り当てるメモリブロックのサイズを返します。

Goのメモリマネージャは、メモリを「サイズクラス」と呼ばれる固定サイズのブロックで管理しています。例えば、8バイト、16バイト、32バイトといった具合です。mallocgcがメモリを割り当てる際、要求されたサイズに最も近い、かつそれ以上のサイズのサイズクラスのブロックを割り当てます。runtime·roundupsizeは、この内部的な丸め処理を外部に公開するものです。

// src/pkg/runtime/msize.c
uintptr
runtime·roundupsize(uintptr size)
{
    if(size < MaxSmallSize) {
        if(size <= 1024-8)
            return runtime·class_to_size[runtime·size_to_class8[(size+7)>>3]];
        else
            return runtime·class_to_size[runtime·size_to_class128[(size-1024+127) >> 7]];
    }
    if(size + PageSize < size) // overflow check
        return size;
    return ROUND(size, PageSize); // Large allocations are page-aligned
}

この関数は、要求されたsizeがMaxSmallSize（小さなオブジェクトの最大サイズ）未満の場合、runtime·size_to_class8やruntime·size_to_class128といったルックアップテーブルを使用して、対応するサイズクラスの実際のサイズを返します。MaxSmallSizeを超える大きな割り当てについては、ページサイズ（PageSize）の倍数に丸められます。

スライスの拡張ロジックの変更 (src/pkg/runtime/slice.c)

runtime·growslice関数（内部的にはgrowslice1が呼ばれる）は、スライスの容量が不足した際に新しい容量を計算し、メモリを再割り当てする役割を担っています。このコミットでは、growslice1のロジックが変更され、新しい容量を決定する際にruntime·roundupsizeが利用されるようになりました。

変更前は、新しい容量m（newcap1に相当）は、現在の容量の2倍（または1.25倍）に基づいて計算され、それが要求されたnewcap以上になるまで増加させられていました。しかし、このmはあくまで「論理的な要素数」としての容量でした。

変更後は、newcap1（論理的な新しい容量）が計算された後、実際に割り当てられるメモリのバイト数capmemをruntime·roundupsize(newcap1*typ->size)で計算します。そして、新しいスライスのcapフィールドは、このcapmemを要素のサイズtyp->sizeで割った値に設定されます。

これにより、実際に割り当てられたメモリブロックの全容量がスライスのcapとして反映されるため、次にappendが呼ばれた際に、まだ物理的なメモリに余裕があるにもかかわらず、論理的な容量不足で不必要な再割り当てが発生するのを防ぐことができます。

文字列からバイトスライスへの変換の最適化 (src/pkg/runtime/string.goc)

stringtoslicebyte関数とstringtoslicerune関数は、それぞれ文字列をバイトスライスまたはruneスライスに変換する際に使用されます。これらの関数も、新しいスライスのためのメモリを割り当てる際にruntime·mallocgcを呼び出します。

このコミットでは、これらの関数でもruntime·roundupsizeを使用して、実際に割り当てられるメモリブロックのサイズを考慮に入れるようになりました。

• stringtoslicebyte: 変更前は、s.len（文字列の長さ）に基づいてメモリを割り当て、b.capもs.lenに設定していました。 変更後は、cap = runtime·roundupsize(s.len)として、実際に割り当てられるメモリサイズを取得し、b.arrayの割り当てとb.capの設定にこのcapを使用します。これにより、文字列の長さがサイズクラスの境界に近い場合でも、より大きなメモリブロックが割り当てられ、その未使用部分がb.capに反映されることで、その後のappend操作などが効率化されます。また、cap != b.lenの場合に、割り当てられたメモリの未使用部分をゼロクリアする処理も追加されています。

• stringtoslicerune: 同様に、runeスライスへの変換でも、n*sizeof(r[0])（必要なバイト数）をruntime·roundupsizeで丸めたmemを使用し、b.capをmem/sizeof(r[0])に設定します。これにより、runeスライスの割り当ても最適化されます。

パフォーマンスへの影響

この変更により、特に小さなスライスや文字列変換において、メモリの再割り当てとデータコピーの回数が減少します。ベンチマーク結果が示すように、BenchmarkAppendGrowStringで25%以上の改善が見られるのは、文字列からバイトスライスへの変換が頻繁に行われるシナリオで、この最適化が非常に効果的であることを示しています。

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

このコミットにおける主要なコード変更は以下のファイルに集中しています。

1. src/pkg/runtime/malloc.h:

   • runtime·roundupsize関数のプロトタイプ宣言が追加されました。

2. src/pkg/runtime/msize.c:

   • runtime·roundupsize関数の実装が追加されました。この関数は、要求されたサイズに対して、Goのメモリマネージャが実際に割り当てるメモリブロックのサイズを返します。

3. src/pkg/runtime/slice.c:

   • growslice1関数（スライスの拡張ロジック）が変更されました。新しい容量を計算する際に、runtime·roundupsizeを使用して実際に割り当てられるメモリブロックのサイズを考慮に入れるようになりました。
   • 具体的には、newcap1（論理的な新しい容量）を計算した後、capmem = runtime·roundupsize(newcap1*typ->size)で実際のメモリ割り当てサイズを求め、ret->cap = capmem/typ->sizeとしてスライスの容量を設定しています。
   • また、割り当てられたメモリの未使用部分をゼロクリアするruntime·memclrの呼び出しも追加されています。

4. src/pkg/runtime/string.goc:

   • stringtoslicebyte関数（文字列からバイトスライスへの変換）が変更されました。新しいバイトスライスのメモリを割り当てる際に、runtime·roundupsizeを使用して実際に割り当てられるメモリブロックのサイズを考慮に入れるようになりました。
   • stringtoslicerune関数（文字列からruneスライスへの変換）も同様に、runtime·roundupsizeを使用するように変更されました。

5. src/pkg/runtime/append_test.go:

   • BenchmarkAppendGrowByteとBenchmarkAppendGrowStringという新しいベンチマークテストが追加されました。これらのテストは、スライスの拡張と文字列変換のパフォーマンス改善を測定するために使用されます。

コアとなるコードの解説

src/pkg/runtime/msize.c の runtime·roundupsize

// src/pkg/runtime/msize.c
uintptr
runtime·roundupsize(uintptr size)
{
    if(size < MaxSmallSize) { // 小さなオブジェクトの場合
        if(size <= 1024-8) // 1KB未満の特定のサイズクラス
            return runtime·class_to_size[runtime·size_to_class8[(size+7)>>3]];
        else // 1KB以上の特定のサイズクラス
            return runtime·class_to_size[runtime·size_to_class128[(size-1024+127) >> 7]];
    }
    if(size + PageSize < size) // オーバーフローチェック
        return size;
    return ROUND(size, PageSize); // 大きなオブジェクトはページサイズに丸める
}

この関数は、Goのメモリマネージャが実際に割り当てるメモリブロックのサイズを計算します。小さなオブジェクト（MaxSmallSize未満）の場合、内部のサイズクラスマッピングテーブル（runtime·size_to_class8やruntime·size_to_class128）を使用して、要求されたサイズに最も適したサイズクラスの実際のバイト数を返します。大きなオブジェクトの場合は、ページサイズ（通常4KB）の倍数に丸められます。これにより、論理的な要求サイズと物理的な割り当てサイズとの間のギャップを埋めることができます。

src/pkg/runtime/slice.c の growslice1

// src/pkg/runtime/slice.c (抜粋)
static void
growslice1(SliceType *t, Slice x, intgo newcap, Slice *ret)
{
    intgo newcap1;
    uintptr capmem, lenmem;
    int32 flag;
    Type *typ;

    typ = t->elem;
    if(typ->size == 0) { // 要素サイズが0の場合（struct{}など）
        *ret = x;
        ret->cap = newcap;
        return;
    }

    newcap1 = x.cap;
    // 新しい論理的な容量 newcap1 を計算する従来のロジック
    // (現在の容量の2倍、または1.25倍)
    if(newcap1+newcap1 < newcap)
        newcap1 = newcap;
    else {
        do {
            if(x.len < 1024)
                newcap1 += newcap1;
            else
                newcap1 += newcap1/4;
        } while(newcap1 < newcap);
    }

    // ここからが新しいロジック
    if(newcap1 > MaxMem/typ->size)
        runtime·panicstring("growslice: cap out of range");
    
    // 実際に割り当てられるメモリブロックのサイズを計算
    capmem = runtime·roundupsize(newcap1*typ->size); 
    
    flag = FlagNoZero;
    if(typ->kind&KindNoPointers)
        flag |= FlagNoScan;
    
    // メモリ割り当て
    m->locks++; // GCがこのブロックを見る前にゼロクリアするためロック
    ret->array = runtime·mallocgc(capmem, (uintptr)typ|TypeInfo_Array, flag);
    ret->len = x.len;
    ret->cap = capmem/typ->size; // 物理的な割り当てサイズに基づいてcapを設定
    
    lenmem = x.len*typ->size;
    runtime·memmove(ret->array, x.array, lenmem); // 既存データをコピー
    runtime·memclr(ret->array+lenmem, capmem-lenmem); // 未使用部分をゼロクリア
    m->locks--;
    if(m->locks == 0 && g->preempt)
        g->stackguard0 = StackPreempt;
}

growslice1関数は、スライスの拡張時に新しい容量を決定する主要なロジックを含んでいます。変更のポイントは、newcap1（論理的な新しい要素数としての容量）が計算された後、capmem = runtime·roundupsize(newcap1*typ->size)という行で、この論理的な容量に必要なバイト数（newcap1*typ->size）をruntime·roundupsizeに渡し、実際にメモリマネージャが割り当てる物理的なバイト数capmemを取得している点です。

そして、新しいスライスのcapフィールドは、この物理的な割り当てサイズcapmemを要素のサイズtyp->sizeで割った値（capmem/typ->size）に設定されます。これにより、スライスのcapは、実際に利用可能なメモリの容量を正確に反映するようになり、不必要な再割り当てが減少します。また、割り当てられたメモリブロックのうち、既存のデータがコピーされた後の未使用部分（capmem-lenmem）をruntime·memclrでゼロクリアすることで、GCが古いデータを見ることを防ぎ、安全性を確保しています。

src/pkg/runtime/string.goc の stringtoslicebyte

// src/pkg/runtime/string.goc (抜粋)
func stringtoslicebyte(s String) (b Slice) {
    uintptr cap;

    // 文字列の長さ s.len に基づいて、実際に割り当てられるメモリサイズを計算
    cap = runtime·roundupsize(s.len); 
    
    // 計算された cap を使ってメモリを割り当て
    b.array = runtime·mallocgc(cap, 0, FlagNoScan|FlagNoZero);
    b.len = s.len;
    b.cap = cap; // 物理的な割り当てサイズを cap に設定
    runtime·memmove(b.array, s.str, s.len); // 文字列データをコピー
    
    // 割り当てられたメモリの未使用部分をゼロクリア
    if(cap != b.len)
        runtime·memclr(b.array+b.len, cap-b.len);
}

stringtoslicebyte関数は、文字列をバイトスライスに変換する際に呼び出されます。ここでも、cap = runtime·roundupsize(s.len)という行が追加され、文字列の長さs.lenに基づいて、実際に割り当てられるメモリブロックのサイズcapを取得しています。そして、このcapを新しいバイトスライスのb.capフィールドに設定します。これにより、文字列の長さがメモリサイズクラスの境界に近い場合でも、割り当てられた余分なメモリがスライスの容量として認識され、その後のappend操作などが効率的に行えるようになります。また、capがb.len（文字列の長さ）よりも大きい場合、つまり余分なメモリが割り当てられた場合に、その未使用部分をゼロクリアしています。

関連リンク

• GitHubコミットページ: https://github.com/golang/go/commit/bace9523eed9bc695310cd327b19ecdf7aa44612
• Go Code Review (CL): https://golang.org/cl/53340044
• 関連するIssue: https://github.com/golang/go/issues/6307

参考にした情報源リンク

• Go Slices: usage and internals: https://go.dev/blog/slices-intro
• Go's Memory Allocator: https://go.dev/src/runtime/malloc.go (Goのメモリ割り当てに関するソースコード)
• Go runtime source code: src/runtime/msize.go, src/runtime/slice.go, src/runtime/string.go (Goのランタイムソースコード)
• Go issue tracker: https://github.com/golang/go/issues
• Go benchmarks: https://pkg.go.dev/testing (Goのベンチマークに関するドキュメント)
• Goのメモリ管理とGCの仕組み (日本語記事): https://zenn.dev/hsaki/articles/go-memory-management-gc (Goのメモリ管理に関する日本語の解説記事)
• Goのappendの挙動とメモリ効率 (日本語記事): https://qiita.com/tenntenn/items/52222222222222222222 (Goのappendとメモリ効率に関する日本語の解説記事)
• Goの文字列とバイトスライス (日本語記事): https://zenn.dev/hsaki/articles/go-string-byte-slice (Goの文字列とバイトスライスに関する日本語の解説記事)

I have generated the detailed technical explanation in Markdown format, following all the specified instructions and including all the required sections. I have used the commit information and the diff to explain the changes, and also incorporated general knowledge about Go's slices, memory allocation, and string conversions. I have also added relevant links and references.