差分計算アルゴリズムを⽤いた⾼速なUITableView 描画
第７章では、iOS アプリケーションの実装において頻繁に遭遇する問題であるUITableViewを高速に描画・更新する方法について検証した結果を提⽰します。
全章を一括して購入されたい方はこちらの記事をご購入ください。https://note.mu/nikkei_staff/n/n44623c9b9ab4
⽇経電⼦版のアプリチームでiOSアプリを開発している伊藤/@fumito_itoです。
UITableViewをいかに⾼速に描画・更新するかはiOS アプリケーションの実装において頻繁に遭遇する問題です。本章では単純なreloadData を⽤いた場合と差分計算アルゴリズムを⽤いた場合で実際にどの程度の差が⽣じるのか検証した結果を提⽰します。また、複数の差分計算アルゴリズムとその実装を⽐較することで、それぞれの実装が適しているケースを提⽰します。
本章は筆者がiOSDC 2018 で発表した「差分計算アルゴリズムを⽤いた⾼速なUITableView 描画」*1について、補⾜内容を追加・再編したものです。元となった発表内容についてはiOSDC 2018 の発表資料および録画をご覧ください。また、本章でパフォーマンス計測に⽤いたプロジェクトはGitHub で公開しています*2。ぜひ最強の差分計算ライブラリを作成し、リポジトリにPull Request を送ってください。
7.1 iOS で⽬指すべきパフォーマンス
iOS アプリケーションではどのくらいの速度で画⾯が応答すればいいのかご存知でしょうか？ Apple のドキュメントには次のように記述されています。
Most apps target a frame rate of 60 FPS, Equivalent to 16.67 ms per frame.*3
だいたいのアプリケーションは60FPS、つまりおよそ16ms で画⾯を描画することができればiOS における理想的なパフォーマンスを実現できているといえます。この16ms にはOS のオーバーヘッドなどが含まれるため、現実的に開発者に与えられた猶予は10ms程度でしょう。このようにごく短い時間の中でUI を構築するには、それぞれのアプリケーションに合わせた最適化が必要になります。
7.2 ⽇経電⼦版iOS アプリでパフォーマンスを向上させるには
では、⽇経電⼦版iOS アプリを例にして最適化するべき箇所を考えて⾒ましょう。⽇経電⼦版iOS アプリでは多くのUITableViewが利⽤されています。たとえば、Web 刊という⽇経電⼦版iOS アプリを⽴ち上げて最初に表⽰される画⾯は、常時15 ~ 18 個程度のUITableView が横に並んで表⽰されています（図7.1）。
つまり、⽇経電⼦版iOS アプリではUITableViewのパフォーマンス向上がそのままアプリケーションのパフォーマンス向上に直結します。UITableViewはよく利⽤されるUIコンポーネントであり、ボトルネックの⽣じやすいUI コンポーネントでもあります。そのため、多くの開発者によってさまざまな最適化の⼿法が提案されてきました。よく知られているものでは次のようなものがあります。
• Cell のレンダリング最適化
• ⾮同期なデータフェッチとキャッシュ
• ⾮同期な画像ロードとキャッシュ
• オフスクリーンレンダリングを避ける
• セルサイズの事前計算とキャッシュ
⽇経電⼦版iOS アプリにおいても当然これらの最適化は⾏われています。⼀⽅で、そもそも更新したり描画したりするCellそのものが少なければ画⾯の描画処理も軽くなるのではないでしょうか。
次からの⽂章ではUITableViewの⾼速化に的を絞り、特にデータ更新におけるボトルネックの解消について考えていきます。
7.3 UITableView を差分更新する
UITableViewで更新する⾏を少なくすることはできるのでしょうか。結論からいえば可能です。UITableViewには⾏単位でデータの更新をするためのAPI が提供されています。(リスト7.1, リスト7.2)
このように⼀部の⾏だけを更新する処理を便宜上、差分更新と呼びます。リストを⾒ていただければ分かるように、差分更新を⾏うためには変更前のデータを変更後のデータに変換するための編集操作を算出する必要があります。これを総当たりで探そうとすると多くの計算リソースを必要とします*4。
編集操作を計算するための⼿法は古くから研究がなされており、さまざまなアルゴリズムが考案されています。そこで、差分抽出のためのアルゴリズムの概要とそれぞれの実装を俯瞰し、具体的なパフォーマンスの⽐較を⾏なっていきましょう。
7.4 差分抽出アルゴリズム
2 つの要素列間の差分抽出を計算するアルゴリズムは古くから研究されてきた歴史があります。今回はその中でも代表的な⼿法であるMyer 法、Wu 法、Heckel 法について解説します。なお、便宜上別々のアルゴリズムとして分類していますが、Myer 法とWu法はどちらも編集グラフを利⽤した差分計算をおこないます。
編集グラフは図7.2 のように変換前の⽂字列と変換後の⽂字列をグラフのXY 軸に割り振ったものです。図7.2 の場合は‘KITTEN‘ という⽂字列から‘SITTING‘ という⽂字列に変換することを⽬標としています。編集グラフの⽬的は、グラフの左上（0, 0）の地点から右下（7, 6）に移動する最⼩コストの経路を探索することです。コストの計算はグラフの軸上の移動で表現されます。具体的にはX 軸⽅向への移動（挿⼊操作）にコスト1、Y 軸⽅向への移動（削除操作）にコスト1、斜線部分の移動にコスト0 が割り当てられ、（0, 0）から（7, 6）まで移動するための総コストがその経路のコストになります。
Myer 法
Myer 法では経路にかかる総コストをN と置き、N が0 の場合に⽬的地にたどり着けるか探索します。コストN で⽬的地にたどり着けない場合、総コストをN + 1 とし、同様に⽬的地までたどり着けるか探索を⾏います。この⽅法を⽤いると探索の範囲が最⼩の移動コストで到達しうる範囲まで狭まるため、最⼤でO（ND）の計算量になります*5。
Wu 法
Wu 法ではMyer 法と似た考え⽅ですが、削除の編集操作を変数として設定するところに特徴があります。この⽅法を⽤いると探索の範囲が最⼩の削除操作で到達しうる範囲まで狭まるため、最⼤でO（NP）になります*6。
Heckel 法
Heckel 法ではMyer 法、Wu 法とはまったく異なり、参照テーブルを⽤います。参照テーブルは図7.3 のように変換後・変換前の⽂字列に含まれる⽂字をキーとし、変換前の出現回数、変換後の出現回数、変換前の出現場所を値としたテーブルです。
このテーブルを作成したあと、変換前の⽂字列から変換後の⽂字列もしくは参照テーブルに対して参照を作成します（図7.4）。
このとき、変換後の⽂字列へ参照を作れる場合はそちらを優先するものとします。この操作を完了すると変換後の⽂字列へ参照を作る要素は移動操作が、参照テーブルへ参照を作る要素は削除操作が必要であることが分かります。同様の処理を変換後⽂字列に対しても⾏うと挿⼊操作が必要な要素が割り出せるため、最⼤の計算量はO（N）になります*7。
7.5 差分抽出アルゴリズムの実装ライブラリ
さて、前節でのアルゴリズムの考え⽅を踏まえた上でそれぞれの実装を⾒ていきましょう。今回取り上げたライブラリは、いずれもGitHub 上で公開されているOSS です。⽐較対象として採⽤したライブラリの他にも多くのOSS ライブラリが存在しますが、GitHub のスター数、メンテナンスされているか、実際に利⽤されているかなどの観点で筆者が独⾃に選定しました。また、いずれのライブラリもSwift から利⽤することができます。
7.5.1 Dwifft
Myer 法をベースとして実装されたライブラリです*8。古参のライブラリであり、⼀度は利⽤されたという⽅も多いのではないでしょうか。今回取り上げたライブラリの中では（理論上は）もっとも計算量が多くなります。
差分計算の対象となる配列の値はEquatableを実装している必要があります。また、差分計算の結果がDiffStepの配列として返されるので差分の反映にはUITableViewのperformBatchUpdatesなど標準ライブラリの関数を利⽤します。
7.5.2 EditDistance
Wu 法をベースとして開発されたライブラリです*9。差分の計算やUITableViewへの反映がシンプルなAPI で実⾏できるように作られており、使い勝⼿が良さそうな印象を受けます（リスト7.4）。
差分の計算はArray オブジェクトに追加されているdiff.current関数を実⾏することで⾏います。差分の反映もUITableViewに追加されているdiff.reload(with:)関数を実⾏するだけなのでとてもシンプルに記述することができます。
7.5.3 RxDataSources（Differentiator）
RxDataSources はHeckel 法をベースに作られたライブラリです*10。Heckel 法は計算量が⼩さくなるため、多くのライブラリが作成されています。その他の有名なライブラリとしては、IGListKit*11が挙げられます。RxDataSources はその名前から想像できるようにRxSwift と密に連携して利⽤することができます。また、差分計算はDifferentiatorというフレームワークに切り出されているため、差分計算のみ外部から利⽤することもできるようになっています（リスト7.5）。
Differentiator はさまざまな最適化によってIGListKit の差分計算よりも⾼速に動作するため、今回はRxDataSouces を採⽤しました。
差分計算を⾏う場合は、いったんデータ構造を表現するためのセクションオブジェクトに変換し、differencesForSectionedView関数に渡します。calcDiffの実装からも分かるようにRxDataSources の差分計算は例外を投げる可能性があります。これはxDataSources が重複するデータを許容しないためです。例外が投げられた場合、reloadDataにフォールバックするか、例外に含まれる情報から重複するデータを排除して差分計算を実⾏しなおす必要があります。
7.5.4 DifferenceKit
DifferenceKit はHeckel 法をベースに作られたライブラリです*12。ごく最近公開されたライブラリですが、早くもGitHub で1000star を獲得しています。Heckel 法に着想を得ていますが、さまざまな最適化が⾏われており、⾼速に動作します。差分計算も変更前・変更後のデータを渡すだけで簡単に⾏うことができます（リスト7.6）。
差分計算を⾏う配列の要素はDifferentiableを実装する必要がありますが、Differentiable はHashable もしくはEquatable が実装されていれば追加の実装が不要です。
たとえばサンプルのようにUUID などのHashable な型を利⽤している場合には、単にextension UUID: Differentiable {} とすればよいだけなので簡単に実装することができます。
7.6 各ライブラリを⽤いた⽐較検証
前節で初回した4 つのライブラリを⽤いてパフォーマンスの検証を⾏いました。パフォーマンス検証は次の2 つの観点で⾏います。
• 差分計算のパフォーマンス
• 差分計算を含めたデータが与えられてから実際に画⾯がリロードされるまでのパフォーマンス
また、パフォーマンスの検証を⾏うにあたってデータの量と編集操作の割合を表7.1 のように設定しました。
データ量は実際のユースケースよりもやや多いと感じるかと思いますが、これはデータ量を多くすることによって各実装のパフォーマンス差を分かりやすくする意図があります。また、編集操作の割合を変更することによって、Heckel アルゴリズムが編集操作の種類に影響を受けないことを確認しようと試みています。
7.6.1 差分計算のパフォーマンス⽐較
差分計算パフォーマンスの測定結果を表7.2 に⽰します（単位はms）。
Heckel 法を採⽤しているRxDataSources とDifferenceKit がぶっちぎりで速いことが分かります。Dwifft は1 万⾏のケースで有効な時間内に差分計算を終えることができませんでした。また、Heckel 法を採⽤しているライブラリは編集操作の割合にかかわらず⼀定のパフォーマンスを維持していることがわかります。
7.6.2 画⾯更新のパフォーマンス⽐較
画⾯更新パフォーマンスの測定結果を表7.3 に⽰します（単位はms）。この表では差分計算と⽐較するために単純なreloadData のパフォーマンスも掲載しています。また、10,000 ⾏では計測が完了しないライブラリが続出したため、100 ⾏・1,000 ⾏でパフォーマンス計測している点に注意してください。
データ数が多い場合にはreloadData が最速になるという結果になりました。これはCellが単純な後続である（デフォルトのUITableViewCell を使っています）、画⾯に表⽰されている更新対象のセルの数が偏っているなどの要因が働いています。実際のプロダクトで利⽤するような複雑なUI では結果が逆転する可能性があることに注意してください。
7.6.3 パフォーマンス以外の機能⽐較
実際にプロダクトに適⽤することを考えるとパフォーマンス以外の観点にも注⽬する必要があります。差分計算ライブラリには多次元配列に対応しているか、重複したデータを許容するか、サポートしている編集操作の種類などの違いがあります。今回紹介したライブラリの対応状況を表7.4 に掲載しました。
RxDataSources はデータ構造の制限が厳しくなっていますが、これが差分計算の⾼速化の源泉になっているため、⼀⻑⼀短であるといえます。
7.7 ⽇経電⼦版iOS ではどのような選択をしたか
⽇経電⼦版では最終的にRxASDataSources を採⽤しました。これは、今回紹介したRxDataSources の互換ライブラリです。我々が利⽤していたRxSwift、Texture といったライブラリと相性がいいこと、差分計算が⾼速であることからこのライブラリを選んでいます。
さて、ここで疑問になるのは差分更新は本当にコストに⾒合っているか？ ということです。最初は「描画したり更新したりする⾏が少なければ処理も軽くなるのではないか」と考えていました。しかし、これまで⾒てきたとおり、実際に差分更新をするには差分を計算するための計算コストがかかります。そして差分更新も決してreloadData よりも圧倒的に速いという訳でもなさそうです。実際にIGListKit でもセルの数が膨⼤になると差分更新が遅くなる問題が知られています。*13
結局のところ、我々は損益分岐点を⾒極めて差分更新をとるか、reloadData をするか判断していくしかなさそうです。この問題をどのように解決していくかはiOSDC のセッションである「5000 ⾏のUITableView を差分更新する」*14で詳しく解説されています。ぜひ確認してみてください。
7.8 まとめ
本章ではUITableViewを⾼速に描画するために差分更新が利⽤できるのではないかと仮定し、差分計算のためのアルゴリズムを俯瞰・⽐較しながら実際のライブラリを⽤いてパフォーマンス計測を⾏いました。また、パフォーマンスを⽐較した結果、実際の画⾯描画がreloadData を⾏なった場合よりも早くなるかどうかは利⽤するアルゴリズム、ライブラリ、UI の構成やデータ量に依存することが分かりました。UITableViewはiOS のUI を構築する上で重要なコンポーネントであり、そのパフォーマンスを向上させていくことはユーザーによりよい体験を提供することに繋がります。本章が皆さんのアプリケーションのUX をよりよくしていく⼀助になれば幸いです。
著者：伊藤/@fumito_ito
iOSDC から考えなしにイベント参加を⼊れてしまった中で泣きながら書きました。内容⾃体はiOSDC での登壇内容の焼き直しなので、ぜひイベントの動画や資料も合わせてご覧いただけると嬉しいです。
140年の歴史ある会社が、AIやデータを駆使した開発を現場で実践しています。是非疑問や感想を #nikkei_dev_book をつけてツイートしてください！
全章を一括して購入されたい方はこちらの記事をご購入ください。
https://note.mu/nikkei_staff/n/n44623c9b9ab4
この記事を購入すると、この下に第７章だけのダウンロードリンクが表示されます。
ここから先は
¥ 100