とうとう、JPOUG Advent Calendar 2014 も最終日となりました。今年もご参加頂いた皆様に感謝しつつも、去年に続き、オオトリを務めさせていただきます。
Oracleデータベースも12.1.0.2というバージョンでIn-Memoryかつカラム型で分析系ワークロード用を高速化するオプションが導入されていることはご存じの通りです。
このIn-Memoryオプションという文脈で
"ディスクは遅くメモリーは速い。だからIn-Memoryなデータベースは速い"
とか
"分析系ワークロードはカラム型といったデータフォーマット合っている。だからカラム型が速い"
とか
"データベースの処理をSIMD(シムディー)とかVector処理といった処理で行うと速い"
とか
なかなか、上記のキーワードがどのようにデータベース処理と関連しているか不明な状態で説明されることが多いのではないか。と思う今日この頃です。
今日は、In-Memoryやカラム型やSIMDといったキーワードを自分なりに関連あることとして、ここにメモ書きを残そうと思います。
言葉でアレコレ説明しても、よく分からん。(どなたかはSIMDの気持が知りたい。と仰っていた)なので、とてつもなくシンプルな疑似コードで説明してみたいと思います。
* ちなみに、以下示される疑似コードはOracleとも他のデータベースの作りとも全く関係ありません。目的は、疑似コードで処理のイメージを掴めれば良い程度の簡単なものです。(要はこんなにデータ構造はシンプルではないですし、コードもこんなに非汎用的ではないですし、正直、WHERE句のSIMD適用はこんなにお手軽ではないですし)
前提)
以下のような数十カラムを含むテーブル構成で1億件のランダムなデータが入っていると想定
SQLで書くと以下のような感じ
こんなテーブルをコードで書くと(とりあえずC)、以下のような構造体の配列(これは通常のロー型を想定)になると思います
上記に適当にデータを詰め込んだあと(適当なランダムな値という意味で、値がソート済みだとリソース使用状況が大きく異なりますので注意)、以下のようなSQLを想定したコードを書いてみます。
SQLで書くと以下のような感じ
さあ、これで、一応In-Memoryで処理する準備ができましたので、これを実行してみます。が、ディスクベースより当然高速なのは明白で且つCPUは100%/coreの状態で処理するので、perfコマンドで、CPUのプロファイルを取りながら、上記コードのどこに問題があるか見てみるとしましょう。
1億件のデータで、そのSELECTIVITYを0% ～ 100%まで10段階で評価してみましょう。
まず目を引くのはCPT(Cycles Per Tuple)の大きさです。これは1行の処理をするのにかかったCPUサイクルを示しますが、1行あたり23.8サイクルもかかっています。
似たような指標としてIPC(Instructions Per Cycle)の低さも目につきます。これは1CPUサイクルあたり実行したCPUインストラクション数を示していますが、昨今のCPUは複数のCPUインストラクション実行ユニットを持っているにも関わらず、IPCは1を下回る低い数値です。
この原因として、大きく2+αあると思われます。
1に関して
In-Memoryで、ディスクI/Oがないとはいえ、CPUから見れば、非常に低速なMemoryからデータをCPUキャッシュに持ってくるのはコストが高く、上手くCPUキャッシュを使うことを考えないと、データベースの性能も上手く引き出せない。という事で、最初に定義したような構造体の配列(いわゆるArray of Structure(AoS))では、l_quantityというメンバーしか参照していないにも関わらず、無駄にキャッシュロードが発生しています。であれば、配列の構造体(Structure of Array(SoA))にした方が良いのではないか？
非常に乱暴に言うと、AoSをロー型のデータ構造だとするとSoAはカラム型のデータ構造と言えると思います。
2に関して
最初に示したselect_count_gt()なる関数ではforループの脱出条件の評価とループ内のWHERE句に相当する条件評価の2つがありますが、SELECTIVITYを可変にして行った実験からもWHERE句に相当するIF分岐の予測は、SELECTIVITYが50%になると最悪になっています。これは当然なわけですが、何とか分岐予測ミスを発生しない。つまり分岐そのものをなくす方向で処理したい。
3に関して
少しだけ2とも関連しますが、今までのムーアの法則に従ってCPUクロックがどんどん高くなる世界なら、CPU内の多少の無駄な処理も、高くなるクロック数が隠ぺいしてくれていましたが、さすがに、クロック数の伸びは鈍化しています。これからは、パフォーマンスを最適化したいと思ったら、CPUに無駄な処理をさせないことを考える必要があります。つまりCPUインストラクションの削減と、結果としてCPUサイクルの低減が主なターゲットとなります。そこでSIMDが登場します。SIMDを使ったコードは基本的にバルク処理で、いちいち分岐するような処理には向いていません。なので、SIMDを考えるなら2も合わせて考えることになります。
という事で、まず1のデータ構造をロー型からカラム型(非常におおざっぱなのは前述の通り)に変えてみます。
先ほどの構造体はこんな感じになります。
さらに先ほどのデータ件数を数える関数は以下のようになります。
先ほどと同じ条件とデータで実行してみます。
どうでしょう？
キャッシュミスが大きく減少しました(1/100程度)。それにともなって、CPT(1行を処理するのに必要な平均CPUサイクル数)やIPC(CPU命令の実行効率)が大きく改善されるSELECTIVITYがある事が分かりますね。
ただ、データ構造を変えただけだと、最初のロー型(を模したもの)に比べてSELECTIVITYによる分岐予測ミスが増減する傾向に変化はありません。(最終的には、CPTもSELECTIVITYによって悪化する傾向に変化はありません)
次は、この分岐ミスをなくすようにコードを書き換えてみます。
(* SIMDに行く前に通らねばならない道ですので)
上記は、WHERE句の条件がTRUEであろうがFALSEであろうがcntという変数を加算します。ただしTRUEは1、FALSEは0という言語仕様を利用しています。これは、分岐せずに常に一定の処理(ここではcnt変数への加算)を実行するため、CPUインストラクション数は増加しますが、分岐ミスが減少し、分岐ミスによるパイプラインハザードのペナルティを払わない方がCPUサイクルを消費しないであろうとの仮定の上に成り立っています。
では、結果を見てみましょう。
どうでしょうか？SELECTIVITYに依存せず、どのような条件下でも一定のパフォーマンスを出すことが出来ていますね。分岐予測ミス恐ろしや。
それでは最後に、さらにパフォーマンスを上げたい(というか、さらに最適化させたい)ので、SIMDを使ったコードに書き換えてみます。
x86系プロセッサではSIMDとしてSSEやAVXがサポートされています。SSEは128ビット幅のレジスターを使っていて、AVXからは256ビット幅のレジスターを使えます。
では、SSE(128ビット幅)のコードを以下に示します。
少しだけ説明すると
_mm_set1_epi32()
比較対象(ここでは50)のINT型を128ビットレジスターに登録します(INT型は32ビットなので、128ビットレジスターには4つ同時に格納されます)
_mm_load_si128()
比較元のデータを4つ分(INT(32ビット)を128ビット分)SIMDのレジスターに登録します。
_mm_cmpgt_epi32()
上記のレジスター2つを一気に比較します。その戻りは、128ビットレジスターに真なら32ビット分の0xff....f、偽なら0となります。
_mm_movemask_ps()で
先ほどの32ビットマスクをINTに変換し、_mm_popcnt_u32()で、INT中に1のフラグが立っている数を数えます。
少々、見慣れませんが、まぁ、そんな感じです。
では、結果を見てみましょう。(基本的に他と変化のあるCPTとIPCのみチャート化)
どうでしょう？
先ほどのブランチフリー版にくらべて、IPCが少し落ちていますが、CPU命令数が減少したおかげで、CPTが減少していることが分かりますね。
おまけでAVX(正確にはAVX2の256ビット幅のレジスター)でも実験
* 実際に256ビット幅で整数を扱おうとするとAVX2が必要で、AVX2はHaswellからのサポートです。
結果は以下のようになります。
どうでしょう？
AVX2使用時はSSE時と比較してレジスター幅が倍増している恩恵をきちんと受けていることが分かりますね。
これで、本当に最後ですが、各処理(ロー型、カラム型、ブランチフリー、SSE、AVX2)での処理時間のチャートを示しておきます。
少しだけ、まとめめいたものを書くとすると、大量のデータを効率良く処理するときには
を考えないといけない。
その時にネックになるのは、
とか。
これらをなるべく排除する方法として
等があるというのが私の理解です。さらには、SIMDを使うには、そもそもデータ構造(ロー型とかカラム型)を最初に考えていないと効率よく使えないような気がしているし、SIMDを使って効率良く処理にするには分岐が沢山あっちゃいけない気もしています。
という事で、最初に上げたキーワード(In-Memory、カラム型、SIMD)は私の中では、かなりつながった感があります。
ちょっと長いエントリになってしまいましたが、私の理解するIn-Memoryとかカラム型とかSIMDとかの気持ちが分かってもらえたでしょうか？
それでは、皆様よいクリスマスを！
Oracleデータベースも12.1.0.2というバージョンでIn-Memoryかつカラム型で分析系ワークロード用を高速化するオプションが導入されていることはご存じの通りです。
このIn-Memoryオプションという文脈で
"ディスクは遅くメモリーは速い。だからIn-Memoryなデータベースは速い"
とか
"分析系ワークロードはカラム型といったデータフォーマット合っている。だからカラム型が速い"
とか
"データベースの処理をSIMD(シムディー)とかVector処理といった処理で行うと速い"
とか
なかなか、上記のキーワードがどのようにデータベース処理と関連しているか不明な状態で説明されることが多いのではないか。と思う今日この頃です。
今日は、In-Memoryやカラム型やSIMDといったキーワードを自分なりに関連あることとして、ここにメモ書きを残そうと思います。
言葉でアレコレ説明しても、よく分からん。(どなたかはSIMDの気持が知りたい。と仰っていた)なので、とてつもなくシンプルな疑似コードで説明してみたいと思います。
* ちなみに、以下示される疑似コードはOracleとも他のデータベースの作りとも全く関係ありません。目的は、疑似コードで処理のイメージを掴めれば良い程度の簡単なものです。(要はこんなにデータ構造はシンプルではないですし、コードもこんなに非汎用的ではないですし、正直、WHERE句のSIMD適用はこんなにお手軽ではないですし)
前提)
以下のような数十カラムを含むテーブル構成で1億件のランダムなデータが入っていると想定
SQLで書くと以下のような感じ
create table large_table ( l_quantity number ,l_tax number ,... ,(沢山) ,... );
こんなテーブルをコードで書くと(とりあえずC)、以下のような構造体の配列(これは通常のロー型を想定)になると思います
typedef struct {
int l_quantity;
int l_tax;
...
(沢山)
...
} LARGE_TABLE_t;
LARGE_TABLE_t large_table = (LARGE_TABLE_t*)malloc(sizeof(LARGE_TABLE_t) * 100000000);
上記に適当にデータを詰め込んだあと(適当なランダムな値という意味で、値がソート済みだとリソース使用状況が大きく異なりますので注意)、以下のようなSQLを想定したコードを書いてみます。
SQLで書くと以下のような感じ
SELECT count(*) FROM large_table WHERE l_quantity > 50;
普通(ロー型をイメージした)バージョン
これをCで表現して以下のような関数にしてみました。/*
引数
第1引数: LARGE_TABLE_tとして渡される構造体の配列の個数(ここでは100,000,000)
第2引数: LARGE_TABLEの構造体のポインター
第3引数: 条件に指定する数値(ここでは50)
戻り
結果として、条件にマッチしたデータの個数
*/
int select_count_gt(int n, LARGE_TABLE_t* tab, int* val)
{
int cnt = 0, i;
int v = *val;
for (i=0; i<n; ++i) {
if (tab[i].l_quantity > v) {
cnt++;
}
}
return cnt;
}
さあ、これで、一応In-Memoryで処理する準備ができましたので、これを実行してみます。が、ディスクベースより当然高速なのは明白で且つCPUは100%/coreの状態で処理するので、perfコマンドで、CPUのプロファイルを取りながら、上記コードのどこに問題があるか見てみるとしましょう。
1億件のデータで、そのSELECTIVITYを0% ～ 100%まで10段階で評価してみましょう。
 |
