Repository navigation
Description
Status: designed
Part of #3227.
Depends on: #3302, #3305
TL;DR
Goal: A snap near an earlier snap of the same worker reads no road record again and projects the point only onto the roads whose box meets the snap window. The candidates of each snap stay the same.
Problem: On format 10, Region::snap decodes and projects each road of each level-1 cell that meets the snap window, on each call. A short request is 4 times slower than on the old engine (deleted by #3498), and the route catalog of the bake takes 184 to 290 s where it took about 105 s.
Decision: Each worker keeps a small cache of the decoded shapes of the last level-1 cells that it snapped in, with the box of each road (at most 4 MiB, the least recently used cell goes first). The snap tests the box of each road against the snap window before it projects the point onto the road. No format change.
Rejected:
- A box for each road in the geometry part (a format change). It adds 16 bytes to each of the 7.7 million directed roads of Switzerland (124 MB, 31 % of the 399 MB of road records) to each download, and a new bake. It helps only the first snap in an area, and that snap is already faster than on the old engine.
- A coarser index inside each level-1 cell (a format change): the same cost, and more format.
- A cache of the road boxes only, without the shapes. It is about 7 times smaller, but each snap decodes the roads near the point again: 1,000 to 2,400 roads for a 250 m snap in the four city centers of the table in Facts.
- The cache without the box test. A warm snap then still projects the point onto each road of the window: 4,700 to 10,150 roads for a 250 m snap in the four city centers of the table in Facts.
- One cache that all workers share. It needs a lock, and a worker no longer holds only its own memory.
- Accept the cost: the catalog stage stays 2 to 3 times slower, and the speed gate of Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 fails for the short requests.
Systems: routing
Contracts: none
Size: S (1 system, no contract change, no new dependency, about 250 changed lines)
Facts
Measured for pull request #3468 on Switzerland (4 cores, 15 GB RAM), the bake of routing-overlay at 67320e4 (download level 4). The request is the pinned request of 7.4 km of the table of #3305. Medians of 31 warm runs in one process, with the list of snaps of the router cleared before each run, in ms:
| old engine | new engine | |
|---|---|---|
touring, whole request |
1.73 | 7.07 |
mtb/technical, whole request |
1.05 | 9.22 |
| snap of the two points | 0.29 / 0.31 | 5.70 / 7.28 |
| search | 1.20 / 0.44 | 0.94 / 1.34 |
| unpacking | - | 0.11 / 0.14 |
| line | 0.20 / 0.25 | 0.30 / 0.40 |
- The two points decode 3,587 and 2,759 roads.
- With cold pages the old snap is slower: Route engine: the road search on format 10, and the test of the old engine against the new one #3303 measured 6.1 ms against 2.9 ms for each point, where each point was new to the process. So only repeated snaps in one area got slower.
- The route catalog of the bake (
planner/router-build/src/catalog/mod.rs) snaps along route relations: 148,190 snap calls take 488 s summed over 4 workers, 3.3 ms each, 69 % of its routing time.Stage catalogtakes 290.1 s inscratch-3311/run-afterand 106.9 s on the old engine inscratch-3311/run-before(both in/home/user/obc-bake). - A second cause is not in the snap, and this issue does not change it: with the snaps in the list of the router,
mtb/technicaltakes 0.65 ms on the old engine and 1.88 ms on the new one, because of the two open seed cells (rule O1 of Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305). Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 chooses the level sizes. - Long routes are not affected: the 273 km route takes 51 ms against 2,014 ms.
Found in the code and in the level 3 install switzerland/packages-l3/install:
-
Region::snapcollects the road IDs of each level-1 cell whose box meets the window, and of each long road whose box meets it, into aBTreeSet. It fails withError::Limitabove 100,000 roads. Then, for each road,snap::candidatesfinds the road's level-1 cell (Shared::place), checks the snap bit of the profile (Group::allowed), decodes the road (Geometry::road) and projects the point onto each segment (snap::project).snap::candidatessorts the result by distance, then by road ID. -
Regionis the handle of one worker. It already holds one decoded road (road: RefCell<Road>).Region::forkgives a new handle for another worker. The service forks a new handle after a panic (planner/service/src/lib.rs).Routerkeeps a list of the last 32 snaps by point and profile (router.rs), so it does not help a point that is near an earlier one but not the same. -
Rule 4 of the route package: an installed file never changes under its name, and a host opens a new
Regionafter an install that removed cells. So decoded shapes stay correct for the life of aRegion. -
The level 3 install has 9,210 level-1 cells. A level-1 cell holds 842 roads (median) and 1,500 at most, and 7.6 points for each road on average. Decoded at 12 bytes for each point and 20 bytes for each road (its box and the end of its points), a level-1 cell takes 77 KB (median), 166 KB (90 %) and 601 KB (the largest).
-
Roads in the level-1 cells that meet a snap window, and the roads among them whose box meets the window:
point radius level-1 cells roads box meets the window decoded size of the cells Zurich main station (47.378, 8.540) 250 m 12 10,150 2,356 0.65 MB Zurich main station 1 km 55 48,971 29,959 2.96 MB Bern (46.948, 7.447) 250 m 9 8,218 1,482 0.59 MB Lausanne (46.520, 6.630) 250 m 9 6,393 1,710 0.37 MB Lucerne (47.050, 8.300) 250 m 5 4,697 1,029 0.33 MB Alps (46.600, 8.000) 250 m 3 2,234 22 0.55 MB
Why the candidates stay the same
- The shapes. The cache holds the output of the same
decode_roadon the same bytes. The bytes never change while theRegionlives (rule 4). - The box test. The point that
snap::projectgives lies on a segment of the road, so it lies inside the box of the road (geometry::lerprounds between the two integer ends). When the box does not meet the window, that point is outside the window. The window is wider than the radius on each side, so the distance (Point::distance) is aboveradius_mandsnap::projectgives no candidate. This holds for each latitude up to 85° and each radius up to 5 km thatsnap::windowallows.Region::snapalready uses the same property when it skips a level-1 cell whose box does not meet the window (rule 5 of the route package). - The order. The result is sorted by distance, then by road ID, so the order in which the snap visits the roads does not change it. Each road is visited once. The catalog check of "Done when" tests the box test on the 148,190 snaps of real data; the new test of plan step 4 tests the cache.
- The errors. The first pass of the snap reads the same records as today, so
MissingRegionandError::Limitcome for the same requests. One difference, on damaged bytes only: a cache fill decodes each road of the cell, also a road that the profile cannot use, so a damaged record of such a road now givesInvalidData.
Memory
- Each
Regionholds at mostSNAP_CACHE_BYTES(4 MiB) of decoded shapes, or one level-1 cell when that cell alone is larger. It holds at most 256 level-1 cells, so a lookup is a short scan. The bytes of a cell are 12 for each point and 20 for each road, counted on the capacity of its lists. - 4 MiB holds the 55 level-1 cells of a 1 km snap at Zurich main station (2.96 MB), the widest window that a route request snaps with (
REACH_M). A probe of the alternatives (alternatives.rs) can snap with a window of up to 5 km. Its cells then push out the older cells, and the result does not change. - Service: each worker holds its search (at most 64 MiB) and its cache (at most 4 MiB), far below 1 GB.
- Phone and WebAssembly: the same
Regioncode, with no thread and no lock. One worker holds at most 4 MiB more. In WebAssembly the 4 MiB stay in the linear memory of the module once used. - A new
Region(openorfork) starts with an empty cache. So does the handle that the service forks after a panic.
Plan
- Create
planner/router/src/shapes.rs:pub(crate) const SNAP_CACHE_BYTES: usize = 4 << 20, the cacheShapesand the decoded cellCellShapes.CellShapesholdspoints: Vec<Point>(the shapes of all roads of the cell, one after the other) and, for each road, the end of its points and its box[i32; 4](west, south, east, north).CellShapes::road(k) -> (&[Point], [i32; 4]).Shapesis aVecDequeof((record, index), CellShapes), the least recently used cell first, and its byte total.Shapes::get(&mut self, key: (u32, u32), fill: impl FnOnce(&mut CellShapes) -> Result<()>) -> Result<&CellShapes>: a hit moves the cell to the back; a miss fills a new cell, keeps nothing whenfillfails, then drops cells from the front until the total and the count fit the bounds, but never the new cell. The key is the record of the download cell indirectory.binand the index of the level-1 cell in it. The byte total counts the capacity of the two lists of each cell, andgetshrinks the lists of a new cell to their length, so the bound is the memory that the cache holds. Addmod shapes;toplanner/router/src/lib.rs. - In
planner/router/src/snap.rs,projecttakes the shape (&[Point]) in place of&Road.candidatesbecomes two functions:check(policy: Policy) -> Result<()>(the policy check of today) andselect(found: Vec<Candidate>, policy: Policy) -> Candidates(the sort, the ambiguity and the truncation of today). - In
planner/router/src/region.rs,Regiongets the fieldshapes: RefCell<Shapes>, empty inopenandfork.Region::snaphas two passes:- The first pass reads what it reads today and lists each level-1 cell that meets the window (its
Cell, its index and its range of road IDs) and each long road whose box meets the window and that is not in a listed range. It givesMissingRegionas today. The road limit counts the same roads as today (the roads of the listed cells and the listed long roads) after each download cell. - Then
snap::check(policy). - The second pass takes each listed level-1 cell from
Shapes::get. Itsfilldecodes each road of the cell withGeometry::roadinto the road of the handle, and appends the shape and the box. Then the pass reads the group record of the cell once (Topology::level1,Group::level1). For each road whose box meets the window and whose snap bit is set (Group::allowed), it callssnap::project. Each listed long road goes the way of today:Shared::place,Group::allowed,Shared::road,snap::project. - Then
snap::select. - The module comment says that a
Regionkeeps the decoded shapes of the last level-1 cells that it snapped in, and still decodes nothing at open.
- The first pass reads what it reads today and lists each level-1 cell that meets the window (its
- Tests:
shapes.rs:the_cache_keeps_its_bounds_and_drops_the_least_recently_used_cell: a hit keeps a cell, a new cell pushes out the oldest, a cell above the bound stays alone, and a failed fill keeps nothing.planner/router-build/tests/engines.rs:a_snap_gives_the_same_candidates_cold_and_warm: for each point ofsnap_pointsand for both radii (250 m andREACH_M), the candidates of oneRegionthat snapped each earlier point are equal to those of a new fork (candidates, which compares the bits of each fraction and distance).
Files
planner/router/src/shapes.rs: create: the cache of decoded level-1 cells and its unit test.planner/router/src/lib.rs: change:mod shapes;.planner/router/src/snap.rs: change:projecttakes a shape;candidatesbecomescheckandselect.planner/router/src/region.rs: change: the cache field, the two passes ofsnap, the module comment.planner/router-build/tests/engines.rs: change: the cold and warm test.
Done when
-
./tools/obc test -p planner-routerand./tools/obc test -p planner-router-buildpass../tools/obc exec cargo clippy -p planner-router -p planner-router-build --all-targets -- -D warningspasses../tools/obc exec cargo check -p planner-router --target wasm32-unknown-unknownpasses.cargo fmt --all. -
The catalog, before and after, on the Switzerland bake (
/home/user/obc-bake, see its README: one bake on the baseline layers takes about 6 minutes, under the build lock, withLD_LIBRARY_PATHof~/.obc-geos-env.sh):cd /home/user/obc-bake && flock /home/user/obc-target/.build.lock python3 -I scratch-3311/bake_layers.py \ bin/obc-data-3471 switzerland/switzerland-bounds-sorted.osm.pbf switzerland/glo30 scratch-3311/run-3471 \ --layers switzerland/run-base/layers --download-level 3
route-catalog.jsoninresult.jsonhas the SHA-256 of the base of the pull request:06a90759…ofscratch-3311/run-afterwhen no routing code changed after7c1469fa8, else a bake of the base the same way. So the 148,190 snaps of the catalog give the same routes.Stage cataloginresult.jsontakes at most 130 s. This design chooses 130 s: about 20 % above the 106.9 s of the old engine (scratch-3311/run-before), against 290.1 s before this change. Buildbin/obc-data-3471as the README says (./tools/obc exec cargo build --release --locked -p obc-data-steps, then copyobc-data). -
The short request, before and after, on
switzerland/packages-l3/install: thepinnedrequest of 7.4 km of the table of Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3468, whichcompare switzerland/packages-l3/install 40 2 --new-only --max-km 12 --profiles touringdraws. Measure it as Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3468 did: 31 warm runs in one process, the list of snaps of the router cleared before each run and the cache of theRegionkept, with a timer that is not committed. Pass: the median of the snap of each point is at most 0.15 ms (the old engine: 0.29 ms for the two points), and the median of the whole request is at most 1.73 ms (the old engine). Also report the first snap of each point in the process: it must not be slower than before the change. -
The pull request lists
Requirements:asAGENTS.mdsays.
Open questions for the owner
- The bound of the cache on the phone. Each worker holds at most 4 MiB of decoded shapes, on the server, on the phone and in WebAssembly. A smaller bound on the phone needs a setting, such as the search limit (
Region::set_search_limit). Recommendation: one constant of 4 MiB for each host, because the phone has one worker and 4 MiB holds the widest snap of a route request in a city center. - The mark of the whole short request. Of the 1.73 ms of the old engine, the search, the unpacking and the line take 1.37 ms on the new engine, which this change does not touch. If the snap reaches its mark of 0.15 ms and the whole request is still above 1.73 ms, is the issue done? Recommendation: yes; the rest belongs to the level sizes of Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310.
Activity