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 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 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 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
[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
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)
@@ -117,32 +117,33 @@
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 (way.getTagCount() 0) {
+elemList.add(way);
}
-
- // in any case add it to the element list
- quadTree.add(way);
}
+ log.error(Creating quadlist took +(System.currentTimeMillis()-t1)+ ms);
+ ElementQuadTree quadTree = new ElementQuadTree(saver.getBoundingBox(), elemList);
long tb1 = System.currentTimeMillis();
+ log.error(Creating quadtree took +(tb1-t1)+ ms);
// Load the boundaries that intersect with the bounding box of the tile
ListBoundary boundaries = BoundaryUtil.loadBoundaries(boundaryDir,
saver.getBoundingBox());
long tb2 = System.currentTimeMillis();
- log.info(Loading boundaries took +(tb2-tb1)+ ms);
+ log.error(Loading boundaries took +(tb2-tb1)+ ms);
// go through all boundaries, check if the necessary tags are available
// and standardize the country name to the 3 letter ISO code
@@ -190,11 +191,11 @@
Collections.reverse(boundaries);
- log.info(LocationHook prepared after,
-(System.currentTimeMillis() - t1), ms);
+ log.error(Preproc bounds sorted after +
+(System.currentTimeMillis() - tb2)+ ms);
- log.info(Quadtree depth: +quadTree.getDepth());
- log.info(Quadtree coords: +quadTree.getCoordSize());
+// log.info(Quadtree depth: +quadTree.getDepth());
+// log.info(Quadtree coords: +quadTree.getCoordSize());
// Map the boundaryid to the boundary for fast access
MapString, Boundary boundaryById = new HashMapString, Boundary();
@@ -338,8 +339,10 @@
}
bIter.remove();
- if (quadTree.getCoordSize() = 0) {
-log.info(Finish Location Hook: Remaining boundaries: +boundaries.size());
+ if (quadTree.isEmpty()) {
+if (log.isInfoEnabled()) {
+ log.info(Finish Location Hook: Remaining boundaries: +boundaries.size());
+}
return;
}
}
@@ -373,6 +376,8 @@
return true;
}
+ private static long sumTime = 0;
+
public void end() {
long t1 = System.currentTimeMillis();
log.info(Starting with location hook);
@@ -381,8 +386,11 @@
assignPreprocBounds();
}
- log.info(Location hook finished in,
-(System.currentTimeMillis() - t1), ms);
+ long dt = (System.currentTimeMillis() - t1);
+ log.error(Location hook finished in +
+dt+ ms);
+ sumTime += dt;
+ log.error(Sum: +sumTime);
}
Index: src/uk/me/parabola/mkgmap/main/Main.java
===
--- src/uk/me/parabola/mkgmap/main/Main.java (revision 2153)
+++ src/uk/me/parabola/mkgmap/main/Main.java (working copy)
@@ -95,7 +95,14 @@
* @param args The command line arguments.
*/
public static void main(String[] args) {
-
+ try {
+ Thread.sleep(1L);
+ } catch (InterruptedException exp) {
+ // TODO Auto-generated catch block
+ exp.printStackTrace();
+ }
+ long t1 = System.currentTimeMillis();
+
// We need at least one argument.
if (args.length 1) {
System.err.println(Usage:
