OSMバイナリレコード形式を根本的に変更するため、メモリ使用量やパフォーマンスについて気がかりである。 簡単な所からテストを始めて見通しをつけたい。
建物を表すレコードは簡単であるが、数は全体の過半数を占める。 まず、このレコードだけを作り、レンダリングを行い、メモリ使用量やパフォーマンスを確認したい。
殆どの建物は一つの Wayレコードで完結している。レンダリング上のタグは building だけのケースが殆どである。
他にNodeタグによるレコード、Relationタグによるレコードがあるが、数量的にはWayレコードが大半を占める。 このため、建物だけのレンダリングである程度の見通しがつく。
c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Parser -run hot 建物レコード数＝19163, Wayレコード＝31309, 建物レコードの平均タグ数＝1.020717, 平均Node数＝6.7095447 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Parser -run kanto 建物レコード数＝4331819, Wayレコード＝7026273, 建物レコードの平均タグ数＝1.0707476, 平均Node数＝6.527187 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class Parser -run japan 建物レコード数＝19373553, Wayレコード＝32023242, 建物レコードの平均タグ数＝1.0443347, 平均Node数＝6.330969
バイナリレコード形式
num_kvs, {key, val}*, num_nds, {lon, lat}* ..... 第一案
length, num_kvs, {key, val}*, {lon, lat}* ..... 第二案
に従って、建物レコードだけを出力した結果は kanto が 252MB(61.1B/レコード)、
japan が 1,122MB(59.3B/レコード) となった。
最初のプログラムは第一案に従った。第二案でもファイルサイズは変わらない。 いずれがよいかは、地図アプリのプログラムによる。
num_kvs, {key, val}* の平均長は 8バイト強であり、座標値がレコードの大半を占める。
座標値の差を１～５バイトで表した方が、ファイルサイズ自体は小さくなるが、処理が複雑になり、符号化、復号化に時間がかかる。 このため、先頭ノードの座標値のみ４バイトで表し、後続ノードについてはその前との差を２バイトで表す。 ただし、一つでも２バイトで表せないときには、全ての差分化を断念する。
差分コードをdefaultとして、差分コードで表せないとき、特殊 key として、Key.int_code を含めることにした。 kanto.dat は 165MB(35％減)、japan.dat は 718MB(41％減)となった。
空間検索結果はレコード毎のオブジェクト管理が妥当であるが、メッシュ単位のブロックキャッシュとしてはレコードが多いため、 オブジェクト管理のオーバヘッドが問題になる。
まずは、境界ボックスとレコード長を配列構造で管理したい。 ここでは、差分を使わなければ、レコード当たり18～20バイトのメモリが必要となる。
差分では 10バイトで済む。差分で管理するレコード群と差分を使わないレコード群の二つに分ける案もある。 安直に 18～20バイトを使うのでなく、時間をかけて、削減方法を探りたい。 ただし、18～20バイト/レコードであればそれほどメモリを圧迫しない。現状と大差がないであろう。
レコード長や境界ボックスの縦横は大抵の場合、２バイトで表される。 縦横は大きめであれば安全サイドであるから、４～１６で割った数を使えば、２バイトで表されるケースが増える。
num_tagsおよび num_nodesを長さに変えれば、レコード長はなくてもよい。
num_nodes はやめて、レコード長を先頭２バイトに置く。レコード長が 15ビットで表せないレコードに限り、 先頭４バイトをレコード長とする。これで空間検索のスキャンはできる。
バイナリレコード形式を
num_kvs, {key, val}*, num_nds, {lon, lat}*
としたときのプログラムを下に示す。
kanto.dat は 165MB(35％減)、japan.dat は 718MB(41％減)となった。
差分コードを使わなかった場合は
kanto が 252MB(61.1B/レコード)、
japan が 1,122MB(59.3B/レコード) であった。
Parser.java
バイナリレコード形式を次のように変更した。ファイルサイズは変わらない。
length(2/4), num_kvs(2), {key,val}*, {lon,lat}* ... point/line/polygon
length(2/4), num_kvs(2), {key,val}*, {num_nds(4)}*, {lon,lat}* ... multipolygon
レコード長は第二案ではバイナリレコードの先頭と重複するが、おそらく、レコード配列のアクセスの方が速くなるだろう。
境界ボックスは４バイトx４＝16バイト使用する場合には、北西と南東の座標値とした方がよい。 殆どのレコードでは、縦横の長さはそれぞれ２バイトで表現できるため、このときは北西(4x2バイト)と縦横(2x2バイト)がよい。 しかし、縦横を２バイトで表現できないレコードがあるため、混在させると、空間検索時間が長くなる。
境界ボックスの縦横、座標値の差分を２バイトで表すレコードと差分を使わず、全て４バイトで表すファイルを分ける方が パフォーマンスはよい。しかし、メッシュ分割では元々ファイル数が多い。それが２倍になるのには抵抗がある。
境界ボックスとレコード長を全て４バイトとした場合は管理データは 20バイト/レコードとなる。 建物レコードの場合、バイナリレコードは約 60バイト/レコードであるから、全体で約80バイト/レコードとなる。
建物レコードは比較的小さく、全レコードの平均値は 100バイトあるいはそれ以上になると思われるので、 管理オーバヘッドは 20％以下になる。我慢できない大きさではない。 もう少し考えて、いい案を思いつかなければ、まずは、この案でプログラムを作ってみよう。
なお、現在は、境界ボックスやレコード長はバイナリレコードに含めており、この方が少し全体のメモリ使用量が少なくてすむ。 しかし、境界ボックスやレコード長をまとめた方が空間検索が高速化される可能性があるため、新しい方法を試したい。
とりあえず、ファイルをバイト配列として読み込み、スキャンして、レコード数だけを求めた。タブレットでの実行結果を 下に示す。65ms は全体の時間であり、ファイル読み込み時間は 28ms である。スキャンは ByteBuffer を使った。
これまでは、境界ボックスはバイナリレコードファイルに含めている。 バイト配列をスキャンして、境界ボックスを求めるのは、時間的に厳しい可能性が高い。 境界ボックスをレコードに含める場合、平均的にレコードサイズは８バイト以上増加する。
バイナリレコードファイルのフォーマットを変更して、先頭に、レコード長や境界ボックスなどをまとめておく案もある。 空間検索のパフォーマンスは向上し、管理メモリも減らせる可能性がある。
まずは、今回のフォーマットで境界ボックスを作り出す時間を計測してみる。
管理データは初めてバイナリレコードファイルを読み込んだ時、生成し、ファイルにセーブしておく。 ２回目からはそのファイルを読み込む。時間がかかるのは一回目だけであるから、それほど不便はないであろう。
管理データはレコード当たり 32バイト(4byte x 8)程度となろう。
scan 392698records, 37ms #1 /storage/emulated/0/Map/kanto12/3638/1612.dat 65ms 14476KB
時間がかかるのは、ByteBuffer のオーバヘッドかもしれない。 下のgetShort()メソッドを使ってみた。
static int getShort(byte[] ba, int off) {
return (ba[off] << 8) | (ba[off+1]&0x00ff);
}
(ba[off]&0x00ff << 8) | (ba[off+1]&0x00ff) とすべきか？
結果は下のように大幅に速くなった。しかし、これでもほぼ全バイトをスキャンするには時間がかかるであろう。
scan 392698records, 6ms #1 /storage/emulated/0/Map/kanto12/3638/1612.dat 30ms 14476KB