リングバッファを作るときstd::dequeを使うのはちょっと楽でちょっと損

容量に上限があるキューを実現するためには、リングバッファを用いるのが最も効率的です。

しかし、ポインタの操作を含むコードを自分で書くのは間違いのもとです。効率を最優先する場合以外は、ライブラリを使うほうが良いです。

C++の場合、std::deque*1を使うと以下の意味でそれほど効率が落ちることはありません。

  • 挿入のたびにメモリ確保が走ることはない（std::listのような連結リストではこの要件を満たせない）
  • 挿入または削除のたびに要素の移動が発生することはない（std::vectorには効率の良いpop_frontが存在せず、erase(vec.begin())などとするとこの要件を満たせない）

正しく実装されたリングバッファと比べて、劣る点は以下の点です。

  • かなり多くのメモリを要求する（libstdc++の実装では、少なくとも8192バイト*2必要です）
  • TLBをたくさん占有する（非常に小さいリングバッファであれば一つのページ内に収まります。一方、std::dequeで作った場合、デフォルトのアロケータはページ境界を無視して4096バイト取るため、四つのページを使用することが多いです）
  • キャッシュヒットしにくい（大きな領域を事実上使い捨てていくことになるためです）

*1:std::queueとしないほうが、デバッグの時に中身を出力できて楽です。

*2:https://ja.cppreference.com/w/cpp/container/deque によれば一つのチャンクが4096バイトで、リングバッファを運用するためには二チャンク必要なためです。実際計測してみるとそうなっています。

gshare分岐予測器について、の補足

gshare分岐予測器について - よーるの補足です。

分岐命令の上位アドレスとグローバル分岐履歴をxor、について

吉瀬 謙二, 片桐 孝洋, 本多 弘樹, 弓場 敏嗣:「高性能プロセッサのための代表的な分岐予測器の実装と評価」Technical Report UEC-IS-2003-2, Version 2003-05-0

http://www.arch.cs.titech.ac.jp/~kise/SimAlpha/doc/uec-is-2003-02.pdf

という論文に書いてありました。

直近の分岐履歴を分岐命令の上位アドレスとxor、について

直近の分岐履歴を分岐命令の下位アドレスとxorする場合、以下のようなパターンでインデックスが衝突してしまう可能性があります。 従って、直近の分岐履歴を分岐命令の下位アドレスとxorする場合、理想的なハッシュ関数を使った場合と比べて衝突が増えます。

  • PCαは、分岐方向履歴とは無関係に、予測不可能な分岐をする。
  • PCαがtakenだった場合、いくつかの当てられる分岐が来た後、PCβが予測の難しい（しかし分岐方向履歴を見れば当てられる）分岐である。
  • PCαがnot-takenだった場合、いくつかの当てられる分岐が来た後、PCγが予測の難しい（しかし分岐方向履歴を見れば当てられる）分岐である。
  • PCβとPCγは同じ関数内の近い位置にあり、その上位アドレスは一致している。

直近の分岐履歴を分岐命令の上位アドレスとxorする場合、このようなプログラムの構造（taken側とnot-taken側のPCのビット表現が似ていることが多い）が原因で生じる理想的なハッシュ関数とのずれは、かなり低く抑えられます。

cbp5の分岐トレースが440個、について

443個ありうち3個壊れています、と書きましたが、どうやら壊れているのではなくあまりにも予測が簡単すぎてmisp. /KIが0.0000になっているようです。 集計用スクリプトの書き方が甘く、misp. /KIが0.0000のものはエラー落ちしたものとみなしているのが原因だったようです。

グローバル分岐履歴長を22より大きくするのは性能を低下させる、について

グローバル分岐履歴長22というのは具体的に意味のある数字ではなく、どのようなトレースを選ぶかに大きく依存します。 cbp5の分岐トレースの中には、23回周期のループを回っているだけのようなトレース（SHORT_MOBILE-53、上で壊れていると勘違いしたトレース）が存在します。 これはグローバル分岐履歴長を22以上にすると完璧に当てることができるようになるため、少し無理してでもグローバル分岐履歴長22を確保したほうがよいという結論が得られています。

無限に容量がある場合でもgshare分岐予測器で取り扱うことのできるグローバル分岐履歴長はそれほど大きくできないということは、一般論として事実です。

