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

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

このコミットは、Goランタイムのタイマー実装において、内部で使用されているヒープの構造をバイナリヒープ（2-aryヒープ）から4-aryヒープ（四分木ヒープ）に変更するものです。これにより、多数のタイマーが存在する場合のパフォーマンスが向上します。特に、タイマーの追加や削除といった操作の効率化が図られています。

コミット

  • コミットハッシュ: fcf6a7e5ceb79f771bcf8e783c85535bfaad4f9c
  • 作者: Sokolov Yura funny.falcon@gmail.com
  • 日付: Wed Aug 21 18:51:37 2013 +0400

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

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

元コミット内容

time: make timers heap 4-ary

This slightly improves performance when a lot of timers are present

$ misc/benchcmp ../old_timers_m.txt ../new_timers_m.txt
benchmark                           old ns/op    new ns/op    delta
BenchmarkAfterFunc                       6884         6605   -4.05%
BenchmarkAfterFunc-2                     4473         4144   -7.36%
BenchmarkAfterFunc-3                     8601         6185  -28.09%
BenchmarkAfterFunc-4                     9378         8773   -6.45%
BenchmarkAfter                           7237         7278   +0.57%
BenchmarkAfter-2                         4638         3923  -15.42%
BenchmarkAfter-3                         8751         6239  -28.71%
BenchmarkAfter-4                         9223         8737   -5.27%
BenchmarkStop                             603          496  -17.74%
BenchmarkStop-2                           795          577  -27.42%
BenchmarkStop-3                           982          680  -30.75%
BenchmarkStop-4                          1164          739  -36.51%
BenchmarkSimultaneousAfterFunc            657          593   -9.74%
BenchmarkSimultaneousAfterFunc-2          816          757   -7.23%
BenchmarkSimultaneousAfterFunc-3          844          830   -1.66%
BenchmarkSimultaneousAfterFunc-4          785          771   -1.78%
BenchmarkStartStop                        238          239   +0.42%
BenchmarkStartStop-2                      249          234   -6.02%
BenchmarkStartStop-3                      271          268   -1.11%
BenchmarkStartStop-4                      293          295   +0.68%

R=golang-dev, dvyukov, bradfitz, r
CC=golang-dev
https://golang.org/cl/13094043

変更の背景

Goランタイムのタイマーは、内部的に最小ヒープ（min-heap）として実装されており、最も早く期限が来るタイマーが常にルートに位置するように管理されています。従来のGoランタイムでは、このヒープがバイナリヒープ（2-aryヒープ）として実装されていました。

しかし、多数のタイマーが同時に存在する場合、バイナリヒープの操作（特に要素の挿入や削除に伴う「siftup」や「siftdown」）は、理論的な計算量では効率的であるものの、実際のCPUキャッシュの利用効率という点で課題がありました。バイナリヒープでは、親と子の関係がメモリ上で離れていることが多く、キャッシュミスが発生しやすくなります。キャッシュミスはCPUの処理速度に比べて非常にコストが高いため、これが全体のパフォーマンスボトルネックとなる可能性がありました。

このコミットは、ヒープの構造を2-aryから4-aryに変更することで、このキャッシュ効率の問題を改善しようとするものです。4-aryヒープは、各ノードが最大4つの子を持つため、ヒープの深さが浅くなります。これにより、ヒープ操作中にアクセスされる要素がメモリ上でより局所的になり、CPUキャッシュのヒット率が向上します。結果として、ベンチマーク結果が示すように、特にタイマーの追加や停止といった頻繁な操作において顕著なパフォーマンス改善が見られました。

前提知識の解説

ヒープ (Heap)

ヒープは、ツリーベースのデータ構造であり、ヒープのプロパティ（親ノードの値がその子ノードの値よりも常に大きいか小さいか）を満たします。Goのタイマーシステムでは、最小ヒープ（min-heap）が使用されます。これは、親ノードの値が常にその子ノードの値以下であるというプロパティを持つヒープです。これにより、ルート要素（ヒープの最小値）を効率的に取得できます。タイマーの場合、この最小値は最も早く期限が来るタイマーに対応します。

バイナリヒープ (Binary Heap)

