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 のパイプラインがあって、数時間でやれるんだったら、試してみたくなるだろう?
