[josm-dev] QuadBucket iteration speed (faster than josm-ng Storage)

Dave Hansen dave at sr71.net
Sun Nov 1 22:35:23 GMT 2009


There have been some concerns that using QuadBuckets makes data set
iterations too slow.  First of all, I hope that QuadBuckets will vastly
reduce the number of full iterations over the data set that are
*required* and replace them with coordinate-based searches.  But, the
concern is valid.

I've done some performance analysis of QuadBuckets outside of JOSM in a
little microbenchmark I just wrote.  I've varied the bucket size, and
run some searches.  Here are the results:

http://daveh.dev.openstreetmap.org/josm/quadbuckets-perf.png 

You can see that the search times have a nice stable optimal area when
the buckets are between about 40 and 400 objects in size.  The iteration
times behave as expected and improve pretty linearly as bucket sizes
increase.

With a 256-member bucket, QuadBuckets are about 2.5x as slow as an
ArrayList or LinkedList, but still retain virtually all of the search
speed: 

        QuadBuckets<Node> iteration: 970 runs in 2001 ms, avg time: 2.0628867 ms
        ArrayList<Node> iteration: 2803 runs in 2001 ms, avg time: 0.713878 ms
        LinkedList<Node> iteration: 2370 runs in 2001 ms, avg time: 0.8443038 ms
        Storage<Node> iteration: 954 runs in 2001 ms, avg time: 2.0974844 ms

Note that this is a little microbenchmark, so the real JOSM results are
likely to be even less noticeable.  So, I'd like to change the default
bucket size to 128 or 256.

I also tried implementing a new QuadBucket iterator.  This one keeps a
linked-list of all of the QuadBucket nodes so that each jump to a new
tree node is always just a single pointer dereference.  That appears as
"qb-new-iterate" in the graph.  It's never much better than the existing
iterator.  

I got the josm-ng Storage code from here:

http://svn.openstreetmap.org/applications/editors/josm-ng/src/org/openstreetmap/josmng/utils/

-- Dave





More information about the josm-dev mailing list