分岐履歴を折りたたむことでより長い分岐履歴を使ったほうが良いか、について

エントリ数2Mi（512KiB、インデックスは21bit）の時、グローバル分岐履歴長22を使うほうがやや性能が高くなりました。 同様の現象は、この事例以外には見つかりませんでした。

gshare分岐予測器について

gshare分岐予測器というのは、単純な構造の分岐予測器の中では最も性能が良い分岐予測器であり、1993年に発表されました。

このgshare分岐予測器について、あまり教科書に書いていないことを調べたので、まとめておきます。

この記事には、以下のものが含まれます。

  • gshareの適切なインデックスの作り方
  • 容量ごとに最適なグローバル分岐履歴とその理由

以下では、分岐予測器の簡単な仕組みおよびbimodal分岐予測器（per Address 2-bit saturating counter scheme）についての知識を前提とします。

gshare分岐予測器とは

bimodal分岐予測器は、単にその分岐命令の分岐方向の偏りだけを頼りに分岐方向を予測します。 分岐命令のアドレス（の下位Nビット）をインデックスとし、パターンヒストリーテーブル(PHT)という飽和二ビットカウンターの配列にアクセスすることで、予測を行います。

それに対しgshare分岐予測器は、グローバル分岐履歴（直近いくつかの条件分岐命令の分岐方向の系列）を利用し、他の分岐命令の分岐方向との相関をもとらえることで予測精度を向上させる手法です。 分岐命令のアドレス（の下位Nビット）とグローバル分岐履歴をxorしたものをインデックスとし、PHTにアクセスすることで予測を行います。 xorした場合情報が失われてしまいますが、使われていないPHTエントリを有効活用できるようになります。

ちなみに、分岐命令のアドレス（の下位Nビット）とグローバル分岐履歴を連結したものをインデックスとする分岐予測器はgselect分岐予測器と呼ばれますが、利用されるPHTエントリに偏りが生じるため、gshare分岐予測器のほうが性能が良いとされています。

正しいインデックスの作り方

分岐命令のアドレス（の下位Nビット）とグローバル分岐履歴をxorするという手法は有名ですが、具体的にどのようにxorするのかについて、詳細に書かれた教科書を見たことがありません。

実は、ここでのxorの仕方は結構重要です。複数の異なる分岐命令＆グローバル分岐履歴が同じインデックスになってしまう（エイリアスが起こる）場合、破壊的な学習が行われ、予測精度が低下してしまいます。

理想的なハッシュ関数を使えばエイリアス頻度を最小限に抑えることができます。しかし、xorするだけという単純なハッシュ関数を用いて理想的なエイリアス頻度を達成するには、少し工夫が必要です。

【間違い】分岐命令の下位アドレスとグローバル分岐履歴をxor

PC9 PC8 PC7 PC6 PC5 PC4 PC3 PC2 PC1 PC0
ghist3 ghist2 ghist1 ghist0

このようにしてしまうと、頻繁にエイリアスが発生してしまいます。なぜなら、プログラムの多く実行される部分は狭い範囲に集中していることが多く、そこに含まれる分岐命令のPCの上位ビットは似ていることが多いからです。

【正解】分岐命令の上位アドレスとグローバル分岐履歴をxor

PC9 PC8 PC7 PC6 PC5 PC4 PC3 PC2 PC1 PC0
ghist3 ghist2 ghist1 ghist0

このようにすることで、近くに存在する分岐命令との狭い範囲にある分岐命令がお互いにエイリアスの関係になってしまう事態が避けられます。 当然遠い位置にある特定の分岐命令との間でエイリアスが起こる可能性は残されるのですが、理想的なハッシュ関数と比べそのような事態が発生する頻度が高いということはないはずです。

【最良】直近の分岐履歴を分岐命令の上位アドレスとxor

PC9 PC8 PC7 PC6 PC5 PC4 PC3 PC2 PC1 PC0
ghist0 ghist1 ghist2 ghist3 ghist4 ghist5 ghist6

もし使用するグローバル分岐履歴長が長めである場合、順番を逆にし、直前の分岐履歴がPCの最上位ビットとxorされるようにするほうがやや良い性能を示すようです。 一般に、直近の分岐履歴のほうが需要であることが原因であると思われます。

PHTの容量と分岐履歴長毎の予測性能

