Closed
Description
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
endswrites the order key of each road (layout::keys, which takes the key function): au64, herelayout::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::finishthen 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_keyin place oflayout::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_ordercomputes 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::permutedandLists::permutedread 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::applysorts 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).Terraindecodes 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_BYTESwhen it is lower (work.rs#L12-L25).
Plan
layout.rs:spatial_key(point: Point) -> Result<u64, String>: the Morton key and the range check of today'sspatial_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).layout.rs:bounds(keys: &Column<u64>, buckets: usize) -> Vec<u64>:sort::sortedof a copy of the keys; the key at each multiple of ⌈R / K⌉, without repeats. The bucket of keykisbounds.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.layout.rs:Buckets::new(bounds: Vec<u64>);push(&mut self, road: &Road, key: u64)appends the road to theRoadsof 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::sortedof the key column gives the final order of the bucket,Roads::append_permutedadds it, and the bucket is dropped. The second result is the emit index of each final road.lib.rs:Roads::append_permuted(&mut self, bucket: &Roads, order: &[u32], terrain: …)extends each column ofselfwith the values ofbucketinorder. Without terrain the shapes are gathered too. With terrain it reserves the slots of the new shapes of the bucket (lengths fromterrain::pieces), visits the roads of the bucket by (GLO-30 square of the first point, fine cell), samples each withterrain::sampleand writes its shape,ascent_manddescent_minto its slot.Roads::permuteandLists::filledgo.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;piecesbecomes public;applygoes.step.rschanges the warnings afterfinishin today's order: it removes the line "No DEM applied…", adds the terrain line ofapply, then the credits ofTerrain::attribution.osm.rs:emittakeskeysandBuckets, pushes each road withkeys[i], and returns the finalRoads. 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.layout.rs:spatial_orderbecomesorder(graph: &mut Graph, terrain: …)for graphs that tests build in memory:spatial_keyof the last point of each road,bounds,Buckets, and the remap of the turn rules through the second result offinish. The bake does not call it.step.rs:Terrain::openbefore the import; walk 1,keys,bounds, walk 2,finishwith the heights; then the terrain is dropped andprepareruns.- 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 callsorderwith heights and keeps its check of the shape and heights of each road; its check of the visit order goes; the tests that calledspatial_ordercallorder.
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 intoBuckets.planner/router-build/src/lib.rs: change:Roads::append_permuted;permutegoes.planner/router-build/src/column.rs: change:Lists::filledgoes; slots of known lengths for one bucket.planner/router-build/src/terrain.rs: change:sample,pieces;applygoes.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
obc test -p planner-router-build,obc test -p planner-service, clippy on both with--all-targets -- -D warnings.- The Switzerland 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 terrain, profiles
all) gives the same SHA-256 ofmanifest.json,overlays.sqliteandroute-catalog.jsonas before the change. - In a cloud container with 4 cores and 15 GB of RAM, two Germany bakes up to the overlay index (the catalog and the blocks are left out):
- Uncapped: the pull request records the time, the own peak and the work folder peak W of each stage. The emit with the terrain takes at most 110 % of the terrain and the order before the change together; when it takes more, the pull request reports it to the owner before the merge.
- Capped: in a memory cgroup (for example
systemd-run --scope -p MemoryMax=…, or the limit of the container) of the largest own peak plus W / 4, withOBC_DATA_MEMORY_BYTES= W / 16, because the sort run does not read the cgroup before Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297. The pull request records the time of each stage against the uncapped bake. Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 gates the whole bake at twice the uncapped time. When a stage takes more than twice its uncapped time here, the pull request names the stage and the column that it reads at random, and the owner decides whether Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 or a new sub-issue takes it.
Out of scope
- The key function of the partition (
layout::partition_key): Routing bake: the partition into nested cells, and the roads in cell order #3300. The cgroup limit for the sort run and the bucket count: Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297. - One terrain sample for both directions of a road (bake.md finding 10): a geometry decision of Route package format 10: the contract, the writer and the installer #3301.
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::checktakes 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::pushtakes theRoadby value with itsRoadSource, and returns an error when the road count passesu32.- The import prints a stage line, "Sampling terrain and ordering the roads into K buckets".
terrain::resampled_lenis new andterrain::piecesstays private.planner/service/tests/http.rsdid 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.
Metadata
Metadata
Assignees
Labels
No labels
Activity