| ロー型データ構造時のperfの結果 |
まず目を引くのはCPT(Cycles Per Tuple)の大きさです。これは1行の処理をするのにかかったCPUサイクルを示しますが、1行あたり23.8サイクルもかかっています。
似たような指標としてIPC(Instructions Per Cycle)の低さも目につきます。これは1CPUサイクルあたり実行したCPUインストラクション数を示していますが、昨今のCPUは複数のCPUインストラクション実行ユニットを持っているにも関わらず、IPCは1を下回る低い数値です。
この原因として、大きく2+αあると思われます。
- CacheミスによるCPUのストール
- 分岐ミスによるCPUにパイプラインハザード
- そもそも、こんな簡単なコードをもっと効率的に実行できないか？(要はCPUインストラクション数、結果的にCPUサイクル数を減らせないか？)
1に関して
In-Memoryで、ディスクI/Oがないとはいえ、CPUから見れば、非常に低速なMemoryからデータをCPUキャッシュに持ってくるのはコストが高く、上手くCPUキャッシュを使うことを考えないと、データベースの性能も上手く引き出せない。という事で、最初に定義したような構造体の配列(いわゆるArray of Structure(AoS))では、l_quantityというメンバーしか参照していないにも関わらず、無駄にキャッシュロードが発生しています。であれば、配列の構造体(Structure of Array(SoA))にした方が良いのではないか？
非常に乱暴に言うと、AoSをロー型のデータ構造だとするとSoAはカラム型のデータ構造と言えると思います。
2に関して
最初に示したselect_count_gt()なる関数ではforループの脱出条件の評価とループ内のWHERE句に相当する条件評価の2つがありますが、SELECTIVITYを可変にして行った実験からもWHERE句に相当するIF分岐の予測は、SELECTIVITYが50%になると最悪になっています。これは当然なわけですが、何とか分岐予測ミスを発生しない。つまり分岐そのものをなくす方向で処理したい。
3に関して
少しだけ2とも関連しますが、今までのムーアの法則に従ってCPUクロックがどんどん高くなる世界なら、CPU内の多少の無駄な処理も、高くなるクロック数が隠ぺいしてくれていましたが、さすがに、クロック数の伸びは鈍化しています。これからは、パフォーマンスを最適化したいと思ったら、CPUに無駄な処理をさせないことを考える必要があります。つまりCPUインストラクションの削減と、結果としてCPUサイクルの低減が主なターゲットとなります。そこでSIMDが登場します。SIMDを使ったコードは基本的にバルク処理で、いちいち分岐するような処理には向いていません。なので、SIMDを考えるなら2も合わせて考えることになります。
という事で、まず1のデータ構造をロー型からカラム型(非常におおざっぱなのは前述の通り)に変えてみます。
カラム型をイメージしたバージョン
先ほどの構造体はこんな感じになります。
typedef struct {
int *l_quantity;
int *l_tax;
...
(沢山)
...
} LARGE_TABLE_t;
LARGE_TABLE_t large_table;
large_table.l_quantity = (int*)malloc(sizeof(int) * 100000000);
...
さらに先ほどのデータ件数を数える関数は以下のようになります。
int select_count_gt_columnar(int n, LARGE_TABLE_t* tab, int* val)
{
int cnt = 0, i;
int v = *val;
for (i=0; i<n; ++i) {
if (tab.l_quantity[i] > v) {
cnt++;
}
}
return cnt;
}
先ほどと同じ条件とデータで実行してみます。
 |
