Skip to content

Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305

Closed

Description

@timohueser

Status: done

Part of #3227.
Depends on: #3303, #3304

TL;DR

Goal: The search crosses each closed cell in one step with its cost table, the router unpacks only the legs that its leg program chooses, and each route cost and each chosen candidate stays that of today's engine.
Problem: The engine of #3303 uses the roads of every cell, so its labels grow with the square of the distance: the prototype counted 4.9 to 6.1 million settled labels at 150 to 250 km, against about 3,900 with tables. Each inner leg runs one search for each candidate of its end point and builds the road path of each (router.rs#L294-L316); with tables, the unpacking of a path costs as much as its search (13.7 ms against 9.2 ms at 150 to 250 km in the prototype). max_geometry limits three different things. The prototype proved the open rule for one start road and one end road only, with no seed costs, no ceiling and no tie-break.
Decision:

  • Open rule. The seed cells are the level-1 cells of the roads of all seeds. A cell is closed when no seed cell lies in it and it has a table; else it is open (rules O1 to O4).
  • Closed step. A road whose junction lies in a closed cell takes the table of the highest closed cell: the forward side reads the row of the road, the backward side its column. All other rules of Route engine: the road search on format 10, and the test of the old engine against the new one #3303 stay (rules C1 to C5).
  • Exact by one argument. For one search the open rule fixes one graph, and both sides search it. Its costs between its roads are the costs on the roads (E1 to E5). The property test checks the same statement on random graphs.
  • Path of steps. A search returns its cost and its path as steps (road, level). The router unpacks the steps of the chosen legs after the leg program, level by level: before each level it announces all ranges of that level, then it replaces each step by a search inside its cell on the level below (U1 to U6).
  • Limits. max_geometry becomes max_points, max_roads and max_steps. The search limit of a worker goes from 768 MiB to 64 MiB.
  • Service and release. planner-service opens the folder of ROUTE_CELLS (Follower: install format 10, and limits for memory maps #3307) when the variable is set. A route answer then names the SHA-256 of directory.bin as its package, so the release and the route overlays name that identity from the same pull request on.

Rejected:

  • The stop at top_f + top_b ≥ best of the prototype. It ends before the tie-break between candidates is decided (S5, S6).
  • A map from each border road to its row and column (the prototype). The lists of Route package format 10: the contract, the writer and the installer #3301 are sorted, so one binary search for each settled road finds the place; a table value needs no lookup.
  • Open cells for each pair of a start and an end candidate. One search serves all candidates; the union of their cells is one rule.
  • Unpacking inside the search, or depth first (the prototype). The first unpacks paths that the leg program drops. The second reads the cells of a path one after the other from a cold disk.
  • One search for all candidates of an inner end point. It needs a stop rule and a tie-break of its own. The searches for each candidate are cheap now, and only the chosen one is unpacked.
  • A search from both ends inside a cell, or the path stored in the tables. The first needs reverse turns for each cell of the path; the second more table bytes. The pull request measures the unpacking first.
  • No second sum of the path. It is the one check that finds a table that does not fit its roads.

Systems: routing, obc-data, planner-map-baking
Contracts: specs/planner-release.md (routing_package), specs/route-api.md (package), specs/obc-data.md (the formats of the route service)
Size: L (the exactness of the engine; 2 systems; about 1,600 changed lines)
Branch: routing-overlay

Facts

The open rule

  • O1. Seed cells. The seed cells of a search are the level-1 cells of the roads of all its seeds (Seed::node), start and end, also of a seed that S3 does not push. The open junction is the arrival junction of Seed::node on both sides. A start seed is a candidate road, so that is the arrival junction of the start candidate. An end seed is a road from which a turn enters the end candidate, so that is the departure junction of the end candidate: the junction that the epic and the prototype name for the end. It is never the departure junction of Seed::node. Eight candidates on each side give at most 16 seed cells.
  • O2. Closed cell. A cell of level ℓ is closed, for one search and its profile, when (a) no seed cell lies in it, and (b) it has a table: its slot has more than 0 bytes, and for a level above the download level the upper cell is installed with its group part. Each other cell is open.
  • O3. Level of a junction. X is the level-1 cell of the junction. sep(X, S) is 0 when the two IDs are equal, else the level whose bit field holds the highest set bit of X xor S: the two cells are apart at each level up to sep and in one cell above it. m is the least sep(X, S) over the seed cells. L(X) is the highest level at or below m at which the cell of X has a table, or 0. So the cell of X at level L(X), named M(X), is closed, and each cell of X above it is open.
  • O4. Which junction. The forward side takes the arrival junction of the road: X is the level-1 cell of the road. The backward side takes the departure junction: X is the cell of the road when its index is at or after entering, else the cell that departure names. When that cell is not installed, the road has no arc on the backward side (S2).

A phone area that holds a cell above the download level only in part does not have that upper cell (rule 3 of #3301). By O2 (b) the cell is open, and the search uses the tables of its children that are installed. The roads of a child that is not installed do not exist on the phone (S2). The search reaches roads only in the level-1 cells that are seed cells.

The closed step

  • C1. In S7, the expansion of road r with cost c first takes ℓ = L(X) by O3 and O4. With ℓ = 0 it uses the turns, as in Route engine: the road search on format 10, and the test of the old engine against the new one #3303. Else it uses the table T of C = M(X) for the profile.
  • C2. Forward. r is an entering road of C. Its row p is its index in its level-1 cell for level 1, else its place in the entering list of C. Each column q with a finite T[p][q] relaxes the leaving road q of C with c + T[p][q]. A leaving road in a download cell that is not installed is skipped.
  • C3. Backward. r is a leaving road of C. Its column q is its place in the leaving list of C (for level 1 the leaving list of the block). Each row p with a finite T[p][q] relaxes the entering road p of C (for level 1 the road p of the cell) with c + T[p][q]. Table::column reads the copy by column when the table has one.
  • C4. A place is one binary search by (download cell ID, index), which is the order of the list. A road that is not in its list is InvalidData; E1 shows that correct data never gives it.
  • C5. Level of a label. The slot of a label keeps the level of the step that set it in one spare byte: 0 for a seed or a turn, else ℓ. S1 to S6, S9 and S10 do not change. The path of S8 becomes a list of steps (road, level), where the level is that of the step that leads to the road: from the forward label of the road, or from the backward label of the road before it. The second sum of S8 moves to U6.

Cost for each settled road: O3 (at most 16 xor), the record of C and the place (two binary searches), about 0.1 µs. Cost for each table value: one read, one sum, the run-time ID of the road reference (the last download cell is remembered) and one label probe.

Why the result is exact

  • E1. One graph. Fix one search. Two cells M(X) and M(Y) are equal or share no junction: of two nested closed cells only the larger can be an M. A road is inside when its two junctions lie in one cell M. The nodes of the overlay graph are the other roads. A node whose arrival junction has level 0 has its turns as arcs; each target departs at that junction, so it is a node. A node whose arrival junction lies in M departs outside M, so it is an entering road of M. Its arcs go to the leaving roads of M with the values of T; a leaving road arrives outside M, so it is a node. C2 and the turns give the arcs out of a node; C3 and the reverse turns give the same arcs into a node. Each seed road is a node, because each cell of its arrival junction is open (O1). So the two sides search one graph in its two directions, and each road with a label is a node.
  • E2. Equal costs. Each arc is the cost of a path of roads (T1), so no cost in the overlay graph is below the cost on the roads. Now take a path of roads between two nodes. After a node whose arrival junction has level 0, the next road is a node and the turn is an arc. After a node that enters M, the next roads are inside M up to the first road that arrives outside M; each turn of this part is at a junction of M, so T is at most its cost (T1). So the path splits into arcs with at most its cost. The costs between two nodes are equal in both graphs, for each start seed and each end seed.
  • E3. The loop. S3 to S7 are today's loop; the argument needs only that no weight is negative. Let P be a path with the least triple (D, b, a) of S10. On P the final forward label of each road is (the cost of P up to it, a) and the final backward label is (the cost of P after it, b); a lower pair gives a lower triple. S7 drops no road of P, because each of these costs is at most D ≤ best. At the stop, each road of P with a forward cost below top_f was popped forward with its final label, and the same holds backward with top_b. If a road x was not popped forward and a road y at or after x was not popped backward, then D ≥ top_f + top_b > best, which is false. So take the first road x that was not popped forward: the road before it set its final forward label (or x is a seed), and x was popped backward. If each road was popped forward, take the last road, which has its backward label from its seed. For that road, the later of its two final label sets, or its pop when both came from seeds, ran S6 with both final labels. So best = D and roots = (b, a).
  • E4. Ceiling. best starts at the ceiling. E3 holds for each D at or below it, and S6 takes a path of exactly the ceiling, because its roots are below (255, 255).
  • E5. Any set of closed cells. E1 and E2 need two facts only: each closed cell has a table by T1, and the arrival junction of each seed road lies in no closed cell. So O2 (b) and a partial area change the work and not the result. E3 and S10 give today's triple, because today's search is the same loop on the graph of the roads.
  • E6. Unpacking. U3 and U4 are the search of the bake for one row with a target, so they find a path of exactly the table value (T7).

Unpacking

  • U1. RoutingData::unpack(&mut self, metric: &str, legs: &[&Found], control: &Control) -> Result<Vec<Vec<u32>>> gives the roads of each leg. A step of level 0 is a turn. The default body, for Selection, copies the roads.
  • U2. Level by level. From the highest level of the steps of all legs down to 1: first one Host::announce with the spans that the steps of this level read (U5), then each step of this level becomes steps of the level below (U3, U4).
  • U3. Level 1. Step a → b in the level-1 cell C of a: a search of one side from a with cost 0 on the turns of C. It uses the forward labels and queue of the workspace, both cleared for each step, and S1, S4 and the forward relaxation of S7 with best = T[a][b] of C. It has no backward labels and no meeting test. A road of C is relaxed and expanded. A leaving road is relaxed only when it is b, and is not expanded. The search stops when b is popped. The cost of b must be T[a][b]; another cost, or an empty queue before b, is InvalidData. The new steps are the parents from b back to a, each with level 0.
  • U4. Level ℓ ≥ 2. Step a → b in C, the level-ℓ cell of the arrival junction of a: the same search on the tables of level ℓ − 1. A popped road y is an entering road of the child of C that holds its arrival junction. Each finite value of its row relaxes the leaving road z of that child when z is b or arrives in C. The search stops when b is popped; its cost must be T[a][b] of C. The new steps have level ℓ − 1.
  • U5. Spans. For a step of level ℓ ≥ 2: the two lists and the table of each child of its cell. For a step of level 1: the topology block and the group block of its level-1 cell. Region sorts the spans and gives each once. After the last level the router calls announce of Route engine: the data layer on format 10 and the host interface #3302 for the geometry, and line reads it.
  • U6. Limits and the second sum. More than Control::max_roads roads in the legs of one route is Error::Limit (a fixed limit, Route service: request classes, the limit error as status 422, the probe radius #3308). cancelled is asked at each step and at each 1,024 pops. For each leg, the sum of the weights of its turns must be Found::arcs (the cost of the search less its two seed costs), else InvalidData.

Plan

#3305 is one pull request with three code commits in this order, and one docs: commit. The tests of the first commit pass on it alone. The third commit must be in the same pull request as step 8: from that step on the service answers with the identity of the directory.

Commit 1: steps, the unpack call, the limits. No search rule changes.

  1. planner/router/src/overlay.rs: Found becomes { cost, arcs, path: Vec<Step>, source, target } with Step { road: u32, level: u8 }; Query::max_roads becomes max_steps. Region::search and Selection::search give steps of level 0. planner/router/src/data.rs: RoutingData::unpack (U1) with its default body, which copies the roads and applies U6.
  2. planner/router/src/router.rs:
    • Control: max_geometry goes. max_points (250,000) limits the points of an answer. max_roads (250,000) limits the roads of the chosen legs of one route. max_steps (250,000) limits the steps of the path of one search. Each is Error::Limit. The values are today's, so a request fails only where it fails today; the paths of candidates that the leg program drops no longer count. Work::witnesses goes.
    • Choice holds a leg as the slice of one road (two points on one road) or as a Found. The leg program stores it for each end candidate. After it has chosen the candidates, one call of unpack takes the Found of each chosen leg. Then the code that leg_batch has today makes the slices of each leg: the first road starts at the fraction of its start candidate, the road of the end candidate is added up to its fraction, and an empty slice goes.
  3. planner/router-build/tests/engines.rs: its tests of Route engine: the data layer on format 10 and the host interface #3302 and Route engine: the road search on format 10, and the test of the old engine against the new one #3303 pass. New only_the_chosen_legs_are_unpacked: a request through a junction with several candidates runs more searches than legs, and Stats counts the unpacking of two legs.

Commit 2: the open rule, the closed step, the unpacking.

  1. planner/router/src/region.rs: closed(x: u32, level: u8, profile) -> Result<Option<Closed>> gives the two lists and the table of the cell of level-1 cell x at a level, or none when it has no table (O2 b). Level 1: the level-1 record and Group::table(profile, its index). Level 2 to the download level: the upper record with that level and ID in the topology part of the download cell (a binary search), and the slot after the level-1 slots. Above the download level: the directory record of the upper cell (a binary search by level and ID), when install.bin names it, and its two parts.
  2. planner/router/src/overlay.rs: the seed cells (O1) at the start of search; level(side, road) (O3, O4); expand by C1 to C3; the level byte of Labels (C5). Stats gets the settled labels of each level, the table values read, the roads and the settled labels of the unpacking, and on native targets the time of the search and of the unpacking.
  3. planner/router/src/overlay/unpack.rs (new): U2 to U6 for Region.
  4. overlay.rs: SEARCH_BYTES is 64 MiB: several times the labels that the epic expects for a worker (under 10 MB), so only a defect reaches it.
  5. planner/service/src/main.rs: when ROUTE_CELLS is set, the service opens that folder, and fails at its start when it does not open; else it opens the folder of its argument. --formats prints one more entry, "planner/routing-cells": 10 (cells::FORMAT), beside planner/routing. The follower reads the answer as a map of layer and format (services.rs#L58-L71); no layer has this name, so its check of a release ignores the entry, and Follower: install format 10, and limits for memory maps #3307 sets RLIMIT_DATA of the route service only when it finds it. planner/service/README.md: the variable and the entry. From here on a follower of the branch serves format 10.
  6. planner/router/src/compare.rs and examples/compare.rs: the columns of the new Stats. The rules of check do not change.
  7. Tests. Each fixture calls tables::build of Routing bake: the cost tables of each profile for each cell #3304 with a threshold of 16 bytes for the column copy, so that some tables have one and C3 reads it.
    • engines.rs: the fixture town() gets its tables before cells::write, so each test runs with tables; the partial install then has upper cells that are open. The request set gets two more requests, between the two end junctions of the long road in both orders. The long road is a candidate at both points, so its cost is the ceiling of the search, and the other candidates are searched under it across closed cells. For at least one profile the answer must be the long road alone, so the ceiling held, while Stats shows a settled label of a level above 0. For each kind 2, 3 and 4 (via point, turnaround, pin), Stats must show such a label in at least one request. Else the test fails.
    • planner/router-build/tests/overlay.rs (new), the_search_gives_the_least_cost_and_candidates_on_random_graphs: 24 graphs from a fixed xorshift, each with 150 to 300 junctions at random points, roads to 2 to 4 near junctions in one or both directions, and one island. Routing bake: the partition into nested cells, and the roads in cell order #3300's layout::order with sizes [4, 16, 64] and download level 2, so level 3 has upper cells; a graph with fewer than 3 cells of level 3 is drawn again. Two profiles of synthetic columns: road costs 1 to 8 (so many paths have equal costs), some roads excluded, turn costs 0 to 3, some turns forbidden. Then two installs: all cells; and each download cell of one upper cell plus about half of the download cells of the next upper cell, so one upper cell is complete and closed and one is partial and open.
      For each install and profile, 40 calls of RoutingData::search: 1 to 4 start seeds and 1 to 4 end seeds on installed roads, costs 0 to 20, each with its own choice. Among them: a start seed and an end seed on one road; all seeds in one level-1 cell; a start seed, and in another call an end seed, on a border road of the top level whose departure cell is no seed cell (the end seed then gets its forward label from a table and expands backward by a column); a ceiling of none, of the true cost and of the true cost less 1. In the partial install, one call has its seeds on two sides of the complete upper cell, and one on two sides of a download cell of the partial upper cell.
      The oracle relaxes the arcs of the installed roads (S2, read through the views, no table) to a fixed point and gives the least (cost, end choice, start choice) at or below the ceiling. The search must give the same triple, or none when the oracle gives none. unpack must give roads from the road of the start seed to the road of the end seed, each pair a turn, with the sum of U6. For each install, the test fails when no path has a step of each level; for the partial install, also when no path has a step of level 3 in the complete upper cell or no step of level 2 in the partial one. Run time under 15 s.
  8. planner/router/README.md: the open rule in two sentences and the module overlay/unpack.

Commit 3: the release and the overlays name the identity of the directory.

  1. planner/router-build/src/step.rs: overlays::write gets the lower-case hex SHA-256 of directory.bin of this bake as its package, in place of package::digest(&manifest). cells::write runs before the overlay index; where the step has another order, the overlay index moves after it. overlays.rs does not change.
  2. tools/planner_grid_index.py, compose: routing_package of the release is files["routing/directory.bin"]["sha256"] (the file of the index of kind routing-cells; its transport is identity, so the hash is that of the bytes). The overlay check compares info["routing_package"] with the same hash. Region, bounds, OSM hash and profiles still come from graph; Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 moves them.
  3. tools/planner_grid_maps.py, the overlays: read index.json of planner/routing/cells/grid; fail when metadata["routing_package"] is not files["routing/directory.bin"]["sha256"] of that index; keep the value. host/obc-data-steps/src/planner.rs: the step planner/overlays/grid gets layer_files("planner/routing/cells/grid", &["index.json"]) in place of the index of planner/routing/grid; PLANNER_ROUTING.revision goes up by one, because the overlay index changes.
  4. tools/planner_verify.py: the identity check compares document['routing_package'] with runtime.digest(output / 'routing/directory.bin'). The comparison of routing/blocks.json with graph and the loop over the cell descriptors stay until Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311.
  5. Tests: tools/tests/test_planner_grid_index.py and the overlay fixture of tools/tests/test_planner_grid_maps.py take the hash of routing/directory.bin. host/obc-data-steps/tests/planner_build.rs: routing_package of the release and of maps/overlays.json are the SHA-256 of routing/directory.bin.

Commit docs:.

  1. specs/planner-release.md: the manifest row routing_package is "SHA-256 of routing/directory.bin, the identity of the route package". In the paragraph on overlays.pmtiles, the metadata routing_package is that identity, and the sentence on routing/blocks.json of a grid release goes. specs/route-api.md: package in the answer table and in the table of GET /v1/region is "The SHA-256 of directory.bin of the route package". specs/obc-data.md, Serve: planner-service --formats gives planner/routing and planner/routing-cells.

Alternatives on the overlay: the method does not change. The route with BASE/less-climbing uses the tables of that profile (T4). A probe route is a request of three points. What changes: each of the about 15 searches settles thousands of labels, not millions. What does not: each candidate route is unpacked and gets its line, and accept costs a route of another profile with endpoint for each piece. So an alternatives request costs about the unpacking and the line of the primary route for each candidate, at most 6 times.

#3305 deletes on the branch: max_geometry and Work::witnesses. The road expansion of #3303 stays as the step of an open cell. What stays for #3311: the old engine and Opened, as #3303 lists.

Files

  • planner/router/src/region.rs, overlay.rs, overlay/store.rs: change: closed; the open rule, the closed step, steps; the level byte.
  • planner/router/src/overlay/unpack.rs: create.
  • planner/router/src/data.rs, search.rs: change: unpack; steps of level 0.
  • planner/router/src/router.rs: change: the three limits; the legs unpacked after the leg program.
  • planner/router/src/compare.rs, planner/router/examples/compare.rs: change: the columns.
  • planner/service/src/main.rs, planner/service/README.md: change: ROUTE_CELLS; the entry planner/routing-cells of --formats.
  • planner/router-build/tests/engines.rs: change. planner/router-build/tests/overlay.rs: create.
  • planner/router/README.md: change.
  • planner/router-build/src/step.rs: change: the package of the overlay index.
  • tools/planner_grid_index.py, tools/planner_grid_maps.py, tools/planner_verify.py: change: routing_package.
  • host/obc-data-steps/src/planner.rs: change: the input of the overlay grid step, the revision.
  • tools/tests/test_planner_grid_index.py, tools/tests/test_planner_grid_maps.py, host/obc-data-steps/tests/planner_build.rs: change.
  • specs/planner-release.md, specs/route-api.md, specs/obc-data.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 tests engines and overlay in CI. On the owner's PC (16 GB, 6 cores, release build, under nice), on the Switzerland bake of the branch with the tables of Routing bake: the cost tables of each profile for each cell #3304: compare OLD NEW 24 1 --max-km 300, 240 requests, no difference. The old engine sets the run time: a request with a via point runs one old search for each candidate of that point, so the estimate is 10 to 20 minutes. The pull request records the time and the number of ties.
  • A difference in the candidates at equal route cost can be a tie-break of the old engine with landmarks. The builder checks it as Route engine: the road search on format 10, and the test of the old engine against the new one #3303 says: the same seeds to RoutingData::search of both engines. When the new engine gives the lesser triple of S10, the builder reports the request to the owner and does not change the new engine.
  • The pull request records for Switzerland, for touring and mtb/technical, 5 routes each near 10, 50, 150 and 250 km: the time of the old engine (one profile at a time, budget usize::MAX, so it holds each tested profile); for the new engine the time of the search and of the unpacking, the settled labels by level, the table values read, the roads, the time of the whole request, and the peak search bytes. The peak search bytes are the own memory of a worker for a request; the memory of the service process is a measurement of Follower: install format 10, and limits for memory maps #3307 and Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310.
  • In the cloud container of Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 (4 cores, 15 GB of RAM), on the Germany bake of Routing bake: the cost tables of each profile for each cell #3304's pull request (or one new bake): the same table for touring with 3 routes each near 10, 50, 150, 300, 600 and 900 km, and compare OLD NEW 8 1 --max-km 300 for all profiles (80 requests, one of each kind, about 15 minutes) with no difference.
  • Cold files: the longest route of Switzerland and of Germany with --cold, with and without --no-announce: the time and the major page faults.
  • The speed gate, which Route engine: the road search on format 10, and the test of the old engine against the new one #3303 does not have: on Switzerland no route of the table takes longer on the new engine than on the old one. The builder also reports to the owner before the merge when: the longest Germany route takes more than 1 s with warm files (the gate of Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310); the unpacking takes more than 3 times the search on that route (then a smaller level 1 or a search from both ends, as the epic names them, is a follow-up); or a search holds more than 16 MiB.
  • planner-service --formats prints {"planner/routing":9,"planner/routing-cells":10}; a test in planner/service/tests/http.rs or of main.rs asserts the two entries.
  • obc test -p obc-data-steps and obc test affected --base origin/routing-overlay (it runs the tests of tools/) pass. python3 docs/build_docs.py --check-links passes.
  • On the owner's PC, obc data update local and obc data serve local on the branch: a route through the local follower has package equal to routing_package of the release and of maps/overlays.json, and the web planner shows the route overlays for that route.
  • The phone: the tests of OBCKit pass in CI, as companion-ios/README.md says. The owner checks in the app, against the local follower, that an online route is accepted.
  • The pull request has the line Requirements: and says that public docs changed, in their own docs: commit.

Out of scope

Built differently

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

  • Five code commits and two docs: commits, not three and one: the plan steps were pushed one after the other, and the review fixes followed.
  • The default unpack has no second sum (U6). The old engine keeps the second sum in its search, as before; the overlay engine sums again in its unpacking.
  • Costs::of_columns in planner-router-build builds the cost columns of the property test. routing-cells is a mandatory index in tools/planner_grid_index.py. tools/planner_verify.py hashes routing/directory.bin only when the release check gives it one that changed. tools/tests/test_planner_grid_maps.py had no overlay fixture; it has one test now.
  • The property test bakes each second graph with four levels (sizes 4, 16, 64, 128 and download level 3), so CI runs the code of a level between 2 and the download level. Its host records each announce: each list, table and block that the unpacking reads must be announced before. The review found that the unpacking announced almost nothing for a step of a level from 2 to below the download level; that is fixed.
  • Measured on Switzerland (4 cores, 15 GB RAM), on the bake of routing-overlay at 67320e4: compare OLD NEW 24 1 --max-km 300 gives 240 requests, 0 differences, 49 ties, in 358 s. The table runs add 320 requests with 0 differences. Each tie has the same cost, and the old data costs the new roads. The longest route (273 km, touring) takes 51 ms (search 8.7 ms, unpacking 27.5 ms) against 2,014 ms; the slowest row (236 km) takes 81 ms against 1,907 ms. The largest search held 615 KB. Cold, the 273 km route takes 105 to 125 ms with 216 major page faults, and 119 to 159 ms with 577 faults without the announce (the disk of the cloud container is virtual).
  • The bake: manifest.json, route-catalog.json and the identity of format 10 do not change. overlays.sqlite changes: its package is the SHA-256 of cells/directory.bin.
  • The speed gate is missed on short routes. The pinned request of 7.4 km takes 7.1 ms against 1.7 ms (touring) and 9.2 ms against 1.1 ms (mtb/technical), medians of 31 warm runs. Two causes, both outside this issue. Region::snap of Route engine: the data layer on format 10 and the host interface #3302 decodes each road of each level-1 cell of the snap window on each request (5.7 to 7.3 ms for the two points; the old engine keeps its decoded pages and needs 0.3 ms). And the two seed cells are open, so the search has a floor of about 1 ms in cells of up to 512 junctions (the level sizes are with Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310). The owner decides on a follow-up for the snap.
  • The unpacking takes 3.2 times the search on the longest touring route (2.6 times for mtb/technical), above the mark of 3. The follow-up that the epic names (a smaller level 1, or a search from both ends) is open for the owner.
  • Open, for the owner: each Germany point of "Done when" (the commands are under "Owner steps" in the pull request), obc data update local and obc data serve local with the web planner, the phone against the local follower, the xcodebuild suites.
  • Review notes with no change: no CI fixture has a step two levels above the download level, so the announce of the children that are upper cells runs only on a real region. The sizes of the four-level graphs end at 128, not 256, because a graph of 150 to 300 junctions gives one cell of 256.

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