Skip to content

Terrain: the seam of the reference terrain in bounded memory #3298

Closed

Description

@timohueser

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 with archive.tile as Seam::measure does today, not through Terrain::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 depths from 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 of Seam::new does 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::open runs Seam::measure on reach(bounds) and adds the SHA-256 of each held tile to the identities (planner.rs#L160-L166).
  • Seam::measure decodes 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::new computes 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); cell returns [−FEATHER_M, 0] for any other tile (#L489-L494).
  • depths reads 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 two f32, 32 KiB for each tile.
  • held_digests decides "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 in Recent (planner.rs#L98-L104, #L304-L342).
  • national_in reads Seam::cell for each coverage cell of a box of the terrain tile sweep (planner.rs#L272-L276, terrarium.rs#L78).

Plan

  1. planner.rs: Coverage holds full: [u64; 64] (one bit for each cell) and bias: f32. depths(coverage: impl Fn((u32, u32)) -> Option<&Coverage>, ti, tj) keeps its arithmetic and reads the bits.
  2. planner.rs: Seam holds the sorted held tiles of the reach, and two caches under one Mutex: coverages (4,096 tiles, None for a tile that is not held, has no best model or lies outside the reach) and depths (256 tiles, None for 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::bias of each, the error of today for a missing bias, and the bias lines. Seam::cell(i, j, recent) takes the depths from recent, else from the cache, else computes them: the coverages of the 3 × 3 block (each from archive.tile and the bit count of today), then depths, then the filter of today.
  3. planner.rs: Recent gets the last 4 depth tiles beside its archive tiles. Seam::at, Terrain::height and national_in pass it; national_in gets a Recent of its own.
  4. planner.rs: Seam::measure and Seam::new go. The tests build a Seam from a map of coverages through the same constructor that the archive uses.
  5. Tests. The two seam tests of planner.rs and the archive tests of tests/planner.rs keep 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_in with a Recent.
  • 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/reference gives the same manifest.json, and a planner/terrain bake of a box that holds an edge of the archive gives the same terrain.mbtiles SHA-256, as before the change.
  • The pull request records the own memory (RssAnon) after Terrain::open on the whole archive, the time of the open, and the time of the planner/terrain bake of the box, before and after the change.

Out of scope

Built differently

Pull request #3326 built this design, into develop, with these changes:

  • Seam::open takes the held tiles, not a window. Terrain::open reads 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 Recent of 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::shared uses the same keep as 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::open of the whole archive takes 0.001 to 0.003 s (0.69 to 0.76 s before) and adds 280 KiB of own memory. The terrain.mbtiles of 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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions