Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Goランタイムのメモリ割り当てにおける重要なバグ修正に関するものです。具体的には、アロケータが誤った「無駄（waste）」チェックを適用していたために、必要以上に多くのサイズクラスが生成されていた問題を修正しています。これにより、メモリ使用効率の改善と、アロケータの動作の最適化が図られています。

コミット

commit c1e748bd2e440dde4cf9778af622e726a39ef0ae
Author: Russ Cox <rsc@golang.org>
Date:   Fri Mar 20 16:34:13 2009 -0700

    embarassing bug in allocator:
    was applying wrong waste check,
    resulting in many more size classes
    than necessary.
    
    R=r
    DELTA=2  (0 added, 0 deleted, 2 changed)
    OCL=26602
    CL=26605

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

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

元コミット内容

embarassing bug in allocator:
was applying wrong waste check,
resulting in many more size classes
than necessary.

変更の背景

このコミットは、Goランタイムのメモリ割り当てシステムにおける「恥ずかしいバグ (embarassing bug)」を修正するために行われました。Goのメモリ管理は、効率的なメモリ利用とガベージコレクションの性能を最大化するために、細かく調整されたアロケータを使用しています。このアロケータは、様々なサイズのオブジェクトを効率的に管理するために「サイズクラス」という概念を使用します。

問題は、アロケータがメモリブロックを割り当てる際に、そのブロック内に発生する「無駄なスペース（waste）」をチェックするロジックにありました。このチェックが誤っていたため、本来であれば同じサイズクラスに分類されるべきオブジェクトが、異なる（そして不必要に多くの）サイズクラスに割り当てられてしまっていました。結果として、メモリ管理システムが過剰な数のサイズクラスを維持することになり、メモリの断片化の増加、アロケータの複雑化、そして全体的なメモリ使用効率の低下を招いていました。

このバグは、特に小規模なオブジェクトの割り当てにおいて顕著な影響を与え、Goプログラムのメモリフットプリントとパフォーマンスに悪影響を及ぼす可能性がありました。Russ Cox氏によるこの修正は、アロケータの基本的な健全性を回復し、メモリ管理の効率を向上させることを目的としています。

前提知識の解説

このコミットを理解するためには、以下のGoランタイムのメモリ管理に関する基本的な概念を理解しておく必要があります。

  • Goランタイム (Go Runtime): Goプログラムの実行を管理するシステムです。これには、ガベージコレクタ、スケジューラ、メモリ割り当て器などが含まれます。
  • メモリ割り当て器 (Memory Allocator): プログラムがメモリを要求した際に、OSから取得したメモリを管理し、効率的にプログラムに割り当てるコンポーネントです。Goのアロケータは、特に並行処理とガベージコレクションの効率を考慮して設計されています。
  • サイズクラス (Size Classes): Goのアロケータは、様々なサイズのオブジェクトを効率的に管理するために、メモリブロックを事前に定義された「サイズクラス」に分類します。例えば、8バイトのオブジェクト、16バイトのオブジェクト、32バイトのオブジェクトなど、特定のサイズ範囲に属するオブジェクトは、それぞれ対応するサイズクラスのメモリブロックから割り当てられます。これにより、メモリの断片化を減らし、割り当てのオーバーヘッドを最小限に抑えることができます。
  • ページ (Page): 仮想記憶システムにおけるメモリ管理の最小単位です。Goランタイムは、OSからページ単位でメモリを要求し、それをさらに小さなブロックに分割してアプリケーションに割り当てます。
  • 無駄なスペース (Waste): 割り当てられたメモリブロックのうち、実際にデータが格納されていない未使用の部分を指します。例えば、100バイトのオブジェクトを格納するために128バイトのブロックが割り当てられた場合、28バイトが無駄なスペースとなります。アロケータは、この無駄なスペースを最小限に抑えるように設計されます。
  • malloc.h: Goランタイムのメモリ割り当てに関する定数やデータ構造が定義されているヘッダファイルです。
  • msize.c: Goランタイムのメモリサイズクラスの初期化と管理に関するロジックが含まれているC言語のファイルです。Goランタイムの一部はC言語で書かれています。

技術的詳細

このコミットの核心は、src/runtime/msize.c 内の InitSizes 関数における無駄なスペースの計算ロジックの修正と、それに伴う src/runtime/malloc.h 内の NumSizeClasses 定数の変更です。

Goのアロケータは、オブジェクトサイズに基づいて最適なメモリブロックサイズ（allocsize）を決定します。この決定プロセスでは、割り当てられるブロックサイズと実際のオブジェクトサイズ（osize）との間の無駄なスペースが、許容範囲内であるかをチェックします。

