通常は地図は高ズーム状態のことが多く、ここでのパフォーマンス不足はない。低ズームは全体のファイルをメモリに楽に読み込めるため、問題は起きない。中ズームで、関東から関西、九州というように広範囲にスクロールするとき、 地図の表示に少し時間がかかる。時には、メモリ不足が起きる。
特に、中ズームでのパフォーマンス向上を目指して、可変長バイトコードの採用を検討してきた。 高ズームでは現状に比べてそれほど大きなファイルサイズ縮小効果は得られないが、中ズームでは現状よりも４、５割縮小する。
可変長バイトコードについては復号化時間が気がかかりでこれまで採用を見送ってきたが、 符号化されたコードは１、２バイトのケースが多いことに直目して、復号化プログラムの高速化を実現した。
これまでは、座標値データの差分が全て２バイトで表現できる場合に限り、差分を２バイトで表す差分コードとしていたが、 これを可変長バイトコードに変える。 座標値データだけでなく、レコード長、ノード数といった他の数値についても可変長バイトコードとする。
ただし、タグ部への適用な当面保留する。タグ部には多彩な数値があることと、平均的なサイズが比較的小さいため、 可変長バイトコード化によるファイルサイズ縮小効果が限定的であることが理由である。 将来的には、タグ部についても見直しを図り、可変長バイトコード化する可能性はある。
xmlファイルは Nodeセクション、Wayセクション、Relationセクションの順である。
Wayオブジェクトは複数の頂点(Node)からなる折れ線データである。道路などの部分区間や 一つで建物などを表すもの、大きな多角形領域境界線の部分区間などを表す。 頂点の座標値自体は Nodeオブジェクトに含まれる。
Relationオブジェクトは Node や Way や Relation をメンバー(子供)とする複合体である。
バイナリレコードはそれぞれ一つの地図上の表示物(Point、Line、Polygon、Multipolygon)を表す。 Point は一つの Nodeオブジェクトで形成される。LineおよびPolygon は一つ以上の Wayオブジェクトで作られる。 Relationが作り出すのが Line、Polygon、Multipolygon である。
Nodeセクション、Wayセクションは巨大なため、パソコンでは日本地図領域の全データを同時にメモリに載せることはできない。 そのため、１パスで、xmlファイルからOSMバイナリレコードファイルを作り出すことはできない。
このため、第一フェーズとしては、xmlファイルをバイナリ化して、 Nodeセクション、Wayセクション、Relationセクションに分けておく。
今回は次のようなフォーマットとしている。xml ファイルでは、Wayセクションのノード列は ノードID（osm_id）列であるが、 それを座標値に置き換えたものを出力する。 文字コードは UTF-8 とする。
length, osm_id, lon, lat, {key, val}* ----- Node
length, osm_id, num_nds, {lon, lat}*, {key, val}* ----- Way
length, osm_id, num_members, {type, ref, role}*, {key, val}* ----- Relation
大半のNodeは Wayを構成する頂点の座標のみを表す。 ごく一部が単独で例えばバス停や交差点の信号機などの Pointレコードとなる。
一部の Way は Relation のメンバーとなるが、単独で、Line（道路など）や Polygon（建物、公園など）が多い。
Relationは都道府県境界(Polygon/Multipolygon)、広域森林(Polygon/Multipolygon)、バス路線などを表す。 バス路線はバス停(Point)や道路(Line)をメンバーとしてもつ。 メンバーは、通常は、それぞれ、単独でバス停レコード、道路レコードにもなっている。 Map3では、バス路線道路には中央に細い青線を引いている。バス路線レコードを新たに追加するのではなく、 バス停レコード、道路レコードにバス路線id列を含めている。
Relationの扱いが一番難しい。 広域森林は Polygon/Multipolygon とせざるを得ないが、高速バス路線Relationなどは長いLineレコードにすると 境界ボックスが巨大となり、レンダリングの負担が増す。 都道府県境界線も繋ぎ合わせると巨大な Polygon/Multipolygon となる。境界線に沿って、内側に、 東京都、埼玉県といった文字を描画するだけであれば、一つの Polygon/Multipolygon レコードとはせず、 無数の 境界線Lineレコードに沿って 東京都、埼玉県といった文字を描画するようにした方がよい。
陸地ポリゴンも本州、北海道など巨大であるが、これを多数のポリゴンに分割したもので陸地の描画を行う。 広域森林の場合、内部に穴(inner polygon)があるため、プログラムによる自動分割が難しいが、 何らかの方法で分割できれば、描画時間が短縮される。
Node、Way、Relation の場合はファイルサイズはさほど気にする必要はないが、 OSMバイナリレコードは直接、レンダリングに使うものであるからなるべくコンパクトにする必要がある。 また、無数のレコードから所望のレコードを素早く抽出する必要がある。
Map4 では Map3 とは大幅に異なるシンプルなフォーマットとする。
head(4), [num_nds(4)], {lon,lat}*, {key,val}* ... point/line/polygon
head(4), {num_nds(4)}*, {lon,lat}*, {key,val}* ... multipolygon
head:
第0,1bit(0x03) 0: point、 1: line、 2: polygon、 3: multipolygon
下位３バイト レコード長
num_nodes:
multipolygonの場合、最終要素(最終inner polygonノード数)の最上位ビットは 1 とする。
multipolygon の {num_nds(4)}* は少しわかりにくい。
可変長バイトコード化では、先頭に polygon 数を置き、
num_polys, {num_nds}*
としている。また、head は type と length を分離している。
次に、大きく、プログラムを修正するときがくれば、フォーマットを可変長バイトコードと合わせたい。
メッシュ(zoom相当)に分割するのみで、バイナリレコードフォーマットは上記と同じ。
ブロック分割されたファイル毎に実行する。
レコードフォーマットは以下の通りとする。
head(1), length, [num_nds], {lon,lat}*, {key,val}* ... point/line/polygon
head(1), length, num_polys, {num_nds}*, {lon,lat}*, {key,val}* ... multipolygon
head:
第0,1bit(0x03) 0: point、 1: line、 2: polygon、 3: multipolygon
head(レコード type) は１バイト固定、 length、 num_polys、num_nds は 符号なし可変長バイトコード である。
length には、head と length 自体の長さは含まれない。
先頭の lon、lat は４バイト固定整数ペアで、次のノードから 可変長バイトコード(符号あり)とする。
ただし、multipolygonの場合、各polygon毎に先頭は４バイト固定整数ペアとする。
タグ部 {key,val}* は入力ファイルのものと同じ。
レコード毎に空間検索に使う境界ボックスなどの管理データを持つ。
メモリ上では int配列とする。先頭は flag;type;length、flag は width、height が各２バイト、合わせて４バイトの時 0、それぞれ４バイトの時 1 とする。type 0（Pointレコード）のときは width;height はなし(共に値は１なので省略)。
head;length(4), minlon(4), minlat(4), width;height(0/4/8) head: 第0,1bit(0x03) 0: point、 1: line、 2: polygon、 3: multipolygon 第4bit(0x10) 0: width, height は２バイト、 1: width, height は４バイト
type、length は実際上はバイナリレコードと同じものであるから、 境界ボックス(minlon、minlat、width、height) をバイナリレコードに含めれば、平均的には約12バイト増で済むが、 byte配列から int、short値を取り出すのは固定長であってもシフトや加算演算が必要となる。
厳密にはバイナリレコードでの length には、バイナリコードにおける type と length 自体の長さは含んでいないが、 管理部の length はこれらを含んだレコード全体の長さを表す。
空間検索では全レコードの境界ボックスのチェックを行う。 抽出されたレコードについてのみ可変長バイトコードの復号化を行う。 管理データの境界ボックスの参照は座標値列データの参照より桁違いに多い。このため、両者は一体化できない。
現在は、バイナリレコードファイルを読み込んだ時点でこの管理データを生成している。 これには、全レコードについて可変長バイトコードの復号化が必要となる。
この時間を短縮するために、ByteCoder でこのデータを作成し、全レコード分をまとめて、 バイナリレコードファイルの先頭部に置くものとする。
実行結果を下に示す。低ズーム用は管理データによる増分があり、元のファイルと大差がない。
中ズームでは大幅な縮小となった。 陸地ポリゴンデータ、タイル画像キャッシュ、レンダリング用OSMデータにも大量のメモリが必要となるため、 179MB全体を同時にメモリに置くのは難しいが、現在の表示範囲の周囲のバイナリレコードファイルを バックグラウンドで先行読み込みをすれば、レスポンスの向上が期待できる。
高ズームについても特に high7 では大きな圧縮効果が得られている。
高ズームについては、現バージョンの地図アプリの high13 2.56GB、high7 733MB との差が大きい。 high7 には主に広域森林、都道府県や市区町村境界線レコードが含まれる。
境界線はラインレコードで描画できるため、おおきなレコードは使わない。しかし、 境界線に沿って、都道府県名などを描画するためには、 境界線をつなぎ合わせて巨大なポリゴンレコードにする必要がある。 これら大きなポリゴンの重複度合などを計測して吟味すれば、現在の数値が妥当かどうかわかるであろう。
高ズームでは目立たないため、チェックしにくいが、今のところ、目視では地図に異状は見られない。 前のプログラムに大きな無駄が含まれていたのか、あるいは、今回のプログラムに、 大きなデータ抽出漏れがあるのか不明である。
異常があれば、レコードの重複度合などを出力して、結果を吟味したい。 現時点では、ブロックのまたがり(重複)が予想以上に小さい。 今後、マージンの追加により、重複が多少増える可能性があるが、極端に大きく増えるものではない。
分割ファイル バイトコード＋管理
japan-low3 10.8MB 10.3MB
japan-mid7 266MB 179MB
japan-high7 165MB 53.9MB
japan-high12 2.84GB 2.27GB
Androidタブレットでこのファイルを読み込みテストを行う。 ファイル読み込み時間、管理用int配列データを作る時間、管理用データをスキャンする時間などを計測する。
より高速な方法があれば、後から変更するとして、まずは DataInputStream を使うことにする。
最初にファイル先頭の４バイトを読み込む。これで管理部のサイズとレコード部のサイズが分かる。
管理部を readInt で４バイトずつ読み込んでみると、時間がかかりすぎる。
readAll開始 /storage/36C5-1401/Map4/byte4/japan-mid7/112/50.dat readAll: length＝34316382 readAll: lenIndexes＝8991792 readAll: size=24MB time=2545mS
やはり、大きな単位で byte配列に読込んで、自前のメソッドで int配列にセットする方法をとる。
２MBのバッファを用意して、２MB毎にここに読込んでから getInt(byte[] buffer, int off) を 使って int配列にコピーした。２回実行してみた。以下のように、読み込み時間は問題のない値になった。 大半が管理データを int配列にセットする時間である。 可変長バイトを復号化して境界ボックス値を求める場合、下の３倍ほどの時間がかかるため、 この方法を採用する。
readAll: size=24MB time=170mS readAll: size=24MB time=151mS
バッファサイズを２MBから10MBに増やして、４回実行した結果は 167、103、114、133ｍS であった。
バッファサイズ４MBでは 171、156、109、142 mS であった。
このバッファはバイナリレコードファイルの読み出しだけで使用するものである。 レンダリング時に別の用途で使い道があれば、10MBでもよいが、当面は 4MB としておく。
レンダリングはマルチスレッドであるため、スレッド毎にバッファを備える。
空間検索ではタイルのレンダリング毎に管理データをスキャンしてレンダリングの対象となるレコードを抽出する。 このとき、管理データの全ての値が読み出される。 この読み出し時間を４回計測した結果は 7、10、5、4 mS となった。空間検索では、レンダリングタイルの境界と レコードの境界ボックスの比較が行われる。検索対象となった場合は、可変長バイトコードを復号化して、 int型の経度、緯度を求める。この値をレンダリング対象のタイル座標に変換する。 この座標変換処理の方が復号化よりも時間がかかる。 このことから、スキャン時間は境界ボックスの判定を含めても、十分に小さいと言える。
念のため、中ズームでの最大ファイルでの計測を行っておく。
readAll開始 /storage/36C5-1401/Map4/byte4/japan-mid7/113/50.dat readAll: length＝44011850 readAll: lenIndexes＝11115588 readAll: size=31MB time=304mS readAll: scan_time=9mS readAll: size=31MB time=129mS readAll: scan_time=11mS readAll: size=31MB time=202mS readAll: scan_time=12mS
地図では目立たないが、パフォーマンス上、陸地ポリゴンがかなりの比重を占めている。
現在は高ズームと中ズームの２段階である。 高ズーム用ポリゴン、マルチポリゴンのノードを間引いて、中ズーム用を用意した方がよい。
高ズーム用ポリゴンは分割されているが、それでも巨大なポリゴンが多いため、 レコードの重複が極めて多い。日本地図領域に限定すれば、中ズーム用ファイル全体を メモリにのせることができるかもしれない。この場合、工夫すれば、重複レコードは 排除できる。メモリ使用量が大幅に削減できる。
中ズームのレンダリングで陸地ポリゴンレコードがどれくらいのメモリ使用量であるかを調べたい。 小さければ現状のままでもよい。
プログラムを使わなくても、ブロック分割したファイルのサイズから割り出せる。
zoom 5で分割している。日本の半分以上が 5/28/12 である。このファイルは 24.1MB である。
高ズーム用OSMバイナリレコードは zoom 12 と 7 で分割しているのに対して、陸地ポリゴンは zoom 5 と 1 で分割している。もっと大きな値で分割したいのであるが、ポリゴンが巨大なため、 重複が多くなりすぎるためである。
このために、レンダリング負荷が予想以上に大きい。
自前のプログラムで分割すればパフォーマンスの向上が図れる。
しかし、プログラムによる分割は簡単ではない。分割線が南北、または東西の境界線と二度だけ交わる場合、 その線でポリゴンを二つに分割できる。海岸線が入り組んでいて、三回以上交わる場合、分割は簡単ではない。 このため、以前作った分割プログラムは三回以上交わるものは分割線の候補から除外している。
Map４ではプログラムのスリム化を目指しているため、自前の分割は行わない。
一度レンダリングした陸地だけのタイル画像をストレージに保存しておく。 陸地だけ、海だけといった単色タイルが多くなる。この無駄を減らす工夫は後から行う。
陸地ポリゴンデータは半年～２年に一度更新するだけであるから、保存したファイルは長く使える。 通常はシンプルな画像のため、圧縮率は高く、ファイルサイズが小さくなるため、読み込み時間は速い。
無駄の省き方は単色タイルはファイルを削除して、データとすることである。
また、例えば、zoom 12 のあるタイルが単色であれば、その子供(zoom 13)の４つのタイルも同じ単色である。 孫(zoom 14)以下についても同じことが言える。
この方法により、実際に保存する陸地ポリゴンタイルファイルや管理データは減らすことができる。
一度はレンダリングすることになるため、バイナリレコードファイルは現在と同じように必要である。 したがって、このファイルサイズはなるべく小さくしたい。
zoom 5分割では、日本地図全体は 5/28/12(24.1MB)、5/28/11(4.62MB)、 5/27/12(17.4MB)、5/27/13(24.4MB) となる。 可変長バイトコードにより、かなり縮小するとは思うが、トータルでは かなりの大きさである。
間引きは行わないとしても、高ズーム用は zoom 6分割、 中ズーム用は zoom 4～5分割として、精度を小数点以下５桁にすれば、 多少はファイルサイズが小さくなるであろう。
可変長バイトコード実装は上記にそって、 陸地ポリゴンだけのレンダリングからスタートしたい。