logo separator

[mkgmap-dev] [PATCH v1] LocationHook speedup

From WanMil wmgcnfg at web.de on 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 
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.


> Gerd

More information about the mkgmap-dev mailing list