Why do some countries take a lot longer in the "sorting ways" step than others?

[kuwapa]

I've just finished writing a bash script to process all countries and have been testing it. I've been noticing that some countries like Botswana, Egypt, etc take a lot longer in the sorting ways step in comparison to other countries with similar amount of data and number of tiles. As an example, Angola & Algeria get generated in just under 5 mins while Botswana ends up taking upwards of 20 minutes.

Why does this happen - is it an optimisation yet to be added to tilemaker or is it something to do with the data in those particular countries?

[kleunen]

Maybe the ways are not stored sorted? And some countries are still presorted while others are more random? Wild guess.

[systemed]

I've not benchmarked this particular case, but my default assumption as to why some countries take longer than others would always be relations. Assembling multipolygon relations into geometries is slow, and if a country has more of them, then processing will take longer. Something like https://www.openstreetmap.org/relation/349348 in Botswana, with 11217 members, will require a lot of time to process. (This isn't an issue unique to tilemaker: I believe there are some US National Forests that osm2pgsql just can't cope with, for the same reason.)

https://github.com/systemed/tilemaker/blob/master/src/osm_store.cpp#L376-L438 is the code that assembles multipolygons from their constituent ways. It's a for loop inside a for loop inside a while loop which, in big relations, is going to be pretty slow. I think it might be possible to optimise this by creating a map of start/end node ID→[way IDs] on entering the method, and then using this to look up the next candidate to append.

(This may not necessarily explain why the pause happens after "Sorting ways", but .pbf reading is multithreaded and the relation processing happens immediately after sorting ways, so I guess it's quite feasible.)

[systemed]

Some progress in #327.