[PATCH v1] quick distance calculation
Folks, OK, so the parallelisation code has not been very successful so far but we can still speed up mkgmap. You have probably noticed that it spends a huge proportion of its time in Math.acos() which is being called from Coord.distance(). The attached patch renames distance() to slowDistance() and introduces a new quickDistance() function that is based on the code that was in the MultipolygonRelation class. I have tested quickDistance() against slowDistance() and for maps in the UK and Germany it produces distances that are very similar (within 0.5% or better). It is substantially faster and so I believe we should change to using it as long as it doesn't introduce any issues. So please try out this patch and report: a - if any breakage is observed b - performance increase/decrease Cheers, Mark
With all the postings to the list in the last 24H or so, it's easy to miss stuff - so just in case you missed this patch, please give it a go as I believe it provides a useful performance boost. Thanks, Mark
On Tue, May 19, 2009 at 12:57 AM, Mark Burton <markb@ordern.com> wrote:
With all the postings to the list in the last 24H or so, it's easy to miss stuff - so just in case you missed this patch, please give it a go as I believe it provides a useful performance boost.
I've applied and tested this patch: at first glance, it seems OK. I didn't notice breakage or similar problems. I also did not do any performance tests, so I cannot say if the compilation time has improved significantly. I'll do more extensive tests later. Cheers.
Clinton,
I've applied and tested this patch: at first glance, it seems OK. I didn't notice breakage or similar problems. I also did not do any performance tests, so I cannot say if the compilation time has improved significantly. I'll do more extensive tests later.
Please do, I think you will be pleasantly surprised by the speed gain. Cheers, Mark
On 09-05-16 19:54:31 CEST, Mark Burton wrote:
It is substantially faster and so I believe we should change to using it as long as it doesn't introduce any issues.
So please try out this patch and report:
a - if any breakage is observed
how much difference is tolerable...? enabling your diagnostic code, i've observed differences typically in the range of .25% to .4%, with some exceptions like... quickDistance() = 1.4536911305450404 slowDistance() = 1.446011378093334 (0.5310990333860841% difference) quickDistance() = 1.4535945914221295 slowDistance() = 1.446011378093334 (0.5244227980276771% difference) ... and a number of lines where the relative difference doesn't really compute: quickDistance() = 0.0 slowDistance() = 0.09493529796600342 (100.0% difference)
b - performance increase/decrease
i compiled my village four times with and without the patch: with: make basemap1 56.00s user 0.99s system 143% cpu 39.621 total without: make basemap1 65.33s user 1.02s system 132% cpu 49.988 total without: make basemap1 70.27s user 1.19s system 137% cpu 52.111 total with: make basemap1 58.36s user 1.07s system 144% cpu 41.124 total with: make basemap1 55.84s user 1.20s system 134% cpu 42.394 total without: make basemap1 66.21s user 0.90s system 131% cpu 51.153 total with: make basemap1 51.98s user 1.14s system 142% cpu 37.339 total without: make basemap1 69.27s user 1.03s system 137% cpu 51.306 total -> with avg: 55.54s user -> without avg: 67.77s user -> the compile with the patch takes only some 81% of the time. (in case the type of CPU matters, /proc/cpuinfo on this laptop says "AMD Turion(tm) 64 X2 Mobile Technology TL-52".) rj
Hi Robert, Many thanks for the feedback.
how much difference is tolerable...?
enabling your diagnostic code, i've observed differences typically in the range of .25% to .4%, with some exceptions like...
quickDistance() = 1.4536911305450404 slowDistance() = 1.446011378093334 (0.5310990333860841% difference) quickDistance() = 1.4535945914221295 slowDistance() = 1.446011378093334 (0.5244227980276771% difference)
... and a number of lines where the relative difference doesn't really compute:
quickDistance() = 0.0 slowDistance() = 0.09493529796600342 (100.0% difference)
Well, that's a good question. As distance() mostly gets called to determine which of a bunch of points is nearest, it probably doesn't matter at all that the result is slightly "wrong". I don't believe that the quality of the values returned by distance() will affect the accuracy of the map. Perhaps it will make some difference to the routing but, at this time, I am not convinced that distance() needs to be super^2 accurate. If anyone knows otherwise, please say.
b - performance increase/decrease
i compiled my village four times with and without the patch:
with: make basemap1 56.00s user 0.99s system 143% cpu 39.621 total without: make basemap1 65.33s user 1.02s system 132% cpu 49.988 total without: make basemap1 70.27s user 1.19s system 137% cpu 52.111 total with: make basemap1 58.36s user 1.07s system 144% cpu 41.124 total with: make basemap1 55.84s user 1.20s system 134% cpu 42.394 total without: make basemap1 66.21s user 0.90s system 131% cpu 51.153 total with: make basemap1 51.98s user 1.14s system 142% cpu 37.339 total without: make basemap1 69.27s user 1.03s system 137% cpu 51.306 total
-> with avg: 55.54s user -> without avg: 67.77s user
-> the compile with the patch takes only some 81% of the time.
(in case the type of CPU matters, /proc/cpuinfo on this laptop says "AMD Turion(tm) 64 X2 Mobile Technology TL-52".)
Well, that's not as good a speedup as I have been seeing. Without using the parallelism patch, i.e. just using 1 core, I get around x2 performance on a very quick machine when using the quick-distance patch. Anyway, thanks again for taking the time to give it a go. Cheers, Mark
On Tue, 19 May 2009, Mark Burton wrote:
Well, that's a good question. As distance() mostly gets called to determine which of a bunch of points is nearest, it probably doesn't matter at all that the result is slightly "wrong".
Really? In that case you could as well change the metric from Euclidean to something more simple like the Manhattan metric: dist = abs(lat2-lat1) + costab[lat1] * abs(lon2-lon1) where costab is a table lookup for cos(). This will still find a point that is close, but it is not guaranteed to be the same as with the Euclidean metric. Would that matter? -Wolfgang
Hi Wolfgang,
Well, that's a good question. As distance() mostly gets called to determine which of a bunch of points is nearest, it probably doesn't matter at all that the result is slightly "wrong".
Really? In that case you could as well change the metric from Euclidean to something more simple like the Manhattan metric:
dist = abs(lat2-lat1) + costab[lat1] * abs(lon2-lon1)
where costab is a table lookup for cos(). This will still find a point that is close, but it is not guaranteed to be the same as with the Euclidean metric. Would that matter?
Good question. Unfortunately, my maths is not so good so I can't answer it. Absolute distance measurement is still required in a couple of places so we don't want to give up too much accuracy for the sake of speed. In terms of performance, I think the new quickDistance() is not so bad now (at least when compared to the performance of slowDistance()) and if you look at the java jprof output it no longer dominates so the gain achieved by using a method such as suggested above may not be so great. Of course, we could use a slower, more accurate, function for those calculations that really would benefit from the increased accuracy and a "quick and dirty" function for everywhere else. Cheers, Mark
On Wed, 20 May 2009, Mark Burton wrote:
Really? In that case you could as well change the metric from Euclidean to something more simple like the Manhattan metric:
dist = abs(lat2-lat1) + costab[lat1] * abs(lon2-lon1)
where costab is a table lookup for cos(). This will still find a point that is close, but it is not guaranteed to be the same as with the Euclidean metric. Would that matter?
Good question. Unfortunately, my maths is not so good so I can't answer it.
This is not a question of maths but of the requirements of the algorithm: Do you need "a close" or "the closest" point?
Absolute distance measurement is still required in a couple of places so we don't want to give up too much accuracy for the sake of speed.
I would suggest to retain the original distance() for all places where the exact distance is needed and to define approximateDistance() for other cases -- either using your current implementation or something minimalistic like my proposal depending on the requirements. -Wolfgang PS: If it's just for finding nearest neighbours, you can improve the performance of your code by 1. Working in map units (no conversion) 2. Replacing the if-blocks by Math.abs() or the ternary "? :"-operator 3. Computing the cosine by table lookup 4. Removing sqrt to compute squared distances 5. Removing scale factors for the output
participants (4)
-
Clinton Gladstone -
Mark Burton -
Robert Joop -
Wolfgang v. Hansen