一般に、bimodal分岐予測器もgshare分岐予測器も、PHTの容量を増やせば増やすほど予測性能が向上します。もちろん、エイリアスが十分発生しなくなる容量まで増やすと、性能向上は頭打ちとなります。

gshare分岐予測器では、グローバル分岐履歴長を伸ばせば伸ばすほど遠い分岐命令との相関もとらえられるようになります。しかし、それに伴い以下の二種類の問題が発生するため、グローバル分岐履歴長を伸ばせば伸ばすほど予測性能が上がるわけではありません。

  • 学習するべきパターンが増加し、エイリアスの可能性が増加する（グローバル分岐履歴長3であれば、一つの分岐アドレスにつき最大で8パターン覚える必要がある*1）
  • 遠い過去の分岐履歴との相関がない分岐について、初見のパターンである割合が増加する（bimodal分岐予測器なら前に見たことのある分岐命令アドレスで当てられたのに、というケース）

実測

分岐予測器の世界的な大会である、cbp5のルールに従って、各手法の分岐予測ミス率を測りました。cbp5では、分岐命令の系列（トレース）が440個*2公開されており、付属のシミュレータを使うと千命令当たりの予測ミス回数（misp./KI）が出力されます。440個のトレースについて、その平均をとることで、いろいろな分岐パターンを当てることができるかを評価します。

440回もシミュレータを動かす必要があるため、データを取るには10時間以上かかります。

f:id:lpha_z:20200308222444p:plainf:id:lpha_z:20200308222535p:plain
図1 PHT容量ごとの分岐予測ミス率（cbp5トレースにおける千命令あたりの分岐予測ミス数）

図1は、PHTのエントリ数を変更したときの、各分岐予測器（bimodal, gshareでグローバル分岐履歴長が1, 2, 4, 8, 12, 16, 22, 28のもの）の予測ミス率を表しています*3。

測定の結果わかったことは、

  • PHTエントリ数が256未満なら、gshareを使わずにbimodalを使ったほうが良い
  • PHTエントリ数が256～64 Kiくらいの時、容量を二倍にするごとにグローバル分岐履歴長を2増やすくらいがよい。グローバル分岐履歴長を伸ばしすぎるとかえって性能が低下する
  • PHTエントリ数が64 Ki～4 Miくらいの時、PHTのインデックスのビット数と同じだけのグローバル分岐履歴長が良い*4
  • PHTエントリ数が4 Mi以上ある場合でも、グローバル分岐履歴長を22より大きくするのは性能を低下させる

なぜそうなるのか

PHTエントリ数が256未満なら、gshareを使わずにbimodalを使ったほうが良い

PHTエントリ数が非常に小さいため、エイリアスの可能性が非常に高く、容量性ミスが発生しています。したがって、学習するべきパターン数を抑えることが重要です。

PHTエントリ数が256～64 Kiくらいの時、容量を二倍にするごとにグローバル分岐履歴長を2増やすくらいがよい。グローバル分岐履歴長を伸ばしすぎるとかえって性能が低下する

PHTエントリ数は標準的な数ですが、エイリアスの可能性がそれなりにあり、競合性ミスが発生しています。したがって、破壊的な競合の発生確率を下げるためにグローバル分岐履歴長をほどほどに抑えることが重要です*5

PHTエントリ数が64 Ki～4 Miくらいの時、PHTのインデックスのビット数と同じだけのグローバル分岐履歴長が良い

PHTエントリ数は非現実的な数になってきており、十分なエントリ数があります。したがって、遠くの分岐との相関を捉えるため、グローバル分岐履歴長をなるべく長くすることが重要です。

PHTエントリ数が4 Mi以上ある場合でも、グローバル分岐履歴長を22より大きくするのは性能を低下させる

PHTエントリ数は事実上無限大とみなせます。グローバル分岐履歴が長すぎる場合、「過去の分岐との相関はないが、分岐方向は偏っている分岐」を当てるために非常に多くのパターンを学習する必要があります。つまり、"初期参照ミス"の発生が支配的な領域です。したがって、"初期参照ミス"の数を減らすため、グローバル分岐履歴長をむやみに長くしないことが重要です。

エントリー数4 GiのPHTを使用したときの、分岐履歴長毎のgshare分岐予測器の性能の比較

f:id:lpha_z:20200308230450p:plain

分岐履歴長22のところで最小値を取っていることがわかります。

