clmemo@aka: iphone_dev_jp feat. Ben Zotto の講演まとめ

2014-04-22、iphone_dev_jp において Penultimate の開発者 Ben Zotto 氏の講演が開かれた。

日時: 2014-04-22 (火) 19:00-21:30
場所: アーク森ビル 31F 株式会社ドコモ・イノベーションベンチャーズラウンジ

Penultimate は iPad 用の手描きアプリ。Evernote に描いた絵を保存できる。

講演では、Penultimate のパフォーマンスでボトルネックとなった「画像」の内部処理が語られた。

iOS と Evernote

Penultimate は特定のタイミングとイベントで Evernote と同期 (sync) する。Evernote API は画像のデルタ保存 (差分だけを保存する技術) をサポートしていないので、全て上書きになる。

iOS には画像を扱うメソッドが 2 つある。

UIImagePNGRepresentation
UIImageJPEGRepresentation

PNG と JPEG のメソッド。PNG は可逆圧縮で、JPEG は不可逆圧縮。

2.5 MB の RAW データをそれぞれの方式で圧縮した場合のデータが示された。使う画像は、メモのような書き物、画像的な図、そして書き物と図を一緒にした dense。

結果は、メモや図では PNG に運配が上がる (メモ: 145 KB < 155 KB; 図: 110 KB < 136 KB) ものの、dense では JPEG の方が良かった (dense: 251 KB > 191 KB)。

PNG-8

Dense を考えれば PNG より JPEG の方が好ましいか。

ここで Penultimate が扱うデータに注目してみる。Penultimate では 32bit の PNG 画像など扱わない。せいぜい使う色の数は 256。ならば、256 色のカラー・パレットを持つ PNG-8 形式を使えば画像サイズは 1/4 になる。

PNG-8 には pngquant というツールで変換できる。その結果は次の通り:

	PNG	JPEG	PNG-8
メモ	145 KB	155 KB	61 KB
図	110 KB	136 KB	36 KB
Dense	251 KB	191 KB	91 KB

このように、Dense であっても PNG-8 の方が JPEG よりサイズが小さい。

補: Quantization

PNG (32bit) から PNG-8 に変換する手順を簡単に書いておく。

元の画像から色のヒストグラムを作成する
最適化されたカラー・パレットを決定する
各ピクセルに対して、カラー・パレットから最適な「色」を決める

3 番目の手順は、コードで書けばこんな感じになる。

for (pixel in image) {
  for (color in palette) {
    // 元の色に対して color が合うかどうか判定する
  }
  // 選んだ色をピクセルに貼り付ける
}

第 1 試行

Mac では 0.7 ms で実行できた。

iPad では 6 秒かかった。

遅すぎる!!

プロファイルを取ると、Quantization の手順 3. で時間を喰っていることが分かった。

第 2 試行

上記コードの内側のループを SSE のアセンブラで、外側のループを OpenMP で処理したい...

のだけど、どちらも iOS にはない。

ので、SSE の代わりに ARM NEON を、OpenMP の代わりに Grand Central Dispatch を使う。

その結果は... 5 秒だった。

The fastest implementation of a slow algorithm is still slow.

遅いアルゴリズムを最速にチューニングしても、遅いものは遅い (意訳)

第 3 試行

内側のループを外してみる。

pngquant は「どんな画像」に対しても「良い」カラー・パレットを作成する。けれど、Penultimate は手描きアプリだから描ける画に制限がある。だから、事前に「ある程度良い」カラー・パレットを作成可能なはず... というアイデア。

具体的には pngquant をオフラインで実行し予めパレットとテーブルを作成する。これらを最初からアプリの中に保存。必要な時に (都度々々作成するのではなく) ロードする。

これで実行速度は 0.5 秒になった。

第 4 試行

そして、最後の試み。予め作ったカラー・パレットを 3 次元表示してみる。

これはまるで、立方体にテクスチャーを貼ったもののように見える。3D テクスチャーと言えば OpenGL。

3 次元を 2 次元に展開すると (ref. ボロノイ図) こうなる。

このデータを OpenGL から使うように再コーディング。OpenGL は CPU ではなく GPU を使うことができるので (特にこの手の処理では) 処理能力の向上が期待される。

結果... 0.025 秒。

圧倒的じゃないか!!

Morals of the Story

Zotto 氏は最後に開発の肝を紹介した講演を閉じた:

Find your bottlenecks with profiling
Use peculiarities of your data to find opportunities
Put the platform to work!

(意訳)

プロファイリングでボトルネックを見つけなさい
扱うデータの特異性を有効利用しなさい
プラットホームで動くようにしなさい

あとがき

iOS の話だったけど、XCode とか、UI とか、NSObject とか全く出なかった。データ最適化の手法を見せつけられた。なんか、C の世界に戻って来た気がした。

OpenGL の高速化には舌を巻いた。

最後の質問タイムで、こんな質問が出た。「何をもって、最適化の『終点』としたのか? 何故 0.5 秒で満足しなかったのか?」。Zotto 氏は「自分はエンジニアで...云々」「でも、当時はプロジェクト・マネージャーもやってて...云々」と前置きを宣わって、こうとどめを刺した。

そこに OpenGL のパイプラインがあって、数時間でやれるんだったら、試してみたくなるだろう?

clmemo@aka

Pages

2014-04-24

iphone_dev_jp feat. Ben Zotto の講演まとめ