Repository navigation
Description
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_geometrybecomesmax_points,max_roadsandmax_steps. The search limit of a worker goes from 768 MiB to 64 MiB. - Service and release.
planner-serviceopens the folder ofROUTE_CELLS(Follower: install format 10, and limits for memory maps #3307) when the variable is set. A route answer then names the SHA-256 ofdirectory.binas itspackage, so the release and the route overlays name that identity from the same pull request on.
Rejected:
- The stop at
top_f + top_b ≥ bestof 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
- Route engine: the road search on format 10, and the test of the old engine against the new one #3303: the rules S1 to S10;
overlay::expandis the one place where a road is expanded; a label slot of 24 bytes has spare bytes; the reverse turns of a level-1 cell. Route engine: the data layer on format 10 and the host interface #3302:Regionfinds the level-1 record of a road and the run-time ID of a road reference;Host::announce. - Routing bake: the cost tables of each profile for each cell #3304: the rules T1 to T7. A table value is the least cost from an entering road to a leaving road over turns in the cell; it holds the cost of the leaving road and not that of the entering road (T1). Each cell with a written slot has a table (T4).
cells::Tablegivesrowandcolumn; a table above 16 KiB also holds its values by column (T5). The search of the bake inside a cell, with a target, finds each value again (T7). - Route package format 10: the contract, the writer and the installer #3301: the entering and the leaving list of a cell are sorted by run-time ID; the place of a road is its row or column; for level 1 the row is the index of the road in its cell. A slot of 0 bytes, or an upper cell that is not installed, means no table (rule 3).
departurenames the level-1 cell of the departure junction of an entering road. - Routing bake: the partition into nested cells, and the roads in cell order #3300: a level-1 cell ID holds one bit field for each level, the top level in the highest bits. A road is in the cell of its arrival junction. The children of a cell are one range of cells of the level below.
- The prototype takes the level of a road from its arrival junction on the forward side and from its departure junction on the backward side (prototype_mld.rs#L483-L493, #L537, #L566), stops at
≥ best(#L517), reads a column with a stride (#L588) and unpacks depth first (#L624-L655). - The end seeds of a candidate road are the roads from which a turn enters it (router.rs#L485-L496). Each of them arrives at the departure junction of the candidate.
max_geometrylimits the roads of all candidate searches of a request (router.rs#L307-L310), the points of an answer (#L408) and the roads of one path (#L525).leg_batchmakes the road slices of each found path (#L538-L543).- The alternatives are one route with the profile
BASE/less-climbingand up to four routes through a probe point (alternatives.rs#L37-L118);acceptcosts a route of another profile again withendpointfor each piece (#L163-L189). - The phone accepts an online route only when its
packageis therouting_packageof the release (PlannerService.swift#L448). The web planner hides the route overlays when theirrouting_packageis not thepackageof the latest route (route-overlays.ts#L171-L179). Today the bake gives the overlay index the hash of the format 9 manifest (step.rs#L88), the overlay grid step replaces it by the hash ofrouting/blocks.json(planner_grid_maps.py#L164-L168), the release takes the same hash (planner_grid_index.py#L83, #L92-L94), and the verify step compares it (planner_verify.py#L229-L231). The engine of format 10 names the SHA-256 ofdirectory.bin(rule 1 of Route package format 10: the contract, the writer and the installer #3301). - The epic: a leg of 2,000 km crosses about 2,900 level-1 cells and 38,000 roads.
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 ofSeed::nodeon 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 ofSeed::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.
Xis 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 ofX xor S: the two cells are apart at each level up tosepand in one cell above it.mis the leastsep(X, S)over the seed cells.L(X)is the highest level at or belowmat which the cell ofXhas a table, or 0. So the cell ofXat levelL(X), namedM(X), is closed, and each cell ofXabove it is open. - O4. Which junction. The forward side takes the arrival junction of the road:
Xis the level-1 cell of the road. The backward side takes the departure junction:Xis the cell of the road when its index is at or afterentering, else the cell thatdeparturenames. 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
rwith costcfirst takesℓ = L(X)by O3 and O4. Withℓ = 0it 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 tableTofC = M(X)for the profile. - C2. Forward.
ris an entering road ofC. Its rowpis its index in its level-1 cell for level 1, else its place in the entering list ofC. Each columnqwith a finiteT[p][q]relaxes the leaving roadqofCwithc + T[p][q]. A leaving road in a download cell that is not installed is skipped. - C3. Backward.
ris a leaving road ofC. Its columnqis its place in the leaving list ofC(for level 1 theleavinglist of the block). Each rowpwith a finiteT[p][q]relaxes the entering roadpofC(for level 1 the roadpof the cell) withc + T[p][q].Table::columnreads 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)andM(Y)are equal or share no junction: of two nested closed cells only the larger can be anM. A road is inside when its two junctions lie in one cellM. 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 inMdeparts outsideM, so it is an entering road ofM. Its arcs go to the leaving roads ofMwith the values ofT; a leaving road arrives outsideM, 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 insideMup to the first road that arrives outsideM; each turn of this part is at a junction ofM, soTis 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
Pbe a path with the least triple(D, b, a)of S10. OnPthe final forward label of each road is (the cost ofPup to it,a) and the final backward label is (the cost ofPafter it,b); a lower pair gives a lower triple. S7 drops no road ofP, because each of these costs is at mostD ≤ best. At the stop, each road ofPwith a forward cost belowtop_fwas popped forward with its final label, and the same holds backward withtop_b. If a roadxwas not popped forward and a roadyat or afterxwas not popped backward, thenD ≥ top_f + top_b > best, which is false. So take the first roadxthat was not popped forward: the road before it set its final forward label (orxis a seed), andxwas 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. Sobest = Dandroots = (b, a). - E4. Ceiling.
beststarts at the ceiling. E3 holds for eachDat 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, forSelection, copies the roads. - U2. Level by level. From the highest level of the steps of all legs down to 1: first one
Host::announcewith 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 → bin the level-1 cellCofa: a search of one side fromawith cost 0 on the turns ofC. It uses the forward labels and queue of the workspace, both cleared for each step, and S1, S4 and the forward relaxation of S7 withbest=T[a][b]ofC. It has no backward labels and no meeting test. A road ofCis relaxed and expanded. A leaving road is relaxed only when it isb, and is not expanded. The search stops whenbis popped. The cost ofbmust beT[a][b]; another cost, or an empty queue beforeb, isInvalidData. The new steps are the parents frombback toa, each with level 0. - U4. Level ℓ ≥ 2. Step
a → binC, the level-ℓ cell of the arrival junction ofa: the same search on the tables of level ℓ − 1. A popped roadyis an entering road of the child ofCthat holds its arrival junction. Each finite value of its row relaxes the leaving roadzof that child whenzisbor arrives inC. The search stops whenbis popped; its cost must beT[a][b]ofC. 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.
Regionsorts the spans and gives each once. After the last level the router callsannounceof Route engine: the data layer on format 10 and the host interface #3302 for the geometry, andlinereads it. - U6. Limits and the second sum. More than
Control::max_roadsroads in the legs of one route isError::Limit(a fixed limit, Route service: request classes, the limit error as status 422, the probe radius #3308).cancelledis asked at each step and at each 1,024 pops. For each leg, the sum of the weights of its turns must beFound::arcs(the cost of the search less its two seed costs), elseInvalidData.
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.
planner/router/src/overlay.rs:Foundbecomes{ cost, arcs, path: Vec<Step>, source, target }withStep { road: u32, level: u8 };Query::max_roadsbecomesmax_steps.Region::searchandSelection::searchgive steps of level 0.planner/router/src/data.rs:RoutingData::unpack(U1) with its default body, which copies the roads and applies U6.planner/router/src/router.rs:Control:max_geometrygoes.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 isError::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::witnessesgoes.Choiceholds a leg as the slice of one road (two points on one road) or as aFound. The leg program stores it for each end candidate. After it has chosen the candidates, one call ofunpacktakes theFoundof each chosen leg. Then the code thatleg_batchhas 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.
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. Newonly_the_chosen_legs_are_unpacked: a request through a junction with several candidates runs more searches than legs, andStatscounts the unpacking of two legs.
Commit 2: the open rule, the closed step, the unpacking.
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 cellxat a level, or none when it has no table (O2 b). Level 1: the level-1 record andGroup::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), wheninstall.binnames it, and its two parts.planner/router/src/overlay.rs: the seed cells (O1) at the start ofsearch;level(side, road)(O3, O4);expandby C1 to C3; the level byte ofLabels(C5).Statsgets 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.planner/router/src/overlay/unpack.rs(new): U2 to U6 forRegion.overlay.rs:SEARCH_BYTESis 64 MiB: several times the labels that the epic expects for a worker (under 10 MB), so only a defect reaches it.planner/service/src/main.rs: whenROUTE_CELLSis set, the service opens that folder, and fails at its start when it does not open; else it opens the folder of its argument.--formatsprints one more entry,"planner/routing-cells": 10(cells::FORMAT), besideplanner/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 setsRLIMIT_DATAof 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.planner/router/src/compare.rsandexamples/compare.rs: the columns of the newStats. The rules ofcheckdo not change.- Tests. Each fixture calls
tables::buildof 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 fixturetown()gets its tables beforecells::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, whileStatsshows a settled label of a level above 0. For each kind 2, 3 and 4 (via point, turnaround, pin),Statsmust 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'slayout::orderwith 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 ofRoutingData::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.unpackmust 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.
planner/router/README.md: the open rule in two sentences and the moduleoverlay/unpack.
Commit 3: the release and the overlays name the identity of the directory.
planner/router-build/src/step.rs:overlays::writegets the lower-case hex SHA-256 ofdirectory.binof this bake as its package, in place ofpackage::digest(&manifest).cells::writeruns before the overlay index; where the step has another order, the overlay index moves after it.overlays.rsdoes not change.tools/planner_grid_index.py,compose:routing_packageof the release isfiles["routing/directory.bin"]["sha256"](the file of the index of kindrouting-cells; its transport isidentity, so the hash is that of the bytes). The overlay check comparesinfo["routing_package"]with the same hash. Region, bounds, OSM hash and profiles still come fromgraph; Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 moves them.tools/planner_grid_maps.py, the overlays: readindex.jsonofplanner/routing/cells/grid; fail whenmetadata["routing_package"]is notfiles["routing/directory.bin"]["sha256"]of that index; keep the value.host/obc-data-steps/src/planner.rs: the stepplanner/overlays/gridgetslayer_files("planner/routing/cells/grid", &["index.json"])in place of the index ofplanner/routing/grid;PLANNER_ROUTING.revisiongoes up by one, because the overlay index changes.tools/planner_verify.py: the identity check comparesdocument['routing_package']withruntime.digest(output / 'routing/directory.bin'). The comparison ofrouting/blocks.jsonwithgraphand 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.- Tests:
tools/tests/test_planner_grid_index.pyand the overlay fixture oftools/tests/test_planner_grid_maps.pytake the hash ofrouting/directory.bin.host/obc-data-steps/tests/planner_build.rs:routing_packageof the release and ofmaps/overlays.jsonare the SHA-256 ofrouting/directory.bin.
Commit docs:.
specs/planner-release.md: the manifest rowrouting_packageis "SHA-256 ofrouting/directory.bin, the identity of the route package". In the paragraph onoverlays.pmtiles, the metadatarouting_packageis that identity, and the sentence onrouting/blocks.jsonof a grid release goes.specs/route-api.md:packagein the answer table and in the table ofGET /v1/regionis "The SHA-256 ofdirectory.binof the route package".specs/obc-data.md, Serve:planner-service --formatsgivesplanner/routingandplanner/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 entryplanner/routing-cellsof--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-buildandobc test -p planner-servicepass, withobc exec cargo clippy -p <crate> --all-targets -- -D warningsfor each.cargo check -p planner-router --target wasm32-unknown-unknownand--target aarch64-apple-iospass.cargo fmt --allandobc suites checkpass.- Gate of the epic: the tests
enginesandoverlayin CI. On the owner's PC (16 GB, 6 cores, release build, undernice), 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::searchof 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
touringandmtb/technical, 5 routes each near 10, 50, 150 and 250 km: the time of the old engine (one profile at a time, budgetusize::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
touringwith 3 routes each near 10, 50, 150, 300, 600 and 900 km, andcompare OLD NEW 8 1 --max-km 300for 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 --formatsprints{"planner/routing":9,"planner/routing-cells":10}; a test inplanner/service/tests/http.rsor ofmain.rsasserts the two entries.obc test -p obc-data-stepsandobc test affected --base origin/routing-overlay(it runs the tests oftools/) pass.python3 docs/build_docs.py --check-linkspasses.- On the owner's PC,
obc data update localandobc data serve localon the branch: a route through the local follower haspackageequal torouting_packageof the release and ofmaps/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.mdsays. 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 owndocs:commit.
Out of scope
- The table bytes and their bake: Routing bake: the cost tables of each profile for each cell #3304. The level sizes and the proof on Germany with the follower: Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310. The phone area and its FFI: Phone: an offline area of whole cells, installed with the same installer #3309.
- A new method for alternatives, one search for all candidates of an inner point, and goal direction.
- The route catalog on format 10, and the deletion of the old engine,
OpenedandMAX_WORKERS: Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311.
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
unpackhas 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_columnsinplanner-router-buildbuilds the cost columns of the property test.routing-cellsis a mandatory index intools/planner_grid_index.py.tools/planner_verify.pyhashesrouting/directory.binonly when the release check gives it one that changed.tools/tests/test_planner_grid_maps.pyhad 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-overlayat67320e4:compare OLD NEW 24 1 --max-km 300gives 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.jsonand the identity of format 10 do not change.overlays.sqlitechanges: its package is the SHA-256 ofcells/directory.bin. - The speed gate is missed on short routes. The
pinnedrequest 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::snapof 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
touringroute (2.6 times formtb/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 localandobc data serve localwith 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.
Activity
Route engine: the open rule, the closed step and the unpacking of the…
Route engine: ROUTE_CELLS in the service, the columns of compare, the…
Route engine: the comment of the reverse turns names the open cells
Planner release: the release and the overlays name the identity of th…
docs: routing_package and package are the SHA-256 of the route directory
Route engine: the unpacking announces each cell below the download le…
docs: the overlay grid reads the index of the routing cells grid