Skip to content

Route engine: the snap on format 10 decodes each road of its window on each request #3471

Open

Description

@timohueser

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

Found in the code and in the level 3 install switzerland/packages-l3/install:

  • Region::snap collects the road IDs of each level-1 cell whose box meets the window, and of each long road whose box meets it, into a BTreeSet. It fails with Error::Limit above 100,000 roads. Then, for each road, snap::candidates finds 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::candidates sorts the result by distance, then by road ID.

  • Region is the handle of one worker. It already holds one decoded road (road: RefCell<Road>). Region::fork gives a new handle for another worker. The service forks a new handle after a panic (planner/service/src/lib.rs). Router keeps 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 Region after an install that removed cells. So decoded shapes stay correct for the life of a Region.

  • 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_road on the same bytes. The bytes never change while the Region lives (rule 4).
  • The box test. The point that snap::project gives lies on a segment of the road, so it lies inside the box of the road (geometry::lerp rounds 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 above radius_m and snap::project gives no candidate. This holds for each latitude up to 85° and each radius up to 5 km that snap::window allows. Region::snap already 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 MissingRegion and Error::Limit come 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 gives InvalidData.

Memory

  • Each Region holds at most SNAP_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 Region code, 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 (open or fork) starts with an empty cache. So does the handle that the service forks after a panic.

Plan

  1. Create planner/router/src/shapes.rs: pub(crate) const SNAP_CACHE_BYTES: usize = 4 << 20, the cache Shapes and the decoded cell CellShapes. CellShapes holds points: 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]). Shapes is a VecDeque of ((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 when fill fails, 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 in directory.bin and the index of the level-1 cell in it. The byte total counts the capacity of the two lists of each cell, and get shrinks the lists of a new cell to their length, so the bound is the memory that the cache holds. Add mod shapes; to planner/router/src/lib.rs.
  2. In planner/router/src/snap.rs, project takes the shape (&[Point]) in place of &Road. candidates becomes two functions: check(policy: Policy) -> Result<()> (the policy check of today) and select(found: Vec<Candidate>, policy: Policy) -> Candidates (the sort, the ambiguity and the truncation of today).
  3. In planner/router/src/region.rs, Region gets the field shapes: RefCell<Shapes>, empty in open and fork. Region::snap has 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 gives MissingRegion as 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. Its fill decodes each road of the cell with Geometry::road into 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 calls snap::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 Region keeps the decoded shapes of the last level-1 cells that it snapped in, and still decodes nothing at open.
  4. 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 of snap_points and for both radii (250 m and REACH_M), the candidates of one Region that 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: project takes a shape; candidates becomes check and select.
  • planner/router/src/region.rs: change: the cache field, the two passes of snap, the module comment.
  • planner/router-build/tests/engines.rs: change: the cold and warm test.

Done when

  • ./tools/obc test -p planner-router and ./tools/obc test -p planner-router-build pass. ./tools/obc exec cargo clippy -p planner-router -p planner-router-build --all-targets -- -D warnings passes. ./tools/obc exec cargo check -p planner-router --target wasm32-unknown-unknown passes. 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, with LD_LIBRARY_PATH of ~/.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.json in result.json has the SHA-256 of the base of the pull request: 06a90759… of scratch-3311/run-after when no routing code changed after 7c1469fa8, else a bake of the base the same way. So the 148,190 snaps of the catalog give the same routes. Stage catalog in result.json takes 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. Build bin/obc-data-3471 as the README says (./tools/obc exec cargo build --release --locked -p obc-data-steps, then copy obc-data).

  • The short request, before and after, on switzerland/packages-l3/install: the pinned request 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, which compare switzerland/packages-l3/install 40 2 --new-only --max-km 12 --profiles touring draws. 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 the Region kept, 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: as AGENTS.md says.

Open questions for the owner

  1. 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.
  2. 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.
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