DSIRNLP #3 LZ4 の速さの秘密に迫ってみる
- 1. LZ4 の 速さの秘密に 迫ってみる DSIRNLP #32012.9.30 KOMIYA Atsushi (@komiya_atsushi) 1
- 2. Who ? 2
- 3.
- 4.
- 5.
- 6.
- 7. #TokyoWebmining 運営 7
- 8. Agenda 1. What isLZ4 ? 2. Dictionary compression 3. Why fast ? 4. Conclusion 8
- 9. おことわり •LZ4 の •使い方の話はしません •仕様の話もほとんどしません •速く処理をするための工夫にのみ着目 してお話しします 9
- 10. What is LZ4? 10
- 11. What is LZ4? URL : http://fastcompression.blogspot.jp/p/lz4.html http://code.google.com/p/lz4/ 11
- 12. What is LZ4? URL : http://fastcompression.blogspot.jp/p/lz4.html http://code.google.com/p/lz4/ 非常に高速な 圧縮アルゴリズム 12
- 13. How fast ? •snappy_unittest.cc に手を加えて計測 • テストデータ：enwik8 (http://mattmahoney.net/dc/textdata.html) 13
- 14. How fast ? •snappy_unittest.cc に手を加えて計測 • テストデータ：enwik8 (http://mattmahoney.net/dc/textdata.html) [MB/s] slow fast 14
- 15. How fast ? •snappy_unittest.cc に手を加えて計測 • テストデータ：enwik8 (http://mattmahoney.net/dc/textdata.html) vs. snappy x1.73 faster (comp.) x1.23 faster (decomp.) [MB/s] slow fast 15
- 16. Compression ratio [%] good bad 16
- 17. Compression ratio [%] good bad 速度重視の他ライブラリ（snappy / lzo）と 比較しても遜色ない圧縮率 17
- 18. Dragon Quest Xand LZ4 18 引用元 (Gigazine)：http://gigazine.net/news/20120824-dragonquest-backstage-cedec2012/
- 19. Hadoop and LZ4 19 引用元 : https://issues.apache.org/jira/browse/HADOOP-7657
- 20. … and somefeatures •Scalability : multi-threading •Support ARM processors •BSD License •Bindings •C# / Java / Python / Perl / JS / PHP / Ruby / LUA / Go / Haskell / Erlang 20
- 21.
- 22. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 22
- 23. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 23
- 24. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 【例】 おまえのものはおれのもの、おれのものもおれのもの 24
- 25. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 【例】 おまえのものはおれのもの、おれのものもおれのもの 原則として、１文字ずつ 左から右へ読み進める 25
- 26. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 【例】 おまえのものはおれのもの、おれのものもおれのもの いま着目している文字列（右側）が、 過去（左側）のどの場所にどの長さで 出現したのか？ を求める 26
- 27. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 【例】 ここに着目 おまえのものはおれのもの、おれのものもおれのもの いま着目している文字列（右側）が、 過去（左側）のどの場所にどの長さで 出現したのか？ を求める 27
- 28. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 【例】 ここに着目 おまえのものはおれのもの、おれのものもおれのもの いま着目している文字列（右側）が、 過去（左側）のどの場所にどの長さで 出現したのか？ を求める 28
- 29. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 【例】 ここに着目 おまえのものはおれのもの、おれのものもおれのもの いま着目している文字列（右側）が、 過去（左側）のどの場所にどの長さで 出現したのか？ を求める 29
- 30. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 【例】 おまえのものはおれのもの、おれのものもおれのもの 一致情報（場所、長さ）を符号化する 30
- 31. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 【例】 おまえのものはおれのもの、おれのものもおれのもの おまえのものはおれ(6,3)、(6,5)も(6,5) 31
- 32. Dictionary compression •gzip (zlib)などど同じスライド窓ベース の辞書式圧縮アルゴリズムを採用 【例】 おまえのものはおれのもの、おれのものもおれのもの おまえのものはおれ(6,3)、(6,5)も(6,5) ６つ前の３文字と 一致しているよ！ 32
- 33. Pattern matching problem •辞書式圧縮アルゴリズムは 「文字列照合問題」 「文字列探索問題」 と捉えることができる 33
- 34. Why fast ? 34
- 35.
- 36. 機能をちょっと 制限する 36
- 37. API 構成 37
- 38.
- 39. API 構成 •ブロック単位での圧縮・伸長のみをサポート データ 39
- 40. API 構成 •ブロック単位での圧縮・伸長のみをサポート データ ブロック ブロック ブロック ブロック ライブラリ利用者がブロックに分割する 40
- 41. API 構成 •ブロック単位での圧縮・伸長のみをサポート データ ブロック ブロック ブロック ブロック LZ4_compress() LZ4_compress() LZ4_compress() LZ4_compress() それぞれのブロックごとに API を呼び出す 41
- 42. API 構成 •ブロック単位での圧縮・伸長のみをサポート データ ブロック ブロック ブロック ブロック LZ4_compress() LZ4_compress() LZ4_compress() LZ4_compress() 圧縮済み 圧縮済み 圧縮済み 圧縮済み 42
- 43. API 構成 •ブロック単位での圧縮・伸長のみをサポート •ブロックごとに API を呼び出す • ブロックの大きさは任意（<1.9GB）に指定できる •デメリット • zlib のようなストリーム処理ができない •メリット • API 側の実装がシンプルになる（co-routine 的な 実装をしなくていい） • API 呼び出しをマルチスレッド化できる 43
- 44. 泥臭い努力をする 44
- 45.
- 46. 2/4/8 バイト単位でまとめてアクセス •バイト列をまとめて処理したいことが よくあります •２つのバイト列の比較 •バイト列のコピー（memcpy()） •ハッシュ値の計算 • 連続する４バイトをハッシュ値計算に使う •バイト列のまま、１バイトずつ処理し ていては効率がよくない… 46
- 47. 2/4/8 バイト単位でまとめてアクセス •byte のポインタを word / dword / qword のポインタと してアクセスすれば、複数バイトを まとめて処理できるようになる！ •アライメントの境界をまたいで アクセスすると怒られる CPU 向けに、 ちょっと工夫が必要 47
- 48. 2/4/8 バイト単位でまとめてアクセス アライメントの境界を超えてメモリアクセスすると エラーとなってしまう環境のために、構造体経由で アクセスする 48
- 49.
- 50. 探索を端折る 50
- 51. ハッシュ表による探索 51
- 52. ハッシュ表による探索 •ハッシュ表で４バイトの一致がある場所を 検出する •連続する４バイトをハッシュして key とする • value はその４バイトの出現位置 •デメリット • ハッシュ衝突により、一致を検出できない ことがある（衝突したら諦める） •メリット • 定数オーダーで一致があるかないかを判別 することができる 52
- 53. ハッシュ表による探索 圧縮対象の文字列 GrapeAppleGrapefruit 今着目しているこの文字列に ハッシュ表 一致する場所を探そう hashTable[ 0] : 7 “pleGrapefr...” ・・・ hashTable[12] : 2 “apeAppleGr...” hashTable[13] : 5 “AppleGrape...” ・・・ hashTable[27] : 1 “rapeAppleg...” ・・・ hashTable[33] : 0 “GrapeApple...” ・・・ hashTable[36] : 3 “peAppleGra...” 53 ・・・
- 54. ハッシュ表による探索 圧縮対象の文字列 GrapeAppleGrapefruit “eGra” のハッシュ値は 27 ハッシュ表 hashTable[ 0] : 7 “pleGrapefr...” ・・・ hashTable[12] : 2 “apeAppleGr...” hashTable[13] : 5 “AppleGrape...” ・・・ hashTable[27] : 1 “rapeAppleg...” ・・・ hashTable[33] : 0 “GrapeApple...” ・・・ hashTable[36] : 3 “peAppleGra...” 54 ・・・
- 55. ハッシュ表による探索 圧縮対象の文字列 GrapeAppleGrapefruit ハッシュ表 hashTable[ 0] : 7 “pleGrapefr...” ・・・ hashTable[12] : 2 “apeAppleGr...” hashTable[27] のエントリ hashTable[13] : 5 “AppleGrape...” とは文字列が一致しないの ・・・ で、エントリを上書きして hashTable[27] : 9 “eGrapefrui...” 次に進む ・・・ hashTable[33] : 0 “GrapeApple...” ・・・ hashTable[36] : 3 “peAppleGra...” 55 ・・・
- 56. ハッシュ表による探索 圧縮対象の文字列 GrapeAppleGrapefruit 次の “eGra” のハッシュ値 ハッシュ表 は 33 hashTable[ 0] : 7 “pleGrapefr...” ・・・ hashTable[12] : 2 “apeAppleGr...” hashTable[13] : 5 “AppleGrape...” ・・・ hashTable[27] : 9 “eGrapefrui...” ・・・ hashTable[33] : 0 “GrapeApple...” ・・・ hashTable[36] : 3 “peAppleGra...” 56 ・・・
- 57. ハッシュ表による探索 圧縮対象の文字列 GrapeAppleGrapefruit 次の “eGra” のハッシュ値 ハッシュ表 は 33 hashTable[ 0] : 7 “pleGrapefr...” ・・・ hashTable[12] : 2 “apeAppleGr...” hashTable[13] : 5 “AppleGrape...” ・・・ hashTable[27] : 9 一致 “eGrapefrui...” ・・・ hashTable[33] : 0 “GrapeApple...” ・・・ hashTable[36] : 3 “peAppleGra...” 57 ・・・
- 58. ハッシュ表による探索 圧縮対象の文字列 GrapeAppleGrapefruit ハッシュ表 hashTable[ 0] : 7 “pleGrapefr...” ・・・ hashTable[12] : 2 “apeAppleGr...” hashTable[13] : 5 “AppleGrape...” hashTable[33] のエントリ ・・・ と文字列が５文字一致する hashTable[27] : 9 “eGrapefrui...” ので圧縮する（＆エントリ ・・・ を上書きする） hashTable[33] : 10 “Grapefluit...” ・・・ hashTable[36] : 3 “peAppleGra...” 58 ・・・
- 59. 探索位置をスキップする 59
- 60. 探索位置をスキップする •圧縮しにくい（=一致するものがない） 文字列の並びを読み飛ばす仕組み •snappyでも採用されている •スキップの幅を少しずつ広げる 60
- 61. 探索位置をスキップする •圧縮しにくい（=一致するものがない） 文字列の並びを読み飛ばす仕組み •snappy でも採用されている •スキップの幅を少しずつ広げる hogelNieafhInknQVS4Swk2QwOZmzSOthogehogehoge 61
- 62. 探索位置をスキップする •圧縮しにくい（=一致するものがない） 文字列の並びを読み飛ばす仕組み •snappy でも採用されている •スキップの幅を少しずつ広げる hogelNieafhInknQVS4Swk2QwOZmzSOthogehogehoge 最初は １文字ずつ 62
- 63. 探索位置をスキップする •圧縮しにくい（=一致するものがない） 文字列の並びを読み飛ばす仕組み •snappy でも採用されている •スキップの幅を少しずつ広げる hogelNieafhInknQVS4Swk2QwOZmzSOthogehogehoge なかなか一致が 見つからないなら、 ２文字おきに探す 63
- 64. 探索位置をスキップする •圧縮しにくい（=一致するものがない） 文字列の並びを読み飛ばす仕組み •snappy でも採用されている •スキップの幅を少しずつ広げる hogelNieafhInknQVS4Swk2QwOZmzSOthogehogehoge それでも見つからなければ ４文字おきにする 64
- 65. 探索位置をスキップする •圧縮しにくい（=一致するものがない） 文字列の並びを読み飛ばす仕組み •snappy でも採用されている •スキップの幅を少しずつ広げる 一致 hogelNieafhInknQVS4Swk2QwOZmzSOthogehogehoge 一致する文字列が見つかった ところでリセットする 65
- 66. 探索位置をスキップする •圧縮しにくい（=一致するものがない） 文字列の並びを読み飛ばす仕組み •snappyでも採用されている •スキップの幅を少しずつ広げる •デメリット •圧縮できる文字列を取りこぼしてしまう •メリット •無駄な比較の回数を減らすことができる 66
- 67.
- 68. 【参考】スキップされた一致の回収 •スキップにより取りこぼされてしまっ た文字列の一致をちょっとだけ回収す るしくみ •後方方向だけでなく、前方にも向かって 一致を確認する 68
- 69. 【参考】スキップされた一致の回収 •スキップにより取りこぼされてしまっ た文字列の一致をちょっとだけ回収す るしくみ •後方方向だけでなく、前方にも向かって 一致を確認する 一致 hogefugalNi … ZmzSOthogefugahoge 4文字の一致が見つかった 69
- 70. 【参考】スキップされた一致の回収 •スキップにより取りこぼされてしまっ た文字列の一致をちょっとだけ回収す るしくみ •後方方向だけでなく、前方にも向かって 一致を確認する 後に続く ga が一致している hogefugalNi … ZmzSOthogefugahoge 70
- 71. 【参考】スキップされた一致の回収 •スキップにより取りこぼされてしまっ た文字列の一致をちょっとだけ回収す るしくみ •後方方向だけでなく、前方にも向かって 一致を確認する さらには前に続く ho も一致 している（計8文字の一致） hogefugalNi … ZmzSOthogefugahoge 71
- 72. 【参考】スキップされた一致の回収 •スキップにより取りこぼされてしまっ た文字列の一致をちょっとだけ回収す るしくみ •後方方向だけでなく、前方にも向かって 一致を確認する •メリット •時間性能に大きな影響を与えることなく 圧縮性能を改善できる 72
- 73.
- 74. 一致長の算出 ２つの文字列の一致長を高速に求めたい… きみがためはるののにいでてわかなつむ … きみがためをしからざりしいのちさへ … 74
- 75. 一致長の算出 ２つの文字列の一致長を高速に求めたい… きみがためはるののにいでてわかなつむ … きみがためをしからざりしいのちさへ … １文字ずつ比較すれば 確実！ （けど遅い…） 75
- 76. 一致長の算出 •概要 • ハッシュ表により検出された４文字の一致に 続く、後続の一致文字数を算出する •戦略 1. 4 or 8 バイトの単位でざくざく一致を確認 • 32bit 環境は 4 バイト、64bit 環境は 8 バイト 単位 2. 上記単位での不一致が見つかったところで、 厳密な一致長を確定する 76
- 77. ざっくりと一致を確認する 77
- 78. ざっくりと一致を確認する •２つの文字列を４or８バイトずつずら しながら XORをとる •XOR の結果が 0 なら一致しているよね •XOR の結果が 0 でなければ一致してない よね • 後述する処理により、何バイトの一致があっ たのかを厳密に算出する 78
- 79. ざっくりと一致を確認する 一致 FooBarBarBarFooBarBarBaz 最初の４バイトの一致が見つかった状態 79
- 80. ざっくりと一致を確認する FooBarBarBarFooBarBarBaz ‘arBa’ ⊕ ‘arBa’=0 続く４バイトの XOR の結果が 0 なら次の４バイトへ 80
- 81. ざっくりと一致を確認する FooBarBarBarFooBarBarBaz ‘rBar’ ⊕ ‘rBaz’!=0 XOR の結果が 0 でないところで ざっくり一致長の算出を終える 81
- 82. 一致長を厳密に確認する 82
- 83. 一致長を厳密に確認する •早い話が、LSB を求める問題になる •４or８バイトの XORの結果(!=0)から以下 の方法で算出 • x86 の bsr 命令を利用する • [VC] _BitScanReverse/_BitScanReverse64() • [gcc] __builtin_clzll() • 頑張って計算する • 二分探索 • De Bruijn 数列を利用 83
- 84. 一致長を厳密に確認する •De Bruijn 数列を使ったLSB ぽい計算 •条件分岐を一切排除することができる • 補数 • ビット積 • 乗算 • ビットシフト • ルックアップテーブル参照 詳細は右記URLを参照：http://fastcompression.blogspot.jp/2011/12/fast-sequence-comparison.html 84
- 85. 細かいことは しない 85
- 86. 辞書式圧縮アルゴリズムの出力 •出力されるもの •リテラル文字列（圧縮できない文字列） •リテラルの長さ •一致した場所の情報 •一致した長さ •圧縮率を高めるにはビット単位で出力 したいところ •Huffman 符号／算術符号などを利用 86
- 87.
- 88.
- 89. Conclusion 89
- 90.
- 91.
- 92. We’re hiring !!! 分析力をコアとする情報最適化企業 では、一緒に楽しくお仕事できる エンジニアを募集しています！ 92
- 93. こちらも募集中！ データマイニング＋WEB勉強会＠ 東京（#TokyoWebmining）では スピーカーを大絶賛募集中です！ https://groups.google.com/forum/?fromgroups=#!forum/webmining-tokyo 93