バイナリヒープは、各ノードが最大2つの子を持つヒープです。配列で実装されることが多く、インデックス i のノードの親は (i-1)/2、左の子は 2*i+1、右の子は 2*i+2 で計算されます。挿入（siftup）と削除（siftdown）の操作は、ヒープの高さに比例する時間計算量 O(log n) で行われます。

d-aryヒープ (d-ary Heap)

d-aryヒープは、各ノードが最大 d 個の子を持つヒープです。バイナリヒープはd-aryヒープの特殊なケースで、d=2 の場合です。配列で実装される場合、インデックス i のノードの親は (i-1)/d、最初の子は d*i+1 で計算されます。

d-aryヒープの利点は、ヒープの高さが log_d n となり、d が大きいほどヒープが浅くなることです。これにより、siftup 操作（要素を上に移動させる）の比較回数が減り、理論上は高速になります。しかし、siftdown 操作（要素を下に移動させる）では、d 個の子の中から最小値を見つけるために d 回の比較が必要となるため、O(d log_d n) の計算量となります。

キャッシュ局所性 (Cache Locality)

CPUはメインメモリよりも高速なキャッシュメモリを持っています。データがキャッシュに存在する場合、アクセスは非常に高速ですが、キャッシュにない場合はメインメモリから読み込む必要があり、これがパフォーマンスのボトルネックとなります。キャッシュ局所性とは、プログラムがアクセスするデータがメモリ上で互いに近い位置にある、または時間的に近い期間に繰り返しアクセスされる特性を指します。

d-aryヒープでは、d 個の子がメモリ上で比較的近い位置に配置されるため、siftdown 操作時にこれらの子にアクセスする際にキャッシュミスが減少する傾向があります。これは、理論的な計算量ではバイナリヒープが優れていても、実際の実行速度ではd-aryヒープが有利になることがある主要な理由です。

siftup と siftdown

ヒープのプロパティを維持するために使用される基本的な操作です。

  • siftup (または heapify-up): 新しく挿入された要素や、値が減少した要素がヒープのプロパティを破った場合に、その要素を親と比較し、適切な位置に移動させる操作です。要素が親より小さい場合、親と交換し、このプロセスをルートに到達するか、プロパティが満たされるまで繰り返します。
  • siftdown (または heapify-down): ルート要素が削除された後、新しいルート要素がヒープのプロパティを破った場合に、その要素を子と比較し、適切な位置に移動させる操作です。要素が子より大きい場合、最小の子と交換し、このプロセスを葉に到達するか、プロパティが満たされるまで繰り返します。

技術的詳細

このコミットの主要な変更点は、Goランタイムのタイマーヒープの実装において、親と子のインデックス計算ロジックを2-aryヒープから4-aryヒープに対応するように変更したことです。

siftup 関数の変更

従来のバイナリヒープでは、インデックス i のノードの親は (i-1)/2 で計算されていました。4-aryヒープでは、これが (i-1)/4 に変更されます。これにより、要素がヒープを上に移動する際に、より少ない比較回数で適切な位置に到達できるようになります。

siftdown 関数の変更

従来のバイナリヒープでは、インデックス i のノードの左の子は i*2 + 1 で計算され、右の子は i*2 + 2 でした。4-aryヒープでは、最初の左の子が i*4 + 1 となり、さらに i*4 + 2, i*4 + 3, i*4 + 4 の子も考慮する必要があります。

siftdown のロジックは、現在のノードの when 値（タイマーの期限）と、その4つの子の中で最も小さい when 値を持つ子を比較し、必要であれば交換するという形に拡張されました。これにより、要素がヒープを下に移動する際に、4つの子の中から最小の子を効率的に見つけ出すための追加の比較ロジックが導入されています。

この変更は、理論的な計算量では siftdown が d 倍の比較を必要とするため遅くなる可能性がありますが、前述のキャッシュ局所性の向上により、実際のパフォーマンスでは有利に働くことが多いです。特に、Goのタイマーシステムでは、タイマーの追加（siftup が関与）と削除（siftdown が関与）が頻繁に行われるため、全体的なバランスを考慮した最適化と言えます。

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

src/pkg/runtime/time.goc ファイルにおいて、siftup および siftdown 関数のヒープインデックス計算ロジックが変更されています。

siftup 関数