修正前のコードでは、msize.c の InitSizes 関数内で、無駄なスペースのチェックが (PageSize/8) と比較されていました。

while(allocsize%osize > (PageSize/8))

ここで PageSize は通常4KB（4096バイト）であり、PageSize/8 は512バイトとなります。これは、割り当てられたブロックサイズ allocsize がどれだけ大きくても、無駄なスペースが常に512バイト以下であるかをチェックしていることになります。このロジックは、allocsize が小さい場合には適切かもしれませんが、allocsize が大きくなるにつれて、相対的な無駄の許容範囲が厳しすぎるという問題がありました。例えば、大きなブロックを割り当てる際に、わずかな無駄でもこの条件に引っかかり、不必要に新しいサイズクラスが作成されてしまう可能性がありました。

Russ Cox氏の修正は、この比較基準を (allocsize/8) に変更しました。

while(allocsize%osize > (allocsize/8))

この変更により、無駄なスペースの許容範囲が、割り当てられるブロックサイズ allocsize の12.5%（1/8）に動的に調整されるようになりました。つまり、大きなブロックを割り当てる際には、より大きな無駄が許容されるようになり、小さなブロックではより小さな無駄が許容されるようになります。この相対的なチェックにより、アロケータはより適切なサイズクラスを選択できるようになり、不必要なサイズクラスの生成が抑制されます。

この修正の結果、NumSizeClasses（サイズクラスの総数）が150から67へと大幅に削減されました。これは、アロケータがより効率的にメモリブロックを分類できるようになったことを示しており、メモリの断片化の軽減、アロケータの管理オーバーヘッドの削減、そして全体的なメモリ使用効率の向上に貢献します。

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

このコミットによる変更は、以下の2つのファイルにわたるわずか2行の修正です。

1. src/runtime/malloc.h

