Skip to content

Route engine: the road search on format 10, and the test of the old engine against the new one #3303

Closed

Description

@timohueser

Status: done

Part of #3227.
Depends on: #3302

TL;DR

Goal: The route engine answers each request on an install of format 10 with the route cost and the candidate roads of today's engine, and a worker holds only the labels and the queues of its search.
Problem: After #3302 the data of format 10 is there, but no search runs on it. Today's search needs the decoded graph. Each search resets a label directory that has one entry for each 512 road IDs of the package, which a phone area with sparse IDs pays in full. A queue entry has 32 bytes, because the landmark key needs 128 bits. No test compares two engines.
Decision:

Rejected:

  • Labels by cell: one block of labels for each level-1 cell that the search touches. A relaxation of a table of Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 then finds the level-1 cell of its target first, a binary search for each value. One label slot for each road ID, or today's blocks of 512 IDs. The IDs of a phone area are sparse, and a border road of an upper level takes a block of its own. A hash table by road ID has no array over the ID space and needs one probe.
  • The road ID and the label in two arrays. A probe then reads two places; one slot is one cache line.
  • Reverse turns kept across searches. After Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 a search enters at most 16 level-1 cells on its roads. To build them again costs less than a cache with a rule for dropping.
  • A cargo feature for the new engine. The comparison needs both engines in one binary.
  • A service that is generic over the engine. The service, the phone library and each example would then choose; one open chooses for all.
  • A tie that is checked by its turns only. A wrong cost column gives the same wrong sum twice; the old engine must cost the path.
  • The route catalog on the new engine now. It follows long lines, which are slow without tables.

Systems: routing
Contracts: none
Size: M (1 system, about 1,300 changed lines)
Branch: routing-overlay

Facts

The search rules

