Skip to content

Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310

Closed

Description

@timohueser

Status: done

Part of #3227.
Depends on: #3305

TL;DR

Goal: On Germany, measurements show that the bake fits 16 GB, that its stages that read work files slow by at most 2 times when the page cache holds a quarter of the work files, and that the new engine gives the route costs of the old engine, answers each long leg across Germany in less than 1 s with warm files, and holds less than 1 GB of its own memory for each worker. The level sizes and the download level come from these measurements; the owner sees the tables before the values go into data/planner.toml.
Problem: The figures of the overlay come from a prototype on Switzerland and Belgium (7.7 and 5.4 million roads, one start state, no seed costs). The level sizes of #3300 (factor 8 from 512 junctions) and the download level (#3301's default 4) have no measurement on a graph of Germany's size, and the growth of the border roads with the cell size comes from two small countries (engine review D2). Europe has work files several times the RAM of the bake machine.
Decision:

Facts

Plan

  1. planner/router/src/compare.rs and examples/compare.rs (Route engine: the road search on format 10, and the test of the old engine against the new one #3303 owns them; Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 adds):

    • requests gets min_m: each later spot is at least min_m from A. With min_m above 0 the kinds 5, 6 and 7 are left out (one road, or at most 40 km).
    • Options: --min-km K; --profiles a,b,… (else all); --new-only (NEW alone and no check, for --cold, --workers and the cold start; OLD is then not opened); --repeat-new N (NEW runs each request N times and the last run counts; OLD runs once); --layouts (OLD and NEW are installs of two layouts of one bake: the check compares, route by route, the reason, the cost and the error kind, and each position by its projected coordinate, not by road ID or pieces; a request with snap_truncated on either side is skipped and counted, because the cut at 8 candidates breaks ties by road ID); --workers N (with --new-only: N threads, each with its own router over one opened install, which take the requests in turn); --json FILE (one line for each request); --areas (step 2).
    • A line holds the profile, the kind, the points, the straight km of each leg, and for each side the outcome, the cost, the error kind, the time of routes plus answer::answer and the settled labels (OLD: 1,024 × the calls of cancelled, as the prototype counted them; NEW: Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305's Stats of the last search); with --cold also the open time, the major faults (/proc/self/stat) and read_bytes (/proc/self/io). A thread samples RssAnon of /proc/self/status every 10 ms; the summary gives the value after the open and the peak, the median, P90 and largest time for each side, and leaves out the first OLD request of each profile (it loads the profile). The Linux reads are under cfg(target_os = "linux").
  2. compare --areas INSTALL, the table for the download level. For each level ℓ from 2 to the top of the install: the cells; the roads per cell (median, largest); the objects of a whole package at that level (2 + groups for each cell, plus the upper cells) and their median and largest size, from the bytes per road of each part of the download cells; the world file count (that count scaled by 10^9 / the roads of Germany) and the bytes of the world directory.bin (Route package format 10: the contract, the writer and the installer #3301: 48 + 72 × (2 + groups) bytes for each record; at 250,000 files about 19.5 MB, which each phone area downloads, Phone: an offline area of whole cells, installed with the same installer #3309); and the area overhead: the installed routing bytes of an area divided by those of its own roads (the roads whose arrival junction lies in it). An area takes the level-ℓ cells whose box meets it, grown as Phone: an offline area of whole cells, installed with the same installer #3309 grows it; the box of a level-ℓ cell is the union of the boxes of its level-1 cells; long roads do not count (Route package format 10: the contract, the writer and the installer #3301 rule 2). Two kinds of area: each zoom-9 tile, and each 3 × 3 block of them, that lies wholly inside the Germany bounds and has no tile at their edge. The median and P90 of each kind.

  3. The runs, all under nice, in this order. Before run 1 the builder reports the cost to the owner: about 11 to 13 h in the container (bake A about 3 h with the catalog, bake B about 2.5 h, the routes about 3.5 h, of which the old engine takes about 3 h on the long bands, the cold start a few minutes, bake C 2.5 to 4 h). Nothing that is timed runs beside another run in one container. A second container of the same size can bake B while the first bakes A, which saves about 2.5 h; the owner chooses.

    1. Bake A. obc data update of a folder target with the region europe/germany and --only planner/routing (Routing bake: four cached layers: source, roads, costs, package #3299), cell_sizes = [512, 4096, 32768, 262144, 2097152, 16777216, 134217728], download_level 4. Records: for each layer and stage the time, the own peak (RssAnon), the RSS peak, and the page cache that the container leaves (15 GB less the RSS peak) against W; W as Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 measures it; the bytes of each layer, of format 9, of the format 10 objects and of the install; the time of cells install (Route package format 10: the contract, the writer and the installer #3301) on 4 workers; Routing bake: the partition into nested cells, and the roads in cell order #3300's level statistics; Routing bake: the cost tables of each profile for each cell #3304's table bytes of each level; Route package format 10: the contract, the writer and the installer #3301's count of long roads and the largest long list of one download cell.
    2. Bake B. The same with cell_sizes = [256, 2048, 16384, 131072, 1048576, 8388608, 67108864, 536870912]. The source layer is cached. The same records.
    3. Routes. For each band (km) 0–25, 25–75, 75–150, 150–300, 300–600, 600–900: compare A9 A10 C 1 --min-km … --max-km … --profiles road,touring,mtb,hiking,gravel --repeat-new 2 --json …, with C = 20 for the bands up to 300 km and 10 above (A9 the format 9 package of bake A, A10 its install). Then compare A10 B10 --layouts with the same bands and --repeat-new 2: new engine against new engine, which checks B and gives B's warm times. Then --new-only --cold on A10 and on B10 over the bands 300–900, and --new-only --workers 1 and --workers 4 on A10 over the same bands.
    4. Cold start, on the chosen install: Maps::evict, then planner-service INSTALL with ROUTE_WORKERS=4: the time to /health 200, then the first 20 requests of the band 300–600 one after another, each with its time, major faults and read_bytes.
    5. Bake C. After the choice of step 4, the chosen layout again from an empty store, in a memory cgroup of the largest own peak of its uncapped bake plus W / 4, with OBC_DATA_MEMORY_BYTES as Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296's capped run sets it unless Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 makes the sort run read the cgroup. The time of each stage against the uncapped bake (for B, its source stages against bake A).
  4. The layout. For each layout: the sum over the bands 300–600 and 600–900 of the median warm time of the new engine over the 5 profiles. The layout with the lower sum wins when it is at least 10 % lower; else the one with fewer table bytes for each road. A layout that fails a gate loses. Reason: the epic's goal is the time of long legs, and the tables are about 33 of about 170 installed bytes for each road (3.3 for each profile). The pull request also records, for each layout, the fit of log(median border roads) against log(median junctions) over the levels 2 to the second highest.

  5. The download level. From the table of step 2 for the chosen layout: the lowest level whose world file count is at most 250,000. A lower level gives a smaller area overhead on the phone (Phone: an offline area of whole cells, installed with the same installer #3309), and Follower: install format 10, and limits for memory maps #3307 sets vm.max_map_count of the server from the file count of its installs. The builder writes nothing into data/planner.toml before the owner has seen the tables of steps 2 and 4 and agreed, or chosen other values.

  6. data/planner.toml, [routing]: cell_sizes and download_level get the values, each with a one-line comment: chosen on a Germany bake with compare; the layout by the time of long legs, the download level by the area bytes on the phone. With the new values, a Switzerland bake on the owner PC under nice and compare OLD NEW 48 1 --max-km 40 (Route engine: the road search on format 10, and the test of the old engine against the new one #3303's gate) report no difference.

  7. When a gate fails. The pull request does not merge before the owner decides. The builder writes the gate, the numbers and the lever of this table as a comment on Routing: hierarchical search and disk storage #3227; the owner names the sub-issue that takes it.

    Failure Lever Sub-issue
    A cost or an error kind differs A fault: the request becomes a case of Route engine: the road search on format 10, and the test of the old engine against the new one #3303's test engines The one of the faulty part, usually Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305
    Bake A does not finish in 15 GB, in the route catalog The catalog on format 10; Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311's Germany bake then carries this gate Format 10 becomes the only format: delete the old engine and format 9, merge routing-overlay into develop #3311
    Bake A does not finish in 15 GB, in another stage The stage with the largest own peak: the budget rule of Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297, the partition exception of Routing bake: the partition into nested cells, and the roads in cell order #3300 Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297, Routing bake: the partition into nested cells, and the roads in cell order #3300
    A gated stage of C takes more than 2 times its uncapped time Its random reads; the bucket size of Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296 for the emit and the terrain Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296, or Routing bake: join the nodes to the ways with a sort, and do the tag work in the scan of the ways #3295 to Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297 for their stage
    A warm long leg takes 1 s or more, the search most of it The other layout; a lower COLUMNS_FROM of Routing bake: the cost tables of each profile for each cell #3304 when the backward side reads most Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310, Routing bake: the cost tables of each profile for each cell #3304
    A warm long leg takes 1 s or more, the unpacking most of it The unpacking of Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305: a smaller level 1 (layout B), unpacking from both ends Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305
    Cold leg or cold start slow (no gate) The prefetch of Route engine: the data layer on format 10 and the host interface #3302 (announce), the order of the parts on disk of Route package format 10: the contract, the writer and the installer #3301 Route engine: the data layer on format 10 and the host interface #3302, Route package format 10: the contract, the writer and the installer #3301
    Own memory of 1 GB or more for each worker The label store and the search limit of Route engine: the road search on format 10, and the test of the old engine against the new one #3303 and Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305

Files

  • planner/router/src/compare.rs, planner/router/examples/compare.rs: change: min_m, the options, the check of --layouts, the JSON lines, the memory samples, --areas.
  • data/planner.toml: change: cell_sizes, download_level.

Done when

Out of scope

Progress

Pull request #3473 merged the tools of Plan steps 1 and 2 into routing-overlay. It is a partial step: this issue stays open.

  • Done: the options of compare (--min-km, --profiles, --new-only, --repeat-new, --layouts, --workers, --json, --areas), with two tests in planner-router-build.
  • Built differently: --layouts moves each pin to the candidate at the same coordinate (compare::repin), and each side costs the roads of its own route on its own data. The settled labels of OLD are the exact count. --profiles replaces --profile. With --cold, the NEW columns are those of the warm route. In the --areas table each road has the same installed bytes, and a cell above the level has 1 + groups objects.
  • Proof on Switzerland (4 cores, 15 GB RAM): old against new gives 0 differences on 150 requests of two bands. Layout A against layout B (from 256 junctions) gives 0 differences and 0 skipped requests. Each of 4 workers holds 10.1 MB of own memory. --areas on layout A: 162,066 world files at level 3 and 20,452 at level 4; the median overhead of a zoom-9 tile is 3.48 at level 3 and 12.81 at level 4.
  • Next: the Germany runs of Plan step 3, on the owner's machine. The commands are under "Owner steps" in pull request Route bench for the Germany proof: bands, profiles, new-only, layouts, workers, JSON lines, download-level table (#3310, steps 1 and 2) #3473. One change to them: build from origin/routing-overlay, because the branch claude/3310-germany-bench is merged. The bakes run with handover/tools/bake_layers.py of the archive branch claude/overlay-handover, not with obc data update, because compare needs the packages as plain folders.
  • Then: Plan steps 4 to 6 (the layout, the download level with the owner's answer, data/planner.toml) in a second pull request. In it, compare::grown uses the growth rule of install::area_cells (Phone: an offline area of whole cells, installed with the same installer #3309) in place of its own copy.

Built differently

Pull requests #3473 (the tools, see "Progress") and #3490 (the values) built this design, into routing-overlay, with these changes:

  • The Germany runs did not run. The owner deferred them on 2026-11-15: no machine for them. Plan step 3, the capped bake and each Germany gate of "Done when" move to the first bake of that size, with workstream 8 of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000. Not proven: the bake in 16 GB at the size of Germany, the gate of the capped page cache, a sixth level, legs above 273 km, the cold start on a real disk.

  • The choice rests on Switzerland (the bake of routing-overlay at 67320e4, 4 cores, 15 GB RAM). The layout stays A (cell_sizes from 512): layout B (from 256) has a median of 46.0 ms against 51.5 ms on legs of 150 to 229 km, which is not clearly 10 % lower, and it has twice the files.

  • download_level is 3 (it was 4). The owner's rule: a large offline area must not grow against today's format; a very small area may grow. The routing bytes of a phone area, download and installed, in MB:

    Area Format 9 Level 2 Level 3 Level 4
    Uri tile, 0.15 M own roads 30.1 / 30.6 29.4 / 45.9 57.0 / 92.8 166.0 / 275.7
    Valais tile, 0.09 M own roads 18.4 / 18.7 16.3 / 24.4 34.3 / 52.9 150.7 / 247.9
    Zurich tile, 1.34 M own roads 130.3 / 131.9 127.0 / 222.7 173.7 / 305.4 296.9 / 527.6
    3 × 3 tiles in the Alps, 1.74 M own roads 222.1 / 224.8 180.0 / 293.4 225.8 / 377.1 334.6 / 581.3
    Whole bounds 740.7 / 748.9 608.7 / 1,043.3 598.7 / 1,035.5 593.1 / 1,055.1

    Format 9 is measured with the selection code of develop on the blocks output of the same bake. At level 3 the package has 1,169 objects and a directory.bin of 99,280 B; the world estimate is 162,066 files and a directory of 12.8 MB. Level 2 gives the download of format 9, but its world estimate is 1,345,325 files and a directory of 106.5 MB, above the limit of 250,000 files.

  • The installed bytes grow at each level, 1.4 to 1.7 times for a large area: the installed files are not compressed. The owner's answer on this is open.

  • The gates on the level 3 install: compare OLD NEW 48 1 --max-km 40 gives 480 requests, 0 differences, 42 ties; compare OLD NEW 24 1 --max-km 300 gives 240 requests, 0 differences, 49 ties.

  • What a tie is, measured on the 49 ties: the roads that only one of the two routes uses have a median of 197 m and at most 4.0 km; the two lines are a median of 21 m apart; the total length differs by a median of 9 m and at most 666 m. No tie lies within 1 km of a leg end.

  • A phone area against the full install (the 3 × 3 block at level 3, 102 requests inside it, 3 profiles): 98 give the same route, 3 find no path on both, 1 has a higher cost on the phone because the route of the full install leaves the area. No tie, and no lower cost on the phone.

  • install::grown is the one rule that grows an area by the snap window; install::area_cells and the table of compare --areas call it.

  • Open: the Requirements: line of both pull requests is not checked (the verification token was absent).

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