| カラム型データ構造時のperfの結果 |
どうでしょう？
キャッシュミスが大きく減少しました(1/100程度)。それにともなって、CPT(1行を処理するのに必要な平均CPUサイクル数)やIPC(CPU命令の実行効率)が大きく改善されるSELECTIVITYがある事が分かりますね。
ただ、データ構造を変えただけだと、最初のロー型(を模したもの)に比べてSELECTIVITYによる分岐予測ミスが増減する傾向に変化はありません。(最終的には、CPTもSELECTIVITYによって悪化する傾向に変化はありません)
カラム型をイメージしつつブランチフリーなバージョン
次は、この分岐ミスをなくすようにコードを書き換えてみます。
(* SIMDに行く前に通らねばならない道ですので)
int select_count_gt_columnar_branch_free(int n, LARGE_TABLE_t* tab, int* val)
{
int cnt = 0, i;
int v = *val;
for (i=0; i<n; ++i) {
cnt += (tab.l_quantity[i] > v)
}
return cnt;
}
上記は、WHERE句の条件がTRUEであろうがFALSEであろうがcntという変数を加算します。ただしTRUEは1、FALSEは0という言語仕様を利用しています。これは、分岐せずに常に一定の処理(ここではcnt変数への加算)を実行するため、CPUインストラクション数は増加しますが、分岐ミスが減少し、分岐ミスによるパイプラインハザードのペナルティを払わない方がCPUサイクルを消費しないであろうとの仮定の上に成り立っています。
では、結果を見てみましょう。
 |
