[Patch] Faster BoundaryGrid

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[Patch] Faster BoundaryGrid

Gerd Petermann
Hi WanMil,

attached is a small patch which drastically improves BoundaryGrid for
tiles that contain mostly sea. I found such a tile in south-america, and the patched version is > 10 times faster.
It contais a large part of the pacific, and BoudaryGrid searches the boundary zip file for
> 5000 different *.bnd files, most of them do not exist in your bounds_20120401.zip , so the
code in BoundaryUtil searches through all elements of the zip file to find out that it doesn't exist.

The patch creates a HashSet first with the  available files and calls the load routine only for
those that exist.

Gerd
BoundaryGrid.java.patch
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Faster BoundaryGrid

WanMil
Hi Gerd,

the patch looks good but I am a bit in doubt if it really improves the
overall performance for most cases (I haven't measured myself).

Did you measure the performance diffs when all bounds files are
available? This is more likely than the case that the tile contains
mostly sea.
I believe the patched version is slower if the bounds files are
available because the
BoundaryUtil.getBoundaryDirContent(boundaryDirName) method might take
some time to list the several thousand bounds files.

WanMil

> Hi WanMil,
>
> attached is a small patch which drastically improves BoundaryGrid for
> tiles that contain mostly sea. I found such a tile in south-america, and the
> patched version is>  10 times faster.
> It contais a large part of the pacific, and BoudaryGrid searches the
> boundary zip file for
>> 5000 different *.bnd files, most of them do not exist in your
>> bounds_20120401.zip , so the
> code in BoundaryUtil searches through all elements of the zip file to find
> out that it doesn't exist.
>
> The patch creates a HashSet first with the  available files and calls the
> load routine only for
> those that exist.
>
> Gerd
> http://gis.19327.n5.nabble.com/file/n5680180/BoundaryGrid.java.patch
> BoundaryGrid.java.patch
>
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/Patch-Faster-BoundaryGrid-tp5680180.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Faster BoundaryGrid

Gerd Petermann
In reply to this post by Gerd Petermann
Hi WanMil,

you are right, the patched code is a bit slower for the normal case.
I see two solutions:
1) We don't allow directories in the zip file. With this restriction we can simply stop searching if the wanted bnd file is not found instead of traveling through thousends of entries.
We can alarm the user when we find a directory structure within the zip.
2) We save the list that is created in LocationHook.init() and use it as a parm for the BoundaryGrid
constructor.

I'd prefer option 1, what do you think?

Gerd

GerdP wrote
Hi WanMil,

attached is a small patch which drastically improves BoundaryGrid for
tiles that contain mostly sea. I found such a tile in south-america, and the patched version is > 10 times faster.
It contais a large part of the pacific, and BoudaryGrid searches the boundary zip file for
> 5000 different *.bnd files, most of them do not exist in your bounds_20120401.zip , so the
code in BoundaryUtil searches through all elements of the zip file to find out that it doesn't exist.

The patch creates a HashSet first with the  available files and calls the load routine only for
those that exist.

Gerd
BoundaryGrid.java.patch
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Faster BoundaryGrid

WanMil
Hi Gerd,

I also prefer solution 1.

WanMil

> Hi WanMil,
>
> you are right, the patched code is a bit slower for the normal case.
> I see two solutions:
> 1) We don't allow directories in the zip file. With this restriction we can
> simply stop searching if the wanted bnd file is not found instead of
> traveling through thousends of entries.
> We can alarm the user when we find a directory structure within the zip.
> 2) We save the list that is created in LocationHook.init() and use it as a
> parm for the BoundaryGrid
> constructor.
>
> I'd prefer option 1, what do you think?
>
> Gerd
>
>
> GerdP wrote
>>
>> Hi WanMil,
>>
>> attached is a small patch which drastically improves BoundaryGrid for
>> tiles that contain mostly sea. I found such a tile in south-america, and
>> the patched version is>  10 times faster.
>> It contais a large part of the pacific, and BoudaryGrid searches the
>> boundary zip file for
>>> 5000 different *.bnd files, most of them do not exist in your
>>> bounds_20120401.zip , so the
>> code in BoundaryUtil searches through all elements of the zip file to find
>> out that it doesn't exist.
>>
>> The patch creates a HashSet first with the  available files and calls the
>> load routine only for
>> those that exist.
>>
>> Gerd
>>   http://gis.19327.n5.nabble.com/file/n5680180/BoundaryGrid.java.patch
>> BoundaryGrid.java.patch
>>
>
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/Patch-Faster-BoundaryGrid-tp5680180p5682445.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Faster BoundaryGrid

Gerd Petermann
Hi WanMil,

attached is the reworked patch.
Changes compared to r2724:
- Performance improvement when a zip file is used to store precompiled boundaries and input file contains a large area of sea. Since we don't generate *.bnd files for sea-only tiles, the old algorithm did a costly sequential search for each *.bnd file that would cover such a sea-only tile.
- Drawback: Boundaries in a  zip file containing directories are only found if they are in the topmost level

BoundaryGrid_v2.patch

I had to change the logic a bit to avoid opening the zip file again and again. I fear this conflicts with your precompiled_sea.patch.

Gerd

WanMil wrote
Hi Gerd,

I also prefer solution 1.

WanMil

> Hi WanMil,
>
> you are right, the patched code is a bit slower for the normal case.
> I see two solutions:
> 1) We don't allow directories in the zip file. With this restriction we can
> simply stop searching if the wanted bnd file is not found instead of
> traveling through thousends of entries.
> We can alarm the user when we find a directory structure within the zip.
> 2) We save the list that is created in LocationHook.init() and use it as a
> parm for the BoundaryGrid
> constructor.
>
> I'd prefer option 1, what do you think?
>
> Gerd
>
>
> GerdP wrote
>>
>> Hi WanMil,
>>
>> attached is a small patch which drastically improves BoundaryGrid for
>> tiles that contain mostly sea. I found such a tile in south-america, and
>> the patched version is>  10 times faster.
>> It contais a large part of the pacific, and BoudaryGrid searches the
>> boundary zip file for
>>> 5000 different *.bnd files, most of them do not exist in your
>>> bounds_20120401.zip , so the
>> code in BoundaryUtil searches through all elements of the zip file to find
>> out that it doesn't exist.
>>
>> The patch creates a HashSet first with the  available files and calls the
>> load routine only for
>> those that exist.
>>
>> Gerd
>>   http://gis.19327.n5.nabble.com/file/n5680180/BoundaryGrid.java.patch
>> BoundaryGrid.java.patch
>>
>
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/Patch-Faster-BoundaryGrid-tp5680180p5682445.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev