Ut Video Codec Suite 高速化の11年 梅澤威志/ゆーむ (twitter: @umezawa_takeshi) IM@S Engineer Talks 2019

自己紹介 梅澤威志 / ゆーむP 本業は某ネット企業の ソフトウェアエンジニア 箱マスからのアイマスP ニコマスも少々 響P Blog: http://umezawa.dyndns.info/wordpress/ GitHub: https://github.com/umezawatakeshi 箱マスからのアイマスP ニコマスも少々 ニコ百: https://dic.nicovideo.jp/a/ゆーむp 響P ぬーかわ

目次 Ut Video Codec Suite is 何 作り始めたきっかけ 圧縮手法 高速化の歴史

Ut Video Codec Suite is 何

Ut Video Codec Suite is 何 映像キャプチャ向け可逆圧縮コーデック 各種プラットフォームで使えた（過去形（涙 http://umezawa.dyndns.info/wordpress/?cat=28 https://github.com/umezawatakeshi/utvideo FFmpeg に互換実装がある

いろんなところで使われている ニコマス方面とか MMD 方面とか ニコニコの コンテンツツリーで 子作品25240 （2019-07-06現在） http://commons.nicovideo.jp/tree/im1922939

いろんなところで使われている (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 （以下略）

いろんなところで使われている (3) 映像作品の納品フォーマットとして（伝聞 映像上映イベントの再生フォーマットとして FRENZ というイベントで 2017 年から使われている https://frenz.jp/

作り始めたきっかけ

エースコンバット6をキャプりたかった 2007年にエスコン6のプレイ動画をHD (720p) でキャプりたかった 非圧縮 YUV422 だと 1280x720x2x60=約110MB/s 今なら単発HDDでもこれぐらい出るが当時は無理だった（最外周の一番速いところでも70MB/sぐらい） SSDもまだまだバカ高かった 何らかの圧縮をしてからHDDに保存する必要がある ちなみにできた動画が https://www.nicovideo.jp/watch/sm1770031

Huffyuv 2007年後半、キャプチャ向け映像コーデックとして有力なのは Huffyuv であった HDキャプチャ用途だと以下の問題があった 圧縮比がちょっと足りない 速度がちょっと足りない シングルスレッド MMX 前提（= SSE2 を使っていない）

どう問題になるか 圧縮比があまり高くないので、やっぱり単発HDDでは追いつかないことが時々ある 仕方ないので2台でRAID0していた RAIDしても今度はCPUの処理が追いつかないことが時々ある 定格 2.4GHz の CPU を 3.0GHz まで OC してお茶を濁す

ちかたない 自分に需要がある 自分に作る能力がある 作ることに対する興味がある ので作る 他人にもたぶん需要がある 自分に作る能力がある 作ることに対する興味がある ので作る 年末ごろからどういう方向で作るかを考え始めた（…と記憶している（曖昧

圧縮手法

そもそも論 一般的に映像エンコードはこんな処理をする 左右の画像は http://icooon-mono.com/ より

圧縮手法 大枠としては Huffyuv と変わらない 異なる圧縮原理を考えるような脳みそは無い Huffyuv が（時代背景のせいで）できなかったことをやることによって性能を向上させる 説明（手法の必然性）の理解しやすさの観点から、圧縮の処理順序の逆順で説明する

圧縮手法 – ハフマン符号 エントロピー符号化の一種であるハフマン符号を使って圧縮 Huffyuv では符号語テーブルが画像によらず固定だったので最適な符号化になっておらず圧縮比が低かったが、UtVideo では（ほぼ）正しくハフマン符号を使うので（ほぼ）最適である

圧縮手法 – フレーム内予測 単に画像を直接ハフマン符号化しても小さくならない 近傍のピクセルから値を予測してそれとの差を取り、値をゼロ付近に集めてエントロピー（情報量）を削減すると、圧縮しやすくなる 予測の際は、近傍のピクセルと値が近いことが多い、という性質を利用する

圧縮手法 – フレーム内予測 (2) 予測タイプは現在3種類ある left – 左の値を予測値とする gradient – 左、上、左上の値からなる1次関数で予測値を得る 予測値 = left + top – topleft median – 左、上、 gradient の3つのうちの中央値を予測値とする 予測値 = median(left, top, gradient) UtVideo においては median, left, gradient の順に実装した

圧縮手法 – フレーム内予測 (3) 予測値の計算（と予測値との差の計算）は3種類とも SIMD 化できる ピクセル間に依存関係がないので、ちゃんと要素数分だけ速くなる SIMD (Single Instruction Multiple Data) 複数のデータに対して同一の処理をまとめて行う並列化体系のこと

圧縮手法 – フレーム内予測 (4) 予測の復元（「予測値との差」だけがある状態から元の値を計算する）は、 median の場合 SIMD 化できない 前のピクセルの値が次のピクセルの予測値の計算に使われており、しかも式が線形ではないから gradient と left は線形なので、要素数分とまでは行かないが SIMD 化で速くなる

圧縮手法 – planar 変換 チャンネルごとに分解する（planar変換） 画像は三原色（+アルファチャンネル）から成るが、チャンネルごとに圧縮のしやすさが異なる。 圧縮のしやすさが異なるものは別々に処理した方が効率が良い

唐突に x86 のレジスタ構成 x86 のレジスタはこういう形式でアクセスできるようになっている EBX, ECX, EDX もある （他にもあるけど割愛） EAX に 0x12345678 を入れると、 AX として見ると 0x5678、 AH は 0x56、 AL は 0x78 となる ここで AL に 0x90 を入れると AX は 0x5690 になる

細かいデザイン ハフマン符号化では、シンボルに対する符号語をテーブル参照で取ってきて、シフトしてつなげていく、という処理になる

細かいデザイン ハフマン符号化では、シンボルに対する符号語をテーブル参照で取ってきて、シフトしてつなげていく、という処理になる

細かいデザイン ハフマン符号化では、シンボルに対する符号語をテーブル参照で取ってきて、シフトしてつなげていく、という処理になる

細かいデザイン (2) CL レジスタに符号語長が入ると都合が良い ECX レジスタの上位 24bit が空いてるので符号語を入れる x86 の可変シフト命令ではシフトするビット数を CL レジスタで指定するため ECX レジスタの上位 24bit が空いてるので符号語を入れる 符号語長と符号語を一発で ECX にロードできる

高速化の歴史

1.1.3 (2008-04-18) 最初の public release 予測タイプは median のみ 遅い 合計約2000行

2.1.0 (2008-05-01) スライス方式によりマルチスレッド化した スレッド間の同期処理はほとんどないので単純にコア数分だけの高速化になっている

2.2.0 (2008-05-07) ハフマン符号の符号化/復号化 と フレーム内予測の予測/復元 をアセンブリ言語で書いた 特に、コンパイラが吐いてくれない命令を駆使することで高速化した SHLD – ハフマン符号化/復号化 BSR – ハフマン復号化 CMOVcc – フレーム内予測 これでおおむね Huffyuv と同程度の速度になった

3.3.0 (2008-05-17) 部分レジスタストールを回避するように書き換えて predict median の復元を高速化 長いレジスタ（たとえば EAX）の部分（たとえば AL）を更新した後に、更新した場所以外を含む領域を使おうとすると、部分の更新を一旦全体に結合するためにペナルティがかかる。これを部分レジスタストールという readme によるとハフマン符号等も含めた全体で 20% ほど速くなったらしい（単体だと50%ぐらい？

3.3.0 (2008-05-17) (2) SHLD 命令の使い方が甘かったのを改良してハフマン符号の符号化を高速化 元の符号化のコードは C++ で書いたものをそのままアセンブリ言語で書き直した感じの物で、あまり効率が良くなかった

3.7.0 (2008-06-07) predict median の復元で CMOVcc 命令を駆使する代わりに MMX の PMAX/PMIN 命令を使って高速化 MMX は SIMD 命令セットであるが、この修正では最大値/最小値を一発で計算する命令を単一要素に対して使っている（CMOVcc 命令はそれほど速くない この時の blog に「肝心のハフマンデコードが速くならないのでそろそろ限界が…」とか書いてある

3.8.0 (2008-06-10) ハフマンデコードが速くならないので諦めて predict left フレーム内予測方式を追加 それなりにややこしい処理をする predict median と比べると単純であり、復元がハフマン復号化のついでにできるので圧倒的に高速である（デコードは全体で1.5倍速 代わりに圧縮比は下がる

7.0.0 (2009-10-22) x64 版を追加 ちなみに Windows 7 の発売日あわせである UtVideo のバージョンも 7 なのはたまたま とりあえず全部 C++ で書いてある（昔からある C++ コードが使われる）ので非常に遅い

7.1.0 (2010-04-04) AMD Athlon （K10 マイクロアーキテクチャ）でRGB/RGBA の処理が猛烈に遅い問題の解決 具体的には全体で3倍ぐらい遅かった RGB/RGBA の場合、 planar 変換時に各 plane のポインタが同じ速度で進む 各 plane バッファの先頭アドレスはそれぞれ「キリがいい」ので、各ポインタが常にキャッシュの同じエントリアドレスを指す

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 を参照

8.2.0 (2010-09-05) 短い符号語の場合にテーブル一発参照方式をとることでハフマン復号化を高速化 以前はデコードテーブルを小さく（約4KB）するためにめんどくさい（=時間のかかる）処理をやっていたが、今時1次キャッシュは32KBあるのでシンプルに行けることに気づいた 全体として20%以上速くなったらしい

8.2.0 (2010-09-05) (2) こんな感じ 符号語長のところに「12bit に収まっていない」と書いてあったら、次のシンボルのデコードは以前と同じ処理にフォールバックする

8.3.0 (2010-10-11) 8.4.0 (2010-10-17) predict left で native なフォーマットへのデコードで、ハフマン復号化の出力を planar 形式を経由せずに直接フレームバッファに書き込むようにして高速化 predict left の場合ハフマン復号化のついでにフレーム内予測の復元をすることが現実的 メモリコピーと変換処理が削減された

8.3.0 (2010-10-11) (2) 8.4.0 (2010-10-17) (2) こんな感じで直接復号化していく

8.5.0 (2010-11-02) ハフマン復号化でループ内のレジスタ間 MOV 命令を1個削減して高速化 命を削ってクロックを削れ！ ループが1周10クロックぐらいなので、これだけで10%も速くなる 命を削ってクロックを削れ！ あと x64 が x86 と同程度にアセンブラ化された

12.1.0 (2013-04-23) packed <-> planar 変換を SIMD 化して高速化 Sandy Bridge (Core i 2000 series) だとシャッフル命令が十分に速い 2008年ごろは開発マシンに Merom (Core 2 Quad Q6600) を使っており、 シャッフル命令が速くなかったせいで逆に遅くなっていた ちなみにシャッフル命令が「だいぶ速くなった」のは Penryn （Merom の次）である。

12.1.0 (2013-04-23) (2) RGBA の変換の場合、 以前は 64 シンボル処理するのに 64 クロック SIMD 化すると Sandy Bridge で 6 クロック Merom で走らせるとたぶん 24 クロック あれ、なんで遅くなるんだ…？

12.2.0 (2013-05-12) 再び部分レジスタストールを回避してハフマン復号化が高速化 全体で見て5～10%ぐらい 部分レジスタストール怖い

13.2.0 (2013-09-21) x64 で、64bit レジスタを駆使することで SHLD 命令を回避してハフマン復号化を高速化した Haswell マシン (Core i7-4770) を調達したので BMI2 命令 (SHLX, SHRX) を使ってさらに高速化 両方合わせて Haswell なら最大25%高速化

17.2.0 (2016-12-30) ハフマン復号化で、テーブル1回の lookup で複数シンボル同時に出力するようにして劇的に高速化した ハフマン復号化単体で言うと倍ぐらい行ける ただし、復号化のついでに predict left の復元をやることができなくなる（やろうとすると複雑すぎて遅くなる）ので、デコード全体としてはそこまでではない

17.2.0 (2016-12-30) (2) それなりに圧縮できている場合は複数シンボルぶんの符号語が 12bit の中に収まっている可能性が高いので、だったらまとめて処理すれば速い 代わりにデコードテーブルがかなり大きくなった（3倍）

17.2.0 (2016-12-30) (3) こんな感じ この図の例だと 3シンボル同時に 出力される

18.0.0 (2017-04-01) predict gradient フレーム内予測方式を追加 圧縮比が predict left より高めで、かつ SIMD 化のしやすさは left と同程度、といういいことづくめ 圧縮比が高いとメモリアクセス等が減るので、結果的に速くなる 今まで実装を避けていたのを後悔するレベル

18.0.0 (2017-04-01) (2) ハフマン符号化をループアンローリングして高速化 ループ1周が数クロックなので、アンローリングの結果としてループ終了判定が削減されるだけでそれなりに速くなる（そこまで劇的な効果は無かったが このあたりでフルHDの YUV420 クリップのデコードが 1000fps を超えた

20.2.0 (2019-01-14) x64 で、2シンボル同時に符号化することでハフマン符号化を高速化 符号語長は最大24bitであるが、64bitレジスタになら2シンボル分載せることができることを利用する

20.2.0 (2019-01-14) (2) 2シンボルずつ符号化する場合、エンコードテーブルが1次キャッシュ (32KB) どころか2次キャッシュ (256KB) にも収まらない 1シンボルずつなら 8B x 256エントリ = 2KB であるが、 2シンボルずつだと 8B x 64Kエントリ = 512KB 一方、シンボルの出現確率には偏りがあるので、よくアクセスされるのは 256KB の範囲に収まるとみなして構わない

20.2.0 (2019-01-14) (3) 2次キャッシュにおおむね収まるなら、レイテンシの増加による性能劣化を上回って高速化できる 2次キャッシュのレイテンシは1次キャッシュの 3倍であるが、ループアンローリングのついでに先行して符号語をロードすることでレイテンシを完全に隠蔽できる x64 だとレジスタが多いのでこういうことが可能 結果としてハフマン符号化だけを見ると倍速で処理できるようになった

20.3.0 (2019-03-14) 20.5.0 (2019-05-09) 一時バッファとしての planar フォーマットを経由せず、レジスタ上で処理してメモリアクセスを削減することで、特にマルチスレッド時の高速化をした マルチスレッド時はコアの処理速度ではなくメインメモリの帯域で律速しているから 極端な計測条件だと倍速になる

20.3.0 (2019-03-14) (2) 20.5.0 (2019-05-09) (2) 劇的に速くなることは理論的に予想できていたが、ルーチンの種類が爆発的に増えるので避けていた

20.3.0 (2019-03-14) (3) 20.5.0 (2019-05-09) (3) 複数 plane 同時に処理することになるので、ついでに predict median の復元の効率化が図られてそこでも高速化した 同じ plane の前のピクセルには依存関係があるが、異なる plane のピクセルには依存関係がないので並列処理可能

結局どこまで速くなったか 60倍 Core i7-4770 / 8.4.0 までは x86 8.5.0 からは x64 マルチスレッド / predict median / crowd_run 4K

One More Thing… 19.0.0 の時に SIMD にやさしいフォーマットとして UtVideo T2 を 追加した さすがに発表時間が足りないので詳細は割愛

俺たちの最適化はこれからだ！ 梅澤先生の 次回作 次バージョンにご期待ください T2 の説明もご期待ください（いつだ