What a map vertex costs

Here is a building in the centre of Warsaw the way our previous offline map format stored it, :

Grid step 73 cm. Corners move by up to 44 cm, 28 cm on average.

The dashed line is the outline as it was mapped in OpenStreetMap. Every vertex of a GLMap tile sits on a grid laid over the tile, and the tiles that serve street-level zooms cover about 3 km of Warsaw each. With 12 bits per axis the grid step there is 73 cm, and the orange lines show how far each corner moved to reach it. At zoom 13 nobody sees that. At zoom 17, where these buildings fill the screen, the corners visibly go astray. the step is 18 cm.

gom5, our new map format, moved to 14 bits. Those two extra bits per axis cost bytes in the file, bytes in the download and time in decoding, and we did not see all of it at once.

Three bytes

gom4 stored each vertex as two 12-bit numbers, three bytes, with no encoding at all. Fixed width has two properties that are easy to forget until they are gone: the engine can find the tenth vertex of a line without reading the first nine, and it can skip a whole line by moving forward three bytes per point.

The obvious way to get 14 bits is to keep the fixed width: 28 bits, three and a half bytes per vertex. The map of the Masovian Voivodeship, the region around Warsaw, has 43.4 million vertices, so that would add 22 MB to it.

Deltas and varints

Neighbouring vertices of a line are close to each other, so instead of each position a format can store the first point and then the difference to the previous one. A difference can be negative; zigzag encoding moves the sign into the lowest bit, so that −1 becomes 1, 1 becomes 2 and −2 becomes 3, and small differences of either sign stay small numbers. Then each number is written as a varint: seven bits of value per byte, and the eighth bit says whether another byte follows.

Here is a real line in all three codecs, bit by bit. Hover over a point to see where its bits are:

bits of a valueleading zerosvarint "more" bitfield width

 

In the first ribbon every point costs 24 bits, however close it is to the previous one. In the second, every byte spends its orange bit on saying whether the number goes on, and the faded cells are leading zeros of values that did not need all seven bits. Compare the , five points and long walls, with the , 118 points that are mostly close together.

How many bytes a delta needs depends on the data, so we counted all of them in the Masovian map on the 14-bit grid:

 

Two thirds of the per-axis deltas fit into seven bits, and nearly all of the rest into fourteen. On average a vertex came out at about three bytes: the same as in gom4, with a grid four times finer. On our test region in July the gom5 file was even a little smaller than the gom4 one. We shipped that.

The download

The first cost showed up in the download. Maps travel as xz archives, and xz is very good at the regular, fixed-width records of gom4. With the same compression level, xz -9, the three versions of the Masovian map come out like this:

gom4, 12-bit grid203.3 MB file125.3 MB with xz -9

gom5, varint deltas208.8 MB file148.6 MB with xz -9

gom5, bit-packed lines196.1 MB file151.2 MB with xz -9

The is 2.7% larger than the , mostly because gom5 has since gained polygon identities, but its archive is 19% larger: 148.6 MB against 125.3 MB. Most of that is the precision itself. The two extra bits per axis say where inside the old 73 cm cell a corner really is, and no compressor can remove information that is really there. Four bits per vertex times 43.4 million vertices is 22 MB; the archive grew by 23 MB.

Decoding

The second cost was time. A varint is read one byte at a time, and its length is known only after its last byte. To skip a line, the reader has to walk through every byte of it.

When we profiled tile loading on the Masovian map this October, decoding varints took 14% of the time. We tried a decoder without branches: load eight bytes at once, count the leading continuation bits to get the length, mask out the value. It decoded every tile identically and was 5 to 8% slower. The next load cannot start until the length of the current number is known, and that chain of dependencies lost to a branch predictor that guesses the length and is right most of the time. We threw it away.

One width per line

In July we had estimated per-line bit packing at 4 MB on a 124 MB map and decided it was not worth the complexity. We came back to it in October, while working on online tiles, where reading speed matters as much as size.

The idea is to give each line one field width instead of letting every number choose its own length. After the point count comes a 32-bit head: the first point as two 14-bit numbers and a 4-bit width w, the number of bits the largest zigzag delta of the line needs. Then every delta is two w-bit fields, without continuation bits, and the line is padded to a whole byte. That is the above.

The width is set by the largest step of the line, so the short steps waste bits. Usually the edges of one line are of similar length, and the fits into 13 bytes instead of 14 as varints. The shows the other case: one of its edges is 220 m long, that sets the width to 11 bits, and all 117 deltas pay for it, 326 bytes against 255 as varints. Over the whole map the first kind of line wins by a wide margin, as the numbers below show.

Because the count and the width give the length of a line, skipping a line is one addition again, as in gom4, and the reader passes over lines it does not need without decoding them.

We measured two refinements and kept neither: separate widths for x and y made the file 0.2% larger, because the second width in every head costs more than it saves, and a fancier variant saved another 0.9% but decoded 12% slower.

On the Masovian map the file went from 208.8 MB to 196.1 MB, 6.1% smaller, and loading all 4,260 street-level tiles went from 1,400 to 1,350 ms. Online tiles use the same codec: the tile cache shrank from 210.6 to 198.6 MB, and parsing all of its 4,290 tiles went from 921 to 869 ms.

And the archive grew

The compresses worse than the varint one: 151.2 MB against 148.6 MB, 1.7% more. The likely reason is that its fields no longer line up with bytes. xz looks for repeated byte sequences and predicts each byte from the ones before it, and a 5-bit field that starts three bits into a byte looks like a different byte every time it appears.

So the file on the phone is 12.7 MB smaller and faster to read, and the download is 2.6 MB larger. On the bit-packed codec, the vertex data of the Masovian street-level tiles would be 12.9% smaller on the old 12-bit grid; that is what the 18 cm grid costs today.