Re: [mkgmap-dev] [PATCH v1] quick distance calculation

[Clinton Gladstone]

On Tue, May 19, 2009 at 12:57 AM, Mark Burton ma...@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.
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Re: [mkgmap-dev] [PATCH v1] quick distance calculation

[Mark Burton]

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
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Re: [mkgmap-dev] [PATCH v1] quick distance calculation

[Wolfgang v. Hansen]

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
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev