iphone_dev_jp 東京 feat. Ben Zotto にいってきた #idevjp

iphone_dev_jp 東京 feat. Ben Zotto (Penultimate開発者) - connpass に行ってきました。

英語の発表だったけど、同時通訳の人がうまくて結構理解できました。 (まぁ、こんな画像最適化するようなアプリ作ることはないとは思うけどw)

画像とは関係ない質問をしてしまったけど、質問もしやすい雰囲気でよかった!懇親会の時間が短くなってしまって残念だったけど、LTも含めて楽しかったです。

Ben Zottoさんの発表のまとめ

  • Tiny pictures An Optimization Case Study
    • Ben Zottoさん

Intro

Evernoteの中の人。 Penultimate | Evernote を作っている人。

penultimateは、手書きでメモしたものを画像としてEvernoteと頻繁に同期をはかってるけど、 そのときの通信で画像のサイズを小さくするために最適化に取り組んだという話です。

iOSの普通の画像エンコード

画像とは、RGBAを持ったカラー値の集まりで大きなグリッドを持つものです。

RAWデータはサイズが大きくなるので、当然pnggifとかにエンコードします。

iOSではUIImagePNGRepresentionUIImageJPGRepresentationを使います。 これは速いし、簡単で便利です。

エンコード方法について

PNGはlosslessで、アイコンなどのソリッドカラーのものに向いていて、JPEGは写真などの色の変化が激しいものに向いています。

penultimateには、3つの種類の画像があります。

  1. Writing: 文字だけのようなメモ書き
  2. Diagram: グラフが入ったダイアグラム
  3. Dense: 手書きで塗りつぶした絵や、WritingやDiagramが両方入っているような複雑なもの

基本的にjpegはあまり効果的でなく(写真のようなもの以外)pngの方がよい圧縮率が出せた。

f:id:masato47744:20140422193055j:plain

量子化への1つめのチャレンジ -> PNG-8

PNG-8を使用する。 PNG-8とは256色カラーで扱う色の数を少なくしたもの。PNG-24などに比べて1/4のサイズになる。 PNG-8にするために、pngquant — lossy PNG compressor というライブラリがある。

このライブラリは何をしているかというと以下のようなことをしている。

  1. ヒストグラムを作る
  2. 共通項を、洗い出して最適なパレットを選択する
  3. 最適なパレットの値(index)を各ピクセルに割り当てる

pngquantの圧縮結果

f:id:masato47744:20140422194110j:plain

かなり圧縮に成功したが、Mac上で実行すると、0.7sだったが、iOS上だと、6sもかかってしまった。

とても、プロダクトで使える速度ではないので、Profileで見たらインデックスの割当のところが遅い。 ソースを見ると、forのNested Loop (O (n*m)) の処理があったので、ここを最適化することに決めた。

量子化への2つめのチャレンジ -> アーキテクチャの変更

forループを速くするために、Macでは、SSE アセンブラで速くできそうだが、iOSにはないので、ARM NEONを利用する。 openMPiOSにはないので代わりに、GCDで処理を実装し直す事にした。

それでも、結果は、5s

アルゴリズムに問題がある場合は、何してもダメなもんはダメだということが分かった。

そもそもループ自体が遅いならそもそもループを持たないようにすればいいのではないかと考えた。

量子化への3つめのチャレンジ -> lookupテーブルの採用

ループが遅いならlookup table持てばいいんじゃないかと考え、 はじめから、iOSのBundle内にルックアップテーブルをバンドルしておく。

-> 結果は、0.5s!!

ルックアップテーブルを持って、ループを一つなくしたので、O(n)の計算量になって速くなった。

量子化への4つめのチャレンジ -> OpenGLの採用

さらに、速くできないか考えてみた。RGBは縦軸R、横軸G、高さBの立方体の3D空間とみなすことができるのではと考えました。3DならOpenGLで高速演算が可能になります。 なので、ルックアップテーブルをOpenGLで書き換えました。

-> 結果は、0.025s!!!

OpenGLは、shaderが速く、並列計算も得意なので同時にlookupも速い。 その結果、UIImagePNGRepresentation55-70%画像サイズの圧縮に成功しました。

今回の教訓

  • 面倒でもProfilingできちんとボトルネックを見つけよう
  • penultimate用に最適化したから今回のような良い結果が得られたということ
  • 利用しているアーキテクチャiOSの上で動くか調べること

質疑応答

  • lookup tableのサイズは?
    • 全てのカラーを揃えると4GB。αを捨てれば16MB、ボトムの2bit?を削って256kb
  • GPUでバッテリーを使うんじゃない? テストしてない。
    • そういった懸念は持ってなかったっす。
  • ユーザーが編集したあと必ず同期するの?
    • 特定のタイミングで同期してる。
  • 同期の際に前の画像と現在の画像の差分を見てる?
    • 差分だけ見るのが理想だが、バイナリなので100%リプレイスしてる
  • OpenGLで作ったカラフルなlookup tableみたいなものって何だったの?
  • 汎用的なアルゴリズムのような気がするけどEvernote SDKとかになったり第三者が使えたりする?
    • 計画はないです。特定の目的に特化してるから、役に立たないだろう。
  • EvernoteのSkitchも同じようなアルゴリズム使ってますか
    • 使ってないです。あれは、背景が写真みたいな複雑なやつだから使えない。
  • Storyboard、テスティングフレームワークは何を使ってますか
    • ストーリーボードは使ってないです。なぜなら、iOS3とか4の頃に開発を始めたから。 テストフレームワークは使ってないけど、カスタムのテストを書いている。
  • この一連の改善は誰がどれくらいでやったの?
    • チームが2,3人のチームですが、私一人、一週間でやりました。ARM NEONなんて知らなかったので勉強になりました。
  • Androidとかで使おうと思って、PNG-8圧縮の方向に進んだの?
    • iOS特有のCoreImageとか考えなかった? CoreImageはそもそも選択肢のうちに入ってませんでした。
  • データ転送でさらに圧縮は他にやっていますか?
    • そもそも通信の高速化のために今回の圧縮を行った。gzipみたいな圧縮の方向性とは違うもの。
  • どこまでやったら、ゴールとしていた?
    • プロダクトマネージャーだったから、利益も考えたらそうなった。