[mkgmap-dev] [PATCH v2] LocationHook speedup

Sat Dec 31 13:04:52 GMT 2011

Hi Gerd,

now we have the problem of how to measure the runtime performance.

I have compared unpatched and patched mkgmap. Both versions contain the 
time output of the patched version. I have used one thread only with 15 
european tiles (widely spread over europe) and compare the summarized 
runtime of the LocationHook only because that's what should be improved 
by the patch.

I have done 4 runs of each version. The mean values are:

r2154: 65280 ms for LocationHook, 335325 ms overall runtime
patch: 55173 ms for LocationHook, 313082 ms overall runtime

diff:  10107 ms improvement Hook, 22243 ms improvement overall

The overall improvement is a bit problematic because I would expect that 
it is close to the LocationHook improvement but its twice. The patch 
uses less memory and therefore the GC (which probably runs outside the 
Hook) must do less work. But I am unsure if that's the reason for the 
good overall improvement.

WanMil

> Hello WanMil,
>
> I tried it. With small input files I see no change.
> With larger tiles, it seems to be a bit faster, e.g. runtime decreased
> 270 to 265 secs.
>
>
> Gerd
>
> Date: Sat, 31 Dec 2011 01:18:18 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: [mkgmap-dev] [PATCH v2] LocationHook speedup
>
> I tried to improve the first patch by removing anything not required in
> the Quadtree and by using a different internal data structure.
>
> I've seen performance improvements but please try and test yourself :-)
>
> The most time is now spend in the creation of the Quadtree. So if you
> want to search for more performance just start there.
>
> WanMil
>
>
>>  Gerds patches inspired me to look for more things that could be improved.
>>
>>  I found that the Quadtree used in the LocationHook is not very optimal.
>>  The patch is a first try to increase the performance. The time required
>>  for the LocationHook is reduced by 10-50% which is great.
>>
>>  Warning: I haven't checked so far if the results are equal. So maybe
>>  there are big bugs in the patch... (and the speedup comes from the poor
>>  implementation)
>>
>>  I will do some more tests and optimizations but maybe some of you can
>>  have a look on it, test it and comment it.
>>
>>  Have fun!
>>  WanMil
>>
>>
>>  _______________________________________________
>>  mkgmap-dev mailing list
>>  mkgmap-dev at lists.mkgmap.org.uk
>>  http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
>
> _______________________________________________ mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev