JPEGのIDCTのアルゴリズムを比較してみた

2022/05/21に公開

IDCT test

IDCTのベンチマークテスト[1]

ソースコード

4つのアルゴリズムの比較

  • ベタなやつ: 行列演算を真面目に計算する
  • AP922 : Intel MMX向け実装 Application Note 922
  • AAN : AAN algorithm proposed by Arai, Agui, and Nakajima in 1988
  • LL&M : The Loeffler-Ligtenberg-Moschytz (LLM) algorithm

ベンチマーク的にはLL&Mが一番速い。しかもLL&Mは最後のかけ算と量子化の計算を同時実行可能なので更にかけ算8回分速くなる可能性がある。しかし、実際のデコーダでテストすると誤差値で消えてしまう。試しにオプティマイズのレベルを下げるとAANの方が速くなった。コードが短いのでオプティマイズが効きすぎているかも知れない。

※ IDCT TEST is written by Rust and using Criterion for benchmark.

Benchmark rust 1.60/1.61 on AMD Ryzen 9 4900HS 3.00 GHz/Windows11

// 1.60
standard IDCT           time:   [15.165 us 15.424 us 15.716 us]
AP922 IDCT              time:   [1.3007 us 1.3186 us 1.3372 us] // 理由不明だが遅い
AAN IDCT                time:   [266.52 ns 272.37 ns 278.18 ns] // 55倍前後
AAN f64 IDCT            time:   [296.37 ns 302.61 ns 309.80 ns] // 約1割劣化
LLM IDCT                time:   [238.26 ns 241.88 ns 245.93 ns] // 62倍前後 

// 1.61
standard IDCT           time:   [13.471 us 13.682 us 13.908 us]
AP922 IDCT              time:   [1.1287 us 1.1511 us 1.1737 us]
AAN IDCT                time:   [267.63 ns 271.24 ns 275.14 ns]
AAN f64 IDCT            time:   [293.48 ns 297.60 ns 301.82 ns]
LLM IDCT                time:   [221.41 ns 225.68 ns 230.03 ns]

※ RyzenのAP922が遅いのは恐らくコンパイラの問題。以前実験したときよりかなり遅い。Ryzen限定でオプティマイズが効かなくなった可能性。

Benchmark rust 1.61 on MacBook Pro 13(2018) Core i5 2.3Ghz/MacOS 12.3.1

standard IDCT           time:   [13.616 us 13.878 us 14.117 us]
AP922 IDCT              time:   [489.78 ns 501.59 ns 513.80 ns]
AAN IDCT                time:   [331.70 ns 336.68 ns 341.64 ns]
AAN f64 IDCT            time:   [333.27 ns 336.39 ns 339.58 ns]
LLM IDCT                time:   [279.11 ns 286.40 ns 292.91 ns]

Ryzenより二割程度遅い。2.3Ghz vs 3Ghzなので、速度がクロック依存で出ている。

Benchmark rust 1.61 on Raspberry Pi4(Broadcom BCM2711, quad-core Cortex-A72 64-bit 1.5GHz)/Ubuntu 22.04

standard IDCT           time:   [35.851 us 35.863 us 35.875 us] // ほぼクロック依存。
AP922 IDCT              time:   [753.30 ns 753.49 ns 753.67 ns] 
AAN IDCT                time:   [671.91 ns 672.00 ns 672.10 ns] // 53倍程度
AAN f64 IDCT            time:   [667.66 ns 667.74 ns 667.83 ns]
LLM IDCT                time:   [588.54 ns 588.64 ns 588.76 ns] // 61倍程度

アーキテクチャの異なるRapsberry4でも傾向は変わらない。

脚注
  1. このアーティクルは、JPEGの展開を速くするの続きである。 ↩︎

Discussion