Skip to content

Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296

Closed

Description

@timohueser

Status: done

Part of #3227.
Depends on: #3295

TL;DR

Goal: The bake puts the roads into their final order once, while it emits them, and samples the terrain bucket by bucket inside that one copy: no stage gathers a road column or a shape by a permutation over the whole region.
Problem: spatial_order sorts a permutation and then copies each of 13 road columns and the shape list in that order: a random read of about 62 GB for Europe, 49 GB of it the shapes [est, bake.md finding 2.3]. The terrain runs before it, reads the old shapes and writes the new ones at random places of the whole list, and writes the 49 GB shape list three times (zeros, defaults, heights).
Decision:

  • After walk 1 of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295, one scan of ends writes the order key of each road (layout::keys, which takes the key function): a u64, here layout::spatial_key, today's Morton key of its arrival point, which is the point of its arrival junction. A sort of the keys gives the bucket bounds: a sorted list of keys that cut the roads into K buckets of about equal counts.
  • Walk 2 (the emit of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295) appends each road to the bucket of its key. Buckets::finish then takes the buckets in order: it sorts the (key, emit index) records of a bucket and gathers the bucket straight into the final columns (Roads::append_permuted). The order is that of one sort by (key, emit index), as today, so the manifest ID stays.
  • The terrain runs inside that gather: the roads of a bucket are sampled in the visit order of today (by the GLO-30 square of the first point, then by fine cell) and written into their own slots of the bucket's range. A height does not depend on the order, so the bytes stay; a square decodes about once in each bucket that reaches it.
  • K = ⌈bytes of a bucket before and after the terrain / sort run bytes⌉, at most 256, so the random reads and writes of a bucket fit the page cache that the sort runs already assume.
  • The turn rules resolve after the emit, on the final road IDs: no remap.
  • Routing bake: the partition into nested cells, and the roads in cell order #3300 passes only another key function to layout::keys (layout::partition_key in place of layout::spatial_key). The bounds, the buckets, the emit, the gather with the terrain and the turn rules stay.
    Rejected:
  • Buckets by the top bits of the key: a region uses a small part of the world key, and sea and mountains leave most fixed ranges empty or tiny.
  • The terrain as a pass over all roads in the final order: the Morton order comes back to a square after more than 12 others, so a square of 52 MB decodes about 1.5 to 2.5 times; and the pass writes the shapes a fourth time.
  • A permuted copy of each bucket that is then appended: one more copy of all roads.
  • Emit in way order, then copy into buckets through a map from emit index to final ID: a second copy of all roads and shapes, which Routing: hierarchical search and disk storage #3227 excludes.
  • Keys written in walk 1: in Routing bake: the partition into nested cells, and the roads in cell order #3300 the key needs the partition, which runs after walk 1.
    Systems: routing
    Contracts: none
    Size: S (1 system, no contract change, about 450 changed lines)
    Branch: develop

