Hello list, I got no feedback regarding my last performance patch for mkgmap, so I don't know if nobody tested it. Anyway, here are a few more small suggestions for changes (can be applied http://gis.638310.n2.nabble.com/file/n7123938/mkgmap_performance_2.patch mkgmap_performance_2.patch on r2145 and gmap-mdr branch 2144 as well) : On my dual-core machine, creating a gmapsupp.img of ~ 91MB (Niedersachsen) with max-jobs=2 required ~ 352 secs with r2145, and 268 secs (~ 25% less) with my previous patch + this one, so I think it is worth trying. For removeShortArcsByMergingNodes: - The IdentityHashMap arcCounts counts arcs, but the only result that is used is wether or not an arc was found. My patch replaces this frequently used map and uses a bit in Coord instead. - the current algorithmn tries to find replacements for each point, this is quite costly. One more bit in Coord reduces the number of loops from > 1.000.000 to ~1000. For LocationHook: I've replaced the getUsedLocationTags() by testHasAllTags(). This just returns true if all tags in List remainingLevels are existing, instead of merging HashSets to get the same result. For RuleSet / RuleIndex: I've replaced the HashSet<Integer> by BitSet. This is faster because we don't have to use Collections.sort(candidates); to handle duplicate rules. Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hello Gerd, you do a lot of thinks, especially improving the performance of splitter and mkgmap. That's great, thank you. Can you please upload your patched jar-file? For me and some other people in the list patching is pretty tricky... ;) Cheers, Martin Am 24.12.2011 um 15:13 schrieb GerdP:
Hello list,
I got no feedback regarding my last performance patch for mkgmap, so I don't know if nobody tested it. Anyway, here are a few more small suggestions for changes (can be applied http://gis.638310.n2.nabble.com/file/n7123938/mkgmap_performance_2.patch mkgmap_performance_2.patch on r2145 and gmap-mdr branch 2144 as well) : On my dual-core machine, creating a gmapsupp.img of ~ 91MB (Niedersachsen) with max-jobs=2 required ~ 352 secs with r2145, and 268 secs (~ 25% less) with my previous patch + this one, so I think it is worth trying.
For removeShortArcsByMergingNodes: - The IdentityHashMap arcCounts counts arcs, but the only result that is used is wether or not an arc was found. My patch replaces this frequently used map and uses a bit in Coord instead.
- the current algorithmn tries to find replacements for each point, this is quite costly. One more bit in Coord reduces the number of loops from > 1.000.000 to ~1000.
For LocationHook: I've replaced the getUsedLocationTags() by testHasAllTags(). This just returns true if all tags in List remainingLevels are existing, instead of merging HashSets to get the same result.
For RuleSet / RuleIndex: I've replaced the HashSet<Integer> by BitSet. This is faster because we don't have to use Collections.sort(candidates); to handle duplicate rules.
Gerd
-- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hello Martin, Good to hear that you want to test it. I am not sure if uploading jar files is ok for the rest? (I don't have my own server for this). ciao, Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com.
GerdP <gpetermann_muenchen@hotmail.com> wrote:
Hello Martin,
Good to hear that you want to test it. I am not sure if uploading jar files is ok for the rest? (I don't have my own server for this).
ciao, Gerd
-- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
You can upload files to files.mkgmap.org.uk ..Steve
Hello Steve, thanks, here we go: r2145 patched with addtag_intern.patch and c:\TEMP\mkgmap_performance_2.patch: http://files.mkgmap.org.uk/download/44/mkgmap.jar r2144 patched with addtag_intern.patch and c:\TEMP\mkgmap_performance_2.patch: http://files.mkgmap.org.uk/download/45/mkgmap.jar If you think the patches do not produce correct results, try to describe the error. If the program doesn't execute faster, please send me some info: I use these parms to measure performance on windows: java -XX:+PrintGCTimeStamps -XX:+PrintGCDetails -agentlib:hprof=cpu=samples,depth=20 -Xmx1600m -jar mkgmap.jar ... your normal mkgmap parms > mkgmap.out This produces a file mgkmap.out with some infos about GC and a java.hprof.txt with performance values. Ciao, Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Gerd, the patches looks good to me. Thanks for your work! I have commited the part for the LocationHook. For the other things I have some questions: * Can you please add some javadoc to the new methods? I know the old methods often do not have javadocs but that shouldn't be continued... * RuleIndex.getRulesForTag returns a BitSet that can be modified externally. This is no good style. I know that the BitSet is not modified externally so it's not a bug. But at least is should be documented in the javadoc that the returned BitSet *must not* be modified. * I propose to use an ArrayList instead of HashSet in line 157 of RuleIndex * RuleIndex line 175: The set.clear(i) method changes the BitSet in tagVals/tagnames directly. The unpatched mkgmap is working on a copy. Can you please check carefully if your version is correct? WanMil
Hello list,
I got no feedback regarding my last performance patch for mkgmap, so I don't know if nobody tested it. Anyway, here are a few more small suggestions for changes (can be applied http://gis.638310.n2.nabble.com/file/n7123938/mkgmap_performance_2.patch mkgmap_performance_2.patch on r2145 and gmap-mdr branch 2144 as well) : On my dual-core machine, creating a gmapsupp.img of ~ 91MB (Niedersachsen) with max-jobs=2 required ~ 352 secs with r2145, and 268 secs (~ 25% less) with my previous patch + this one, so I think it is worth trying.
For removeShortArcsByMergingNodes: - The IdentityHashMap arcCounts counts arcs, but the only result that is used is wether or not an arc was found. My patch replaces this frequently used map and uses a bit in Coord instead.
- the current algorithmn tries to find replacements for each point, this is quite costly. One more bit in Coord reduces the number of loops from> 1.000.000 to ~1000.
For LocationHook: I've replaced the getUsedLocationTags() by testHasAllTags(). This just returns true if all tags in List remainingLevels are existing, instead of merging HashSets to get the same result.
For RuleSet / RuleIndex: I've replaced the HashSet<Integer> by BitSet. This is faster because we don't have to use Collections.sort(candidates); to handle duplicate rules.
Gerd
-- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
WanMil wrote
* Can you please add some javadoc to the new methods? I know the old methods often do not have javadocs but that shouldn't be continued...
I totally agree. The attached correction contains comments. I am a little bit in trouble with this because the new methods and the corresponding flags in Coord are only meaningfull inside the existing removeShortArcsByMergingNodes() method of ElementSaver, but I think the performance improvement is worth enough to allow this rather bad coding style.
* RuleIndex.getRulesForTag returns a BitSet that can be modified externally. This is no good style. I know that the BitSet is not modified externally so it's not a bug. But at least is should be documented in the javadoc that the returned BitSet *must not* be modified.
In fact, the method was wrong because it evtl. modified by mistake the BitSet in tagVals. This is corrected with the new patch which returns a newly created BitSet.
* I propose to use an ArrayList instead of HashSet in line 157 of RuleIndex
OK, changed. This part of the code is not performance critical, so I wanted to keep the changes small.
* RuleIndex line 175: The set.clear(i) method changes the BitSet in tagVals/tagnames directly. The unpatched mkgmap is working on a copy. Can you please check carefully if your version is correct?
Good catch, my version was definetly wrong. This is also corrected with the new patch. The new patch adds one more small change: In removeShortArcsByMergingNodes() Coord.distance() is only called if we really have to calculate the length of the arc. If parameter remove-short-arcs is used without a value (or with remove-short-arcs=0), there is no need to calculate the distance, we just need to know if the two points are equal. I also have one question: What is causing mkgmap to produce different results each time when it executes? This makes optimization very difficult because one cannot simply compare old and new result. http://gis.638310.n2.nabble.com/file/n7129718/mkgmap_performance_3.patch mkgmap_performance_3.patch Ciao, Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Gerd On 12/27/2011 09:35 AM, GerdP wrote:
I also have one question: What is causing mkgmap to produce different results each time when it executes? This makes optimization very difficult because one cannot simply compare old and new result.
I don't know why this happens now, and it really shouldn't (apart from the timestamps which are easy to ignore), I will try to find out why. I tried your patches on my laptop but haven't seen such a big difference, perhaps 5% at most, and very little difference on some individual tiles. ..Steve
Hello Steve, Steve Ratcliffe wrote
What is causing mkgmap to produce different results each time when it executes? This makes optimization very difficult because one cannot simply compare old and new result.
I don't know why this happens now, and it really shouldn't (apart from the timestamps which are easy to ignore), I will try to find out why.
thanks, tt would be great if this could be changed.
I tried your patches on my laptop but haven't seen such a big difference, perhaps 5% at most, and very little difference on some individual tiles.
I assume the performance improvements depend heavily on the hardware, the OS and the JVM that is used. I have a dual boot system with WinXP+sun jdk and a 64bit Ubuntu with openJDK . I see very different results. Esp. interesting is that splitter is much faster on linux, while mkgmap is much slower, even with small input files were heap size doesn't matter. Also, it seems to be important to find a proper tile size in splitter. If I use large tiles (high max-nodes value), mkgmap might not have enough memory for max-jobs threads. Since each threads has a zick-zack type curve in heap uage, it is likely to reach the availabe heap maximum when setting max-jobs to a high value. In my test environment, the CPU still is the bottleneck. Ciao, Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com.
On 12/27/2011 01:49 PM, GerdP wrote:
I don't know why this happens now, and it really shouldn't (apart from
the timestamps which are easy to ignore), I will try to find out why.
thanks, tt would be great if this could be changed.
I discovered that it is only boundary lines that are affected. I didn't quite track down the exact cause, but I guess that the relation members are held in a hash map somewhere and are read out in an indeterminate order. Whatever the exact reason, adding a hashCode() method to the Way class prevents the random ordering, so I shall commit that change. ..Steve
Hello Steve, Steve Ratcliffe wrote
On 12/27/2011 01:49 PM, GerdP wrote:
I don't know why this happens now, and it really shouldn't (apart from
the timestamps which are easy to ignore), I will try to find out why.
thanks, tt would be great if this could be changed.
I discovered that it is only boundary lines that are affected.
I didn't quite track down the exact cause, but I guess that the relation members are held in a hash map somewhere and are read out in an indeterminate order.
Whatever the exact reason, adding a hashCode() method to the Way class prevents the random ordering, so I shall commit that change.
your fix helps when I use max-jobs=1, only a few bytes are different then, but I still get random output with max-jobs > 1. Is this expected? Regarding those different bytes for max-jobs=1: You said they are time-stamps. Would it be possible to write a constant value (from a parameter) to these bytes for debugging purposes? Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Gerd
your fix helps when I use max-jobs=1, only a few bytes are different then, but I still get random output with max-jobs> 1. Is this expected?
No its not expected. In fact it appears to happen even for max-jobs=1 when you compile the same file twice on the same run. I will try to track that down too.
Regarding those different bytes for max-jobs=1: You said they are time-stamps. Would it be possible to write a constant value (from a parameter) to these bytes for debugging purposes?
If you look in ImgHeader.createHeader() and CommonHeader.writeHeader() there are calls to write the timestamp, you can replace the date with a constant eg new Date(1325107646). ..Steve
Hello Steve,
your fix helps when I use max-jobs=1, only a few bytes are different then, but I still get random output with max-jobs> 1. Is this expected?
No its not expected. In fact it appears to happen even for max-jobs=1 when you compile the same file twice on the same run. I will try to track that down too.
okay, thanks. Is this related to IdentityHashMaps ?
If you look in ImgHeader.createHeader() and CommonHeader.writeHeader() there are calls to write the timestamp, you can replace the date with a constant eg new Date(1325107646).
Ok, thanks again. I already found one of them yesterday, but missed the other one. Ciao, Gerd
Hi
No its not expected. In fact it appears to happen even for max-jobs=1 when you compile the same file twice on the same run. I will try to track that down too.
okay, thanks. Is this related to IdentityHashMaps ?
Well I've found it. Don't know why it took so long as it was exactly what I thought it might be in the first place! It is FakeIdGenerator - there is only one that is shared across all maps, rather than a separate one being used for each map. Because of the way that it is used, this is difficult to fix. If you modify it to always return the same id then the differences go away on my test map. However the map is smaller than the one made without the mod, so it looks like it is absolutely essential that the ids are different and this is no solution, maybe not even for testing of performance changes. ..Steve
Hi
No its not expected. In fact it appears to happen even for max-jobs=1 when you compile the same file twice on the same run. I will try to track that down too.
okay, thanks. Is this related to IdentityHashMaps ?
Well I've found it. Don't know why it took so long as it was exactly what I thought it might be in the first place!
It is FakeIdGenerator - there is only one that is shared across all maps, rather than a separate one being used for each map.
Because of the way that it is used, this is difficult to fix.
If you modify it to always return the same id then the differences go away on my test map. However the map is smaller than the one made without the mod, so it looks like it is absolutely essential that the ids are different and this is no solution, maybe not even for testing of performance changes.
..Steve
Maybe it's possible to seperate the id ranges of the FakeIdGenerator? Example: startId = 1L << 62 + (tile no - starting with 0) * (1L << 62 / noOfTiles) But that would require that all calls to the FakeIdGenerator are no longer static (or they must use the ThreadLocal object?). WanMil
Hi
Maybe it's possible to seperate the id ranges of the FakeIdGenerator? Example: startId = 1L<< 62 + (tile no - starting with 0) * (1L<< 62 / noOfTiles)
But that would require that all calls to the FakeIdGenerator are no longer static (or they must use the ThreadLocal object?).
That might work, but it's tricky to get the map no to everywhere the fake ids are generated. I have just tested a solution that is probably sufficient for testing performance fixes. There is an option --preserve-element-order which makes the maps used to save the ways into LinkedHashMaps which should mean that the iteration order is defined by the order they are added to the map and not by the hashCode(). I was wondering why this option didn't work to make the maps identical. I found the reason: this simple patch in MultiPolygonRelation: private final Map<Long, Way> tileWayMap; private final Map<Long, String> roleMap = new HashMap<Long, String>(); - private Map<Long, Way> mpPolygons = new HashMap<Long, Way>(); + private Map<Long, Way> mpPolygons = new LinkedHashMap<Long, Way>(); is all that is needed to make the --preserve-element-order option work, at least for my test file. ..Steve
Hello Steve, yes, that works fine, thanks a lot! Together with the proposed changes regarding the "new Date()" parts mkgmap now creates identical output for identical input, which helps a lot when trying performance patches. Attached is the patch that I use for this. http://gis.638310.n2.nabble.com/file/n7139860/identical_output.patch identical_output.patch ciao, Gerd Steve Ratcliffe wrote
There is an option --preserve-element-order which makes the maps used to save the ways into LinkedHashMaps which should mean that the iteration order is defined by the order they are added to the map and not by the hashCode(). I was wondering why this option didn't work to make the maps identical.
I found the reason: this simple patch in MultiPolygonRelation:
private final Map<Long, Way> tileWayMap; private final Map<Long, String> roleMap = new HashMap<Long, String>(); - private Map<Long, Way> mpPolygons = new HashMap<Long, Way>(); + private Map<Long, Way> mpPolygons = new LinkedHashMap<Long, Way>();
is all that is needed to make the --preserve-element-order option work, at least for my test file.
-- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Gerd,
WanMil wrote
* Can you please add some javadoc to the new methods? I know the old methods often do not have javadocs but that shouldn't be continued...
I totally agree. The attached correction contains comments. I am a little bit in trouble with this because the new methods and the corresponding flags in Coord are only meaningfull inside the existing removeShortArcsByMergingNodes() method of ElementSaver, but I think the performance improvement is worth enough to allow this rather bad coding style.
Did you try to use another storage mechanism within the removeShortArcs... method? I don't like storing the infos of the short arcs in *all* coords. Your patch reduces the memory footprint of the Coord object (great!). But I think information should be as local as possible.
* RuleIndex.getRulesForTag returns a BitSet that can be modified externally. This is no good style. I know that the BitSet is not modified externally so it's not a bug. But at least is should be documented in the javadoc that the returned BitSet *must not* be modified.
In fact, the method was wrong because it evtl. modified by mistake the BitSet in tagVals. This is corrected with the new patch which returns a newly created BitSet.
Great!
* I propose to use an ArrayList instead of HashSet in line 157 of RuleIndex
OK, changed. This part of the code is not performance critical, so I wanted to keep the changes small.
* RuleIndex line 175: The set.clear(i) method changes the BitSet in tagVals/tagnames directly. The unpatched mkgmap is working on a copy. Can you please check carefully if your version is correct?
Good catch, my version was definetly wrong. This is also corrected with the new patch.
The new patch adds one more small change: In removeShortArcsByMergingNodes() Coord.distance() is only called if we really have to calculate the length of the arc. If parameter remove-short-arcs is used without a value (or with remove-short-arcs=0), there is no need to calculate the distance, we just need to know if the two points are equal.
I also have one question: What is causing mkgmap to produce different results each time when it executes? This makes optimization very difficult because one cannot simply compare old and new result.
http://gis.638310.n2.nabble.com/file/n7129718/mkgmap_performance_3.patch mkgmap_performance_3.patch
Ciao, Gerd
All in all I see speed improvements using the patch. So after the Coord question is cleared I would like to commit that if nobody vetoes and you agree. Thanks! WanMil
Hi WanMil,
WanMil wrote
* Can you please add some javadoc to the new methods? I know the old methods often do not have javadocs but that shouldn't be continued...
I totally agree. The attached correction contains comments. I am a little bit in trouble with this because the new methods and the corresponding flags in Coord are only meaningfull inside the existing removeShortArcsByMergingNodes() method of ElementSaver, but I think the performance improvement is worth enough to allow this rather bad coding style.
Did you try to use another storage mechanism within the removeShortArcs... method? I don't like storing the infos of the short arcs in *all* coords. Your patch reduces the memory footprint of the Coord object (great!). But I think information should be as local as possible. reg. memory footprint: I fear Coord instances will still require 16 bytes because of the padding that happens. I tried another trick which required an additional integer field in Coord, so I compressed the boolean fields. Later I removed the integer field but kept the rest. We can change that to boolean without problems.
reg. "local information": I totally agree, but I found no better way, and it saved a lot of time on my system. The performance improvement comes from the fact that we can very quickly extract a boolean value from a known object. It will take more time to find something in a different structure. If you have an idea, let me know and I'll try, else we can simply drop that part of the patch and keep Coord.java and ElementSaver.java unchanged. Ciao, Gerd
Hi
reg. "local information": I totally agree, but I found no better way, and it saved a lot of time on my system.
Personally I think that the way you have done it in the patch is much more natural than the existing way! It is also possible to make the Coord structure smaller, since only 24 bits of the latitude and longitude fields are used, so both of the byte values could be located in the un-used 16 bits. Also there are only three values of highwayCount that matter: 0, 1, and more-than-one, so only two bits are required for that. I originally did it that way, but because of a mistake I gave up and went back to a separate field. This would save a bit of memory, but it is only worth doing if it results in a significant improvement in performance. ..Steve
Hello Steve, Steve Ratcliffe wrote
reg. "local information": I totally agree, but I found no better way, and it saved a lot of time on my system.
Personally I think that the way you have done it in the patch is much more natural than the existing way!
Ok, so than the patch is fine for me as well.
It is also possible to make the Coord structure smaller, since only 24 bits of the latitude and longitude fields are used, so both of the byte values could be located in the un-used 16 bits. Also there are only three values of highwayCount that matter: 0, 1, and more-than-one, so only two bits are required for that. I originally did it that way, but because of a mistake I gave up and went back to a separate field. This would save a bit of memory, but it is only worth doing if it results in a significant improvement in performance.
I also thought about this, but I wasn't sure how many bits are really used, and I got the feeling that such bitmask tricks are somehow outaged. I think I'll give it a try. I see two ways: 1) Keep the Coord class, but place these bits somewhere in the two interger fields 2) Use a long and map all fields in some mapping routines. This will be more complex, but could allow to use arrays (long[]) to store coords, and I guess this would mean > 50% memory saving for Coords. Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Am 02.01.2012 13:16, schrieb GerdP:
Hello Steve,
Steve Ratcliffe wrote
reg. "local information": I totally agree, but I found no better way, and it saved a lot of time on my system.
Personally I think that the way you have done it in the patch is much more natural than the existing way!
Ok, so than the patch is fine for me as well.
It is also possible to make the Coord structure smaller, since only 24 bits of the latitude and longitude fields are used, so both of the byte values could be located in the un-used 16 bits. Also there are only three values of highwayCount that matter: 0, 1, and more-than-one, so only two bits are required for that. I originally did it that way, but because of a mistake I gave up and went back to a separate field. This would save a bit of memory, but it is only worth doing if it results in a significant improvement in performance.
I also thought about this, but I wasn't sure how many bits are really used, and I got the feeling that such bitmask tricks are somehow outaged. I think I'll give it a try. I see two ways: 1) Keep the Coord class, but place these bits somewhere in the two interger fields 2) Use a long and map all fields in some mapping routines. This will be more complex, but could allow to use arrays (long[]) to store coords, and I guess this would mean> 50% memory saving for Coords.
Gerd
Thanks for trying the modification. The reason why I insisted a bit on how the reduce the memory footprint is the coastlinefile option. Using this option often requires a lot of memory because the complete coastlines of a big area must be loaded into mkgmap at once. Reducing the memory footprint of the Coord objects should reduce the required memory a lot in this case. But I don't think that the somehow cryptic changes are worthy. So I am fine with your original patch. WanMil
Hello Steve, I tried the "compressed" Coord class. As expected, it requires only 16 Bytes for each instance of Coord instead of 24 bytes, but the performance improvement is small, because the frequently called method getLongitude() is now more complex, so we save a few cycles in GC and add some in at other places. If you want to try, here is the patch: http://gis.638310.n2.nabble.com/file/n7143952/Coord.patch Coord.patch Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-mkgmap-performance-part-2-tp7123938p71... Sent from the Mkgmap Development mailing list archive at Nabble.com.
participants (5)
-
Gerd Petermann -
GerdP
-
Martin -
Steve Ratcliffe -
WanMil