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 _______________________________________________ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/listinfo/josm-dev