Repository navigation
Description
Status: done
Part of #3227.
Depends on: none
TL;DR
Goal: The seam between the reference terrain and GLO-30 takes a bounded memory and decodes nothing when the terrain opens, with heights that are bit-identical to today's.
Problem: Seam::measure decodes each held archive tile of the bounds and the ring around them when Terrain::open runs, and keeps 32 KiB of depths and biases for each tile near the archive. That is about 1.4 GiB for DE, CH, AT, FR and IT and about 9 GiB for all of Europe [est], above the 4 GiB own budget of the routing bake (#3297), and the decode of all tiles is a start-up time that grows with the coverage. The planner terrain step (terrarium) opens the same Terrain.
Decision:
- At open, the seam reads only the index: the sorted list of the held tiles in reach (from
held_digests, which already decides "held" by the file), the bias of the best model of each, and the check that each has a bias. It prints the bias lines of today. - The coverage of a tile (which of its 64 × 64 cells are full, and its bias) is a bitset of 512 B and an
f32. It comes from the tile at first use, decoded witharchive.tileasSeam::measuredoes today, not throughTerrain::shared: so a tile that only the seam reads adds no credit to the attribution. A cache of 4,096 coverages (about 2 MiB) keeps it. A tile outside the reach has no coverage, as today. - The depths of a tile (32 KiB) are computed at first use by today's
depthsfrom the coverages of its 3 × 3 block, and a cache of 256 tiles (8 MiB) keeps them. A tile with no held tile in its 3 × 3 block, or whose depths are all at or below −FEATHER_M, reads as outside: [−FEATHER_M, 0], as the filter ofSeam::newdoes today. So each cell gives the value of today. - Each caller keeps its last 4 depth tiles in
Recent, so the hot path takes no lock.
Rejected: - Bitsets for all held tiles, depths computed at each read: 512 B for each tile is still a table that grows with the coverage (about 150 MB for Europe), and a depth costs a search over up to 1 km of cells.
- Depths stored in the reference archive by the terrain prepare: a new prepared format, and the depths depend on the neighbours, so a new tile changes the files of its ring.
- A smaller cell type for the depths (
f16): the heights change.
Systems: source-preparation
Contracts: none
Size: S (1 system, no contract change, about 250 changed lines)
Branch:develop
Facts
Terrain::openrunsSeam::measureonreach(bounds)and adds the SHA-256 of each held tile to the identities (planner.rs#L160-L166).Seam::measuredecodes each held tile with a best model, counts the full cells and fails when the index states no bias of that model (planner.rs#L450-L476).Seam::newcomputes the depths of each tile within one tile of a held tile and keeps only the tiles with a depth above −FEATHER_M(#L479-L486);cellreturns [−FEATHER_M, 0] for any other tile (#L489-L494).depthsreads only the coverage of the 3 × 3 block of tiles around its tile (planner.rs#L514-L551). A cell is 2^4 × 2^4 archive pixels, so a tile of 1,024 pixels has 64 × 64 cells; a depth and a bias are twof32, 32 KiB for each tile.held_digestsdecides "held" by the tile file, without a decode (reference.rs#L431-L443). The decoded tiles are a shared queue of 256 tiles of 4 MiB, and each caller keeps the last 8 inRecent(planner.rs#L98-L104, #L304-L342).national_inreadsSeam::cellfor each coverage cell of a box of the terrain tile sweep (planner.rs#L272-L276, terrarium.rs#L78).
Plan
planner.rs:Coverageholdsfull: [u64; 64](one bit for each cell) andbias: f32.depths(coverage: impl Fn((u32, u32)) -> Option<&Coverage>, ti, tj)keeps its arithmetic and reads the bits.planner.rs:Seamholds the sorted held tiles of the reach, and two caches under oneMutex: coverages (4,096 tiles,Nonefor a tile that is not held, has no best model or lies outside the reach) and depths (256 tiles,Nonefor outside). The lock covers only the look-up and the insert: a missing coverage decodes and the depths compute outside it, so the parallel heights do not wait; two threads that compute the same tile get the same value, and the first insert stays.Seam::open(archive, window)reads only the index: the held tiles,ReferenceArchive::biasof each, the error of today for a missing bias, and the bias lines.Seam::cell(i, j, recent)takes the depths fromrecent, else from the cache, else computes them: the coverages of the 3 × 3 block (each fromarchive.tileand the bit count of today), thendepths, then the filter of today.planner.rs:Recentgets the last 4 depth tiles beside its archive tiles.Seam::at,Terrain::heightandnational_inpass it;national_ingets aRecentof its own.planner.rs:Seam::measureandSeam::newgo. The tests build aSeamfrom a map of coverages through the same constructor that the archive uses.- Tests. The two seam tests of
planner.rsand the archive tests oftests/planner.rskeep their checks. New:a_held_tile_without_depth_reads_as_outside: a held tile with no full cell, a bias of −2 m and no full neighbour gives [−FEATHER_M, 0] in each cell, as the filter of today;the_seam_keeps_at_most_its_cache: a sweep over 300 tiles keeps at most 256 depth tiles and 4,096 coverages.
Files
host/obc-dem/src/planner.rs: change:Coverage,Seam,Recent,depths, the tests.host/obc-dem/src/terrarium.rs: change:national_inwith aRecent.host/obc-dem/tests/planner.rs: change: the new constructor.
Done when
obc test -p obc-dem,obc exec cargo clippy -p obc-dem --all-targets -- -D warnings,obc test -p planner-router-build.- With the reference archive on the owner's disk: the Switzerland routing bake of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 with
planner/referencegives the samemanifest.json, and aplanner/terrainbake of a box that holds an edge of the archive gives the sameterrain.mbtilesSHA-256, as before the change. - The pull request records the own memory (
RssAnon) afterTerrain::openon the whole archive, the time of the open, and the time of theplanner/terrainbake of the box, before and after the change.
Out of scope
- The SHA-256 of each held tile in the identities and so in the manifest (about 19 MB of JSON for Europe [est]): the identity of a package of format 10 is Route package format 10: the contract, the writer and the installer #3301's.
- The cache sizes of the GLO-30 squares and of the decoded tiles.
Built differently
Pull request #3326 built this design, into develop, with these changes:
Seam::opentakes the held tiles, not a window.Terrain::openreads the held tiles of the reach once, for the identities and for the seam.- A tile whose 3 × 3 block holds no archive tile gives no depths without a look-up in the shared cache, and it puts no entry there. Only the
Recentof the caller keeps that answer, so tiles far from the archive do not push computed depths out of the cache. Each cell has the value that this issue states. Terrain::shareduses the samekeepas the seam, so its decoded tiles hold no duplicate when two threads decode one tile.- Measured with a synthetic archive (144 tiles, 289 MB, an ellipse with a square hole, so convex and concave edges; 4 cores, 15 GB RAM):
Terrain::openof the whole archive takes 0.001 to 0.003 s (0.69 to 0.76 s before) and adds 280 KiB of own memory. Theterrain.mbtilesof a box at the edge of the archive has the same bytes before and after. - Not measured: the real reference archive. The owner merged without the three owner steps of the pull request (the routing bake and the terrain bake with the real archive, before and after). A bake with the real archive shows a fault as another hash.
Activity