Skip to content

Routing bake 3/4: flat working columns in the preparation, and terrain on demand #3240

Closed

Description

@timohueser

Status: done

Part of #3228. Depends on #3239. The words of #3228 apply.

TL;DR

Goal: The preparation of the profiles uses flat 32-bit working columns, and the terrain keeps a bounded number of decoded squares. The Switzerland preparation then peaks at about 3 GB instead of 7.3 GB (target), and the package keeps the same bytes.
Problem: For each profile, the preparation keeps the full cost curve of every road and 64-bit cost arrays, the spatial index is a map of sets, connectivity builds its own copy of the topology, and the routing step decodes every terrain square of the region at once (see the Facts of #3228).
Decision: The preparation keeps cost totals and cost-basis indices, 32-bit working columns, one topology, a sorted list for the spatial index, and closures that it computes road by road. obc-dem decodes a terrain square when a height needs it, and keeps at most 12 squares.
Systems: routing, source-preparation
Contracts: none
Size: M (two systems, about 600 changed lines)

Plan

  1. cost.rs: Costing::new takes the cost-basis dictionary (&mut base::Dictionary) and keeps two columns per road: the total cost and the dictionary index of its cost basis. It drops each cost curve after it takes the total; roads: Vec<Option<RoadCost>> goes. base::metric takes the indices instead of the bases.
  2. lib.rs and base.rs: the bake builds the topology (first, head) once from the sorted edges. write_topology, the turn costs and connectivity::States read it, and connectivity builds only the reverse arcs.
  3. lib.rs: the road totals and the turn costs are u32 working columns. The all-ones value means "unavailable", as in the stored columns, and a finite value that does not fit is an error. All the consumers take these columns: base::metric, landmarks::Junctions::prepare and connectivity::States::snappable. planner_router::base::write_column takes its values as an iterator of u64; the bake maps u32::MAX to u64::MAX on the way in. So the writer picks the stored width from the largest finite value as today, and the bytes stay the same.
  4. lib.rs, spatial index: the bake collects (cell, road) pairs, sorts them, and removes repeated pairs, as the BTreeSet does today. Then it walks the sorted list once: each run of one cell gives the road list of that cell, and each run of one one-degree key gives one directory object. The objects are the same as today.
  5. lib.rs, closures: Doubts.roads stays one byte per road, and the bake computes it before the costing. The closure sets of a road are computed again from its tags while Closures::build reads them, so no road keeps a Vec of closures.
  6. host/obc-dem/src/planner.rs: the GLO-30 files are indexed by square (latitude and longitude). Terrain::height keeps its &self signature. A Mutex holds the decoded squares, as decoded does for the reference tiles. When a height needs a square that is not decoded, height decodes it and drops the oldest square beyond 12. With at most 52 MB per square, the squares take at most about 0.6 GB, and with the 1 GiB of reference tiles the terrain stays under 2 GB. load stays for the terrain tile sweep of terrarium.rs, and loaded squares count toward the same bound only when height decoded them.
  7. step.rs no longer loads the terrain of the whole region. terrain::apply sorts the roads by the GLO-30 square of their first point (latitude, then longitude), then by fine cell. A height near the edge of a square reads at most the four squares around it.
  8. New test in host/obc-dem/tests/planner.rs: heights without load equal the heights after load, and the number of decoded squares stays at or below the bound.

Done when

  • obc test -p planner-router-build, obc test -p obc-dem and clippy on both crates pass.
  • A Switzerland bake gives the same manifest ID as before.
  • The pull request records the peak of each stage of a Switzerland bake, before and after.

Generated by Claude Code

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