[mkgmap-dev] MDR building out-of-memory

Wed May 12 10:08:31 BST 2021

Hi Ticker,

I think the MultiSortKeys were introduced because the on-the-fly solution was far too slow, at least with the normal Java sort. Could well be that the problem was solved with Java 8 or newer releases.

I think there was a special case with maps containing huge numbers of equally named roads causing extreme run times.
This depends on the style. Some styles add a name like "tr2" for each unnamed track with tracktype=grade2.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
Gesendet: Mittwoch, 12. Mai 2021 10:48
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] MDR building out-of-memory

Hi Gerd

Certainly no cache. Maybe reduce the chunk size, but this might
increase copying.

It could be improved by doing a linear chunk split/sort then a multi
-way merge. This would avoid lots of copying assuming the following:

Using the original array to store sorted chunks demands that another
array of the same full size is needed for the final merge. If each
sorted key chunk is converted to a object chunk and these merged, then
although the same total size is needed, it is made of number of smaller
arrays.

The most space efficient solution might be have Mdr11 "implements
Comparable" and generate pairs of sortkeys on the fly and let the java
sort take care of all the details.

The other use of LargeListSorter is Mdr7. I get a higher hit-rate
(~50%) for the first/partialSorter (1046096 allstreets).

However, for the repeated fullNameSorter on the partial results, most
of the lists are just 1 long, with very few more than 10. I guess this
depends on --road-name-config/split-name and use of shields etc, but
LargeListSorted seems overkill.

Ticker

On Tue, 2021-05-11 at 19:15 +0000, Gerd Petermann wrote:
> Hi Ticker,
>
> I think the cache is not meant to improve run time, it is used to
> deduplicate and thus reduce memory. Maybe it would be better to use a
> smaller chunk size and no cache.
> No idea why I didn't use
> merged = new ArrayList<>(len);
>
> Gerd
>
> ________________________________________
> Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> Gesendet: Dienstag, 11. Mai 2021 19:19
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] MDR building out-of-memory
>
> Hi Gerd
>
> I've looked at this, and if Mdr5 space becomes a problem again, I'll
> consider converting to it.
>
> A couple of comments:
>
> My map had 2909735 poi so the sort chunk size was ~727433. The cache
> sizes after each chunk were 563095, 603595, 597239 & 605718. Is the
> cache worth-while for this low hit-rate? Just running the Gmapsupp
> combiner on existing tiles (without --route, so no streets), I got a
> run time of 1 min 44 secs with the cache and 1 min 30 without!
> However
> most of this time is copying the tiles into gmapsupp.img so not an
> accurate statistic.
>
> You could pre-allocate List<> "merged" with the correct size.
>
> Ticker
>
> On Tue, 2021-05-11 at 14:40 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > I've committed the patch as is. I've not seen big changes in
> > performance, but I've used a different (already existing) set of
> > files which was created with my own style. For me,
> > Mdr11.preWriteImpl() is the most problematic part reg. OOM errors.
> >
> > Maybe look at the code which uses LargeListSorter.
> >
> > Gerd
> >
> > ________________________________________
> > Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> > von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> > Gesendet: Dienstag, 11. Mai 2021 13:27
> > An: Development list for mkgmap
> > Betreff: Re: [mkgmap-dev] MDR building out-of-memory
> >
> > Hi Gerd
> >
> > Here is updated version of patch.
> >
> > Changes from last:
> >
> > Uses your cache code for region and country (in 2 places). For
> > British
> > Isles, there are 190 regions and 7 countries, so I don't think the
> > extra memory will be a problem and there should be some performance
> > benefit.
> >
> > Delays allocating cities until it can use sortKeys.size() for
> > initial
> > allocation. For above map this is 0.07% too big, so I don't think
> > trimToSize() is worthwhile.
> >
> > Shares the Sort object between the 4 methods.
> >
> > Ticker
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev at lists.mkgmap.org.uk
https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev