[mkgmap-dev] [PATCH v1] LocationHook speedup

Sat Dec 31 11:11:17 GMT 2011

Am 31.12.2011 09:06, schrieb GerdP:
> Hello WanMil,
>
> thanks for the details regarding the algorithmn.
>
>
> WanMil wrote
>>
>>> Two ideas:
>>> 1) Optimization:
>>> It might save time if we could pass a function pointer to the quadtree.
>>> The
>>> function does the tagging for one element, and we don't have to manage
>>> resultlists. I implemented that, but the program was slower. I assume
>>> that
>>> was caused by the fact that I did not implement the part that removes
>>> elements from the quadtree when they were "fully worked out".
>>
>> I am not sure if managing the resultlists is slow. In the end it
>> consists of adding elements to a HashSet (which I think should be quite
>> fast?!)
>>
> Well, sometimes the resultlist is quite big, e.g. 50% of all nodes in the
> quadtree. This involves some rehashing etc. These actions appear first in my
> java.hprof.
> Anyway, it will not give a performance boost to change that, only a few
> percent.
>
>
>
>>> 2) An completely different approach:
>>> I did not yet fully understand the algorithmn in LocationHook, but I got
>>> the
>>> impression that it might be possible to create a dictionary with
>>> combinations of admin-level tags, and save a reference to that dictionary
>>> instead of adding similar tags to each element. This could save space and
>>> time, but would require additional logic in class Element. Do you think
>>> this
>>> is worth trying?
>>
>> Of course you can try although I don't expect that it will improve much.
>>
> I have to collect some numbers first to be sure about it.
> The dictionary that I have in mind is more or less what is kept in
> List<Boundary>  boundaries
>
> What I don't understand yet regarding LocationHook is that most elements are
> NOT fully worked out after they appeared 1st in a result list. I'll
> investigate that today. If any element was worked out after the first time,
> we simply could save a reference to the entry in the boundary list instead
> of creating result lists and adding similar tags to many elements.

The reason is that the boundaries are not complete. Complete in two 
meanings:
1. Some boundaries are missing due to incomplete OSM data
2. In some areas there might be a boundary with admin_level=7, other 
areas do not have that admin_level. The LocationHook cannot know about 
that and therefore it can remove elements only if they contain all 
remaining tags.

WanMil

>
> Gerd
>