bimodal分岐予測器と、容量ごとに最適な分岐履歴長を使用したgshare分岐予測器の性能の比較

f:id:lpha_z:20200308225810p:plain

分岐予測器としてよく使われる1KiB～64KiBの範囲で、効率よく性能向上が得られています。 特に、容量をつぎ込んだbimodal分岐予測器の限界10.397 misp./KIをたったの512 Byteで実現できます。

また、どれだけ容量をつぎ込んだとしても、5.585 misp./KI止まりです。 gshare分岐予測器には先ほど見たような複数のトレードオフが存在するため、容量をつぎ込めば性能が上がるというわけではありません。

まとめ

gshare分岐予測器について、xorでインデックスを作るといってもエイリアスが起こりにくい作り方をするためには一工夫いることがわかりました。

また、シミュレータで非現実的な大きさまでのgshare分岐予測器の実験を行うことにより、最適なグローバル分岐履歴長の選び方と、なぜそうなるのかの理由がわかりました。

*1:実際に出現するパターンは限られており、指数的には増えないとされています

*2:実際には443個ですが、3つは壊れています

*3:ちなみに、現在最も性能が高いと思われている分岐予測器であるBATAGE（2018年発表）は、8 KiB（PHTエントリ数32768に相当）でmisp./KIが4.183です。

*4:もしかしたら、分岐履歴を折りたたむことでより長い分岐履歴を使ったほうが良い可能性もあります

*5:この問題に対し、1990年代後半にエイリアス発生率を下げる手法が広く研究されました。Bi-mode分岐予測器、Agree-mode分岐予測器、gskew分岐予測器などがその一例です

クイックソートのピボットは中央値でなく四分位数を選択したほうが高速

概要

クイックソートは一般に高速なソートアルゴリズムとして知られています。 アルゴリズム中にはピボットを選択する部分がありますが、ここでなるべく中央値に近い値を選択すると、総比較回数を少なくすることができます。 しかし、最近の高性能プロセッサは投機実行するため、比較回数ではなく分岐予測ミスの回数が性能に大きく影響します。 ピボットとして中央値ではなく四分位数を選択する場合、比較回数が23%増加するものの、分岐予測ミス回数を38%削減し、ソートにかかる時間を20%削減できることが分かりました。

はじめに

去年の末、kimiyukiさん（kimiyuki@うさぎ🐇 (@kimiyuki_u) | Twitter）に「クイックソートのピボットとして中央値ではない値を選んだほうが、分岐予測ミス率が減って高速なのでは」という話をいただきました。 その時私は、「分岐予測ミス率を減らせても、トータルの仕事量が増えてしまって意味がないのでは」と怪しんでいましたが、実際に実験してみると高速化することがわかりました。

以下では、高速化する原因を、モデルを用いて明らかにします。

実際に計測に用いたコード（ピボットをオラクル的に選択できるように改造したクイックソート）は以下です。

#include <array>
#include <utility>

std::array<double, 10000000> arr;

void q_sort( double* begin, double* end, double begin_v, double end_v ) {
        if( end - begin <= 1 ) { return; }

        const double pivot = begin_v*0.75 + end_v*0.25;

        double* p = begin;
        double* q = end;

        for( ; ; ) {
                while( p < q && *p < pivot ) ++p;
                do --q; while( p < q && *q > pivot );
                if( p >= q ) break;
                std::swap( *p, *q );
                ++p;
        }

        q_sort( begin, p, begin_v, pivot );
        q_sort( p, end, pivot, end_v );
}

#include <random>

int main() {
        std::mt19937 mt;
        std::uniform_real_distribution<double> dist(1.0, 2.0);
        for( auto& e : arr ) {
                e = dist(mt);
        }
        q_sort( arr.begin(), arr.end(), 1.0, 2.0 );
}

モデル化

理論

N要素に対するソートアルゴリズムは、N!通りある入力に対して1通りの出力を返すので、エントロピーを \log_2(N!) ビット下げる必要があります。

クイックソートでは、ピボットとして中央値を選んだ場合、一回の分岐命令で1ビットのエントロピーを下げることができます。 一般に、ピボットとしてp:(1-p)に内分する点を選んだ場合、一回の分岐命令で H(p) = - p\log_2(p) - (1-p)\log_2(1-p)ビットのエントロピーを下げることができます。

