Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
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 ListBoundary 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. Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7139804.html 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
Re: [mkgmap-dev] [PATCH V3]mkgmap performance
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 Maplt;Long, Waygt; tileWayMap; private final Maplt;Long, Stringgt; roleMap = new HashMaplt;Long, Stringgt;(); - private Maplt;Long, Waygt; mpPolygons = new HashMaplt;Long, Waygt;(); + private Maplt;Long, Waygt; mpPolygons = new LinkedHashMaplt;Long, Waygt;(); 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-tp7123938p7139860.html 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
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
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 ListBoundary 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 ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Hello WanMil, WanMil wrote 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. ahh, incomplete data always makes things that much more complicated :-( I also just got to that admin_level=7. In Saarland, one of my test cases, I see Verbandsgemeinde Waldmohr http://www.openstreetmap.org/browse/relation/897709 which is the only boundary that has admin_level=7. The interesting thing is: the returned result-list for this boundary is always empty. So, maybe there is a cheaper way to detect this first or does it means that there is a bug in quadtree or the selection of the boundaries? Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7140096.html 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
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Hello WanMil, WanMil wrote 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. ahh, incomplete data always makes things that much more complicated :-( I also just got to that admin_level=7. In Saarland, one of my test cases, admin_level=7 just an example. admin_levels are used differently in countries and in regions etc. I see Verbandsgemeinde Waldmohr http://www.openstreetmap.org/browse/relation/897709 which is the only boundary that has admin_level=7. The interesting thing is: the returned result-list for this boundary is always empty. So, maybe there is a cheaper way to detect this first or does it means that there is a bug in quadtree or the selection of the boundaries? Sounds more like a bug! But it's also possible that the higher admin_levels (8,9,10,11) references all other admin_levels and therefore there all elements of Waldmohr have been removed before querying for it. WanMil Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7140096.html 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 ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [PATCH v2] LocationHook speedup
Hi Gerd, now we have the problem of how to measure the runtime performance. I have compared unpatched and patched mkgmap. Both versions contain the time output of the patched version. I have used one thread only with 15 european tiles (widely spread over europe) and compare the summarized runtime of the LocationHook only because that's what should be improved by the patch. I have done 4 runs of each version. The mean values are: r2154: 65280 ms for LocationHook, 335325 ms overall runtime patch: 55173 ms for LocationHook, 313082 ms overall runtime diff: 10107 ms improvement Hook, 22243 ms improvement overall The overall improvement is a bit problematic because I would expect that it is close to the LocationHook improvement but its twice. The patch uses less memory and therefore the GC (which probably runs outside the Hook) must do less work. But I am unsure if that's the reason for the good overall improvement. WanMil Hello WanMil, I tried it. With small input files I see no change. With larger tiles, it seems to be a bit faster, e.g. runtime decreased 270 to 265 secs. Gerd Date: Sat, 31 Dec 2011 01:18:18 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: [mkgmap-dev] [PATCH v2] LocationHook speedup I tried to improve the first patch by removing anything not required in the Quadtree and by using a different internal data structure. I've seen performance improvements but please try and test yourself :-) The most time is now spend in the creation of the Quadtree. So if you want to search for more performance just start there. WanMil Gerds patches inspired me to look for more things that could be improved. I found that the Quadtree used in the LocationHook is not very optimal. The patch is a first try to increase the performance. The time required for the LocationHook is reduced by 10-50% which is great. Warning: I haven't checked so far if the results are equal. So maybe there are big bugs in the patch... (and the speedup comes from the poor implementation) I will do some more tests and optimizations but maybe some of you can have a look on it, test it and comment it. Have fun! WanMil ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [PATCH v2] LocationHook speedup
Hello WanMil, I think you alew -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7140401.html 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
Re: [mkgmap-dev] [PATCH v2] LocationHook speedup
Hi WanMil, Yes , I think you always have to look at both values, esp. with java and GC. If you optimize a function by allocating a lot of temp. objects, you might see better runtime in this function but overall runtime may be worse because GC gets very busy after executing the function. Gerd WanMil wrote now we have the problem of how to measure the runtime performance. I have compared unpatched and patched mkgmap. Both versions contain the time output of the patched version. I have used one thread only with 15 european tiles (widely spread over europe) and compare the summarized runtime of the LocationHook only because that's what should be improved by the patch. I have done 4 runs of each version. The mean values are: r2154: 65280 ms for LocationHook, 335325 ms overall runtime patch: 55173 ms for LocationHook, 313082 ms overall runtime diff: 10107 ms improvement Hook, 22243 ms improvement overall The overall improvement is a bit problematic because I would expect that it is close to the LocationHook improvement but its twice. The patch uses less memory and therefore the GC (which probably runs outside the Hook) must do less work. But I am unsure if that's the reason for the good overall improvement. -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7140417.html 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
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Hello WanMil, admin_level=7 just an example. admin_levels are used differently in countries and in regions etc. I see Verbandsgemeinde Waldmohr http://www.openstreetmap.org/browse/relation/897709 which is the only boundary that has admin_level=7. The interesting thing is: the returned result-list for this boundary is always empty. So, maybe there is a cheaper way to detect this first or does it means that there is a bug in quadtree or the selection of the boundaries? Sounds more like a bug! But it's also possible that the higher admin_levels (8,9,10,11) references all other admin_levels and therefore there all elements of Waldmohr have been removed before querying for it. hmm, I think you missed the point that we start with lower admin_levels: // Reverse the sorting because we want to start with the lowest admin level Collections.reverse(boundaries); and I found Waldmohr because it prevented the elements from being fully worked out. So, I agree that this seems to be a bug. By the way, I use your bounds from europe_bounds_2006.zip Ciao, Gerd ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [PATCH v2] LocationHook speedup
I've found and fixed another performance bottleneck:
The init method of the LocationHook contained a check if there is any
bounds file in the boundary directory. On my computer this check
requires ~1200ms. This is done for each tile and must be perfomed once
only.
So attached patch saves additionally 1200ms for each tile :-)
WanMil
I tried to improve the first patch by removing anything not required in
the Quadtree and by using a different internal data structure.
I've seen performance improvements but please try and test yourself :-)
The most time is now spend in the creation of the Quadtree. So if you
want to search for more performance just start there.
WanMil
Gerds patches inspired me to look for more things that could be improved.
I found that the Quadtree used in the LocationHook is not very optimal.
The patch is a first try to increase the performance. The time required
for the LocationHook is reduced by 10-50% which is great.
Warning: I haven't checked so far if the results are equal. So maybe
there are big bugs in the patch... (and the speedup comes from the poor
implementation)
I will do some more tests and optimizations but maybe some of you can
have a look on it, test it and comment it.
Have fun!
WanMil
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Index: src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java
===
--- src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java (revision 2153)
+++ src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java (working copy)
@@ -54,7 +54,10 @@
.compile([,;]+);
public static final String BOUNDS_OPTION = bounds;
-
+
+ private static File checkedBoundaryDir;
+ private static boolean checkBoundaryDirOk;
+
private final static HashtableString, String mkgmapTags = new HashtableString, String() {
{
put(admin_level=1, mkgmap:admin_level1);
@@ -92,57 +95,77 @@
nameTags.addAll(LocatorUtil.getNameTags(props));
if (autofillOptions.contains(BOUNDS_OPTION)) {
-
boundaryDir = new File(props.getProperty(bounds, bounds));
- if (boundaryDir.exists() == false) {
-log.error(Disable LocationHook because boundary directory does not exist. Dir:
- + boundaryDir);
-return false;
- }
- File[] boundaryFiles = boundaryDir.listFiles(new FileFilter() {
-public boolean accept(File pathname) {
- return (pathname.isFile() pathname.getName().endsWith(
- .bnd));
-}
+ long t1 = System.currentTimeMillis();
- });
- if (boundaryFiles == null || boundaryFiles.length == 0) {
-log.error(Disable LocationHook because boundary directory contains no boundary files. Dir:
- + boundaryDir);
-return false;
+ synchronized (BOUNDS_OPTION) {
+// checking of the boundary dir is expensive
+// check once only and reuse the result
+if (boundaryDir.equals(checkedBoundaryDir)) {
+ if (checkBoundaryDirOk == false) {
+ log.error(Disable LocationHook because boundary directory is unusable. Dir: +boundaryDir);
+ return false;
+ }
+} else {
+ checkedBoundaryDir = boundaryDir;
+ checkBoundaryDirOk = false;
+
+ if (boundaryDir.exists() == false) {
+ log.error(Disable LocationHook because boundary directory does not exist. Dir:
++ boundaryDir);
+ return false;
+ }
+ File[] boundaryFiles = boundaryDir.listFiles(new FileFilter() {
+ public boolean accept(File pathname) {
+ return (pathname.isFile() pathname.getName()
+ .endsWith(.bnd));
+ }
+ });
+ if (boundaryFiles == null || boundaryFiles.length == 0) {
+ log.error(Disable LocationHook because boundary directory contains no boundary files. Dir:
++ boundaryDir);
+ return false;
+ }
+
+ // passed all checks = boundaries are ok
+ checkBoundaryDirOk = true;
+}
}
+ log.error(Checking bounds dir took
+ + (System.currentTimeMillis() - t1) + ms);
}
return true;
}
private void assignPreprocBounds() {
long t1 = System.currentTimeMillis();
- ElementQuadTree quadTree = new ElementQuadTree(saver.getBoundingBox());
+
+ ListElement elemList = new ArrayListElement(saver.getNodes().size()+saver.getWays().size());
// add all nodes that might be converted to a garmin node (tagcount 0)
for (Node node : saver.getNodes().values()) {
if (node.getTagCount() 0) {
-quadTree.add(node);
+elemList.add(node);
}
}
// add all ways that might be converted to a garmin way (tagcount 0)
// and save all polygons that contains location information
for (Way way : saver.getWays().values()) {
- if (way.getTagCount() == 0) {
-continue;
+ if
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Am 31.12.2011 14:51, schrieb Gerd Petermann: Hello WanMil, admin_level=7 just an example. admin_levels are used differently in countries and in regions etc. I see Verbandsgemeinde Waldmohr http://www.openstreetmap.org/browse/relation/897709 which is the only boundary that has admin_level=7. The interesting thing is: the returned result-list for this boundary is always empty. So, maybe there is a cheaper way to detect this first or does it means that there is a bug in quadtree or the selection of the boundaries? Sounds more like a bug! But it's also possible that the higher admin_levels (8,9,10,11) references all other admin_levels and therefore there all elements of Waldmohr have been removed before querying for it. hmm, I think you missed the point that we start with lower admin_levels: // Reverse the sorting because we want to start with the lowest admin level Collections.reverse(boundaries); No, I didn't. I should have better written admin_levels (11,10,9,8) but the meaning is the same. and I found Waldmohr because it prevented the elements from being fully worked out. Sounds reasonable. But then querying for Waldmohr should have returned some elements, shouldn't it? So, I agree that this seems to be a bug. By the way, I use your bounds from europe_bounds_2006.zip Ciao, Gerd ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [PATCH v2] LocationHook speedup
I used another way to optimize that part. On my machine, the list() method is
much faster than listFiles():
String [] boundaryFileNames = boundaryDir.list();
boolean foundBndFile = false;
for (String s: boundaryFileNames){
if (s.endsWith(.bnd)) {
foundBndFile = true;
break;
}
}
if (!foundBndFile) {
log.error(Disable LocationHook because boundary directory
contains files. Dir:
+ boundaryDir);
return false;
}
Gerd
I've found and fixed another performance bottleneck:
The init method of the LocationHook contained a check if there is any
bounds file in the boundary directory. On my computer this check
requires ~1200ms. This is done for each tile and must be perfomed once
only.
So attached patch saves additionally 1200ms for each tile :-)
WanMil
I tried to improve the first patch by removing anything not required in
the Quadtree and by using a different internal data structure.
I've seen performance improvements but please try and test yourself :-)
The most time is now spend in the creation of the Quadtree. So if you
want to search for more performance just start there.
WanMil
Gerds patches inspired me to look for more things that could be improved.
I found that the Quadtree used in the LocationHook is not very optimal.
The patch is a first try to increase the performance. The time required
for the LocationHook is reduced by 10-50% which is great.
Warning: I haven't checked so far if the results are equal. So maybe
there are big bugs in the patch... (and the speedup comes from the poor
implementation)
I will do some more tests and optimizations but maybe some of you can
have a look on it, test it and comment it.
Have fun!
WanMil ___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Hi WanMil, Date: Sat, 31 Dec 2011 14:55:08 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Am 31.12.2011 14:51, schrieb Gerd Petermann: Hello WanMil, admin_level=7 just an example. admin_levels are used differently in countries and in regions etc. I see Verbandsgemeinde Waldmohr http://www.openstreetmap.org/browse/relation/897709 which is the only boundary that has admin_level=7. The interesting thing is: the returned result-list for this boundary is always empty. So, maybe there is a cheaper way to detect this first or does it means that there is a bug in quadtree or the selection of the boundaries? Sounds more like a bug! But it's also possible that the higher admin_levels (8,9,10,11) references all other admin_levels and therefore there all elements of Waldmohr have been removed before querying for it. hmm, I think you missed the point that we start with lower admin_levels: // Reverse the sorting because we want to start with the lowest admin level Collections.reverse(boundaries); No, I didn't. I should have better written admin_levels (11,10,9,8) but the meaning is the same. No, not really. We check 2,4,5,6 first. and I found Waldmohr because it prevented the elements from being fully worked out. Sounds reasonable. But then querying for Waldmohr should have returned some elements, shouldn't it? No, all elements are kept in the quadtree because they are not fully worked out until this admin_level=7 part is done, or to be more precise, until they are processed for admin_level=8 or higher, because for admin_level=7 nothing is changed in this special case. Gerd ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Am 31.12.2011 15:04, schrieb Gerd Petermann: Hi WanMil, Date: Sat, 31 Dec 2011 14:55:08 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Am 31.12.2011 14:51, schrieb Gerd Petermann: Hello WanMil, admin_level=7 just an example. admin_levels are used differently in countries and in regions etc. I see Verbandsgemeinde Waldmohr http://www.openstreetmap.org/browse/relation/897709 which is the only boundary that has admin_level=7. The interesting thing is: the returned result-list for this boundary is always empty. So, maybe there is a cheaper way to detect this first or does it means that there is a bug in quadtree or the selection of the boundaries? Sounds more like a bug! But it's also possible that the higher admin_levels (8,9,10,11) references all other admin_levels and therefore there all elements of Waldmohr have been removed before querying for it. hmm, I think you missed the point that we start with lower admin_levels: // Reverse the sorting because we want to start with the lowest admin level Collections.reverse(boundaries); No, I didn't. I should have better written admin_levels (11,10,9,8) but the meaning is the same. No, not really. We check 2,4,5,6 first. That would be a bug. But I am very sure that the algorithm starts with admin_level 11. The BoundaryLevelCollator sorts the bounds with admin_level=2 first but then the bounds are reversed. Can you please check if I am wrong? That's important! and I found Waldmohr because it prevented the elements from being fully worked out. Sounds reasonable. But then querying for Waldmohr should have returned some elements, shouldn't it? No, all elements are kept in the quadtree because they are not fully worked out until this admin_level=7 part is done, or to be more precise, until they are processed for admin_level=8 or higher, because for admin_level=7 nothing is changed in this special case. Gerd ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [PATCH v2] LocationHook speedup
Am 31.12.2011 14:58, schrieb Gerd Petermann:
I used another way to optimize that part. On my machine, the list()
method is much faster than listFiles():
String [] boundaryFileNames = boundaryDir.list();
boolean foundBndFile = false;
for (String s: boundaryFileNames){
if (s.endsWith(.bnd)) {
foundBndFile = true;
break;
}
}
if (!foundBndFile) {
log.error(Disable LocationHook because boundary
directory contains files. Dir:
+ boundaryDir);
return false;
}
Gerd
Hi, you missed a no in the errormessage ;)
Henning
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Hi WanMil, sorry, you are right. I must have looked at availableLevels instead of remainingLevels :-( ciao, Gerd Date: Sat, 31 Dec 2011 15:09:03 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Am 31.12.2011 15:04, schrieb Gerd Petermann: Hi WanMil, Date: Sat, 31 Dec 2011 14:55:08 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Am 31.12.2011 14:51, schrieb Gerd Petermann: Hello WanMil, admin_level=7 just an example. admin_levels are used differently in countries and in regions etc. I see Verbandsgemeinde Waldmohr http://www.openstreetmap.org/browse/relation/897709 which is the only boundary that has admin_level=7. The interesting thing is: the returned result-list for this boundary is always empty. So, maybe there is a cheaper way to detect this first or does it means that there is a bug in quadtree or the selection of the boundaries? Sounds more like a bug! But it's also possible that the higher admin_levels (8,9,10,11) references all other admin_levels and therefore there all elements of Waldmohr have been removed before querying for it. hmm, I think you missed the point that we start with lower admin_levels: // Reverse the sorting because we want to start with the lowest admin level Collections.reverse(boundaries); No, I didn't. I should have better written admin_levels (11,10,9,8) but the meaning is the same. No, not really. We check 2,4,5,6 first. That would be a bug. But I am very sure that the algorithm starts with admin_level 11. The BoundaryLevelCollator sorts the bounds with admin_level=2 first but then the bounds are reversed. Can you please check if I am wrong? That's important! and I found Waldmohr because it prevented the elements from being fully worked out. Sounds reasonable. But then querying for Waldmohr should have returned some elements, shouldn't it? No, all elements are kept in the quadtree because they are not fully worked out until this admin_level=7 part is done, or to be more precise, until they are processed for admin_level=8 or higher, because for admin_level=7 nothing is changed in this special case. Gerd ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
[mkgmap-dev] [PATCH v4] LocationHook speedup
Great!
(Although for a nitpicker your patch is wrong. One could create a
directory containing one subdir named 123.bnd. This directory would be
detected as sufficient bounds dir by your patch. But I think we can
ignore this :-)
WanMil
I used another way to optimize that part. On my machine, the list()
method is much faster than listFiles():
String [] boundaryFileNames = boundaryDir.list();
boolean foundBndFile = false;
for (String s: boundaryFileNames){
if (s.endsWith(.bnd)) {
foundBndFile = true;
break;
}
}
if (!foundBndFile) {
log.error(Disable LocationHook because boundary directory contains
files. Dir:
+ boundaryDir);
return false;
}
Gerd
I've found and fixed another performance bottleneck:
The init method of the LocationHook contained a check if there is any
bounds file in the boundary directory. On my computer this check
requires ~1200ms. This is done for each tile and must be perfomed once
only.
So attached patch saves additionally 1200ms for each tile :-)
WanMil
I tried to improve the first patch by removing anything not required in
the Quadtree and by using a different internal data structure.
I've seen performance improvements but please try and test yourself :-)
The most time is now spend in the creation of the Quadtree. So if you
want to search for more performance just start there.
WanMil
Gerds patches inspired me to look for more things that could be improved.
I found that the Quadtree used in the LocationHook is not very optimal.
The patch is a first try to increase the performance. The time required
for the LocationHook is reduced by 10-50% which is great.
Warning: I haven't checked so far if the results are equal. So maybe
there are big bugs in the patch... (and the speedup comes from the poor
implementation)
I will do some more tests and optimizations but maybe some of you can
have a look on it, test it and comment it.
Have fun!
WanMil
___
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Index: src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java
===
--- src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java (revision 2153)
+++ src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java (working copy)
@@ -13,7 +13,6 @@
package uk.me.parabola.mkgmap.reader.osm;
import java.io.File;
-import java.io.FileFilter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
@@ -54,7 +53,10 @@
.compile([,;]+);
public static final String BOUNDS_OPTION = bounds;
-
+
+ private static File checkedBoundaryDir;
+ private static boolean checkBoundaryDirOk;
+
private final static HashtableString, String mkgmapTags = new HashtableString, String() {
{
put(admin_level=1, mkgmap:admin_level1);
@@ -92,57 +94,84 @@
nameTags.addAll(LocatorUtil.getNameTags(props));
if (autofillOptions.contains(BOUNDS_OPTION)) {
-
boundaryDir = new File(props.getProperty(bounds, bounds));
- if (boundaryDir.exists() == false) {
-log.error(Disable LocationHook because boundary directory does not exist. Dir:
- + boundaryDir);
-return false;
- }
- File[] boundaryFiles = boundaryDir.listFiles(new FileFilter() {
-public boolean accept(File pathname) {
- return (pathname.isFile() pathname.getName().endsWith(
- .bnd));
-}
+ long t1 = System.currentTimeMillis();
- });
- if (boundaryFiles == null || boundaryFiles.length == 0) {
-log.error(Disable LocationHook because boundary directory contains no boundary files. Dir:
- + boundaryDir);
-return false;
+ synchronized (BOUNDS_OPTION) {
+// checking of the boundary dir is expensive
+// check once only and reuse the result
+if (boundaryDir.equals(checkedBoundaryDir)) {
+ if (checkBoundaryDirOk == false) {
+ log.error(Disable LocationHook because boundary directory is unusable. Dir: +boundaryDir);
+ return false;
+ }
+} else {
+ checkedBoundaryDir = boundaryDir;
+ checkBoundaryDirOk = false;
+
+ if (boundaryDir.exists() == false) {
+ log.error(Disable LocationHook because boundary directory does not exist. Dir:
++ boundaryDir);
+ return false;
+ }
+ String[] boundaryFiles = boundaryDir.list();
+ if (boundaryFiles == null || boundaryFiles.length == 0) {
+ log.error(Disable LocationHook because boundary directory contains no boundary files. Dir:
++ boundaryDir);
+ return false;
+ }
+ boolean boundsFileFound = false;
+ for (String boundsFile : boundaryFiles) {
+ if (boundsFile.endsWith(.bnd)) {
+ boundsFileFound = true;
+ break;
+ }
+ }
+ if (boundsFileFound == false) {
+ log.error(Disable LocationHook because boundary directory contains no boundary files. Dir:
++ boundaryDir);
+ return false;
+
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Puuuh, but it's also a pity because that would have been an easy improvement ;-) Hi WanMil, sorry, you are right. I must have looked at availableLevels instead of remainingLevels :-( ciao, Gerd Date: Sat, 31 Dec 2011 15:09:03 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Am 31.12.2011 15:04, schrieb Gerd Petermann: Hi WanMil, Date: Sat, 31 Dec 2011 14:55:08 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Am 31.12.2011 14:51, schrieb Gerd Petermann: Hello WanMil, admin_level=7 just an example. admin_levels are used differently in countries and in regions etc. I see Verbandsgemeinde Waldmohr http://www.openstreetmap.org/browse/relation/897709 which is the only boundary that has admin_level=7. The interesting thing is: the returned result-list for this boundary is always empty. So, maybe there is a cheaper way to detect this first or does it means that there is a bug in quadtree or the selection of the boundaries? Sounds more like a bug! But it's also possible that the higher admin_levels (8,9,10,11) references all other admin_levels and therefore there all elements of Waldmohr have been removed before querying for it. hmm, I think you missed the point that we start with lower admin_levels: // Reverse the sorting because we want to start with the lowest admin level Collections.reverse(boundaries); No, I didn't. I should have better written admin_levels (11,10,9,8) but the meaning is the same. No, not really. We check 2,4,5,6 first. That would be a bug. But I am very sure that the algorithm starts with admin_level 11. The BoundaryLevelCollator sorts the bounds with admin_level=2 first but then the bounds are reversed. Can you please check if I am wrong? That's important! and I found Waldmohr because it prevented the elements from being fully worked out. Sounds reasonable. But then querying for Waldmohr should have returned some elements, shouldn't it? No, all elements are kept in the quadtree because they are not fully worked out until this admin_level=7 part is done, or to be more precise, until they are processed for admin_level=8 or higher, because for admin_level=7 nothing is changed in this special case. Gerd ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Flooding in Southern Scotland
Marko and Bartosz, Thank you both for your advice. The mkgmap log showed a very large number of messages, but none at all relating to coastline. But using Bartosz's coastlines-europe file solved the problem (once I had remembered to reference it before the data files), at the expense of a rather larger gmapsupp file. Once again, many thanks. Roger Roger Calvert On 30/12/2011 21:04, Bartosz Fabianowski wrote: You can always use my daily updated coastlines as well. These are based on the Geofabrik Europe extract respectively the complete planet file, so they will be more complete than the coastlines you get from a single-country extract: http://fabianowski.eu/osm/coastlines/ - Bartosz ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Flooding in Southern Scotland
On Sat, Dec 31, 2011 at 05:37:43PM +, Roger Calvert wrote: Thank you both for your advice. The mkgmap log showed a very large number of messages, but none at all relating to coastline. There could have been some MultiPolygonRelation errors related to coastlines. I should mention that the checks in JOSM Validator and mkgmap are not overlapping that much. JOSM detects some things better, but it does not detect land-on-land or sea-on-sea situations as well as mkgmap, as it does not colour the areas. But using Bartosz's coastlines-europe file solved the problem (once I had remembered to reference it before the data files), at the expense of a rather larger gmapsupp file. OK, in that case the issue might be that the Geofabrik cutting polygon is intersecting with some islets that have been added or moved fairly recently. The Europe coastline at http://fabianowski.eu/osm/coastlines/ looks like it could be loaded into JOSM on a computer with enough RAM. It could be an interesting exercise to ask Frederik Ramm for the cutting polygon in *.osm format and load it and the coastlines in JOSM, to see if the Geofabrik polygon can be improved. I did this for Finland a couple of years ago. In addition to the coastline, I observed the country border and a few lakes near the border when I edited the cutting polygon. It took a couple of iterations to get it fully right. Marko ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
