Upgrade to Pro — share decks privately, control downloads, hide ads and more …

[IM@S Engineer Talks 2019] Ut Video Codec Suite...

[IM@S Engineer Talks 2019] Ut Video Codec Suite 高速化の11年 / [IMAS Engineer Talks 2019] 11-year optimization of Ut Video Codec Suite

IM@S Engineer Talks 2019 (https://imas.connpass.com/event/134735/) で発表した、 11年にわたって Ut Video Codec Suite (https://github.com/umezawatakeshi/utvideo) を高速化した内容を発表するプレゼンテーションです。

More Decks by 梅澤威志 / UMEZAWA Takeshi

Other Decks in Technology

Transcript

  1. 自己紹介 • 梅澤威志 / ゆーむP – 本業は某ネット企業の ソフトウェアエンジニア • Blog:

    http://umezawa.dyndns.info/wordpress/ • GitHub: https://github.com/umezawatakeshi – 箱マスからのアイマスP – ニコマスも少々 • ニコ百: https://dic.nicovideo.jp/a/ゆーむp – 響P • ぬーかわ
  2. Ut Video Codec Suite is 何 • 映像キャプチャ向け可逆圧縮コーデック • 各種プラットフォームで使えた(過去形(涙

    • http://umezawa.dyndns.info/wordpress/?cat=28 • https://github.com/umezawatakeshi/utvideo • FFmpeg に互換実装がある
  3. いろんなところで使われている (2) • 海外に紹介されたり • FFmpeg に互換実装が追加されたり D:¥ffmpeg-4.1.3-win64-static¥bin>ffmpeg.exe -codecs ffmpeg

    version 4.1.3 Copyright (c) 2000-2019 the FFmpeg developers built with gcc 8.3.1 (GCC) 20190414 (中略) Codecs: D..... = Decoding supported .E.... = Encoding supported ..V... = Video codec ..A... = Audio codec ..S... = Subtitle codec ...I.. = Intra frame-only codec ....L. = Lossy compression .....S = Lossless compression ------- (中略) D.VIL. txd Renderware TXD (TeXture Dictionary) image D.V.L. ulti IBM UltiMotion (decoders: ultimotion ) DEVI.S utvideo Ut Video DEVI.S v210 Uncompressed 4:2:2 10-bit D.VI.S v210x Uncompressed 4:2:2 10-bit (以下略)
  4. エースコンバット6をキャプりたかった • 2007年にエスコン6のプレイ動画をHD (720p) でキャプりたかった – 非圧縮 YUV422 だと 1280x720x2x60=約110MB/s

    • 今なら単発HDDでもこれぐらい出るが当時は無理だっ た(最外周の一番速いところでも70MB/sぐらい) • SSDもまだまだバカ高かった – 何らかの圧縮をしてからHDDに保存する必要が ある – ちなみにできた動画が https://www.nicovideo.jp/watch/sm1770031
  5. ちかたない • 自分に需要がある – 他人にもたぶん需要がある • 自分に作る能力がある • 作ることに対する興味がある •

    ので作る • 年末ごろからどういう方向で作るかを考え始 めた(…と記憶している(曖昧
  6. 圧縮手法 • 大枠としては Huffyuv と変わらない – 異なる圧縮原理を考えるような脳みそは無い • Huffyuv が(時代背景のせいで)できなかった

    ことをやることによって性能を向上させる • 説明(手法の必然性)の理解しやすさの観点 から、圧縮の処理順序の逆順で説明する
  7. 圧縮手法 – フレーム内予測 (2) • 予測タイプは現在3種類ある – left – 左の値を予測値とする

    – gradient – 左、上、左上の値からなる1次関数で 予測値を得る • 予測値 = left + top – topleft – median – 左、上、 gradient の3つのうちの中央値 を予測値とする • 予測値 = median(left, top, gradient) – UtVideo においては median, left, gradient の順に 実装した
  8. 圧縮手法 – フレーム内予測 (3) • 予測値の計算(と予測値との差の計算)は3 種類とも SIMD 化できる –

    ピクセル間に依存関係がないので、ちゃんと要素 数分だけ速くなる – SIMD (Single Instruction Multiple Data) 複数のデータに対して同一の処理をまとめて行う 並列化体系のこと
  9. 圧縮手法 – フレーム内予測 (4) • 予測の復元(「予測値との差」だけがある状態 から元の値を計算する)は、 median の場合 SIMD

    化できない – 前のピクセルの値が次のピクセルの予測値の計 算に使われており、しかも式が線形ではないから • gradient と left は線形なので、要素数分とま では行かないが SIMD 化で速くなる
  10. 唐突に x86 のレジスタ構成 • x86 のレジスタはこういう形式でアクセスでき るようになっている – EBX, ECX,

    EDX もある (他にもあるけど割愛) • EAX に 0x12345678 を入れると、 AX として見 ると 0x5678、 AH は 0x56、 AL は 0x78 となる – ここで AL に 0x90 を入れると AX は 0x5690 になる
  11. 細かいデザイン (2) • CL レジスタに符号語長が入ると都合が良い – x86 の可変シフト命令ではシフトするビット数を CL レジスタで指定するため

    • ECX レジスタの上位 24bit が空いてるので符 号語を入れる – 符号語長と符号語を一発で ECX にロードできる
  12. 1.1.3 (2008-04-18) • 最初の public release • 予測タイプは median のみ

    • 全部 C++ で書いてあるしシングルスレッド • 遅い • 合計約2000行
  13. 2.2.0 (2008-05-07) • ハフマン符号の符号化/復号化 と フレーム内 予測の予測/復元 をアセンブリ言語で書いた – 特に、コンパイラが吐いてくれない命令を駆使す

    ることで高速化した • SHLD – ハフマン符号化/復号化 • BSR – ハフマン復号化 • CMOVcc – フレーム内予測 – これでおおむね Huffyuv と同程度の速度になっ た
  14. 3.3.0 (2008-05-17) • 部分レジスタストールを回避するように書き 換えて predict median の復元を高速化 – 長いレジスタ(たとえば

    EAX)の部分(たとえば AL)を更新した後に、更新した場所以外を含む領 域を使おうとすると、部分の更新を一旦全体に結 合するためにペナルティがかかる。これを部分レ ジスタストールという – readme によるとハフマン符号等も含めた全体で 20% ほど速くなったらしい(単体だと50%ぐらい?
  15. 3.3.0 (2008-05-17) (2) • SHLD 命令の使い方が甘かったのを改良して ハフマン符号の符号化を高速化 – 元の符号化のコードは C++

    で書いたものをその ままアセンブリ言語で書き直した感じの物で、あ まり効率が良くなかった
  16. 3.7.0 (2008-06-07) • predict median の復元で CMOVcc 命令を駆 使する代わりに MMX

    の PMAX/PMIN 命令を 使って高速化 – MMX は SIMD 命令セットであるが、この修正では 最大値/最小値を一発で計算する命令を単一要 素に対して使っている(CMOVcc 命令はそれほど 速くない • この時の blog に「肝心のハフマンデコードが速くな らないのでそろそろ限界が…」とか書いてある
  17. 3.8.0 (2008-06-10) • ハフマンデコードが速くならないので諦めて predict left フレーム内予測方式を追加 – それなりにややこしい処理をする predict

    median と比べると単純であり、復元がハフマン復号化の ついでにできるので圧倒的に高速である(デコー ドは全体で1.5倍速 – 代わりに圧縮比は下がる
  18. 7.0.0 (2009-10-22) • x64 版を追加 – ちなみに Windows 7 の発売日あわせである

    – UtVideo のバージョンも 7 なのはたまたま – とりあえず全部 C++ で書いてある(昔からある C++ コードが使われる)ので非常に遅い
  19. 7.1.0 (2010-04-04) • AMD Athlon (K10 マイクロアーキテクチャ)で RGB/RGBA の処理が猛烈に遅い問題の解決 –

    具体的には全体で3倍ぐらい遅かった – RGB/RGBA の場合、 planar 変換時に各 plane の ポインタが同じ速度で進む – 各 plane バッファの先頭アドレスはそれぞれ「キリ がいい」ので、各ポインタが常にキャッシュの同じ エントリアドレスを指す
  20. 7.1.0 (2010-04-04) (2) – K10 だと1次キャッシュが 2way セットアソシアティ ブなので、メモリアクセスするたびにキャッシュが スラッシングして猛烈に遅かった

    – 対策として、最初からずらしておけば、今度は絶 対に同じエントリアドレスにはならない – https://speakerdeck.com/umezawatakeshi/x86- x64-optimization-study-4-ut-video-codec-suite-is- slow-on-amd-processors を参照
  21. 8.3.0 (2010-10-11) 8.4.0 (2010-10-17) • predict left で native なフォーマットへのデ

    コードで、ハフマン復号化の出力を planar 形 式を経由せずに直接フレームバッファに書き 込むようにして高速化 – predict left の場合ハフマン復号化のついでにフ レーム内予測の復元をすることが現実的 – メモリコピーと変換処理が削減された
  22. 12.1.0 (2013-04-23) • packed <-> planar 変換を SIMD 化して高速化 –

    Sandy Bridge (Core i 2000 series) だとシャッフル命 令が十分に速い • 2008年ごろは開発マシンに Merom (Core 2 Quad Q6600) を使っており、 シャッフル命令が速くなかった せいで逆に遅くなっていた – ちなみにシャッフル命令が「だいぶ速くなった」の は Penryn (Merom の次)である。
  23. 12.1.0 (2013-04-23) (2) – RGBA の変換の場合、 • 以前は 64 シンボル処理するのに

    64 クロック • SIMD 化すると Sandy Bridge で 6 クロック – Merom で走らせるとたぶん 24 クロック あれ、なんで遅くなるんだ…?
  24. 13.2.0 (2013-09-21) • x64 で、64bit レジスタを駆使することで SHLD 命令を回避してハフマン復号化を高速化した – SHLD

    命令は結構遅いので • Haswell マシン (Core i7-4770) を調達したので BMI2 命令 (SHLX, SHRX) を使ってさらに高速 化 • 両方合わせて Haswell なら最大25%高速化
  25. 17.2.0 (2016-12-30) • ハフマン復号化で、テーブル1回の lookup で 複数シンボル同時に出力するようにして劇的 に高速化した – ハフマン復号化単体で言うと倍ぐらい行ける

    – ただし、復号化のついでに predict left の復元を やることができなくなる(やろうとすると複雑すぎ て遅くなる)ので、デコード全体としてはそこまで ではない
  26. 18.0.0 (2017-04-01) • predict gradient フレーム内予測方式を追加 – 圧縮比が predict left

    より高めで、かつ SIMD 化 のしやすさは left と同程度、といういいことづくめ – 圧縮比が高いとメモリアクセス等が減るので、結 果的に速くなる – 今まで実装を避けていたのを後悔するレベル
  27. 20.2.0 (2019-01-14) (2) – 2シンボルずつ符号化する場合、エンコードテー ブルが1次キャッシュ (32KB) どころか2次キャッ シュ (256KB)

    にも収まらない • 1シンボルずつなら 8B x 256エントリ = 2KB であるが、 2シンボルずつだと 8B x 64Kエントリ = 512KB – 一方、シンボルの出現確率には偏りがあるので、 よくアクセスされるのは 256KB の範囲に収まると みなして構わない
  28. 20.2.0 (2019-01-14) (3) – 2次キャッシュにおおむね収まるなら、レイテンシ の増加による性能劣化を上回って高速化できる • 2次キャッシュのレイテンシは1次キャッシュの 3倍であ るが、ループアンローリングのついでに先行して符号

    語をロードすることでレイテンシを完全に隠蔽できる – x64 だとレジスタが多いのでこういうことが可能 – 結果としてハフマン符号化だけを見ると倍速で処 理できるようになった
  29. 20.3.0 (2019-03-14) 20.5.0 (2019-05-09) • 一時バッファとしての planar フォーマットを経 由せず、レジスタ上で処理してメモリアクセス を削減することで、特にマルチスレッド時の高

    速化をした – マルチスレッド時はコアの処理速度ではなくメイン メモリの帯域で律速しているから – 極端な計測条件だと倍速になる
  30. 20.3.0 (2019-03-14) (3) 20.5.0 (2019-05-09) (3) • 複数 plane 同時に処理することになるので、

    ついでに predict median の復元の効率化が 図られてそこでも高速化した – 同じ plane の前のピクセルには依存関係がある が、異なる plane のピクセルには依存関係がない ので並列処理可能
  31. 結局どこまで速くなったか Core i7-4770 / 8.4.0 までは x86 8.5.0 からは x64

    マルチスレッド / predict median / crowd_run 4K 0.00 20.00 40.00 60.00 80.00 100.00 120.00 140.00 160.00 180.00 200.00 1.1.3 2.1.0 2.2.0 3.3.0 3.7.0 3.8.0 8.2.0 8.4.0 8.5.0 12.1.0 12.2.1 13.2.0 17.2.0 18.0.0 20.2.0 20.5.0 fps encode decode 60倍
  32. One More Thing… • 19.0.0 の時に SIMD にやさしいフォーマットと して UtVideo

    T2 を 追加した – いかんせん圧縮原理(ハフマン符号)が SIMD 化 できないため速度は早晩頭打ちと考えたため – さすがに発表時間が足りないので詳細は割愛