Repository navigation
Description
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:
- New search (
overlay): today's seeds, loop, tie-break and stop rule (rules S1 to S10 below). A label is one slot of 24 bytes in a hash table by road ID. A queue entry has 16 bytes and a key of 64 bits. No landmarks. The backward side builds the reverse turns of a level-1 cell from its forward turns when it first enters the cell. - All cells open. Route engine: the road search on format 10, and the test of the old engine against the new one #3303 does not read the table slots, also when Routing bake: the cost tables of each profile for each cell #3304 has filled them. The loop expands a road in one function; Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 adds the closed-cell step there and changes nothing else in the loop.
- Search limit. The budget of a worker is the most bytes of one search (768 MiB until Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305). It is not an estimate of the data.
- Both engines until Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311.
planner_router::openchooses by the folder: withmanifest.jsonorblocks.jsonit is format 9 and today's engine, else format 10 and the new engine. The service, the phone library and the examples callopen. The service of the branch keeps the folder of its argument, which the follower fills with format 9;ROUTE_CELLSof Follower: install format 10, and limits for memory maps #3307 is read from Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 on, so no follower runs the engine without tables. The route catalog keeps format 9 and today's engine until Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311. - Gate. One comparison (
compare) routes the same requests through both engines. It runs in CI on the fixture of Route engine: the data layer on format 10 and the host interface #3302 and once on Switzerland for the pull request. Route engine: the road search on format 10, and the test of the old engine against the new one #3303 has no speed gate: without landmarks and tables the new search settles 5 to 20 times the labels of today's. Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 has the speed gate.
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
openchooses 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
- Route engine: the data layer on format 10 and the host interface #3302:
RoutingData::search;Regionwith its lookups (the level-1 record of a road, the run-time ID of a road reference),endpoint, and the host;Router::costgives the cost of a route with a profile, exactly. - The search loop: seeds (search.rs#L159-L171), stale entries and the stop rule (#L180-L194), the side (#L195), the meeting tests (#L198-L208, #L230-L240), the relaxation (#L222-L229), the path and its second sum (#L243-L292). Without landmarks the stop rule is
top_f + top_b > best. A unit test asserts that the result is the least (cost, end choice, start choice) (#L428-L459). - An arc weight is the road cost of the target plus the turn cost; all-ones in one of them means no arc (base.rs#L219-L227). A road cost is at least 1 (cost.rs#L14).
- A label block has 6,656 bytes for 512 road IDs, and
resetwalks a directory over all road IDs (search.rs#L8-L37). A queue entry is(i128, u64, u8, u32)(queue.rs#L5). - A start seed is a candidate road with the cost of its rest. The end seeds of a candidate are the roads from which a turn enters it, each with the cost of the used part plus the turn cost (router.rs#L469-L496). Two points on one road set the cost ceiling (router.rs#L497-L524). The router reads
cost,source,targetandroadsof a result (router.rs#L306-L316, #L534-L544). - The service has
Engine = Router<Selection<Files>>(lib.rs#L21), opens and forks inappand loadstouring(http.rs#L39-L53). The phone opens with budget 0, the default (native.rs#L67). The catalog routes on the pages of its own bake (catalog/mod.rs#L337-L344). - Route package format 10: the contract, the writer and the installer #3301: the run-time road ID is the same number in format 9 and in format 10 of one bake (rule 1). An installed folder has
directory.bin, andinstall.binwhen the install is complete (rule 4); it has nomanifest.jsonand noblocks.json. A format 9 folder has one of these two (directory.rs#L188-L200), and before Follower: install format 10, and limits for memory maps #3307 also thedirectory.binof the release. - Route service: request classes, the limit error as status 422, the probe radius #3308:
Error::Limitis a fixed limit, which the same request passes again on an idle service;Error::Memoryis a shortage that a retry can end.
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) andorigin(thechoiceof its seed). A forward cost includes the road. A backward cost is the cost after the road. - S2. Arc. Road
uhas an arc to roadvfor each turnu → vin the block of the level-1 cell ofu. Its weight is the road cost ofvplus 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 isInvalidData. - 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.
beststarts at the ceiling androotsat (255, 255). Each round removes the stale entries at the front of both queues. It stops when one queue is empty ortop_f + top_b > best(a saturating sum; at equal the search goes on). Else it pops from the backward queue whentop_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 ofr,joined = cost_f + cost_b. When(joined, origin_b, origin_f) < (best, roots), thenbest,rootsand 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
rwith costc: each arcr → vrelaxesvwithc + weight. Backward: each arcu → rrelaxesuwithc + weight; this weight holds the cost ofr. A relaxation of roadxwithnextand the originoofrdoes nothing whennext > bestor(next, o) ≥the label ofx. Else it sets the label with parentr, pushes the entry and runs the meeting test ofx. - 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.
sourceis the first start seed whose road, cost and choice are the label of the first road;targetis the same for the last road and the end seeds. No such seed isInvalidData. The engine sums the path again: the two seed costs and each arc weight. A sum that is notbestisInvalidData. - 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 thanmax_roadsroads, or labels, queues and reverse turns above the search limit of the worker areError::Limit, because the limit is one number for each request and no other worker changes it. An allocation that fails isError::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
planner/router/src/overlay.rs(new) definesSeed,QueryandFound(moved fromsearch.rs, which imports them) andStats { 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; anidof all-ones is empty. So a probe reads one cache line. The table doubles when more than half of the slots are used.resetgives 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 au64key, 65 buckets and the entry{ cost: u64, road: u32, origin: u8 }of 16 bytes. A push below the last popped key isInvalidData.
overlay.rs,Workspace(twoLabels, twoQueue, the entered cells) andsearch(shared, workspace, profile, query)by S1 to S10.- One function
expand(side, road, cost, origin)holds S7. Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 puts the test of the closed level before it. - Forward: the level-1 record of
rgives the block (two lookups of Route engine: the data layer on format 10 and the host interface #3302 for each settled road). Aheadvalue belowroadsis a road of the cell, with its cost in the same group block. Another value is a leaving road: its run-time ID from its road reference, its cost from the group block of its own level-1 cell. - Backward: the cell
Cof the departure junction and the target numbert, as inendpointof Route engine: the data layer on format 10 and the host interface #3302. The first time a search needs the turns into a road ofC, it builds the reverse turns ofCby a counting sort ofhead: for each target number, the sources (index inC) and the turn numbers. The entry ofClives in the workspace until the next search starts. Its bytes count for the search limit. Route engine: the road search on format 10, and the test of the old engine against the new one #3303 enters each cell that the backward side reaches; Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 enters only the cells that are open by a seed. - The path (S8) finds the weight of each arc
u → vin the turns ofu.
- One function
planner/router/src/region.rs:Regiongets the workspace and the search limit, andimpl RoutingData for Regiontakes the data functions of Route engine: the data layer on format 10 and the host interface #3302 and addssearch.default_budgetisoverlay::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_budgetis the search limit of S9, at mostquery.heap_bytes.stats()gives theStatsof the last search.search::Workspacekeeps the pops of its last search, so the comparison has the settled labels of both engines.planner/router/src/open.rs(new, native):pub enum Opened { Pages(Selection<Files>), Cells(Region<Maps>) }implementsRoutingDataby delegation, and hasfork,stats,verify(Pages: today's;Cells: nothing, the installer checked) andwarm(profile)(Pages:prepared;Cells: nothing).open(path): a folder withmanifest.jsonorblocks.jsongoes todirectory::open, also when it holdsdirectory.bin: until Follower: install format 10, and limits for memory maps #3307 the follower links each file of a release intorouting/, and Route package format 10: the contract, the writer and the installer #3301 publishesrouting/directory.bin. Each other folder is format 10: withoutdirectory.binor withoutinstall.binit isMissingRegion("The routing install in PATH is not complete"), elseRegion::openonMaps.lib.rsexports thisopen.planner/service/src/:Engine = Router<Opened>;http.rscallswarmin place ofprepared.MAX_WORKERS,--verifyandmain.rsdo not change: the service opens the folder of its argument. The catalog and the bake do not change.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, thenREACH_M). Requestihas kindi % 8, with a first spotAand later spots withinmax_mofA: (0)AtoB, 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 ofAto that ofB, so each point has each road of a junction; (2)A, the junction ofM,B; (3)A,M1,M2,Bwithturnarounds: [1]; (4) kind 0 withstart_positionandend_positionset to the last candidate of each point; (5) the points at 0.25 and 0.75 of the road ofA; (6) the same two points in reverse order; (7) kind 0 withalternatives: true, at most 40 km.check(old, new, request) -> Result<Outcome, String>: both sides callrouteswithControl::default(). Two errors must be the same variant. Else, route by route:reason,cost,snap_truncatedand thestartandendposition of each leg must be equal. When the pieces (road, from, to) are equal too, the two answers ofanswer::answermust be equal withoutpackage. When the pieces differ, it is a tie:old.cost(the new route, its profile)must beSomeof 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.OutcomeisSameorTie.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 becomesrequestsand its testcheck; it no longer skips a request withsnap_truncated, because the two formats of one bake have the same road IDs. It opens both folders withopenand a budget ofusize::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 ofsnapfor each side, over all points.--colddrops NEW, callsMaps::evictand 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 fromcells installof Route package format 10: the contract, the writer and the installer #3301.
- 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: ontown(),compare::requestswith 40 requests for each of the 10 profiles,checkon 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 orNoPath.overlay/store.rs:labels_keep_each_road_through_growth_and_reset(with sparse IDs up to 2^32 − 2), and today's queue test withu64keys.planner/service/tests/http.rs,the_service_opens_an_install_of_format_10:/v1/regionnames the directory hash aspackage, one route answers 200, a folder withdirectory.binand noinstall.bindoes not open, and a format 9 folder that also holdsdirectory.binopens as format 9.
planner/router/README.md: the modulesoverlay,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-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 old engine against the new one): the test
enginesin CI, and on the owner's PC (16 GB, 6 cores, release build, undernice)compare OLD NEW 48 1 --max-km 40on the Switzerland bake of the branch (its format 9 package, and an install of its cells bycells 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_batchmakes them, for a via point too) toRoutingData::searchof 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
snapfor each point, both engines.
- The pull request has the line
Requirements:and says that public docs did not change.
Out of scope
- The host, the data functions and the trait seam: Route engine: the data layer on format 10 and the host interface #3302.
- The closed-cell step, the open rule, the unpacking, a lower search limit, the split of
max_geometry, the speed gate andROUTE_CELLSin the service: Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305. The tables: Routing bake: the cost tables of each profile for each cell #3304. - The follower that installs format 10 and its limits: Follower: install format 10, and limits for memory maps #3307. The phone area, its FFI and its host: Phone: an offline area of whole cells, installed with the same installer #3309.
- The worker count and the request classes: Route service: request classes, the limit error as status 422, the probe radius #3308. The cold start, the own memory of the service and the Germany proof: Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310. The catalog on format 10 and the deletion of the old engine: Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311.
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, notstats()of the last search. A request with a via point or with alternatives runs more than one search, andcompareprints 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 examplecompareand the test fixture call it.Openedallows the lintlarge_enum_variantuntil Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311 removesPages.comparehas the option--profile Pand warms each profile of format 9 before its requests. Its summary line isN requests, D differences, T ties, in S s. With--coldit 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.requestsstops aftercount * 100tries and can return a shorter list.Shared::junctiongives the departure cell and the target number of a road;departuresand the search use it.search::run_with_potentialsets its pop count to 0 at its start.- Measured on Switzerland (4 cores, 15 GB RAM), on the bake of
routing-overlayat67320e4:compare OLD NEW 48 1 --max-km 40gives 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. Fortouring, 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.
Activity
Route engine: the first form of #3303 passes clippy; compare --profile
Route engine: compare warms each profile of format 9 before its requests
Route engine: review fixes of #3303