It'll be a few days before I have time to look at this in much detail and give you my thoughts but from what I can see it sounds promising. We actually use protobufs at my job for shunting around vast amounts of data so I'm pretty familiar with the pros and cons of them. One concern is that even if your binary format becomes reasonably standardised in the OSM world we'll still need to maintain .osm support for the forseeable future.Perhaps that can
be tackled by swapping out the existing cache format with your protobuf
format.
I envisioned it as an alternate format that could exist in parallel with the osm, but also be smaller and faster. I still need to clean up the osmosis patches and turn them into a plugin.
Even that I'm not sure about in the longer term; to tackling some of the harder problems with the splitter will require more than just a linear protobuf or cache format. Data structures such as Btree indexes and so on will likely be required, though I'm sure we can cross that bridge when we come to it.
What harder problems do you think the splitter needs solved? I'm not so sure about your lazy HashMap initialisation in Element.java,
though it does highlight a bug that was introduced by the recent r109 multithreaded patch! Prior to patch r109, Element objects were never recreated, rather .reset() was called to just reset their state for each new node/way/rel.
The reason for this was the costs of initializing were showing up in the profile.
r109 changed that to create new instances each time, hence some of the object churn you were probably seeing that lead you to your patch. I'll have a think about to do here and probably run a few benchmarks to see what works best (eg keeping one current Node/Way/Rel per thread might be best).
May I suggest holding off on this for a bit? The branch that adds support for reading the binary file format refactors this interface so that node/way/rel objects are passed directly instead of using an interface that looks like an XML callbacks. [As an aside, note that in your lazy HashMap patch Collections.EMPTY_SET
results in an unchecked assignment warning. That of course is no big deal, easily fixed with Collections.<String, String>emptyMap().entrySet(). The sting though is that the call to Collections.EMPTY_SET.iterator() actually creates a new iterator object each time(!). Better would be to create a single static immutable iterator and return that]
Good catch. Should I respin the patch or will you?
My multithread changes reduced the real and user CPU time by 30-50% on a uk extract. Other tests, e.g., a whole planet, show almost no effect. I think this is because a lot of my changes increase the efficiency of code that is parallelized, which paradoxically ends up reducing the relative benefits of parellelization.
This sounds promising, I'll look at what you've done further in the next couple of days and hopefully get it committed this weekend.
The single biggest remaining slowdown is that for each point, the splitter sends each Node to each area (represented by an OSMWriter), which writes it in the output file if it is in the bounds of the region (with overlap), or does nothing otherwise. On a whole planet, with 840 areas and 550M nodes, that is over 5 trillion bounds-checks that are not run in parallel. An index that can can map a node to the regions that may contain it could avoid 99% of these checks.
This is something I've been aware of for a long time but haven't found the time to tackle yet. One idea I have is to generate an r-tree in memory and run the node comparisons against that to find out what area(s) each node falls into.
josm already includes a quadtree implementation. I wish it could be disentangled and re-used across the different OSM applications. It'd be a perfect solution here.
I'd estimate it would reduce the number of comparisons required from 840/node to less than 10. I suspect that would be a win over generating a node to area index which would be expensive to create intially, plus expensive in terms of disk access (or alternatively, require lots of RAM). Also, with a bit of effort these r-tree comparisons could be parallelised too.
Perfection isn't necessary. How about a 64x64 array. Divide the world into 4096 regions. Each region contains a list of all areas --- including their overlap --- that intersect it. Then, for each node, you only need to iterate the OSMWriters in that region. Getting the round-offs right would be tricky, but it should be good enough filter out almost all non-matching areas. I'll follow up in a while once I've had a bit more time to investigate and
respond. Many many thanks for your work on all this, very much appreciated!
Chris
Thanks for a useful program. Glad I could help make it better. Scott