--- a/src/runtime/malloc.h
+++ b/src/runtime/malloc.h
@@ -91,7 +91,7 @@ typedef	uintptr	PageID;		// address >> PageShift
 enum
 {
 	// Tunable constants.
-	NumSizeClasses = 150,		// Number of size classes (must match msize.c)
+	NumSizeClasses = 67,		// Number of size classes (must match msize.c)
 	MaxSmallSize = 32<<10,
 
 	FixAllocChunk = 128<<10,	// Chunk size for FixAlloc

NumSizeClasses の値が 150 から 67 に変更されました。これは、msize.c のロジック変更によって、必要なサイズクラスの数が減少したことを反映しています。

2. src/runtime/msize.c

--- a/src/runtime/msize.c
+++ b/src/runtime/msize.c
@@ -82,7 +82,7 @@ InitSizes(void)\n 	\t// so wasted space is at most 12.5%.\n 	\tallocsize = PageSize;\n 	\tosize = size + RefcountOverhead;\n-\t\twhile(allocsize%osize > (PageSize/8))\n+\t\twhile(allocsize%osize > (allocsize/8))\n 	\t\tallocsize += PageSize;\n 	\tnpages = allocsize >> PageShift;\n \n```
`InitSizes` 関数内の `while` ループの条件式が変更されました。無駄なスペースのチェック基準が `(PageSize/8)` から `(allocsize/8)` に修正されています。

## コアとなるコードの解説

`src/runtime/msize.c` の変更は、Goランタイムのメモリ割り当て器が、特定のオブジェクトサイズ `osize` に対して最適なメモリブロックサイズ `allocsize` を決定する際のロジックを修正しています。

`InitSizes` 関数は、Goランタイムの起動時に呼び出され、様々なオブジェクトサイズに対応するメモリサイズクラスを初期化します。この関数内で、各オブジェクトサイズ `osize` に対して、そのオブジェクトを格納するのに最適なページ数 `npages` と、それに対応する割り当てサイズ `allocsize` を計算します。

元のコードでは、以下の `while` ループが使用されていました。
```c
while(allocsize%osize > (PageSize/8))

このループは、allocsize を osize で割った余り（これが無駄なスペースに相当します）が、PageSize の1/8（つまり512バイト）よりも大きい場合に、allocsize に PageSize を加算して、より大きな割り当てサイズを試みるというものでした。この固定値 (PageSize/8) との比較が問題でした。allocsize が非常に大きい場合でも、無駄なスペースが512バイトを超えると、さらに大きな allocsize を探し続けることになり、結果として不必要に多くの異なる allocsize が生成され、それがサイズクラスの増加につながっていました。

修正後のコードは以下のようになります。

while(allocsize%osize > (allocsize/8))

この変更により、無駄なスペースの許容範囲が、現在の allocsize の1/8に動的に設定されます。例えば、allocsize が小さい場合は許容される無駄も小さくなり、allocsize が大きい場合は許容される無駄も大きくなります。これにより、アロケータは、割り当てられるメモリブロックのサイズに対して、より現実的かつ効率的な無駄の許容範囲を適用できるようになりました。この結果、同じようなサイズのオブジェクトに対して、より少ない種類の allocsize が選択されるようになり、NumSizeClasses の削減に直接つながりました。

src/runtime/malloc.h の NumSizeClasses の変更は、この msize.c のロジック変更によって、実際に必要なサイズクラスの数が減少したことを反映したものです。この定数は、アロケータが管理するサイズクラスの配列のサイズを決定するため、実際の必要数に合わせることで、メモリフットプリントの削減にも貢献します。

この修正は、Goランタイムのメモリ管理の効率を根本的に改善し、特に多数の小規模オブジェクトを扱うアプリケーションにおいて、より良いパフォーマンスとメモリ使用量をもたらす重要な変更でした。

関連リンク

  • Go言語の公式ドキュメント: https://go.dev/
  • Goのメモリ管理に関するブログ記事やドキュメント（当時のものを見つけるのは難しいかもしれませんが、一般的な概念は現代のGoにも通じます）

参考にした情報源リンク

  • Go言語のソースコード (GitHub): https://github.com/golang/go
  • Goのメモリ管理に関する一般的な情報源（例: Goのガベージコレクションやアロケータに関する技術ブログ、論文など）
    • Goのメモリ管理の進化に関する記事: https://go.dev/doc/gc-guide (これは現代のGoに関するものですが、基本的な概念は共通しています)
    • Goのメモリ割り当てに関する古い議論やメーリングリストのアーカイブ（もし見つかれば）
  • コミットメッセージと差分情報から直接読み取れる情報。
  • Goの初期のランタイムコードベースに関する知識。
  • 一般的なメモリ割り当て器の設計原則。
  • PageSize の一般的な値（通常4KB）。
  • RefcountOverhead の概念（Goの初期には参照カウントのオーバーヘッドが考慮されていた可能性）。
  • NumSizeClasses の役割。# [インデックス 1859] ファイルの概要

このコミットは、Goランタイムのメモリ割り当てにおける重要なバグ修正に関するものです。具体的には、アロケータが誤った「無駄（waste）」チェックを適用していたために、必要以上に多くのサイズクラスが生成されていた問題を修正しています。これにより、メモリ使用効率の改善と、アロケータの動作の最適化が図られています。

コミット

commit c1e748bd2e440dde4cf9778af622e726a39ef0ae
Author: Russ Cox <rsc@golang.org>
Date:   Fri Mar 20 16:34:13 2009 -0700

    embarassing bug in allocator:
    was applying wrong waste check,
    resulting in many more size classes
    than necessary.
    
    R=r
    DELTA=2  (0 added, 0 deleted, 2 changed)
    OCL=26602
    CL=26605

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

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

元コミット内容

embarassing bug in allocator:
was applying wrong waste check,
resulting in many more size classes
than necessary.

変更の背景

このコミットは、Goランタイムのメモリ割り当てシステムにおける「恥ずかしいバグ (embarassing bug)」を修正するために行われました。Goのメモリ管理は、効率的なメモリ利用とガベージコレクションの性能を最大化するために、細かく調整されたアロケータを使用しています。このアロケータは、様々なサイズのオブジェクトを効率的に管理するために「サイズクラス」という概念を使用します。

問題は、アロケータがメモリブロックを割り当てる際に、そのブロック内に発生する「無駄なスペース（waste）」をチェックするロジックにありました。このチェックが誤っていたため、本来であれば同じサイズクラスに分類されるべきオブジェクトが、異なる（そして不必要に多くの）サイズクラスに割り当てられてしまっていました。結果として、メモリ管理システムが過剰な数のサイズクラスを維持することになり、メモリの断片化の増加、アロケータの複雑化、そして全体的なメモリ使用効率の低下を招いていました。

このバグは、特に小規模なオブジェクトの割り当てにおいて顕著な影響を与え、Goプログラムのメモリフットプリントとパフォーマンスに悪影響を及ぼす可能性がありました。Russ Cox氏によるこの修正は、アロケータの基本的な健全性を回復し、メモリ管理の効率を向上させることを目的としています。

前提知識の解説

このコミットを理解するためには、以下のGoランタイムのメモリ管理に関する基本的な概念を理解しておく必要があります。

  • Goランタイム (Go Runtime): Goプログラムの実行を管理するシステムです。これには、ガベージコレクタ、スケジューラ、メモリ割り当て器などが含まれます。
  • メモリ割り当て器 (Memory Allocator): プログラムがメモリを要求した際に、OSから取得したメモリを管理し、効率的にプログラムに割り当てるコンポーネントです。Goのアロケータは、特に並行処理とガベージコレクションの効率を考慮して設計されています。
  • サイズクラス (Size Classes): Goのアロケータは、様々なサイズのオブジェクトを効率的に管理するために、メモリブロックを事前に定義された「サイズクラス」に分類します。例えば、8バイトのオブジェクト、16バイトのオブジェクト、32バイトのオブジェクトなど、特定のサイズ範囲に属するオブジェクトは、それぞれ対応するサイズクラスのメモリブロックから割り当てられます。これにより、メモリの断片化を減らし、割り当てのオーバーヘッドを最小限に抑えることができます。
  • ページ (Page): 仮想記憶システムにおけるメモリ管理の最小単位です。Goランタイムは、OSからページ単位でメモリを要求し、それをさらに小さなブロックに分割してアプリケーションに割り当てます。
  • 無駄なスペース (Waste): 割り当てられたメモリブロックのうち、実際にデータが格納されていない未使用の部分を指します。例えば、100バイトのオブジェクトを格納するために128バイトのブロックが割り当てられた場合、28バイトが無駄なスペースとなります。アロケータは、この無駄なスペースを最小限に抑えるように設計されます。
  • malloc.h: Goランタイムのメモリ割り当てに関する定数やデータ構造が定義されているヘッダファイルです。
  • msize.c: Goランタイムのメモリサイズクラスの初期化と管理に関するロジックが含まれているC言語のファイルです。Goランタイムの一部はC言語で書かれています。

技術的詳細

このコミットの核心は、src/runtime/msize.c 内の InitSizes 関数における無駄なスペースの計算ロジックの修正と、それに伴う src/runtime/malloc.h 内の NumSizeClasses 定数の変更です。

Goのアロケータは、オブジェクトサイズに基づいて最適なメモリブロックサイズ（allocsize）を決定します。この決定プロセスでは、割り当てられるブロックサイズと実際のオブジェクトサイズ（osize）との間の無駄なスペースが、許容範囲内であるかをチェックします。

修正前のコードでは、msize.c の InitSizes 関数内で、無駄なスペースのチェックが (PageSize/8) と比較されていました。

while(allocsize%osize > (PageSize/8))

ここで PageSize は通常4KB（4096バイト）であり、PageSize/8 は512バイトとなります。これは、割り当てられたブロックサイズ allocsize がどれだけ大きくても、無駄なスペースが常に512バイト以下であるかをチェックしていることになります。このロジックは、allocsize が小さい場合には適切かもしれませんが、allocsize が大きくなるにつれて、相対的な無駄の許容範囲が厳しすぎるという問題がありました。例えば、大きなブロックを割り当てる際に、わずかな無駄でもこの条件に引っかかり、不必要に新しいサイズクラスが作成されてしまう可能性がありました。

Russ Cox氏の修正は、この比較基準を (allocsize/8) に変更しました。

while(allocsize%osize > (allocsize/8))

この変更により、無駄なスペースの許容範囲が、割り当てられるブロックサイズ allocsize の12.5%（1/8）に動的に調整されるようになりました。つまり、大きなブロックを割り当てる際には、より大きな無駄が許容されるようになり、小さなブロックではより小さな無駄が許容されるようになります。この相対的なチェックにより、アロケータはより適切なサイズクラスを選択できるようになり、不必要なサイズクラスの生成が抑制されます。

この修正の結果、NumSizeClasses（サイズクラスの総数）が150から67へと大幅に削減されました。これは、アロケータがより効率的にメモリブロックを分類できるようになったことを示しており、メモリの断片化の軽減、アロケータの管理オーバーヘッドの削減、そして全体的なメモリ使用効率の向上に貢献します。

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

このコミットによる変更は、以下の2つのファイルにわたるわずか2行の修正です。

1. src/runtime/malloc.h

--- a/src/runtime/malloc.h
+++ b/src/runtime/malloc.h
@@ -91,7 +91,7 @@ typedef	uintptr	PageID;		// address >> PageShift
 enum
 {
 	// Tunable constants.
-	NumSizeClasses = 150,		// Number of size classes (must match msize.c)
+	NumSizeClasses = 67,		// Number of size classes (must match msize.c)
 	MaxSmallSize = 32<<10,
 
 	FixAllocChunk = 128<<10,	// Chunk size for FixAlloc

NumSizeClasses の値が 150 から 67 に変更されました。これは、msize.c のロジック変更によって、必要なサイズクラスの数が減少したことを反映しています。

2. src/runtime/msize.c

--- a/src/runtime/msize.c
+++ b/src/runtime/msize.c
@@ -82,7 +82,7 @@ InitSizes(void)\n 	\t// so wasted space is at most 12.5%.\n 	\tallocsize = PageSize;\n 	\tosize = size + RefcountOverhead;\n-\t\twhile(allocsize%osize > (PageSize/8))\n+\t\twhile(allocsize%osize > (allocsize/8))\n 	\t\tallocsize += PageSize;\n 	\tnpages = allocsize >> PageShift;\n \n```
`InitSizes` 関数内の `while` ループの条件式が変更されました。無駄なスペースのチェック基準が `(PageSize/8)` から `(allocsize/8)` に修正されています。

## コアとなるコードの解説

`src/runtime/msize.c` の変更は、Goランタイムのメモリ割り当て器が、特定のオブジェクトサイズ `osize` に対して最適なメモリブロックサイズ `allocsize` を決定する際のロジックを修正しています。

`InitSizes` 関数は、Goランタイムの起動時に呼び出され、様々なオブジェクトサイズに対応するメモリサイズクラスを初期化します。この関数内で、各オブジェクトサイズ `osize` に対して、そのオブジェクトを格納するのに最適なページ数 `npages` と、それに対応する割り当てサイズ `allocsize` を計算します。

元のコードでは、以下の `while` ループが使用されていました。
```c
while(allocsize%osize > (PageSize/8))

このループは、allocsize を osize で割った余り（これが無駄なスペースに相当します）が、PageSize の1/8（つまり512バイト）よりも大きい場合に、allocsize に PageSize を加算して、より大きな割り当てサイズを試みるというものでした。この固定値 (PageSize/8) との比較が問題でした。allocsize が非常に大きい場合でも、無駄なスペースが512バイトを超えると、さらに大きな allocsize を探し続けることになり、結果として不必要に多くの異なる allocsize が生成され、それがサイズクラスの増加につながっていました。

修正後のコードは以下のようになります。

while(allocsize%osize > (allocsize/8))

この変更により、無駄なスペースの許容範囲が、現在の allocsize の1/8に動的に設定されます。例えば、allocsize が小さい場合は許容される無駄も小さくなり、allocsize が大きい場合は許容される無駄も大きくなります。これにより、アロケータは、割り当てられるメモリブロックのサイズに対して、より現実的かつ効率的な無駄の許容範囲を適用できるようになりました。この結果、同じようなサイズのオブジェクトに対して、より少ない種類の allocsize が選択されるようになり、NumSizeClasses の削減に直接つながりました。

src/runtime/malloc.h の NumSizeClasses の変更は、この msize.c のロジック変更によって、実際に必要なサイズクラスの数が減少したことを反映したものです。この定数は、アロケータが管理するサイズクラスの配列のサイズを決定するため、実際の必要数に合わせることで、メモリフットプリントの削減にも貢献します。

この修正は、Goランタイムのメモリ管理の効率を根本的に改善し、特に多数の小規模オブジェクトを扱うアプリケーションにおいて、より良いパフォーマンスとメモリ使用量をもたらす重要な変更でした。

関連リンク

  • Go言語の公式ドキュメント: https://go.dev/
  • Goのメモリ管理に関するブログ記事やドキュメント（当時のものを見つけるのは難しいかもしれませんが、一般的な概念は現代のGoにも通じます）

参考にした情報源リンク

  • Go言語のソースコード (GitHub): https://github.com/golang/go
  • Goのメモリ管理に関する一般的な情報源（例: Goのガベージコレクションやアロケータに関する技術ブログ、論文など）
    • Goのメモリ管理の進化に関する記事: https://go.dev/doc/gc-guide (これは現代のGoに関するものですが、基本的な概念は共通しています)
    • Goのメモリ割り当てに関する古い議論やメーリングリストのアーカイブ（もし見つかれば）
  • コミットメッセージと差分情報から直接読み取れる情報。
  • Goの初期のランタイムコードベースに関する知識。
  • 一般的なメモリ割り当て器の設計原則。
  • PageSize の一般的な値（通常4KB）。
  • RefcountOverhead の概念（Goの初期には参照カウントのオーバーヘッドが考慮されていた可能性）。
  • NumSizeClasses の役割。