Splitting the entire planet in one pass.
Well, technically two passes; the first pass is needed to figure out where to split. A new set of patches and line of development in my tree. Features: About 1/3 of the RAM usage. An entire planet can be split into 1200 areas in one pass with -Xmx5000m --max-nodes=1000000 in one hour. No upper bound on how many areas a node/way/relation can occur in. I've tested large overlaps with nodes in >10 regions. Generate up to 6700 areas in a single pass. (Yes, -Xmx5000m --max-nodes=50000 --max-regions=6700 on a 8gb machine generates 20,000 regions in three passes in 4 hours!) If areas.list says so, areas can overlap. The underlying algorithm can also handle non-rectangular areas. Quite a bit faster RAM usage proportional to the total number of nodes in the output files, at about 4 bytes per output node. Issues: 1. Two passes may be needed for a whole planet with 4gb of physical RAM. 2. Scaling to thousands of areas/output files in one pass can cause problems. a. There may be a system limit on number of open files. b. Per-file memory overhead of Java's IO layer and GzipOutputStream can cause unexpectedly high memory usage. On my machine, this limits me from doing >=10,000 areas per pass. c. The current threading code behaves badly, causing >300k context switches/second. My previous threading code also behaves badly, requiring one thread per output stream. I have new threading code that overcomes both problems and is 15% faster. 3. Dependencies on fastutils and dsiutils jars. 4. Depends on the refactoring I did to support the binary format. 5. Splitter does not find good splits with --max-nodes =< 50000 in the default resolution. Changes: The main memory overhead in the splitter is to track which nodes are in which area. It formerly used a custom IntIntMap. I refactored it to use an Int2ShortMultiMap, then implemented that MutiMap by composing two underlying Int2ShortMap implementations with different space efficiency tradeoffs, a custom sparsearray implementation based on http://google-sparsehash.googlecode.com/svn/trunk/doc/implementation.html, and one imported from a library of java collections specialized to primitive types. The hybrid has a memory overhead of about 4 bytes per output, storing 750m keys with 800m vals in 3.2gb of heap. Testing: I split the cloudmade extract of NY into 160 areas of --max-nodes=100000 and compared my integration branch 'dev' versus SVN trunk. I then compared 3 of the area files. Files have minor differences. My branch reorders the tags within each node compared to trunk. Also, my XML output routines *always* output 7 degrees of precision, even if the data has only 6 degrees of precision (i.e. '123.1234560' instead of '123.123456'). Other notes: I just found out about a curious option -XX:+UseCompressedOops for recent Java VM's. It lets 32-bit pointers be used in a 64-bit VM, which can, for pointer-heavy uses, cut down on memory usage, cache pressure, memory bandwidth, etc. My SparseInt2ShortMap is fairly heavy on pointers and that option appears to offer a 10% memory reduction. Code is in branch 'perf/multiregion'. Code integrating all of my patches is currently available in branch 'dev' in my git repository on github and will be in SVN within a few weeks. Scott
A new set of patches and line of development in my tree.
Wow, looks like you've been really busy on this. Fantastic work! Sounds like you've implemented a lot of things I've wanted to investigate but haven't even had time to look at let alone code up. And all the great performance improvements aside, I think a lot of people will be very interested in the potential of non-rectangular area support so they can clip to eg country boundaries. As I see it the one big remaining problem to solve is to include entire ways & relations if one of their nodes falls within (or they encompass) an area. I think only certain ways/rels need to be taken into account for this which should make the problem a bit easier to deal with. (as an aside, if you want to read more along the lines of compressed oops, take a look at http://blogs.sun.com/jrose/entry/fixnums_in_the_vm to see where things are hopefully headed within the VM. It should, among other things, make using autoboxed primitives much much cheaper) Chris
On Fri, Sep 17, 2010 at 2:06 AM, Chris Miller <chris_overseas@hotmail.com> wrote:
A new set of patches and line of development in my tree.
Wow, looks like you've been really busy on this. Fantastic work! Sounds like you've implemented a lot of things I've wanted to investigate but haven't even had time to look at let alone code up. And all the great performance improvements aside, I think a lot of people will be very interested in the potential of non-rectangular area support so they can clip to eg country boundaries.
That requires having the OSMWriter object decide if it 'really' wants the point or not, IE, return false from nodeBelongsToThisArea() for points inside the bbox. Not too difficult, I suspect, if the polygon handling code is imported from osmosis and areas.list is extended to support giving polygon geometry information.
As I see it the one big remaining problem to solve is to include entire ways & relations if one of their nodes falls within (or they encompass) an area. I think only certain ways/rels need to be taken into account for this which should make the problem a bit easier to deal with.
Still not easy and requires postprocessing and multiple passes. Roughly, these two algo's will work, but it will NOT catch relations/ways that enter an area, but do not contain any nodes in the area: // Algorithm A: To catch all nodes in a way: Set overlap to 0. (Or a low value to try to catch ways that cross the boundary, but do not contain any nodes *in* the area.) Track which areas a way is in (already done in SplitProcessor.ways). Track nodes missing from ways/relations. If way/relation contains a node that is in area X output it in that file and look at the other node ID's in that way/relation. If any of them are not marked as being in area X, store them in a 'missedNodes' SparseInt2ShortMultiMap. In a second pass, output any nodes in the missedNodes map that are not in the coords Map (indicating that they have already been output), then adding them to the coords Map. In postprocessing, read each file and sort to place nodes at the beginning. Algorithm A will get the complete set of ways that cross the boundary in two passes, which means that if a relation contains a way across a boundary, at least that way will be complete, even if other ways in that relation are excluded. Algorithm B is complete, handling relations containing ways/relations, and correct, but much more expensive. // Algorithm B: This algorithm gets everything, eg, relations containing ways/relations and is much more expensive. Because relations can contain relations, we need to effectively implement a breadth first search across the relation graph, where missingXXXX are the 'grey' colored fringe, and coords/ways/relations are the 'black' visited nodes. Set overlap to 0. We saved which ways were output to which region in SplitProcessor.ways Save which relations were output to which areas in SplitProcessor.relations. If a relation references a way has not been output to the region in question, add the missing way to a missingWays map. If a relation references a relation that has not been output to the region in question, add the missing relation to a missingRelations map. In additional passes, output all ways/relations in the missingNodes/missingWays/missingRelations map which have not been already output, removing them from those maps when they are output. They may reference nodes/ways/relations that are not yet in coords/ways/relations, (ie, not output), causing the referenced nodes/ways/relations entities to be added to the missignNodes/missingWays/missingRelations map. Postprocess by sorting all of the data in each output file. it is possible, but the number of passes will be equal to the 2+maximum depth of the directed graph induced by relations.
(as an aside, if you want to read more along the lines of compressed oops, take a look at http://blogs.sun.com/jrose/entry/fixnums_in_the_vm to see where things are hopefully headed within the VM. It should, among other things, make using autoboxed primitives much much cheaper)
Thanks for the link. Scott
On Thu, Sep 16, 2010 at 4:59 PM, Scott Crosby <scrosby@cs.rice.edu> wrote:
Well, technically two passes; the first pass is needed to figure out where to split.
I was excited to see this, however I'm having some difficulty getting your modified splitter code to compile. It looks like something is requiring a Sun-only API: Buildfile: /home/jcollie/dev/osm/OSM-splitter/build.xml prepare: compile: [javac] /home/jcollie/dev/osm/OSM-splitter/build.xml:76: warning: 'includeantruntime' was not set, defaulting to build.sysclasspath=last; set to false for repeatable builds [javac] Compiling 56 source files to /home/jcollie/dev/osm/OSM-splitter/build/classes [javac] /home/jcollie/dev/osm/OSM-splitter/src/uk/me/parabola/splitter/IntList.java:21: package com.sun.xml.internal.bind.v2.runtime.unmarshaller.XsiNilLoader does not exist [javac] import com.sun.xml.internal.bind.v2.runtime.unmarshaller.XsiNilLoader.Array; [javac] ^ [javac] Note: Some input files use unchecked or unsafe operations. [javac] Note: Recompile with -Xlint:unchecked for details. [javac] 1 error BUILD FAILED /home/jcollie/dev/osm/OSM-splitter/build.xml:76: Compile failed; see the compiler error output for details. Total time: 2 seconds I'm using OpenJDK on Fedora, I'd prefer not to have to switch to Sun Java if I don't have to. -- Jeff Ollie
On Tue, Sep 21, 2010 at 3:05 PM, Jeffrey C. Ollie <jeff@ocjtech.us> wrote:
On Thu, Sep 16, 2010 at 4:59 PM, Scott Crosby <scrosby@cs.rice.edu> wrote:
Well, technically two passes; the first pass is needed to figure out where to split.
I was excited to see this, however I'm having some difficulty getting your modified splitter code to compile. It looks like something is requiring a Sun-only API:
That import is totally unused. Truly bizarre. Just delete the line. But I think I know where it came from: When you use a class thats not imported, eclipse makes suggestions. The wrong click can leave behind the import of a random class. Thanks, Scott
On Tue, Sep 21, 2010 at 10:52 PM, Scott Crosby <scrosby@cs.rice.edu> wrote:
On Tue, Sep 21, 2010 at 3:05 PM, Jeffrey C. Ollie <jeff@ocjtech.us> wrote:
On Thu, Sep 16, 2010 at 4:59 PM, Scott Crosby <scrosby@cs.rice.edu> wrote:
Well, technically two passes; the first pass is needed to figure out where to split.
I was excited to see this, however I'm having some difficulty getting your modified splitter code to compile. It looks like something is requiring a Sun-only API:
That import is totally unused. Truly bizarre. Just delete the line. But I think I know where it came from: When you use a class thats not imported, eclipse makes suggestions. The wrong click can leave behind the import of a random class.
Ah, that got me compiling. I'll give it a try once osmosis is done extracting the area I need from the planet. -- Jeff Ollie
Intellij IDEA lets you exclude specific packages and classes from auto imports, I assume Eclipse must have a similar feature. Probably worth enabling/configuring if you don't have it set up already. Here's a few of the most relevant exclusions I use: com.sun sun org.w3c java.sql.Date java.beans.Statement Chris
That import is totally unused. Truly bizarre. Just delete the line.
But I think I know where it came from: When you use a class thats not imported, eclipse makes suggestions. The wrong click can leave behind the import of a random class.
participants (3)
-
Chris Miller -
Jeffrey C. Ollie -
Scott Crosby