よって、ピボットとしてp:(1-p)に内分する点を選んだ場合、 \log_2(N!) / H(p) 回の比較が少なくとも必要です*1。

また、ソートを行うためには比較した後に分岐する必要がありますが、この分岐の飛び先には規則性がありません。 分岐予測器は、単に確率の高いほうに分岐するだろうと予測するしかなく、実際にそのように動作すると考えてよいです。 この場合の分岐予測成功確率は、 \max(p, 1-p)となります。

よって、ピボットとしてp:(1-p)に内分する点を選んだ場合、分岐予測ミスは、 \max(p, 1-p) \times \log_2(N!) / H(p)回発生することになります。

プロセッサのパラメータ

Intel社のSkylakeマイクロアーキテクチャでは、分岐予測ミスペナルティがおおよそ 20 cycle です。また、このコードの場合、ミスがなかった場合と比べて追加で 9 cycle 損します。これは、パイプラインがフラッシュされ、メモリアクセス（5 cycle）と浮動小数点数比較（4 cycle）がやり直しになるためです。

分岐予測ミスが発生しない場合、比較にかかる時間*2は 1 cycle です。

また、実測値を使うと、end - begin > 1の時の関数呼び出しのオーバーヘッドは、約 50 cycle でした。

クイックソートにかかる時間

ソートが完了するまでにかかる時間は、ピボット選択位置pをパラメータとして、

  • 分岐予測ミスペナルティ 29 cycle × \max(p, 1-p) \times \log_2(N!) / H(p) 回
  • 比較コスト 1 cycle × \log_2(N!) / H(p) 回
  • 関数呼び出しコスト 50 cycle × \log_2(N) / H(p) 回

の和としてモデル化できます。

その結果、p=0.2～0.25付近で最小値を取ることがわかります。

定性的な説明

ピボットとして中央値を選択すると、分岐予測ミス確率は50%です。分岐一回で減らせるエントロピーは、1ビットです。よって、分岐予測ミス一回当たりで減らせるエントロピーは、2ビットです。

一方、ピボットとして四分位数を選択した場合、分岐予測ミス確率は25%です。分岐一回で減らせるエントロピーは、0.811ビットです。よって、分岐予測ミス一回当たりで減らせるエントロピーは、3.2ビットです。

このように、減らせるエントロピーが小さくなる（＝トータルの仕事量が多くなってしまう）効果よりも、分岐予測ミス確率が減る効果のほうがはるかに大きいです。

一般に、偏ったピボットをとるほど、一回の分岐予測ミスで減らせるエントロピーは大きくなります。

比較コストや関数呼び出しコストより分岐予測ミスペナルティのほうが十分大きい領域（0.2<p<0.8）においては、なるべく偏ったピボットを選択したほうが効率的です。

ただし、ピボットとしてあまりに偏った値を選択すると、比較コストや関数呼び出しコストが支配的となり、かえって低速になります。

おわりに

クイックソートのピボットは中央値を選ぶのが、比較回数が最小となるため望ましいというのが定説でした。 実際に中央値を選択するのは難しいですが、複数のピボット候補の中央値を選択することでなるべく中央値に近いと思われるピボットを選択する手法が一般に用いられています。

しかし、分岐予測ミスペナルティが非常に大きな近年の高性能プロセッサの場合、中央値に近い値をピボットとして選択するのは、かえって悪手である可能性があることがわかりました。 複数のピボット候補からピボットを選択する手法も、今後は見直す必要がありそうです。

*1:再帰呼び出し終端付近では無駄な比較が多発するため、約1.2倍の比較が実行されるようです

*2:正確にはスループット

sshでログインできなくなった問題と解決策

リモートマシンにsshログインしようとしたところ、パスフレーズの入力後に何も反応しなくなることがありました。

正しくない公開鍵を使った場合や、正しくないパスフレーズを入力した場合はログインできないと応答が返ってくるので、リモートマシンの側の問題ではなさそうです。

-vvvオプションをつけてログを見たところ、first channel unpausesという不思議なログが出ていました。

このメッセージでgoogle検索したところ、

「PowerShellでRestart-Service LxssManagerを実行せよ」

という解決法を発見しました。

しかし、そもそもそのようなコマンドは存在せず、解決しませんでした。

Windows自体を再起動したところ、問題が解決しました。