Facts

  • spatial_order computes the Morton key of the last shape point, sorts (key, road), builds the inverse, remaps the turn rules and permutes the roads (layout.rs#L6-L34). Column::permuted and Lists::permuted read their source in the order of the permutation (column.rs#L100-L103, #L214-L220), and the old and the new lists exist together (lib.rs#L181-L213).
  • The last shape point of a road is the node of its arrival junction, so the key is a function of points[to] (osm.rs#L480-L499).
  • terrain::apply sorts its visit by the GLO-30 square of the first point and the fine cell, so a square decodes about once, counts the new length of each shape from its 2D points, fills a new list with defaults and writes each road into its slot (terrain.rs#L8-L26, #L103-L105). The list is written three times with the zeros of the file growth (column.rs#L130-L137, #L185-L195).
  • Terrain decodes a missing GLO-30 square under a lock and keeps the 12 newest in a queue (obc-dem planner.rs#L103-L111, #L252-L263); a height does not depend on what the queue holds.
  • The step runs the import, the terrain and then the order (step.rs#L59-L68). A sort run is 4 GiB or OBC_DATA_MEMORY_BYTES when it is lower (work.rs#L12-L25).

Plan

  1. layout.rs: spatial_key(point: Point) -> Result<u64, String>: the Morton key and the range check of today's spatial_order. keys(ends: &Column<(u32, u32)>, key: impl Fn(u32, u32) -> Result<u64, String>) -> Result<Column<u64>, String>: key(from, to) of each road in emit order, with the walk-1 junction IDs. The bake passes |_, to| spatial_key(points[to]). osm::junctions (walk 1 of Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295) also returns the shape points of all roads and, when the bake has terrain, the points after the resampling (terrain::pieces, from the 2D points).
  2. layout.rs: bounds(keys: &Column<u64>, buckets: usize) -> Vec<u64>: sort::sorted of a copy of the keys; the key at each multiple of ⌈R / K⌉, without repeats. The bucket of key k is bounds.partition_point(|&b| b <= k), so equal keys share a bucket. K = ⌈(60 B × R + 12 B × (shape points + resampled points)) / work::sort_run_bytes()⌉, from 1 to 256. The bounds change only the speed, never the order.
  3. layout.rs: Buckets::new(bounds: Vec<u64>); push(&mut self, road: &Road, key: u64) appends the road to the Roads of its bucket and (key, emit index, position in the bucket) to its key column. finish(self, terrain: Option<&mut dyn FnMut(Point) -> Result<Option<f64>, String>>) -> Result<(Roads, Column<u32>), String> takes the buckets in order: sort::sorted of the key column gives the final order of the bucket, Roads::append_permuted adds it, and the bucket is dropped. The second result is the emit index of each final road.
  4. lib.rs: Roads::append_permuted(&mut self, bucket: &Roads, order: &[u32], terrain: …) extends each column of self with the values of bucket in order. Without terrain the shapes are gathered too. With terrain it reserves the slots of the new shapes of the bucket (lengths from terrain::pieces), visits the roads of the bucket by (GLO-30 square of the first point, fine cell), samples each with terrain::sample and writes its shape, ascent_m and descent_m into its slot. Roads::permute and Lists::filled go.
  5. terrain.rs: sample(shape: &[Point], structure: bool, height, out: &mut [Point]) -> Result<(u32, u32), String> holds today's resampling, filter and bridge rule for one road; pieces becomes public; apply goes. step.rs changes the warnings after finish in today's order: it removes the line "No DEM applied…", adds the terrain line of apply, then the credits of Terrain::attribution.
  6. osm.rs: emit takes keys and Buckets, pushes each road with keys[i], and returns the final Roads. The turn rules then resolve on the final roads, as Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 leaves them: the same pairs, sorted.
  7. layout.rs: spatial_order becomes order(graph: &mut Graph, terrain: …) for graphs that tests build in memory: spatial_key of the last point of each road, bounds, Buckets, and the remap of the turn rules through the second result of finish. The bake does not call it.
  8. step.rs: Terrain::open before the import; walk 1, keys, bounds, walk 2, finish with the heights; then the terrain is dropped and prepare runs.
  9. Tests. layout.rs: buckets_give_the_order_of_one_sort: 1,000 roads with keys that repeat, bounds for 1 and for 5 buckets, with and without a height function, give the same columns as one sort by (key, emit index) with heights from today's per-road rule. tests/routing.rs: the terrain test calls order with heights and keeps its check of the shape and heights of each road; its check of the visit order goes; the tests that called spatial_order call order.

Files

  • planner/router-build/src/layout.rs: change: spatial_key, keys, bounds, Buckets, order, the test.
  • planner/router-build/src/osm.rs: change: the point counts of walk 1, the emit into Buckets.
  • planner/router-build/src/lib.rs: change: Roads::append_permuted; permute goes.
  • planner/router-build/src/column.rs: change: Lists::filled goes; slots of known lengths for one bucket.
  • planner/router-build/src/terrain.rs: change: sample, pieces; apply goes.
  • planner/router-build/src/step.rs: change: the order of the stages.
  • planner/router-build/tests/routing.rs, planner/service/tests/http.rs: change: order.

Done when

Out of scope

Built differently

Pull request #3334 built this design with these changes:

  • The limits are checked between walk 1 and walk 2. The terrain is now inside the import, so a check after the import would run after the terrain of the whole region. Limits::check takes the road count, the turns and the manifest estimate from the walk-1 ends. Only the closure-set check (check_closures) runs after the import.
  • Walk 1 gives one (from, to) for each road, not for each run.
  • Buckets::push takes the Road by value with its RoadSource, and returns an error when the road count passes u32.
  • The import prints a stage line, "Sampling terrain and ordering the roads into K buckets".
  • terrain::resampled_len is new and terrain::pieces stays private. planner/service/tests/http.rs did not change.
  • The 110 % mark: on North Rhine-Westphalia the emit with the order and the terrain takes 49.0 to 54.6 s, which is 113 to 126 % of the terrain and the order before the change (43.3 s). The old figure does not hold walk 2. From the start of the import to the first profile the change is +6.4 % (217.5 s to 231.4 s). The owner accepted the bake time. The pull request lists four possible savings under "Review notes".
  • The capped run (North Rhine-Westphalia, a memory cgroup of the largest own peak plus W / 4): import 1.01 times the uncapped time, the emit stage 0.99 times, the preparation 1.07 times. 8 buckets and 1 bucket give the same manifest.
  • Germany did not run: the cloud container has 30 GB of disk. The two Germany bakes of "Done when" are open.
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