--- a/src/pkg/runtime/time.goc
+++ b/src/pkg/runtime/time.goc
@@ -225,18 +225,20 @@ static void
 siftup(int32 i)
 {
  int32 p;
+ int64 when;
  Timer **t, *tmp;

  t = timers.t;
+ when = t[i]->when;
+ tmp = t[i];
  while(i > 0) {
-  p = (i-1)/2;  // parent
-  if(t[i]->when >= t[p]->when)
+  p = (i-1)/4;  // parent
+  if(when >= t[p]->when)
   break;
-  tmp = t[i];
  t[i] = t[p];
-  t[p] = tmp;
  t[i]->i = i;
-  t[p]->i = p;
+  t[p] = tmp;
+  tmp->i = p;
  i = p;
  }
 }

siftdown 関数

--- a/src/pkg/runtime/time.goc
+++ b/src/pkg/runtime/time.goc
@@ -244,25 +246,42 @@ siftdown(int32 i)
 static void
 siftdown(int32 i)
 {
- int32 c, len;
+ int32 c, c3, len;
+ int64 when, w, w3;
  Timer **t, *tmp;

  t = timers.t;
  len = timers.len;
+ when = t[i]->when;
+ tmp = t[i];
  for(;;) {
-  c = i*2 + 1;  // left child
+  c = i*4 + 1;  // left child
+  c3 = c + 2;  // mid child
  if(c >= len) {
   break;
  }
-  if(c+1 < len && t[c+1]->when < t[c]->when)
+  w = t[c]->when;
+  if(c+1 < len && t[c+1]->when < w) {
+  w = t[c+1]->when;
   c++;
-  if(t[c]->when >= t[i]->when)
+  }
+  if(c3 < len) {
+  w3 = t[c3]->when;
+  if(c3+1 < len && t[c3+1]->when < w3) {
+  w3 = t[c3+1]->when;
+  c3++;
+  }
+  if(w3 < w) {
+  w = w3;
+  c = c3;
+  }
+  }
+  if(w >= when)
   break;
-  tmp = t[i];
  t[i] = t[c];
-  t[c] = tmp;
  t[i]->i = i;
-  t[c]->i = c;
+  t[c] = tmp;
+  tmp->i = c;
  i = c;
  }
 }

また、src/pkg/time/sleep_test.go には、新しいベンチマーク関数 benchmark が追加され、既存のベンチマークがこの新しいフレームワークを使用するように変更されています。これにより、タイマーヒープの変更によるパフォーマンスの改善をより正確に測定できるようになりました。

コアとなるコードの解説

siftup 関数

  • p = (i-1)/2; が p = (i-1)/4; に変更されました。これは、インデックス i のノードの親のインデックスを計算する際に、バイナリヒープのロジック（2で割る）から4-aryヒープのロジック（4で割る）に切り替わったことを意味します。
  • when = t[i]->when; と tmp = t[i]; がループの外に移動し、現在の要素の when 値とポインタをキャッシュすることで、ループ内のアクセスを最適化しています。
  • 要素の交換ロジックも、tmp 変数を使ってより効率的に行われるように変更されています。

siftdown 関数

  • c = i*2 + 1; が c = i*4 + 1; に変更されました。これは、インデックス i のノードの最初の子（左の子）のインデックスを計算する際に、バイナリヒープのロジックから4-aryヒープのロジックに切り替わったことを意味します。
  • c3 = c + 2; が追加され、4-aryヒープの3番目の子（i*4 + 3）と4番目の子（i*4 + 4）を考慮するためのインデックス計算が導入されました。
  • 複数の子（最大4つ）の中から最小の when 値を持つ子を見つけるための新しい比較ロジックが追加されました。具体的には、まず最初の2つの子 (c と c+1) の中で最小のものを見つけ、次に次の2つの子 (c3 と c3+1) の中で最小のものを見つけ、最後にそれら2つの最小値の中から全体で最小の子を特定します。
  • siftup と同様に、when = t[i]->when; と tmp = t[i]; がループの外に移動し、現在の要素の when 値とポインタをキャッシュすることで、ループ内のアクセスを最適化しています。
  • 要素の交換ロジックも、tmp 変数を使ってより効率的に行われるように変更されています。

これらの変更により、Goランタイムのタイマーヒープは、より多くのタイマーが存在するシナリオにおいて、CPUキャッシュの利用効率を最大化し、全体的なパフォーマンスを向上させるように最適化されました。

関連リンク

参考にした情報源リンク