during writing, much time is spent in seemingly empty tiles

[cldellow]

When generating North America, I noticed that some z6 tiles took a long time. During this time, CPU was at 100%, disk I/O was basically nil, yet the tiles written/sec dropped. I attached a debugger a couple of times and saw most threads were in buildWayGeometry or fast_clip.

The tiles where this happened were surprising to me! For example, z6/21/17, seen below (using protomaps' basemap and the PMTiles Viewer):

This is a stretch of ocean between Baffin Island and a part of Greenland. There's not a lot going on! I also observed this on 20/11, 20/12, 21/8, 21/13, 21/14 and 22/7.

I'm going to try to re-run on a narrow section with some logs to figure out what we're trying to render here.

My intuition is one of two things is happening:

1. We're trying to output some large multipolygon, and then we clip it to nothing (i.e., the z6 tile is in one of its holes)
2. We're trying to output some large multipolygon, and then we clip it to the entire tile (i.e. it covers the z6 tile entirely)

I'm inferring that the cost to copy the multipolygon and clip it is quite expensive, and this is what's causing the slowdown in tile throughput -- we have to do it once per tile per zoom, so for a given z6 tile and its higher zooms, we do this 65,536 times.

At first, I wondered if it would be possible to amortize the clipping cost -- read the polygon once, generate all the clips, and stash them away for future use.

Setting aside the memory usage implications, doing that in a general fashion sounds quite complicated, and definitely beyond my understanding of the geometry code.

But: perhaps there'd be a lot of benefit in just handling the special case where we clip a multipolygon and it's either entirely excluded or covers the tile entirely. If we learned this at some zoom level z, we know it applies to all higher zoom levels. Those zooms can then either directly construct the polygon or exclude it, as appropriate.

I hope to do some digging to confirm this hypothesis, but wanted to at least write it down in case I got distracted.

[cldellow]

I started to investigate the "we're entirely covered by the multipolygon" case, as it seemed easier to get a test case.

I looked at Hudson Bay, at z6/16/18. Every tile from z6 up ought to be entirely covered by Hudson Bay.

If I change tile writing to only emit tiles at z6/16/18 and higher, it takes 2m19s.

If I stub in code that directly emits the clipping bbox as a multipolygon, runtime drops to 45s.

So that seems promising!

Now to figure out how boost::geometry works. It seems like there are some footguns, for example, I wanted to use boost::geometry::equals(polygon, box) to compare the clipped polygon and the clipping bbox.

But it returns false, even though I feel like these two ought to be equal:

• clipping bbox: min_corner=-90.0281, 73.0969 max_corner=-84.3469, 78.7781
• clipped polygon
  • x=-84.3469, y=78.7781 <-- max_corner
  • x=-84.3469, y=73.0969
  • x=-90.0281, y=73.0969 <-- min_corner
  • x=-90.0281, y=78.7781
  • x=-84.3469, y=78.7781

[cldellow]

Well, this works, but leaves me curious about how Boost thinks about equality:

boost::geometry::equals(polygon1, clippingBbox); // false

Polygon polygon2;
boost::geometry::assign(polygon2, clippingBbox);

boost::geometry::equals(polygon1, polygon2); // true

[cldellow]

Opened ~#606~ #607, which provides a big improvement. I still see writing get hung up on the odd tile, but I'm not sure if it's the same root cause or something else.