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

Tue May 19 21:42:18 BST 2009

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