これまでは、簡単化も図ったが、どちらかと言えば、パフォーマンスに拘り、プログラムは複雑になってきた。 Map4 では原点に立ち戻り、シンプル化を目指す。
OSMバイナリレコード形式についても抜本的に変更する。
アプリの要になるのは、OSM地図のレンダリングに使うOSMバイナリレコードのフォーマットである。
できるだけ簡素にしたいが、平均サイズをなるべく小さくしたい。また、パフォーマンスも重要である。
nameタグ、refタグなどの文字列は val とする。(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
第2bit(0x04) 0: 差分座標、1: 絶対座標
下位３バイト レコード長
num_nodes:
multipolygonの場合、最終要素(最終inner polygonノード数)の最上位ビットは 1 とする。
name:en も含んでいるため、文字コードは UTF-8 とした。
バイナリレコードはバイト配列としてそのままメモリに読込む。 全レコードをスキャンして、空間検索に使う境界ボックスなどを int配列に格納する。
class Block {
byte[] vals; // OSMバイナリレコード(ファイル全体をbyte配列として読込んだもの)
int[] idxs; // 境界ボックスなど
// その他
}
データベースでは空間インデックスが使われるが、自作地図アプリではデータベースは一切使用していない。
OSMバイナリレコードは予めメッシュ分割しており、一つのバイナリレコードファイルでの検索は単純な順次検索である。
地図アプリMap3では、zoom 13以上のレンダリングは zoom 13で分割したものを使う。 しかし、広域森林のような巨大なポリゴンは、zoom 13では無数のメッシュ(タイルと同じ)にまたがるため、 重複が多くなる。これを避けるために、zoom 13分割では重複が多すぎるレコードは zoom 7 で分割している。
分割を２段階にするのではなく、境界ボックスが巨大となるレコードは分割せず、レコード毎のファイルにする案もある。 ファイル名は通し番号に境界ボックスの４値を並べたものとする。
zoom 7で分割しても重複はあるため、個別ファイルとした方が全体のファイルサイズは小さくなり、 ファイル読み込み時間は短くなる。
パフォーマンスの向上は期待できるが、分割プログラムやキャッシュ方法は異なるため、プログラムの負担はやや大きくなる。 シンプル化には反するので、大きな効果が期待できなければ見送る。
Parser の出力は Node、Way、Relation に分かれるが、Devider の入出力は一本化されるため、レコード長などの チェックが簡単である。
2024.2.9の結果を下に示す。
c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -devide 3 3 japan-low レコード数=365257, 最大レコード長=202910, 平均レコード長=102.1, 平均タグ数=5.5, 平均タグ長=60.0B 実行時間: 0.03分 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -devide 7 7 japan-mid レコード数=1577121, 最大レコード長=1039134, 平均レコード長=102.9, 平均タグ数=2.9, 平均タグ長=27.4B 実行時間: 0.13分 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -devide 12 7 japan-high レコード数=34220205, 最大レコード長=4539898, 平均レコード長=54.6, 平均タグ数=1.3, 平均タグ長=7.6B 実行時間: 2.15分
早速にタグを絞り込んだ。低中ズーム用ファイルサイズは大幅に縮小した。今後、タグは多少追加すると思うが、 ファイルサイズが大幅に増えることはないであろう。
c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -devide 3 3 japan-low レコード数=365257, 最大レコード長=202876, 平均レコード長=46.3, 平均タグ数=1.0, 平均タグ長=4.1B 実行時間: 0.03分 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -devide 7 7 japan-mid レコード数=1577121, 最大レコード長=1039100, 平均レコード長=79.4, 平均タグ数=1.0, 平均タグ長=3.9B 実行時間: 0.17分
現時点ではパフォーマンスはMap3より劣る。特に、中低ズームでは、ガーベージコレクションが頻発する。 高ズームではそれほど極端ではないので、プログラムを複雑化しない範囲での改善でもいいであろう。
バイナリレコードファイル単位の管理ファイルを設ける、または、 バイナリレコードの前に管理データを置くことも考えられる。
全ブロックの管理ファイルであればメモリに常駐しても負担にならない。
例えば、レコード数がバイナリレコードファイルの先頭にあれば、 Block.get()の int[] buff = new int[10*1024*1024]; をやめられる。
Block.getOSMS() の int[] poly_nodes = new int[256]; byte[] tags_buff = new byte[2048]; を外に出そうとしたが、簡単ではない。マルチスレッド処理のため、static 配列にできない。 スレッド毎のデータをもつ Renderer には移せる。しかし、それだけでは済まず、 リセットとか関連プログラムの修正も必要になる。
安直に new を減らそうとすべきではなく、根本的に処理を見直すべきである。
Map3では OSMに極力配列を置かないようにして、再利用を図った。 Map4では、OSMの再利用は行わず、いくつかの配列データもある。 ガーベージコレクションの対象が増大している。固定長であれば、再利用が簡単であるが、 可変長配列データの再利用は難しい。
Map３のように、データ本体は Block に置き、インデックスを OSM に持つべきかも知れない。 ガーベージコレクションは減らせるが、データ読み出しに時間がかかる。 座標変換をレンダリング処理で行うことになる。
現在は、OSM#pts[] に極座標を入れ、必要に応じて、ポリゴン面積を算出する。 その後、レンダリングするタイル座標に変換する。レンダリング処理が簡単である。
現在のバイナリレコードファイルからレンダリング用バイナリレコードファイル を作り出すのはどうだろう。
可変長バイトとなるタグ部は末尾にまとめる。座標値データ部はint配列とする。 差分座標値は lon、lat を合わせて int とする。標準タグ一つ(key, val合わせて４バイト)を int配列末尾に置く。これにより過半数のレコードは追加タグ部無しとなる。
レンダリングの際、極座標からタイル座標(画素単位)への変換がいるが、 Map３より前はそうしていたように、それほど時間がかかるわけではない。
バイナリレコードファイルを読み込んだ時、byte配列を int配列に変換するが、 これは Map３と同じである。
タグ部はMap3よりも複雑である。 しかし、大半のレコードは key、val 共に２バイトであるから、パース時間は小さい。
メモリ上には置くので、境界ボックスもレンダリング用バイナリレコード含めた方が いいだろう。
何か更なるメリットがほしい。
現在、中ズームは zoom 12 まで、低ズームは zoom 7までとしている。この場合、 レンダリング上、中ズームの精度は zoom 12、低ズームは zoom 7までのの画素単位のタイル座標でよい。 こうすれば、より多くのレコードが差分座標で表現できるため、バイナリファイルサイズが縮小できる。
バイナリレコードの座標をXY平面座標とした場合、面積計算はやりにくくなるため、 必要に応じて面積をバイナリレコードに含める必要がある。
高ズームではブロックファイルの読み込みは稀であり、スクロールしてもI/Oが発生する可能性は小さい。
低ズームでは日本全体のデータがメモリに読込めるため、やはり、I/Oのオーバヘッドは殆どない。
中ズームで日本全体をスクロールするようなとき、最もI/Oオーバヘッドが大きくなる。 現状(2024年3月上旬)では、メモリ不足で地図アプリが落ちることもありうる。
中ズームのブロックファイルは全体で現在は 214MB である。 他に、陸地ポリゴンレコードファイルの読み込みも必要であるため、全ファイルをメモリに読込むのは厳しい。 高ズームから中ズームへの変更であれば、当然、一度はブロックファイルの読み込みが必要となる。
タイルのレンダリングに使用するレコード数が高ズームよりはるかに大きくなるため、 レンダリングにも時間がかかる。
以上のことから、パフォーマンス上は中ズームのレンダリングが最も厳しい。
現在のバイナリレコードの極座標値の精度は小数点以下７桁である。中低ズームではこのような精度は要らない。 現在、中ズームでは zoom 12 で 0.1画素相当の精度があれば十分である。
正確な値ではないが、仮に zoom 20 の精度を小数点以下７桁とした場合、zoom 10での精度は小数点以下４桁でよい。 zoom 12 であれば 小数点以下５桁あれば十分である。小数点以下４桁でも良いかもしれない。
zoom 0 がタイル１枚で経度では360度であるから、256画素で割ると、画素当たり１.4度である。 zoom 10では、画素当たり 0.0014度、zoom 12では 0.00035度/画素であるから、小数点以下４桁～５桁の精度でよいであろう。
中低ズームではノードの間引きを行っているため、 高ズームに比べると、ノード間の座標値の差は大きいが、それでも、差を１バイトで表現できることが多くなるであろう。
可変長バイトコードを使えば、現状よりはファイルサイズをかなり縮小できる可能性がある。
陸地ポリゴンについては、現在は zoom 10以上が高ズームで間引き無し、zoom 9以下が低ズームで間引きありの ２段階であるが、一般のOSMデータと同じく、高中低の３段階として、中ズームにも間引きを施せば、 ファイルサイズは縮小するため、より多くのブロックファイルをメモリにおけるようになり、 パフォーマンスが改善するであろう。
可変長バイトコードは大半が１バイトですむならばラッキーであるが、 ２バイトの比率の方が大きいようであれば、 現在の差分コードとの差が小さくなり、パフォーマンス向上に寄与しない。
可変長バイトコードは座標値列データへの適用がメインであるが、他の数値への適用も考えられる。 レコード長も過半数が１バイトコードとなる。ノード数(または座標値データ長)も１バイトが多い。 タグの key、val も１バイトで済むケースが多い。文字列長も殆どが１バイトでよい。
中低ズームの場合、可変長バイトコードを採用すると、バイナリレコードファイルのサイズが半減する可能性もある。 可変長バイトコードはサイズが１バイトの場合は復号化は簡単である。２バイトのケースは少し処理が増えるが、 ３バイト以上のケースは稀と予想されるので、平均的な復号化時間は少なく、パフォーマンスを低下させる恐れは少ない。 ただし、極力メソッドコールのオーバヘッドを減らす必要があることから、プログラムコードは多少、かさみ、 分かりにくくなるであろう。
高ズームの座標値データについては、小数点以下７桁の精度の場合、１バイトコードよりも、 2バイトコードが多くなることから、ファイルサイズの縮小はあまり期待できない。