Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Hello WanMil, thanks for the util. I am still trying to produce the input for mkgmap with osmosis. The program produces very large temp files, and after hours it crashed because the disk was full :-( Maybe I am not using the best parms? Or doesn't it work on windows? I use this: osmosis -v --rb f:\osm\europe.osm.pbf --tf accept-relations boundary=administrative --used-node idTrackerType=BitSet --used-way idTrackerType=BitSet --wb boundary_relations.osm.pbf Maybe I can download the result somewhere? Ciao, Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7147396.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
Hi Gerd, don't use osmosis: it's *very* slow for such a job. Better use the osmconvert/osmfilter toolchain. That's magnitudes faster... You can find a how to at: http://wiki.openstreetmap.org/wiki/Mkgmap/help/options#Using_precompiled_bounds_for_the_address_index WanMil Hello WanMil, thanks for the util. I am still trying to produce the input for mkgmap with osmosis. The program produces very large temp files, and after hours it crashed because the disk was full :-( Maybe I am not using the best parms? Or doesn't it work on windows? I use this: osmosis -v --rb f:\osm\europe.osm.pbf --tf accept-relations boundary=administrative --used-node idTrackerType=BitSet --used-way idTrackerType=BitSet --wb boundary_relations.osm.pbf Maybe I can download the result somewhere? Ciao, Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7147396.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 v1] LocationHook speedup
Gerd, don't worry. The link to the description was broken on the new help page. I've just corrected it before I replied to you The last time (beginning of December) I've created the boundaries for europe with -Xmx3g and that was *very* close to the OOME. But there is a workaround which I also use to create the world boundaries: One can workout smaller overlapping parts (containing complete countries!) and merge the results of the smaller parts: java uk.me.parabola.mkgmap.reader.osm.boundary.BoundaryMerger boundsdir1 boundsdir2 resultdir WanMil Hello WanMil, Shame on me. I finally found that the description is on the new help page, the place I should have visited first ... By the way: On windows, r2159 is not able to process the european boundaries, but the patch for Coord.java seems to allow the action on windows. So I think this is an argument for it. Working with these large files is still no fun with mkgmap, so I hope I can find something which really improves performance ;-) Gerd G:\mkgmap_all\trunk\distjava -Xmx1600m -jar mkgmap.jar --createboundsfile=f:\osm\europe-boundaries.osm Time started: Tue Jan 03 20:05:54 CET 2012 Exception in thread main java.lang.OutOfMemoryError: Java heap space at sun.awt.geom.Order1.getReversedCurve(Order1.java:198) at sun.awt.geom.Curve.getWithDirection(Curve.java:706) at sun.awt.geom.CurveLink.getSubCurve(CurveLink.java:56) at sun.awt.geom.AreaOp.pruneEdges(AreaOp.java:389) at sun.awt.geom.AreaOp.calculate(AreaOp.java:141) at java.awt.geom.Area.pathToCurves(Area.java:177) at java.awt.geom.Area.init(Area.java:108) at uk.me.parabola.util.Java2DConverter.createArea(Java2DConverter.java:60) at uk.me.parabola.mkgmap.reader.osm.boundary.BoundaryRelation.processElements(BoundaryRelation.java:276) at uk.me.parabola.mkgmap.reader.osm.boundary.BoundaryElementSaver.addRelation(BoundaryElementSaver.java:132) at uk.me.parabola.mkgmap.reader.osm.xml.Osm5XmlHandler$SaxHandler.endElement(Osm5XmlHandler.java:182) at com.sun.org.apache.xerces.internal.parsers.AbstractSAXParser.endElement(AbstractSAXParser.java:601) at com.sun.org.apache.xerces.internal.xinclude.XIncludeHandler.endElement(XIncludeHandler.java:1016) at com.sun.org.apache.xerces.internal.impl.XMLDocumentFragmentScannerImpl.scanEndElement(XMLDocumentFragmentScan nerImpl.java:1782) at com.sun.org.apache.xerces.internal.impl.XMLDocumentFragmentScannerImpl$FragmentContentDriver.next(XMLDocument FragmentScannerImpl.java:2939) at com.sun.org.apache.xerces.internal.impl.XMLDocumentScannerImpl.next(XMLDocumentScannerImpl.java:648) at com.sun.org.apache.xerces.internal.impl.XMLNSDocumentScannerImpl.next(XMLNSDocumentScannerImpl.java:140) at com.sun.org.apache.xerces.internal.impl.XMLDocumentFragmentScannerImpl.scanDocument(XMLDocumentFragmentScanne rImpl.java:511) at com.sun.org.apache.xerces.internal.parsers.XML11Configuration.parse(XML11Configuration.java:808) at com.sun.org.apache.xerces.internal.parsers.XML11Configuration.parse(XML11Configuration.java:737) at com.sun.org.apache.xerces.internal.parsers.XMLParser.parse(XMLParser.java:119) at com.sun.org.apache.xerces.internal.parsers.AbstractSAXParser.parse(AbstractSAXParser.java:1205) at com.sun.org.apache.xerces.internal.jaxp.SAXParserImpl$JAXPSAXParser.parse(SAXParserImpl.java:522) at javax.xml.parsers.SAXParser.parse(SAXParser.java:395) at javax.xml.parsers.SAXParser.parse(SAXParser.java:198) at uk.me.parabola.mkgmap.reader.osm.xml.Osm5MapDataSource.load(Osm5MapDataSource.java:72) at uk.me.parabola.mkgmap.reader.osm.boundary.BoundaryPreparer.run(BoundaryPreparer.java:105) at uk.me.parabola.mkgmap.main.Main.endOptions(Main.java:341) at uk.me.parabola.mkgmap.CommandArgsReader.readArgs(CommandArgsReader.java:126) at uk.me.parabola.mkgmap.main.Main.main(Main.java:114) Gerd Date: Tue, 3 Jan 2012 20:38:42 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Hi Gerd, don't use osmosis: it's *very* slow for such a job. Better use the osmconvert/osmfilter toolchain. That's magnitudes faster... You can find a how to at: http://wiki.openstreetmap.org/wiki/Mkgmap/help/options#Using_precompiled_bounds_for_the_address_index WanMil Hello WanMil, thanks for the util. I am still trying to produce the input for mkgmap with osmosis. The program produces very large temp files, and after hours it crashed because the disk was full :-( Maybe I am not using the best parms? Or doesn't it work on windows? I use this: osmosis -v --rb f:\osm\europe.osm.pbf --tf accept-relations boundary=administrative --used-node idTrackerType=BitSet --used-way idTrackerType=BitSet --wb boundary_relations.osm.pbf Maybe I can download the result somewhere? Ciao, Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1
Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Hello WanMil, I think I understand now what is so special with these admin_level=7 boundaries. They form a collection of admin_level=8 boundaries. So, after working through all admin_level=8 boundaries, the admin_level=7 is also done because the admin_level=8 boundaries have the lies_in tag for them, but LocationHook doesn't recognize that and continues to work through the admin_level=6 boundaries. For each of the level=6 boundaries we retrieve a large number of elements from quadTree, and most of them are already fully worked out. So, if I got this right, we could save a lot of time if we can detect that admin_level=7 should not be added to remainingLevels which would reduce the size of the quadtree earlier. I think we would need a function that determines if a boundary x is completely overlaped by boundaries with a higher admin_level that have the lies_in for x. Does that make sense? Do we have such a function? Gerd 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. ___ 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 Gerd, good idea! I am not sure if this additional preprocessing information has a great effect but it's worth trying that. Up to now we don't have such a function. The place for such a function would be to extend the BoundaryPreparer.workoutBoundaryRelations method. WanMil Hello WanMil, I think I understand now what is so special with these admin_level=7 boundaries. They form a collection of admin_level=8 boundaries. So, after working through all admin_level=8 boundaries, the admin_level=7 is also done because the admin_level=8 boundaries have the lies_in tag for them, but LocationHook doesn't recognize that and continues to work through the admin_level=6 boundaries. For each of the level=6 boundaries we retrieve a large number of elements from quadTree, and most of them are already fully worked out. So, if I got this right, we could save a lot of time if we can detect that admin_level=7 should not be added to remainingLevels which would reduce the size of the quadtree earlier. I think we would need a function that determines if a boundary x is completely overlaped by boundaries with a higher admin_level that have the lies_in for x. Does that make sense? Do we have such a function? Gerd 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. ___ 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 v1] LocationHook speedup
Hello WanMil, OK, I'll first try the effect by hard coding the wanted boundary list. If I really see a big improvement, I know how much complexety the new function can have. My first approach was to use subtract() for the Areas that are in the level=7 boundary, but that it much too slow. Ciao, Gerd Date: Mon, 2 Jan 2012 20:40:32 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Hi Gerd, good idea! I am not sure if this additional preprocessing information has a great effect but it's worth trying that. Up to now we don't have such a function. The place for such a function would be to extend the BoundaryPreparer.workoutBoundaryRelations method. WanMil Hello WanMil, I think I understand now what is so special with these admin_level=7 boundaries. They form a collection of admin_level=8 boundaries. So, after working through all admin_level=8 boundaries, the admin_level=7 is also done because the admin_level=8 boundaries have the lies_in tag for them, but LocationHook doesn't recognize that and continues to work through the admin_level=6 boundaries. For each of the level=6 boundaries we retrieve a large number of elements from quadTree, and most of them are already fully worked out. So, if I got this right, we could save a lot of time if we can detect that admin_level=7 should not be added to remainingLevels which would reduce the size of the quadtree earlier. I think we would need a function that determines if a boundary x is completely overlaped by boundaries with a higher admin_level that have the lies_in for x. Does that make sense? Do we have such a function? Gerd 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. ___ 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 v1] LocationHook speedup
Hello WanMil, okay, I see. This will allow complex calculations. I have to read again how you create that boundary files for europe... Gerd Date: Mon, 2 Jan 2012 20:59:52 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Hi Gerd, you have to do this step during the preprocessing. Time used in preprocessing doesn't matter because that have to be performed once only and most of the mkgmap users just download them and never have to run it themselves. All other aproaches won't work (I am quite sure ;-) WanMil Hello WanMil, OK, I'll first try the effect by hard coding the wanted boundary list. If I really see a big improvement, I know how much complexety the new function can have. My first approach was to use subtract() for the Areas that are in the level=7 boundary, but that it much too slow. Ciao, Gerd Date: Mon, 2 Jan 2012 20:40:32 +0100 From: wmgc...@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup Hi Gerd, good idea! I am not sure if this additional preprocessing information has a great effect but it's worth trying that. Up to now we don't have such a function. The place for such a function would be to extend the BoundaryPreparer.workoutBoundaryRelations method. WanMil Hello WanMil, I think I understand now what is so special with these admin_level=7 boundaries. They form a collection of admin_level=8 boundaries. So, after working through all admin_level=8 boundaries, the admin_level=7 is also done because the admin_level=8 boundaries have the lies_in tag for them, but LocationHook doesn't recognize that and continues to work through the admin_level=6 boundaries. For each of the level=6 boundaries we retrieve a large number of elements from quadTree, and most of them are already fully worked out. So, if I got this right, we could save a lot of time if we can detect that admin_level=7 should not be added to remainingLevels which would reduce the size of the quadtree earlier. I think we would need a function that determines if a boundary x is completely overlaped by boundaries with a higher admin_level that have the lies_in for x. Does that make sense? Do we have such a function? Gerd 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. ___ 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 ___ 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
Gerd,
attached BoundaryLister is a useful util when working with bounds. It
lists the tags of all bounds in the preprocessed bounds files. Just give
the bounds dir as parameter and the BoundaryLister creates a bounds.txt
file containing all the information.
WanMil
Hello WanMil,
okay, I see. This will allow complex calculations. I have to read again
how you create that boundary files for europe...
Gerd
Date: Mon, 2 Jan 2012 20:59:52 +0100
From: wmgc...@web.de
To: mkgmap-dev@lists.mkgmap.org.uk
Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Hi Gerd,
you have to do this step during the preprocessing. Time used in
preprocessing doesn't matter because that have to be performed once only
and most of the mkgmap users just download them and never have to run it
themselves.
All other aproaches won't work (I am quite sure ;-)
WanMil
Hello WanMil,
OK, I'll first try the effect by hard coding the wanted boundary list.
If I really see a big improvement, I know how much complexety the new
function can have. My first approach was to use subtract() for the
Areas
that are in the level=7 boundary, but that it much too slow.
Ciao,
Gerd
Date: Mon, 2 Jan 2012 20:40:32 +0100
From: wmgc...@web.de
To: mkgmap-dev@lists.mkgmap.org.uk
Subject: Re: [mkgmap-dev] [PATCH v1] LocationHook speedup
Hi Gerd,
good idea! I am not sure if this additional preprocessing information
has a great effect but it's worth trying that.
Up to now we don't have such a function. The place for such a
function
would be to extend the BoundaryPreparer.workoutBoundaryRelations
method.
WanMil
Hello WanMil,
I think I understand now what is so special with these
admin_level=7
boundaries.
They form a collection of admin_level=8 boundaries. So, after
working
through all admin_level=8 boundaries, the admin_level=7 is also
done
because the admin_level=8 boundaries have the lies_in tag for
them, but
LocationHook doesn't recognize that and continues to work
through the
admin_level=6 boundaries. For each of the level=6 boundaries we
retrieve
a large number of elements from quadTree, and most of them are
already
fully worked out.
So, if I got this right, we could save a lot of time if we can
detect
that admin_level=7 should not be added to remainingLevels which
would
reduce the size of the quadtree earlier.
I think we would need a function that determines if a boundary x is
completely overlaped by boundaries with a higher admin_level
that have
the lies_in for x.
Does that make sense?
Do we have such a function?
Gerd
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.
___
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
___
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/boundary/BoundaryLister.java
===
--- src/uk/me/parabola/mkgmap/reader/osm/boundary/BoundaryLister.java (revision 0)
+++ src/uk/me/parabola/mkgmap/reader/osm/boundary/BoundaryLister.java (revision 0)
@@ -0,0 +1,31 @@
+package uk.me.parabola.mkgmap.reader.osm.boundary;
+
+import java.io.File;
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.util.List;
+
+public class BoundaryLister {
+
+ /**
+ * @param args
+ * @throws IOException
+ */
+ public static void main(String[] args) throws IOException {
+ File boundsdir = new File(args[0]);
+
+ File[] bndFiles = boundsdir.listFiles(new BoundaryUtil.BoundaryFileFilter());
+ PrintWriter out = new PrintWriter(new File(boundsdir
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 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 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 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 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 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
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] [PATCH v1] LocationHook speedup
Hello WanMil, I tested the patch on r2153, but sorry, I did not see any real improvement. Here are some numbers: Verzeichnis von f:\osm_out_ref\niedersachsen 28.10.2011 15:4111.629.857 63240001.osm.pbf 28.10.2011 15:4113.454.668 63240002.osm.pbf 28.10.2011 15:4115.077.982 63240003.osm.pbf 28.10.2011 15:4111.447.198 63240004.osm.pbf 28.10.2011 15:4112.717.149 63240005.osm.pbf 28.10.2011 15:4112.601.470 63240006.osm.pbf 28.10.2011 15:4110.123.728 63240007.osm.pbf 7 Datei(en) 87.052.052 Bytes 0 Verzeichnis(se), 171.072.065.536 Bytes frei r2153 with original ElementQuadTreeNode.java: G:\mkgmap_all\trunk\distjava -Xmx1600m -Xms1600m -jar mkgmap.jar --max-jobs=1 -c f:\osm\gerd_mkgmap.cfg -c f:\osm_out_ref\niedersachsen\template.args Time started: Fri Dec 30 09:43:09 CET 2011 SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240001.osm.pbf: Creating quadtree took 2594 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240001.osm.pbf: Location hook finished in 15294 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240002.osm.pbf: Creating quadtree took 3250 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240002.osm.pbf: Location hook finished in 20574 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240003.osm.pbf: Creating quadtree took 3906 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240003.osm.pbf: Location hook finished in 18184 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240004.osm.pbf: Creating quadtree took 2718 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240004.osm.pbf: Location hook finished in 12935 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240005.osm.pbf: Creating quadtree took 3905 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240005.osm.pbf: Location hook finished in 13372 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240006.osm.pbf: Creating quadtree took 2390 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240006.osm.pbf: Location hook finished in 12560 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240007.osm.pbf: Creating quadtree took 1578 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240007.osm.pbf: Location hook finished in 8123 ms Time finished: Fri Dec 30 09:50:22 CET 2011 Total time taken: 432735ms r2153 with patched ElementQuadTreeNode.java: G:\mkgmap_all\trunk\distjava -Xmx1600m -Xms1600m -jar mkgmap.jar --max-jobs=1 -c f:\osm\gerd_mkgmap.cfg -c f:\osm_out_ref\niedersachsen\template.args Time started: Fri Dec 30 09:34:16 CET 2011 SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240001.osm.pbf: Creating quadtree took 3155 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240001.osm.pbf: Location hook finished in 12840 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240002.osm.pbf: Creating quadtree took 3155 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240002.osm.pbf: Location hook finished in 17402 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240003.osm.pbf: Creating quadtree took 3780 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240003.osm.pbf: Location hook finished in 15996 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240004.osm.pbf: Creating quadtree took 2296 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240004.osm.pbf: Location hook finished in 10732 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240005.osm.pbf: Creating quadtree took 2859 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240005.osm.pbf: Location hook finished in 12513 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240006.osm.pbf: Creating quadtree took 2561 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240006.osm.pbf: Location hook finished in 10309 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240007.osm.pbf: Creating quadtree took 2077 ms SCHWERWIEGEND (LocationHook): f:\osm_out_ref\niedersachsen\63240007.osm.pbf: Location hook finished in 7154 ms Time finished: Fri Dec 30 09:41:30 CET 2011 Total time taken: 433328ms Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7137649.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, I also thought about reducing the CPU time in LocationHook, but with a different approach: I think a lot of time is used because the quadtree first adds elements to resultList, (a HashSet) and 2nd a loop takes all these elements to add tags. 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. 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? Ciao, Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7137702.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
Hi Gerd, the results are a bit heterogeneous. In some cases the LocationHook finishes much quicker, in some cases it is slower. I have some ideas what can be improved, so I will change the patch and have a additional try. Hello WanMil, I also thought about reducing the CPU time in LocationHook, but with a different approach: I think a lot of time is used because the quadtree first adds elements to resultList, (a HashSet) and 2nd a loop takes all these elements to add tags. 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?!) 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. The algorithm in LocationHook works as follows: 1. All elements (points and lines) having at least one tag are added to the QuadTree. This is expensive - it takes 20-50% of the complete LocationHook time. 2. All preprocessed bounds that overlaps the tile boundaries are loaded from file. There is only little improvement possible (maybe zipping could improve disk access time). 3. The bounds are sorted by their admin_level tag, so that the greatest admin_level (or postcode) comes first. 4. For all elements of the preprocessed bounds the covered elements (points and lines) are searched. All matching elements are tagged with the preprocessed bounds. The preprocessed bounds also contains internal references (mkgmap:lies_in) which are tagged also (e.g. the bounds of the town Cologne contains the information that it is located in region North Rhine Westfalia and Germany). 5. Elements having all tags from the remaining preprocessed bounds are removed from the quadtree because no more information can be added to them. Adding tags is a cheap method with a small memory footprint. At least the footprint is not much bigger than a reference to a dictionary. And you have to maintain the dictionary which I think is expensive. But I don't know exactly how you want to build up the dictionary so I cannot say for sure. Maybe one the following things can contain an improvement: * Analyzing the style rules might help to sort out some of the preprocessed boundaries * Changing the parameters of the Quadtree (max node size 1000) * The Quadtree query for a polygon (ElementQuadtreeNode: public SetElement get(ElementQuadTreePolygon polygon, SetElement resultList)) divides the polygon into bounds of the four subnodes. I expect that this is quite expensive. Maybe there is a better way to reduce the number of quadtree nodes that have to be queried. WanMil Ciao, Gerd -- View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7137702.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
[mkgmap-dev] [PATCH v1] LocationHook speedup
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
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)
@@ -138,6 +138,7 @@
}
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());
@@ -381,8 +382,8 @@
assignPreprocBounds();
}
- log.info(Location hook finished in,
-(System.currentTimeMillis() - t1), ms);
+ log.error(Location hook finished in +
+(System.currentTimeMillis() - t1)+ ms);
}
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,8 @@
* @param args The command line arguments.
*/
public static void main(String[] args) {
-
+ long t1 = System.currentTimeMillis();
+
// We need at least one argument.
if (args.length 1) {
System.err.println(Usage: mkgmap [options...] file.osm);
@@ -115,6 +116,9 @@
} catch (ExitException e) {
System.err.println(e.getMessage());
}
+ long t2 = System.currentTimeMillis();
+ System.out.println(Time: +(t2-t1)+ ms);
+ log.error(Time: +(t2-t1)+ ms);
}
/**
Index: src/uk/me/parabola/util/ElementQuadTreeNode.java
===
--- src/uk/me/parabola/util/ElementQuadTreeNode.java (revision 2153)
+++ src/uk/me/parabola/util/ElementQuadTreeNode.java (working copy)
@@ -1,10 +1,12 @@
package uk.me.parabola.util;
import java.awt.Rectangle;
+import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
import java.util.List;
-import java.util.Map.Entry;
import java.util.Set;
import uk.me.parabola.imgfmt.app.Area;
@@ -17,15 +19,68 @@
public final class ElementQuadTreeNode {
- private static final Logger log = Logger.getLogger(ElementQuadTreeNode.class);
+ private static final Logger log = Logger
+ .getLogger(ElementQuadTreeNode.class);
private static final int MAX_POINTS = 1000;
- private MultiHashMapCoord, Element points;
+ private MultiHashMapCoord, Element pointsOld;
+ private ListObject points;
+ private int noPoints = 0;
+ private boolean sorted = true;
private final Area bounds;
private Area coveredBounds;
private long items = -1;
+ private final static class WayPoint extends HashSetCoord {
+ private final Way way;
+
+ public WayPoint(Way way) {
+ this.way = way;
+ }
+
+ public final Way getWay() {
+ return way;
+ }
+ }
+
+ private final static ComparatorObject comp = new ComparatorObject() {
+ private int getClassId(Object e) {
+ if (e instanceof Node) {
+return 1;
+ }
+ if (e instanceof Way || e instanceof WayPoint) {
+return 2;
+ }
+ if (e instanceof Relation) {
+return 3;
+ }
+ return 4;
+ }
+
+ private long getId(Object e) {
+ if (e instanceof Element) {
+return ((Element) e).getId();
+ } else if (e instanceof WayPoint) {
+return ((WayPoint) e).getWay().getId();
+ }
+ return 0;
+ }
+
+ public int compare(Object o1, Object o2) {
+ if (o1 == o2) {
+return 0;
+ }
+
+ long did = getId(o1) - getId(o2);
+ if (did != 0) {
+return (did 0 ? 1 : -1);
+ }
+
+ return getClassId(o1) - getClassId(o2);
+ }
+ };
+
public Area getCoveredBounds() {
return coveredBounds;
}
@@ -70,8 +125,7 @@
public ElementQuadTreeNode(Area bounds) {
this(bounds, Collections.Element emptyList());
}
-
-
+
public ElementQuadTreeNode(CollectionElement elements) {
this.children = null;
@@ -80,7 +134,7 @@
int minLong = Integer.MAX_VALUE;
int maxLong = Integer.MIN_VALUE;
- this.points = new MultiHashMapCoord, Element();
+ this.pointsOld = new MultiHashMapCoord, Element();
for (Element el : elements) {
CollectionCoord coords = null;
if (el instanceof Relation) {
@@ -88,14 +142,14 @@
} else if (el instanceof Way) {
Way w = (Way) el;
if (w.isClosed()) {
- coords = w.getPoints().subList(0,
