Cache-Oblivious データ構造入門 @DSIRNLP#5

「データ構造と情報検索と言語処理勉強会」にお邪魔して，「Cache-Oblivious データ構造入門」という発表をさせてもらいました．

新年会 + データ構造と情報検索と言語処理勉強会 #DSIRNLP 5 - 参加者は何か発表してネスペシャル - PARTAKE

Cache-Oblivious データ構造入門 @DSIRNLP#5 from Takuya Akiba

実はこういうインターネットから集う感じのいわゆる勉強会に参加するのは初めてでした．発表も初めてなので結構緊張していて大変だったのですが，参加者の皆さんがとても優しくて助かりました．懇親会 (新年会) もとても楽しかったです．主催の overlast さん，会場を提供してくださっていたスマートニュースさん，どうもありがとうございました．

発表の内容は以下のような感じです．

DB の索引としての B 木の利点の復習
Cache-Oblivious の考え方
vEB レイアウト (Cache-Oblivious の例)
実際の事例紹介 (TokuDB)

ちなみに，実況ツイートをしてくださっていた方々の説明が大変良い要約になっています（僕の舌足らずの説明よりよっぽどわかりやすい，ありがとうございます！）．ハッシュタグつきのツイートを適当に引用させてもらいます．一方で，データ構造の説明部分は図を見てもらえば結構一発に近いと思うのでそちらを見てもらえればと思います．

#DSIRNLP 7つ目は @iwiwi さんによる Cache-Oblivious データ構造入門。MySQL など多くのデータベースは B-Tree を使っているが、二分探索木がダメなのはなぜ？メモリとディスクをうまく組み合わせて性能を出すため。説明いつもうまいな〜

2014-01-11 15:35:26 via Echofon

#DSIRNLP 前提1ディスクアクセス時間 >> 計算時間、前提2ディスクは一度に読み込むのはそこそこ速い。一度に読み込むサイズを B とすると、B-Tree は二分探索木より log_B 倍速い。ディスクとメモリを使うなら、それを考慮したデータ構造を設計する必要がある。

2014-01-11 15:38:27 via Echofon

#DSIRNLP B-Tree は読み込みサイズ B を値を使うことでディスクの読み込みの計算量を下げることができる。Cache-Oblivious データ構造は B を使ってはいけない、という設定。縛りプレイ。利点は、ポータブルかつ全てのメモリ階層でそこそこよく最適化できる。

2014-01-11 15:41:46 via Echofon

大規模データを扱うアルゴリズムは、CPUが充分速い状況において一番遅いデバイス（メモリ-キャッシュ間かもしれないし、メモリ-ディスク間かもしれないし、ローカルのSSDキャッシュ-NAS間かもしれない）によって律速されるのでそこを最も効率化する方法から考えるのよね #DSIRNLP

2014-01-11 15:41:51 via web

再帰的に分割した時にサイズがB以下になった領域がディスク上の連続領域に格納されるため、その部分構造がB木の1ノードに対応しているように見ることができる #DSIRNLP

2014-01-11 15:46:08 via web

#DSIRNLP vEB レイアウトは二分探索木を上下に分割して再帰的にエンコード。ブロックサイズ B を知らなくてもディスクの読み込みを O(log_B n) にできる。なぜか？再帰的に探索すると、読み込みサイズが B 以下になったら一度に読めるから。

2014-01-11 15:47:59 via Echofon

MySQL/MariaDB 向けストレージエンジンの TokuDB の Fractal Tree Indexing が Cache-Oblivious ではないか？という話。 #DSIRNLP

2014-01-11 15:50:16 via Twitter for Mac

#DSIRNLP Cache-oblivious データ構造はよさげなのにあまり使われていないらしい。なぜか？計算量では定数倍の部分が無視されるが、実際は定数倍のところが大きい。また、実装が大変。そして、現実的には Cache-aware データ構造に勝てないことが多い。

2014-01-11 15:51:14 via Echofon