Published by breki on 29 Sep 2008 at 10:54 pm
Kosmos And Large Maps
This weekend I was playing around with Kosmos by trying to load large maps (by “large” I mean country-size large). I have never really done this before, since I was more concentrated on smaller areas when I developed the software.
The initial results weren’t really encouraging – Kosmos managed to load the OSM extract of Austria (25 MB of .osm.bz2 file), but the GUI was burning around 1 GB or RAM and it took some time to load. Then I got into investigating how this could be improved.
I managed to do a few things which greatly improved the performance:
- OSM tags were stored as C# generic Dictionaries (for each OSM element). This is a problem, since typically there are no more than few tags for an element. It turns out the ListDictionary class is better suited for small dictionaries, since it uses linked lists instead of hash tables.
- A lot of memory was being taken by “created_by” tags for each OSM node. Since this tag isn’t really much used when rendering maps, I decided to ignore it when loading OSM files (OSMXAPI ignores it too, by the way). This can save a lot of space, since most nodes do not have any other tags – which means the tags dictionary doesn’t even have to be created for such a node.
- Immediately after loading the map, the garbage collector is now called to dispose of any temporary objects. I know, GC isn’t supposed to be called manually by applications, but I guess in these extreme circumstances it can be forgiven – especially since it frees up several MB of RAM immediately.
- The last thing to do was to write a custom OSM XML loader. Until now I used XmlSerializer classes autogenerated from OSM XSD. This has several disadvantages: you have to load the whole OSM file into memory in order to (de)serialize it and also produces a large quantity of intermediate objects which then have to be translated into “proper” OSM objects. But by writing a custom loader which reads XML sequentially (using XmlReader) both of these obstacles can be overcome. Still, writing XML parsing using XmlReader isn’t easy (in fact is real pain in the you know where).
Anyway, after these modifications Kosmos loads Austria data more quickly and with much less memory footprint (around 400 MB). It’s still a slow experience on my machine (E6400, 4 GB RAM), but at least it’s improvement.
I tried to load progressively larger country extracts – the largest one that did load so far without throwing the OutOfMemoryException was France (54 MB). The screenshot above shows Czech Republic (43 MB).
NOTE: by doing this I wasn’t really aiming to achieve some kind of “planet coverage” with Kosmos – it’s virtually impossible for Kosmos GUI to draw the whole planet interactively. But I would like for non-interactive Kosmos Console at least to be able to generate tiles for larger areas (UK or Germany, for example, or even the whole of Europe) in some reasonable time – but there’s a lot of things to do before this is possible. I guess the first steps have been made…
Paolo Molaro on 30 Sep 2008 at 23:44 #
Nice improvements. The last weekend I wrote a prototype renderer (it’s less than 1000 lines of code, so nothing high-quality at large detail levels, yet) and I faced some of the same issues. XmlReader is definitely the way to go. Additionally make sure that strings are atomized (like interning, but I did it with my own code to allow eventual unload) both of the tag names and values (even names are often duplicated so it’s usually worth not special casing them out). For tags I use a string[] array with both tags and values sequentially: almost always there are few tags so saving the memory here is worth it as searching is going to be fast anyway (eventually putting hot tags at the start is an option, depending how really performance critical is tag search during rendering in your app). During load I also calculate a bounding box for ways at a specific zoom level and I prune the way list based on the current view and the calculated scaled bbox (this adds a little time to load, but greatly speedups rendering at high detail level). Ways are also pruned if there is no rule for them at that zoom level. Then, at least in my case (using Cairo for rendering, so I have pdf for free) having different (simplified) rendering rules at low zoom helps a lot (no point setting line cap options if line width is going to be <= 1, for example). The end result is that, for example, the Czech Republic file is loaded and rendered using 370 MB (this is Mono on Linux). I also loaded and rendered the germany file (it used about 1.5 GB on my 2 GB laptop), but in that case the loading time is long (8 minutes, our XmlReader is defintely slower than the MS .net one). I’m sure I can save more loading time (I’m using the code from my osm-helpers assembly, but that builds objects that I’m throwing away because I use the more memory optimized implementation described here). And, yes, created_by is the first tag I discarded (there are a few minor ones like note and source). I’ll automate this to discard all the tags that don’t appear in rendering rules (though this restricts the ability to add rendering rules at runtime in the GUI). I also remap node refs from long to int to save a few more megabytes. Further improvements are possible at higher cost (read changes in the generic string-based rendering code) by turning tag/values combinations into bitflags. Anyway, with the above tricks rendering is almost interactive even with the large maps (1-2 seconds render time, so still aa bit too slow:). Happy hacking! lupus
breki on 01 Oct 2008 at 7:05 #
Paolo, nice ideas!
Some comments from my side: using string[]‘s for tags is a good idea, maybe I’ll try it – but I’m hesitant because I want to keep the structure addable (in case Kosmos becomes an editor, who knows). String interning: funny, I just implemented something like this yesterday: OsmTagFactory class that keeps a dictionary of all created tags and makes sure the same key-value is not created twice. It’s not as strict as interning, but it helps when loading OSM data into memory. Results: from 600,000 tags in Austria.osm only 100.000 are unique. And this could be improved if the keys are treated as case-insensitive (though I don’t know if this is a good idea).
Paolo Molaro on 01 Oct 2008 at 9:57 #
I don’t think string[] prevents editing: changing a value is trivial and removing/add just requires a realloc of the small array, which when interactively editing is not going to be noticeable. Mass changes will be a bit more costly, but not much so and in that case the common thing that happens is to change a value. OsmTagFactory is also a good idea: I tested something similar as well, but using multiple tag/value combinations (and keeping name as an explicit separate field). This shares even more info. Anyway, atomizing I think is more promising memory-wise when you consider that you can insert the string ID instead of the string reference and that you can pre-assign the low ids to highway, landuse etc and their most common values. This means that almost all the tag/value pairs can be represented with two bytes (this of course would work also with ids assigned to OsmTagFactory-like tag/value pairs). As for the maximum node id I think it’s currently just over 300 million. I safely remap them to ints, though: I don’t assume a node ref fits into 32 bits.
breki on 01 Oct 2008 at 12:32 #
You’re right – and since the adding of tags is not done very frequently (compared to retrieving), it shouldn’t be a problem.
How would you represent uncommon/custom tag values (e.g. name=London and similar?). Basically all place names are unique and there can be a large number of them, larger than one or two bytes can cover.
This should suffice for now, I guess.
Paolo Molaro on 01 Oct 2008 at 14:25 #
>> How would you represent uncommon/custom tag values (e.g. name=London and similar?). Basically all place names are unique and there can be a large number of them, larger than one or two bytes can cover.
You use an encoding like utf8 or leb128: an arbitrary integer can be encoded but values up to 127 fit into one byte. Two bytes allows encoding of 16384 values, three bytes up to 2097152, so enough for very large maps. highway=residential will require 2 bytes, name=London 3 or a maximum of 4 bytes. So in the worst case the memory usage is half on 32 bit systems vs using two strings and one fourth on 64 bit systems.
BTW, I also use floats to represent coordinates, the error introduced is less than 0.3 meters), but this is not suitable for editing.
igorbrejc.net » Kosmos 2.3 - now with integrated slippymap! on 13 Nov 2008 at 21:03 #
[...] improvement is in Kosmos’ performance (both speed and memory-wise). I already wrote something about it in September. Anyway, you should be able to load larger chunks of OSM data [...]
igorbrejc.net » Kosmos And Spatial Databases, Part 1 on 23 Oct 2009 at 18:36 #
[...] Kosmos loads all the OSM data into memory. This obviously proves to be a problem for larger areas. Some time ago I worked on optimizing Kosmos memory usage and it proved to be quite successful, but there is still a physical limit of how large an area can [...]