Skip to content

Routing bake: the cost tables of each profile for each cell #3304

Closed

Description

@timohueser

Status: done

Part of #3227.
Depends on: #3299, #3300, #3301

TL;DR

Goal: For each profile and each cell of each level, the bake computes the cost table and writes it into the slot that #3301 reserves in the profile group part, so that the overlay search of #3305 can cross a cell in one step.
Problem: Format 10 of #3301 writes each table slot with 0 bytes, so each cell is open and the search of #3303 uses the roads of every cell: its work grows with the square of the distance. The prototype computed the tables in RAM with u32 values and hash maps, read columns with a stride (prototype_mld.rs#L587-L588), and stopped with an assertion when a value passed 32 bits (#L433). It measured 2.6 to 3.3 B for each road and profile at 4 bytes for each value, and 1.5 s for each million roads and profile on one core.
Decision:

  • A table value is the least cost of a path in the cell from an entering road to a leaving road, with the weight rule of the engine (Costs::arc). It counts each turn of the path and each road after the entering road, the leaving road in full. It never counts the entering road.
  • A new stage tables::build, the last stage of the step planner/routing-costs of Routing bake: four cached layers: source, roads, costs, package #3299, computes level 1 by a search on the roads of each level-1 cell, and each higher level by a search over the tables of the child cells, level after level. A task is one cell: it maps its nodes once and then runs all profiles. It reads each cell as ranges of the layer columns, and the cells of a level run in parallel. Each table is a function of its cell alone, so the bytes do not depend on the thread count. The tables are files of the costs layer, so a change of the cost model repeats them with the costs and the package, not the source or the roads.
  • A table is a header of 16 bytes and the values by row; one width for each table (1, 2 or 4 bytes, the narrowest whose all-ones is above its largest finite value); all-ones means "no path". A table whose values take more than columns_from bytes also holds its values by column. columns_from is an argument of tables::build: the step passes 16,384, a test passes 16.
  • cells::write of Route package format 10: the contract, the writer and the installer #3301 opens the tables from the costs layer and copies them into the slots, and writes a group part for each upper cell. No group part is written twice.
  • A finite value at or above 2^32 − 1 stops the bake with the profile, level and cell ID.
  • Two profiles with equal tables do not share bytes. The writer counts the equal tables, and the pull request reports the share.
    Rejected:
  • A value without the cost of the leaving road. Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 must then read the road cost of each leaving road, in another cell, at each relaxation. A value with the cost of the entering road: the seed of a search already holds the part of that road that the route uses.
  • One width for each level or for the package: at the top level only 27 to 67 % of the values fit 16 bits, so one large value makes all tables of the level wide. A width for each row, or a list of exceptions: engine review D9; a loop over one width has no branch.
  • A column copy by level (levels 4 and up, engine review D4): the level sizes change in Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310. A column copy of each table: it doubles the bytes of the small tables, where a column read with a stride stays in a few pages anyway. No column copy: a column read in a top table of 800 × 800 values touches 625 pages of 4 KiB.
  • Tables in their own object for each cell: one more part kind, and two objects for each group install. Route package format 10: the contract, the writer and the installer #3301 already reserves the slots in the group part.
  • Write the group parts without tables, then rewrite them: each group object is compressed and hashed twice, and the directory is written twice.
  • A sort that joins the costs of the leaving roads to their cells: the reads are near in the cell order (see Facts), so a direct read is enough.
  • Shared bytes for equal tables now: the gain is an estimate of 5 to 10 % (engine review D9) and needs a measurement first.
    Systems: routing, obc-data
    Contracts: specs/route-package.md (format 10 of Route package format 10: the contract, the writer and the installer #3301: the bytes of a cost table)
    Size: L (a stored format: the table bytes; 2 systems; about 1,000 changed lines)
    Branch: routing-overlay

Facts

Table rules

#3305 cites these rules. C is a cell of level ℓ, p a profile, e an entering road of C (it departs outside C and arrives in C), l a leaving road (it departs in C and arrives outside).

  • T1. Value. T[e][l] is the least sum, over the turns of a path e = r0, r1, …, rk = l (k ≥ 1), of the turn cost plus the road cost of the target road, where r1 … rk−1 arrive in C. It does not include the cost of e. So the forward search sets cost(l) = cost(e) + T[e][l], and the backward search sets cost(e) = T[e][l] + cost(l), with the labels of today's search.
  • T2. No path. All-ones of the width of the table means that no such path exists. A turn with an all-ones turn cost or target cost is not a turn. A road is never an entering and a leaving road of the same cell, and no path in a cell reaches an entering road again.
  • T3. Rows and columns. Level 1: the row of e is its index in the level-1 cell; the column of l is its place in the leaving list of the cell's record. Level 2 and higher: the row and the column are the places in the entering and leaving lists of the upper record. Each list is in ascending run-time road ID.
  • T4. Presence. Each cell of each level has a table for each profile of each group part that has its slot. An empty table (no entering or no leaving road) is a header of 16 bytes, so no written slot has 0 bytes, and a cell is open by Route package format 10: the contract, the writer and the installer #3301 rule 3 only when its group part or upper cell is not installed.
  • T5. Bytes. As in the table below. Without the column copy, Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 reads a column with a stride of columns × width bytes. The view cells::Table gives each value as u64, with u64::MAX for no path.
  • T6. Range. Each finite value is at most 2^32 − 2. Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305 adds values in u64.
  • T7. Unpacking. For each finite T[e][l] of level ℓ ≥ 2, the search of plan step 3 from e over the tables of the children of C reaches l with exactly that cost. For level 1, a search from e on the roads that arrive in the cell reaches l with exactly that cost. The path can differ from the bake's when two paths have the same cost.

The bytes of a table, at the offset at of its slot (a multiple of 4 from the start of the part), bytes long:

Field Type Meaning
rows, columns 2 × u32 The entering and the leaving roads of the cell; the view checks them against the record
width u8 1, 2 or 4: the narrowest width whose all-ones is above each finite value. A table with no finite value has width 1
layout u8 0: by row; 1: by row, then by column
zero 6 bytes
by row rows × columns values Value (r, q) at 16 + (r × columns + q) × width
by column rows × columns values, when layout is 1 Value (r, q) at 16 + (rows × columns + q × rows + r) × width

The writer sets layout to 1 when the values by row take more than columns_from bytes and the table has more than one row and more than one column. The bake uses 16,384 bytes. Reason: then a column read with a stride touches more than 4 pages of 4 KiB (the server) or more than one page of 16 KiB (the iPhone). A reader accepts layout 0 and layout 1 for each table and does not check the threshold, so a test package with small tables can hold column copies. All integers are little-endian; the view reads them with no alignment need.

Plan

  1. planner/router/src/cells.rs (Route package format 10: the contract, the writer and the installer #3301's module): Table<'a> with parse(bytes: &[u8], rows: u32, columns: u32) -> Result<Table>: it reads only the header and checks it, the width, that the layout is 0 or 1, and bytes.len() == 16 + rows × columns × width × (1 + layout). It does not check the threshold of the column copy. get(row, column) -> u64, row(row) and column(column) as iterators of u64 (column reads the copy when layout is 1). encode_table(rows, columns, values: &[u64], columns_from: usize, out: &mut Vec<u8>) -> Result<(), u64>: values by row with u64::MAX for no path; it chooses the width and the layout, and returns the first finite value above 2^32 − 2 as the error. Group (Route package format 10: the contract, the writer and the installer #3301) gets table(profile, slot) -> Option<Table>: None for a slot of 0 bytes.
  2. planner/router-build/src/tables.rs (new): pub struct Costs<'a> { totals: &'a [u32], turns: &'a [u32] } (the columns of one profile of the costs layer), pub struct Tables { levels: Vec<Level> }, struct Level { bytes: Column<u8>, at: Column<u64> }: the table of cell c and profile p of the level is bytes[at[c × P + p]..at[c × P + p + 1]], in the order of the cells of Routing bake: the partition into nested cells, and the roads in cell order #3300 and of the profiles of costs.json. Tables::table(level, cell, profile) -> &[u8]; Tables::save(folder) and Tables::open(folder) with Routing bake: four cached layers: source, roads, costs, package #3299's Column::save and Column::open. pub const COLUMNS_FROM: usize = 16_384. build(cells: &Cells, first: &[u32], head: &[u32], profiles: &[Costs], columns_from: usize) -> Result<Tables, String>. The step passes COLUMNS_FROM; each test 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 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 that calls build passes 16, so its small tables have column copies.
    partition.rs (Routing bake: the partition into nested cells, and the roads in cell order #3300): Cells::entering(level, cell) -> impl Iterator<Item = u32> gives the entering list by Routing bake: the partition into nested cells, and the roads in cell order #3300 rule 2. Routing bake: the cost tables of each profile for each cell #3304 adds it and moves the prefix rule of Route package format 10: the contract, the writer and the installer #3301's writer into it, so cells::write and tables::build call the same function.
  3. tables.rs, the task of one cell. It maps the nodes of the cell once, then runs each profile:
    • Level 1, cell with roads a..b and E entering roads: the nodes are the roads a..b, then the leaving roads of the cell (node b − a + q for column q). One pass over the turns first[a]..first[b] maps each target to its node: h − a when a ≤ h < b, else the place of h in the leaving list, by a binary search. A target that is in neither fails the bake ("turn target outside the leaving list of level-1 cell ID"). For each profile, the costs of the leaving roads are read once from totals.
    • Level ℓ ≥ 2, cell C: the children are one range of the cells of level ℓ − 1 (Routing bake: the partition into nested cells, and the roads in cell order #3300 rule 5). The nodes are the entering roads of the children, in child order and list order (so in ascending road ID), then the leaving roads of C. For each column q of each child, one binary search gives its target: a node of a child when the road arrives in C, else a leaving road of C. A target that is in neither fails the bake.
    • For each profile and each row: Dijkstra from the node of the entering road with cost 0, in u64, with a binary heap. A leaving node is settled and not expanded. A road node expands its turns: weight turns[t] + totals[h], or none when one of them is u32::MAX. A child node expands the row of its child table (cells::Table::parse on the store of level ℓ − 1), one arc for each finite value. The search stops when the heap is empty or each leaving node is settled. The row of the table holds the cost of each leaving node.
    • encode_table writes the table with columns_from. Its error stops the bake: "the cost table of profile P, level ℓ, cell ID X holds the value V, above 32 bits".
    • Memory for each worker: the nodes, costs and heap of the largest cell, and the values of one table: a few MB.
  4. tables.rs, build: the levels in order 1, 2, …, top; the store of level ℓ − 1 is complete before level ℓ starts. In a level, the cells go in batches of consecutive cells whose tables take at most 64 MiB (at least one cell; the size bound is rows × columns × 8 × profiles). A batch runs its cells as tasks on the rayon pool of Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297, collects the tables in cell order, and appends them to the store. So the own memory is at most 64 MiB and the scratch of the workers, and the bytes do not depend on the thread count. The stage prints for each level: the tables, their bytes, the bytes for each road and profile, the share of tables of width 1, 2 and 4, the share of bytes in column copies, the largest finite value of each profile, the seconds, and a SHA-256 of the store.
  5. planner/router-build/src/cells.rs (Route package format 10: the contract, the writer and the installer #3301's writer): write opens Tables from the costs layer with the other costs columns. In the group part of a download cell, for each profile of the group, it copies the table of each level-1 cell and then of each upper record into the tables section after the slots, each at a multiple of 4 after zero bytes, and writes at and bytes. For each upper cell and group, it writes the group part of Route package format 10: the contract, the writer and the installer #3301 (header with cells and classes 0, upper 1, classes_at and slots_at 24, one slot for each profile, the tables) and its part entry 2 + g in the directory record. The hashes come from these bytes, so the directory is written once. Summary gets the table bytes of each level, and the bytes of the tables that are equal to the table of an earlier profile of the same group and cell.
  6. planner/router-build/src/step.rs: tables::build is the last stage of the step planner/routing-costs, after the snap bits, with first and head and Cells of the roads layer and the columns of the costs layer. Its output is the files tables/<level>.bytes and tables/<level>.at of the costs layer, listed in layout.json. The stage is a stage of Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297's guard. planner/router-build/examples/cells.rs (Route package format 10: the contract, the writer and the installer #3301) gets cells tables ROADS COSTS: it runs tables::build on the two layers and prints the statistics of step 4, the time and the peak memory; it writes no layer.
  7. host/obc-data-steps/src/planner.rs: the format of planner/routing-costs goes up by one (Routing bake: four cached layers: source, roads, costs, package #3299 rule 6: new files in a work layer), and PLANNER_ROUTING.revision goes up by one (new bytes in the group parts).
  8. specs/route-package.md (format 10 of Route package format 10: the contract, the writer and the installer #3301), the profile group part: the table bytes above, the rules T1 to T7, and that the group part of an upper cell holds only its slots and tables. specs/obc-data.md: the tables in the files of the costs layer. planner/router-build/README.md, "Work files and memory": the tables stage holds at most 64 MiB and the scratch of each worker.
  9. Tests, in tables.rs, with columns_from 16:
    • each_value_is_the_cost_of_a_road_search_in_its_cell: a grid of 12 × 12 junctions with two-way and one-way roads and a dead-end spur, Routing bake: the partition into nested cells, and the roads in cell order #3300's partition with sizes [4, 16, 64]. Three profiles of synthetic columns: costs from a fixed xorshift; the same with a band of excluded roads and a forbidden turn; costs large enough that some tables have width 4. For each cell of each level, each profile, each row and column: the value through cells::Table equals a plain Dijkstra over all roads with the rule of Costs::arc, from the entering road at cost 0, that expands only the roads that arrive in the cell. The test also checks the narrowest width, that the layout is 1 exactly by the rule (16 bytes in the test), that the column copy is the transpose, and that a cell with no leaving road has a table of 16 bytes.
    • a_value_above_32_bits_stops_the_bake: an entering road, one inner road and a leaving road of one level-1 cell, the inner and the leaving road with costs of 2^31; the error names the profile, the level and the cell.
    • Route package format 10: the contract, the writer and the installer #3301's tests in tests/cells.rs call tables::build with columns_from 16 before write. an_install_gives_back_each_road also checks that each slot of each installed group part gives the bytes of Tables::table, for level-1 cells, upper records and upper cells, and that at least one installed table has layout 1. the_bytes_do_not_depend_on_the_threads builds the tables in the same rayon pool as write, so it covers this stage.

Files

  • planner/router/src/cells.rs: change: Table, encode_table, Group::table.
  • planner/router-build/src/tables.rs: create: the stage and its tests.
  • planner/router-build/src/lib.rs: change: the module.
  • planner/router-build/src/partition.rs: change: Cells::entering.
  • planner/router-build/src/cells.rs: change: the call of Cells::entering, the tables in the group parts, the group parts of upper cells, Summary.
  • planner/router-build/src/step.rs: change: the stage in the costs step, its files.
  • planner/router-build/examples/cells.rs: change: cells tables.
  • planner/router-build/tests/cells.rs: change: tables::build in the fixture, the two checks.
  • host/obc-data-steps/src/planner.rs: change: the format of the costs layer, the revision of planner/routing.
  • specs/route-package.md, specs/obc-data.md, planner/router-build/README.md: change.

Done when

  • obc test -p planner-router, obc test -p planner-router-build and obc test -p obc-data-steps pass, with obc exec cargo clippy -p <crate> --all-targets -- -D warnings for each. cargo check -p planner-router --target wasm32-unknown-unknown passes. cargo fmt --all, obc suites check and python3 docs/build_docs.py --check-links pass.
  • Gate of the epic: a Switzerland bake gives the same format 9 manifest ID before and after this change.
  • Check of the values on real data, for the pull request and not for CI: a temporary patch of cells tables (it does not merge) takes about 1,000 rows of the Switzerland bake by a fixed xorshift, spread over the levels, with each table of layout 1 and of width 4 in reach, and compares each value with the road search of the test each_value_is_the_cost_of_a_road_search_in_its_cell. No value differs. The first proof through the engine is the compare gate of Route engine: the overlay search with the cost tables, and unpacking of the chosen legs only #3305.
  • cells tables on the layers of the Switzerland bake with RAYON_NUM_THREADS=1 and with all threads prints the same SHA-256 for each level, and cells write of Route package format 10: the contract, the writer and the installer #3301 then gives the same directory hash. No second bake is needed.
  • The pull request records, from cells tables and cells write on a Switzerland bake with terrain and 10 profiles on the owner's PC (16 GB, 6 cores), and on a Germany bake 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). That container is enough: the stage holds at most 64 MiB and the scratch of 4 workers, and it reads the columns of the layers in cell order:
  • Outcomes that go to the owner before the merge: installed tables above 4 B for each road and profile; a time above 3 s for each million roads and profile on one core; column copies above 25 % of the table bytes; an own peak above 0.6 GB on Germany. When the equal tables hold 10 % or more of the table bytes of Germany, the pull request proposes a follow-up that shares them; the format needs no change for it, because a slot names its bytes by offset.
  • The pull request has the line Requirements: and says that public docs changed.

Out of scope

Built differently

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

  • What an entry holds (rule T1 of the contract, and the doc of the Table view): the least cost from the entering road to the leaving road on roads that arrive in the cell. It holds each turn of the path and the full cost of each road after the entering road, the leaving road included. It does not hold the cost of the entering road. A road between two child cells counts once. All ones means no path. It is the same at each level.
  • A task is one table, of one cell and one profile, and a batch holds at least one table for each thread, so the large cells of the top levels run in parallel. Each thread keeps its scratch between tables.
  • The files are tables.<l>.bytes and tables.<l>.at, flat in the costs folder. Group::table also takes the rows and the columns and returns Result<Option<_>>. The three work layers share the format FORMAT + 3, so all three bake again once. The error of a value above 32 bits names the profile by its index.
  • An upper cell has a group part for each group (part 0 and a part 2 + g; part 1 is absent). The contract says so in each place.
  • Exact on a real region: each entry of each table of Switzerland (5 levels, 10 profiles, 50,270,700 entries) equals a plain search on the roads of the cell; 0 differ. A sample on North Rhine-Westphalia: 798,370 entries, 0 differ. The program of this comparison is not a committed test; the committed grid test compares each entry of each level with an independent search.
  • Measured on Switzerland (4 cores, 15 GB RAM): format 9 keeps its three hashes; the identity of format 10 with tables is 004a933b…, the same for 1 and 4 threads; 160 files, 592.7 MB. The tables take 1.91 installed bytes for each road and profile (2.6 to 3.3 in the prototype) and 1.14 s for each million roads and profile on one core. The own peak of the stage is 51 MiB. 664 tables are also stored by column (18.1 % of the table bytes). The values that fit 16 bits, level 1 to 5: 99.5, 98.1, 90.5, 52.2 and 39.4 %.
  • Open: the Germany figures, with Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310. A review note: the scratch that each thread keeps is global state for a small gain; a local scratch for each task is simpler.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

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