Possible optimization of StyledConverter
Steve, WanMil, the discussion about a prepro for styles inspired me to think about a compiler/optimizer for style rules. 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 see two possible optimizations here: 1) Combine rules that start with the same expression, e.g. highway=*, so that we don't evaluate tags again and again. In the past I used parser generator tools like lexx+yacc. I have the feeling that the rule interpretation is also something that could be done by a table driven parser. 2) A bit off-topic: Use a short instead of a String for the keys of Tags. I think even complex styles will not use more than a few hundred different tag keys. If all used tag keys are stored in an array, we can refer to the position in that array. Some weeks ago I coded that and it turned out to save some CPU cycles because Tags.keyPos() is simpler, but it also required changes in many sources and I found other patches providing more improvement with smaller changes. What do you think about this? Gerd P.S. A storm kept me awake all night long, so maybe I am writing nonsense :-O -- View this message in context: http://gis.638310.n2.nabble.com/Possible-optimization-of-StyledConverter-tp7... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi
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. ..Steve
Hi Steve, thanks for the explanation, I'll verify my assumptions. Regarding your patch: I see a change in the number of evaluated rules, but it is is slightly higher with the patch. I think this proves that my understanding is wrong, but the patch is probably too special, means, it has to be modified for each set of styles. Gerd Steve Ratcliffe wrote
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.
-- View this message in context: http://gis.638310.n2.nabble.com/Possible-optimization-of-StyledConverter-tp7... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi
thanks for the explanation, I'll verify my assumptions. Regarding your patch: I see a change in the number of evaluated rules, but it is is slightly higher with the patch. I think this proves that my understanding is wrong, but the patch is probably too special, means, it has to be modified for each set of styles.
I'd expect it to vary based on the actual input data, the tag/values with the lowest probability of being matched should be moved towards the beginning so that as few rules as possible are selected to begin with. My example of amenity was probably a bad one to include, since I was only looking at amenity=restaurant, and it may not be benificial with other values. I'm would be suprised that the highway one did not make an improvement. But in any case, I didn't see a difference in performance and I suspect that there are better places to look. For example there are 56 hardwired calls to getTag() in StyledConverter. ..Steve
Hello Steve,
My example of amenity was probably a bad one to include, since I was only looking at amenity=restaurant, and it may not be benificial with other values. I'm would be suprised that the highway one did not make an improvement. But in any case, I didn't see a difference in performance and I suspect that there are better places to look.
For example there are 56 hardwired calls to getTag() in StyledConverter.
hmm, do you think about storing the information in e.g. a bitmask rather than in tags? Gerd
Steve, I don't see how this would improve performance. Maybe I am using the wrong parms and don't hit the code, but in my profiling data I only see the IdentityHashMap in addRoadWithoutLoops() and the rules.resolveType(..) calls. Do you have a case where this addtag/gettag technique might slow down the program? Gerd
Date: Sun, 8 Jan 2012 21:49:14 +0000 From: steve@parabola.me.uk To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Possible optimization of StyledConverter
Hi
hmm, do you think about storing the information in e.g. a bitmask rather than in tags?
Yes, if I had done that part, I would have tried to go directly from osm tags to properties on the Element, rather than the two stage process of osm tag to mkgmap:* tag.
..Steve _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
participants (3)
-
Gerd Petermann -
GerdP
-
Steve Ratcliffe