shard the node store to reduce memory usage

systemed / tilemaker

Make OpenStreetMap vector tiles without the stack

https://tilemaker.org/

Other

1.44k stars 229 forks source link

shard the node store to reduce memory usage #571

Closed cldellow closed 10 months ago

cldellow commented 10 months ago

It looks like PR #499 adopts 36 bits as the max size of an OSM ID.

The NodeStore currently uses a full 64 bits for these IDs. This PR changes it to shard the nodes across 16 collections (4 bits) and then store only the last 32 bits in the collection itself.

This reduces memory usage for the NodeStore by 25%, without much impact on runtime.

The CompactNodeStore is still much better, as it has no overhead and constant time lookups -- but I'm often lazy and not using a renumbered PBF file.

cldellow commented 10 months ago

A similar improvement could be made for the way store, and is perhaps worth doing. My intuition was that there are 9x as many nodes as ways, and all nodes are stored during processing, whereas only some ways (but perhaps most in practice?) are stored during processing. The WayStore also doesn't (yet) show up in my massif profiles.

On the other hand, an improvement for ways would also improve --compact mode use.

systemed commented 10 months ago

Neat idea. I'll do a bit of local testing but this looks good - thanks!

The current max OSM way ID is somewhere in the region of 1200000000, i.e. not far above 2**30. So we could probably move WayStore IDs to plain unsharded 32-bit, at least for now.

cldellow commented 10 months ago

The current max OSM way ID is somewhere in the region of 1200000000, i.e. not far above 2**30. So we could probably move WayStore IDs to plain unsharded 32-bit, at least for now.

Oh! That's attractive for how easy it'd be to implement.

Looking at https://wiki.openstreetmap.org/wiki/Stats#Accumulated_ways_and_relations, it looks like there are ~1B ways and they're added at a roughly steady rate of 100M/year, so plenty of headroom.

Looking at my usual test cases, the ratio of stored ways to nodes seems actually much worse than 1:9:

Great Smoky Mountains National Park: 2.5M nodes, 4k ways (1:625)
Kentucky and bits of some surrounding states: 81M nodes, 143k ways (1:566)
Nova Scotia: 12M nodes, 100k ways (1:120)

So whereas the NodeStore change saved 324MB of RAM in the Kentucky case, a similar change for WayStore would only save 0.5MB, I think. Still not a bad idea, but I'll go fishing for some higher payoff things first.

cldellow commented 10 months ago

Oops, just noticed that I botched extracting this PR from my hacked-up development tree. Will fix it sometime this week and push an update.

(I'm pretty sure https://github.com/systemed/tilemaker/pull/571/files#diff-935619b0dbb4696e9b8a02fa69ff07857ddda6efb35289406eb62a766b3b3087R83 ought to be using internal_element_t...but now I wonder if I've missed anything else.)

systemed commented 10 months ago

I had a go last night and it increased the memory usage for great-britain-latest.osm.pbf so that might explain it 😊 No problem - as and when.

systemed commented 10 months ago

Great Britain extract:

master 6min40, 14.1GB
this branch 6m45, 13.8GB
2% memory saving, 1% slower

Germany extract:

master 13m02, 30.7GB
this branch 13m31, 28.7GB
6.5% memory saving, 4% slower

So on balance this looks like a positive change!

cldellow commented 10 months ago

Great to hear! I hope to send a separate PR with some unrelated performance changes that should claw back the runtime cost that was lost here.

systemed commented 10 months ago

I've done a little bit more testing and this is working brilliantly - thanks again!