#3305 cites these rules. top_f and top_b are the least keys of the two queues.

  • S1. State and label. A state is a directed road, named by its run-time ID. Each side has at most one label for a road: cost (u64), parent (the road before it on that side; all-ones for a seed) and origin (the choice of its seed). A forward cost includes the road. A backward cost is the cost after the road.
  • S2. Arc. Road u has an arc to road v for each turn u → v in the block of the level-1 cell of u. Its weight is the road cost of v plus the turn cost, of the profile. All-ones in one of the two means no arc. A turn from or into a download cell that is not installed is no arc, on both sides (rule 2 of Route package format 10: the contract, the writer and the installer #3301). No weight is negative.
  • S3. Seeds. For each start seed, then each end seed, in list order: when (cost, choice) is less than the (cost, origin) of the label of its road (no label is all-ones), the label is set with no parent and the seed is pushed. An empty list on one side gives no path. A seed with a cost of all-ones or a road that is not installed is InvalidData.
  • S4. Queue. The key of an entry is its cost. An entry is stale when its (cost, origin) is not the label of its road.
  • S5. Round. best starts at the ceiling and roots at (255, 255). Each round removes the stale entries at the front of both queues. It stops when one queue is empty or top_f + top_b > best (a saturating sum; at equal the search goes on). Else it pops from the backward queue when top_b < top_f, else from the forward queue, runs the meeting test on the popped road and expands it.
  • S6. Meeting test of road r: when both sides have a label of r, joined = cost_f + cost_b. When (joined, origin_b, origin_f) < (best, roots), then best, roots and the meeting road change. The test runs at each pop and after each relaxation that set a label, not at the seeds.
  • S7. Expand. Forward, road r with cost c: each arc r → v relaxes v with c + weight. Backward: each arc u → r relaxes u with c + weight; this weight holds the cost of r. A relaxation of road x with next and the origin o of r does nothing when next > best or (next, o) ≥ the label of x. Else it sets the label with parent r, pushes the entry and runs the meeting test of x.
  • S8. Path. With no meeting road there is no path. Else the path is the forward parents from the meeting road back to a seed, reversed, and then the backward parents. source is the first start seed whose road, cost and choice are the label of the first road; target is the same for the last road and the end seeds. No such seed is InvalidData. The engine sums the path again: the two seed costs and each arc weight. A sum that is not best is InvalidData.
  • S9. Stops. At each 1,024 pops the search asks cancelled: Error::Cancelled. By the rule of Route service: request classes, the limit error as status 422, the probe radius #3308: a sum above 64 bits, a path of more than max_roads roads, or labels, queues and reverse turns above the search limit of the worker are Error::Limit, because the limit is one number for each request and no other worker changes it. An allocation that fails is Error::Memory.
  • S10. Result. The result is the least (cost, choice of the end seed, choice of the start seed) over all paths from a start seed to an end seed with a cost of at most the ceiling. Today's search gives the same triple. The leg program reads the triple and the roads. So equal triples give equal route costs and equal candidates. The order of pops at equal keys is free, so the roads can differ at equal cost.

Plan

  1. planner/router/src/overlay.rs (new) defines Seed, Query and Found (moved from search.rs, which imports them) and Stats { settled, peak_bytes }. planner/router/src/overlay/store.rs (new):
    • Labels: open addressing with linear probing over a power-of-two number of slots in one array. A slot is { cost: u64, id: u32, parent: u32, origin: u8 }, 24 bytes with its padding; an id of all-ones is empty. So a probe reads one cache line. The table doubles when more than half of the slots are used. reset gives a table of 1,024 slots: it clears the slots when the table has that size, else it frees the array and allocates a new one. So a search does no work that depends on the package.
    • Queue: today's monotone bucket queue with a u64 key, 65 buckets and the entry { cost: u64, road: u32, origin: u8 } of 16 bytes. A push below the last popped key is InvalidData.
  2. overlay.rs, Workspace (two Labels, two Queue, the entered cells) and search(shared, workspace, profile, query) by S1 to S10.
  3. planner/router/src/region.rs: Region gets the workspace and the search limit, and impl RoutingData for Region takes the data functions of Route engine: the data layer on format 10 and the host interface #3302 and adds search. default_budget is overlay::SEARCH_BYTES, 768 MiB (today's least budget; Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 lowers it). memory_budget is the search limit of S9, at most query.heap_bytes. stats() gives the Stats of the last search. search::Workspace keeps the pops of its last search, so the comparison has the settled labels of both engines.
  4. planner/router/src/open.rs (new, native): pub enum Opened { Pages(Selection<Files>), Cells(Region<Maps>) } implements RoutingData by delegation, and has fork, stats, verify (Pages: today's; Cells: nothing, the installer checked) and warm(profile) (Pages: prepared; Cells: nothing). open(path): a folder with manifest.json or blocks.json goes to directory::open, also when it holds directory.bin: until Follower: install format 10, and limits for memory maps #3307 the follower links each file of a release into routing/, and Route package format 10: the contract, the writer and the installer #3301 publishes routing/directory.bin. Each other folder is format 10: without directory.bin or without install.bin it is MissingRegion("The routing install in PATH is not complete"), else Region::open on Maps. lib.rs exports this open.
  5. planner/service/src/: Engine = Router<Opened>; http.rs calls warm in place of prepared. MAX_WORKERS, --verify and main.rs do not change: the service opens the folder of its argument. The catalog and the bake do not change.
  6. planner/router/src/compare.rs (new, public): the request set and the check, for the CI test and the example.
    • requests(router, profile, count, seed, max_m) -> Vec<Request>: a fixed xorshift draws points in the bounds; a point counts when it snaps as the router snaps (250 m, then REACH_M). Request i has kind i % 8, with a first spot A and later spots within max_m of A: (0) A to B, each at the projected point of its nearest candidate, so each point has the two directions of a road; (1) from the last shape point of the road of A to that of B, so each point has each road of a junction; (2) A, the junction of M, B; (3) A, M1, M2, B with turnarounds: [1]; (4) kind 0 with start_position and end_position set to the last candidate of each point; (5) the points at 0.25 and 0.75 of the road of A; (6) the same two points in reverse order; (7) kind 0 with alternatives: true, at most 40 km.
    • check(old, new, request) -> Result<Outcome, String>: both sides call routes with Control::default(). Two errors must be the same variant. Else, route by route: reason, cost, snap_truncated and the start and end position of each leg must be equal. When the pieces (road, from, to) are equal too, the two answers of answer::answer must be equal without package. When the pieces differ, it is a tie: old.cost(the new route, its profile) must be Some of its cost, which checks each turn and each cost of the new path on the old data; the later routes of the request are not compared. Outcome is Same or Tie.
    • planner/router/examples/compare.rs (Routing bake: the partition into nested cells, and the roads in cell order #3300): compare OLD NEW COUNT SEED [--max-km K] [--cold] [--no-announce]. Its request set becomes requests and its test check; it no longer skips a request with snap_truncated, because the two formats of one bake have the same road IDs. It opens both folders with open and a budget of usize::MAX, goes profile by profile, and prints for each request: profile, kind, straight km, and for each side the time, the settled labels and the nanoseconds for each settled label; for NEW also the peak bytes; the outcome. It also prints the time of snap for each side, over all points. --cold drops NEW, calls Maps::evict and opens NEW again before each request, and prints the major page faults (/proc/self/stat). The summary line and the exit codes of Routing bake: the partition into nested cells, and the roads in cell order #3300 stay. An install for it comes from cells install of Route package format 10: the contract, the writer and the installer #3301.
  7. Tests:
    • planner/router-build/tests/engines.rs (Route engine: the data layer on format 10 and the host interface #3302), the_engine_on_format_10_gives_the_costs_and_candidates_of_format_9: on town(), compare::requests with 40 requests for each of the 10 profiles, check on each: no difference, and at most 1 tie in 20 requests. Run time under 20 s.
    • engines.rs, an_install_of_some_cells_routes_on_its_roads: on the install of half of the download cells, a request between two points with installed windows gives a route on installed roads; its cost is that of the full install when the full route uses only installed roads, else it is higher or NoPath.
    • overlay/store.rs: labels_keep_each_road_through_growth_and_reset (with sparse IDs up to 2^32 − 2), and today's queue test with u64 keys.
    • planner/service/tests/http.rs, the_service_opens_an_install_of_format_10: /v1/region names the directory hash as package, one route answers 200, a folder with directory.bin and no install.bin does not open, and a format 9 folder that also holds directory.bin opens as format 9.
  8. planner/router/README.md: the modules overlay, open, compare, and which modules are the old engine.

What stays for #3311: search.rs, queue.rs, landmarks.rs, Selection and its budget, blocks.rs, package.rs, directory.rs, table.rs, storage.rs, the old parts of base.rs, Opened (then open gives Region<Maps>), MAX_WORKERS (#3308), and the catalog on format 9.

Files

  • planner/router/src/overlay.rs, overlay/store.rs, open.rs, compare.rs: create.
  • planner/router/src/region.rs: change: the workspace, the limit, the trait.
  • planner/router/src/search.rs: change: the moved types; the pop count.
  • planner/router/src/lib.rs: change: the modules, open.
  • planner/router/examples/compare.rs: change: the request set, the check, the columns.
  • planner/service/src/lib.rs, http.rs: change: Opened, warm. planner/service/tests/http.rs: change: one test.
  • planner/router-build/tests/engines.rs: change: two tests.
  • planner/router/README.md: change.

Done when

  • obc test -p planner-router, obc test -p planner-router-build and obc test -p planner-service pass, with obc exec cargo clippy -p <crate> --all-targets -- -D warnings for each. cargo check -p planner-router --target wasm32-unknown-unknown and --target aarch64-apple-ios pass. cargo fmt --all and obc suites check pass.
  • Gate of the epic (the old engine against the new one): the test engines in CI, and on the owner's PC (16 GB, 6 cores, release build, under nice) compare OLD NEW 48 1 --max-km 40 on the Switzerland bake of the branch (its format 9 package, and an install of its cells by cells install): 480 requests, no difference. The pull request records the number of ties and the run time (estimate: 5 to 10 minutes; a request with a via point runs one old search for each candidate of that point).
  • A difference in the candidates at equal route cost can be a tie-break of the old engine with landmarks, which only its unit test covers. The builder then gives the seeds of the leg (as leg_batch makes them, for a via point too) to RoutingData::search of both engines and compares (cost, choice of the end seed, choice of the start seed). When the new engine gives the lesser triple, the old engine misses S10: the builder reports the request to the owner and does not change the new engine to copy the old one. When the old engine gives the lesser triple, the new engine has a fault.
  • The pull request records, on the same machine and bake, for touring, with no gate:
    • 5 routes each near 10, 50, 150 and 250 km: for both engines the time, the settled labels and the nanoseconds for each settled label; for the new engine the peak search bytes. Without tables and landmarks the labels grow with the square of the distance (the prototype counted 4.9 to 6.1 million at 150 to 250 km), so several seconds and several hundred MB are expected on the long routes;
    • one 50 km route with --cold, with and without --no-announce: the time and the major page faults. The cold start of the service is a measurement of Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310;
    • the time of snap for each point, both engines.
  • The pull request has the line Requirements: and says that public docs did not change.

Out of scope

Built differently

Pull request #3466 built this design, into routing-overlay, with these changes:

  • The stats come from take_stats(): the counts of all searches since the last call, not stats() of the last search. A request with a via point or with alternatives runs more than one search, and compare prints the counts of the request.
  • open::cells(path, silent) is the one open of an install of format 10, with the check that the install is complete. open, the example compare and the test fixture call it. Opened allows the lint large_enum_variant until Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 removes Pages.
  • compare has the option --profile P and warms each profile of format 9 before its requests. Its summary line is N requests, D differences, T ties, in S s. With --cold it routes NEW once alone first and counts the time and the major page faults of that route only; the column "new ms" is then a second, warm route. requests stops after count * 100 tries and can return a shorter list.
  • Shared::junction gives the departure cell and the target number of a road; departures and the search use it. search::run_with_potential sets its pop count to 0 at its start.
  • Measured on Switzerland (4 cores, 15 GB RAM), on the bake of routing-overlay at 67320e4: compare OLD NEW 48 1 --max-km 40 gives 480 requests, 0 differences, 29 ties, in 576 s. Each tie has the same route cost, and the old data costs the new roads exactly. No request had a difference in its candidates. Over the 480 requests the new engine settles 435.5 million labels against 206.4 million. For touring, a label takes about 1,200 ns against about 500 ns, and a route of 130 to 230 km takes 4 to 8 s against 0.7 to 3 s. The largest search held 580 MB (the limit is 768 MiB). A snap takes 2.9 ms against 6.1 ms for each point.
  • Not measured: routes near 250 km (the longest straight line of the draws on Switzerland was 229 km); a real cold disk (the disk of the cloud container is virtual: a 52 km route takes 1.1 to 1.3 s cold and 1.3 s warm, with 280 major page faults); the gate on the owner's PC; a phone build on a Mac.
  • Review notes with no change: the CI test routes each request on the old engine a second time to count the routed requests. With --cold, "new ms" leaves out the snap time; Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 says so in the module comment of the example.

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