logo separator

[mkgmap-dev] Possible optimization of StyledConverter

From Steve Ratcliffe steve at parabola.me.uk on Thu Jan 5 16:08:08 GMT 2012


> The point that I have in mind is this: Style files typically have many
> different rules starting with e.g.
> highway=*&  ...
> The current iplementation in RuleSet.java and RuleIndex.java will first
> create a set of all rules that might match for the existing tags of a given
> element. Next, it processes each rule until the element is done.
> Let's assume an element that has tag "highway" and maybe 4 other tags
> If we have twenty rules with highway=* and none of them matches, we'll call
> getTag("highway") twenty times, always with the same result. Although
> getTag() is not very complex, it still means a lookup in a hash table.

I don't think that this happens in practice. All rules are rearranged
to have the most selective term first, so unless you have many rules
with highway=* by itself it is one
of the other terms in the expression that is used to select the rule.

So if you had 20 rules of the form:

highway=* & colour=red [0x7 ...]
highway=* & colour=green [0x7 ...]
highway=* & colour=blue [0x7 ...]

And you have an element with highway=primary,colour=blue then
the final rule is the only one that will checked, so you only call
getTag("highway") once.

There is a slight optimisation that could be done by moving common
tags back based on the tag name. See attached patch. This reduces the 
number of rules checked in two common cases in the test I ran.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: demote_terms.patch
Type: text/x-patch
Size: 774 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120105/77f26baf/attachment.bin 

More information about the mkgmap-dev mailing list