これまでは、簡単化も図ったが、どちらかと言えば、パフォーマンスに拘り、プログラムは複雑になってきた。 Map4 では原点に立ち戻り、シンプル化を目指す。4 は 2024年版を意味する。
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
下位３バイト レコード長
num_nodes:
multipolygonの場合、最終要素(最終inner polygonノード数)の最上位ビットは 1 とする。
このファイル形式はその後少し変更した。詳細は後で述べる。
name:en も含んでいるため、ASCII文字も多いが、レコードをメモリ上は short配列とするため、文字コードは UTF-16 とした。
後述するように、OSMバイナリレコードには空間検索用の境界ボックスを追加する。
バイナリレコードはshort配列としてメモリに読込む。
データベースでは空間インデックスが使われるが、自作地図アプリではデータベースは一切使用していない。
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バイトコードが多くなることから、ファイルサイズの縮小はあまり期待できない。
現在は旧版と新版の二つを同時に動かしている。新版はまだ見直しが必要である。
GPS取得回数が２倍になるため、バッテリ消費がその分速い。
これはプログラムを少し複雑にして、地図アプリの平均的なメモリ使用量を大きくする。
このためか、期待した効果が得られていない可能性がある。 何かの機会に、元に戻した方がいいかも知れない。
OSMファイルを更新したり、レンダリングを修正した場合には、この保存ファイルを消去して、 保存ファイルが最新のものになるようにしている。
この方法により、タイル画像の生成頻度は低くなるため、タイル作成時間短縮に拘る必要性は低くなる。
特に、予めバッファを確保しておくには、ブロックファイル(バイナリレコードファイル)の最大サイズを抑えておくほうが よいため、このように変更した。
新版では低ズームはzoom3分割、中ズームはzoom7分割、高ズームはzoom12,zoom7分割とした。
zoom3、7のファイル数は小さいため、さほど問題ではないが、zoom 12 と zoom 13 ではファイル数が３倍前後ことなる。 zoom 13のファイル数は大きくなるため、パソコンからスマホやタブレットに転送するのに時間がかかる。
しかし、パソコン側で全ブロックファイルを一つのzipファイルにまとめて置き、 このzipファイルを Android機で解凍するようにすれば、ファイル数が多いのはそれほど問題にはならないので、 高ズームは zoom 13、zoom 7分割でよいであろう。
他の地図に互すようになるのは10年先かも知れない。しかし、突然、マッパーが増えるかもしれない。 それを期待したい。
８月29日時点では建物数は 2,323万(全レコードの58％)である。 都市部にはマンションが多く、地方には住宅以外の建物の比率が高いため、人口からの推測は難しいが、 日本全体としては全建物の半分程度しかマッピングされていないであろう。
この半年余りで全レコード数は 576万レコード増えている。60％が建物レコードであると推測すると、 予想以上の進捗である。インポートが進んだのかも知れない。
4バイトか8バイトとすれば、殆どのレコードが４バイトで済む。 0/4/8バイトまたは0/8バイトとして、デバッグ上も osm_id の必要性が極めて低い建物などは osm_id を省けば ファイルサイズの増加は僅少となる。タグに osm_id があってもデバッグでは簡単に取り出せないケースがある。