| カラム型データ構造かつブランチフリー時のperfの結果 |
どうでしょうか？SELECTIVITYに依存せず、どのような条件下でも一定のパフォーマンスを出すことが出来ていますね。分岐予測ミス恐ろしや。
カラム型をイメージしつつSIMD(SSE)なバージョン
それでは最後に、さらにパフォーマンスを上げたい(というか、さらに最適化させたい)ので、SIMDを使ったコードに書き換えてみます。
x86系プロセッサではSIMDとしてSSEやAVXがサポートされています。SSEは128ビット幅のレジスターを使っていて、AVXからは256ビット幅のレジスターを使えます。
では、SSE(128ビット幅)のコードを以下に示します。
int select_count_gt_sse(int n, LARGE_TABLE_t* tab, int *val)
{
int cnt = 0, i;
int v = *val;
__m128i vec, cmp, msk;
cmp = _mm_set1_epi32(v);
for (i = 0; i<n; i+=4) {
vec = _mm_load_si128((__m128i*)&tab.l_quantity[i]);
msk = _mm_cmpgt_epi32(vec, cmp);
cnt += _mm_popcnt_u32(_mm_movemask_ps((__m128)msk));
}
return cnt;
}
少しだけ説明すると
_mm_set1_epi32()
比較対象(ここでは50)のINT型を128ビットレジスターに登録します(INT型は32ビットなので、128ビットレジスターには4つ同時に格納されます)
_mm_load_si128()
比較元のデータを4つ分(INT(32ビット)を128ビット分)SIMDのレジスターに登録します。
_mm_cmpgt_epi32()
上記のレジスター2つを一気に比較します。その戻りは、128ビットレジスターに真なら32ビット分の0xff....f、偽なら0となります。
_mm_movemask_ps()で
先ほどの32ビットマスクをINTに変換し、_mm_popcnt_u32()で、INT中に1のフラグが立っている数を数えます。
少々、見慣れませんが、まぁ、そんな感じです。
では、結果を見てみましょう。(基本的に他と変化のあるCPTとIPCのみチャート化)
 |
| カラム型データ構造かつSIMD(SSE)処理時のperfの結果 |
どうでしょう？
先ほどのブランチフリー版にくらべて、IPCが少し落ちていますが、CPU命令数が減少したおかげで、CPTが減少していることが分かりますね。
蛇足でSIMD(AVX2)なバージョン
おまけでAVX(正確にはAVX2の256ビット幅のレジスター)でも実験
* 実際に256ビット幅で整数を扱おうとするとAVX2が必要で、AVX2はHaswellからのサポートです。
int select_count_gt_avx(int n, LARGE_TABLE_t* tab, int *val)
{
int cnt = 0, i;
int v = *val;
__m256i vec, cmp, msk;
cmp = _mm256_set1_epi32(v);
for (i = 0; i<n; i+=8) {
vec = _mm256_loadu_si256((__m256i*)&tab.l_quantity[i]);
msk = _mm256_cmpgt_epi32(vec, cmp);
cnt += _mm_popcnt_u64(_mm256_movemask_ps((__m256)msk));
}
return cnt;
}
結果は以下のようになります。
 |
| カラム型データ構造かつSIMD(AVX)処理時のperfの結果 |
どうでしょう？
AVX2使用時はSSE時と比較してレジスター幅が倍増している恩恵をきちんと受けていることが分かりますね。
これで、本当に最後ですが、各処理(ロー型、カラム型、ブランチフリー、SSE、AVX2)での処理時間のチャートを示しておきます。
まとめめいたもの
少しだけ、まとめめいたものを書くとすると、大量のデータを効率良く処理するときには
- CPU命令の効率を上げること
- 1行処理するのにかかるCPUサイクルを少なくすること
を考えないといけない。
その時にネックになるのは、
- CPUキャッシュミス
- 分岐予測ミス
とか。
これらをなるべく排除する方法として
- カラム型のデータ構造(これはIn-Memoryに特化した話ではないですが、ここでは、In-Memoryという流れで書いています)
- 分岐予測をミスさせない(そもそも分岐させない)アルゴリズム
- CPU命令自体を減少させてCPUサイクルを下げようとするSIMD命令
等があるというのが私の理解です。さらには、SIMDを使うには、そもそもデータ構造(ロー型とかカラム型)を最初に考えていないと効率よく使えないような気がしているし、SIMDを使って効率良く処理にするには分岐が沢山あっちゃいけない気もしています。
という事で、最初に上げたキーワード(In-Memory、カラム型、SIMD)は私の中では、かなりつながった感があります。
ちょっと長いエントリになってしまいましたが、私の理解するIn-Memoryとかカラム型とかSIMDとかの気持ちが分かってもらえたでしょうか？
それでは、皆様よいクリスマスを！
コメント
コメントを投稿