Skip to content

Routing bake: all profiles in one parallel pass, and a limit on the bake's own memory #3297

Closed

Description

@timohueser

Status: done

Part of #3227.
Depends on: #3296

TL;DR

Goal: The bake computes all profiles on all cores with the same bytes for any thread count, sizes its sorts and passes by the memory that it really has, and stops at once when its own memory passes the budget of 4 GiB that the owner set for the routing bake in #3228; no table in its own memory grows with the region, apart from the stated exceptions.
Problem: The bake runs on one thread, apart from the route catalog. The profiles run one after the other: with 17 profiles they took 77 % of the Germany bake, 227 s each [measured, #3251]. About 28 B for each road stay in the bake's own memory, about 9 GB for Europe [est, bake.md finding 3], and nothing enforces the budget. The sort run ignores the cgroup limit and the free memory, so a capped bake thrashes.
Decision:

Facts

Plan

  1. Cargo.toml: rayon (in Cargo.lock through obc-dem). lib.rs: const CHUNK: usize = 65_536, 8 under cfg(test).
  2. work.rs: page_budget() -> u64, read once: min(cgroup memory.max − anon of memory.stat, MemAvailable, OBC_DATA_MEMORY_BYTES − own RssAnon), each where it exists. sort_run_bytes = clamp(page budget / 4, 1 MiB, 4 GiB); Routing bake: order the roads once, in buckets, and sample the terrain inside each bucket #3296's bucket count reads it. The step prints the budget and its source.
  3. host/obc-data/src/engine/cgroup.rs (new): memory() -> Option<Cgroup { max: Option<u64>, anon: u64 }> from /proc/self/cgroup and the cgroup v2 files, with the root as a parameter for tests. obc data: the bake's step limits ignore the cgroup memory cap #3203 reuses it in Limits::machine.
  4. cost.rs: way_bases runs over chunks of ways in parallel. Each chunk fills its rows with IDs of its own Dictionary; the chunk dictionaries are joined in chunk order, and each ID adds the offset of its chunk. A basis can then have two IDs; the renumber of step 6 joins them by value.
  5. lib.rs, road pass: for a group of g profiles, the roads run in chunks in parallel. A chunk reads each road and its shape once and writes, for each profile of the group, totals[r], bases[r] (the way-bases ID) and turns[a] for the arcs of its roads, into columns of known length. g = max(1, ⌊page budget / 4 / (8 B × ways)⌋), at most the profile count: the random reads into the way bases of g profiles fit a quarter of the budget. Costing::transition becomes a function of the two roads and the profile, with no state.
  6. lib.rs, renumber: for each profile in order, one pass over bases in road order inserts each basis into the package Dictionary and writes its ID. These are the IDs of today, and the checks of today.
  7. connectivity.rs: the stack, the pending list, the component sizes and the snap words are Columns; Column gets pop. The reverse step reads the roads that arrive at the departure junction of a road, and the arc of each is first[that road] plus the place of the road among the departures of the junction (one u32 column for each road). reverse_arcs and tail go; the snap bits stay the same. landmarks.rs: the stacks become Columns; Junctions::prepare splits into compute (distance columns and scale) and write. The landmark choice does not change.
  8. lib.rs, profile jobs: one job for each profile runs snappable and Junctions::compute. n = clamp(⌊(page budget − 8 B × R − 4 B × A) / (25 B × R + 4 B × A + 45 B × J)⌋, 1, threads) jobs run at once. Then the writer, in profile order: the landmark tables, metric, then the dictionary and the closures, as today.
  9. lib.rs, closures: one pass in road order gives each set of Graph.sets its final ID at its first use, in a Vec<u32> over the distinct sets; write_closures writes the column through that map with base::write_column, and the set list in final order. The bake no longer calls Closures::build.
  10. lib.rs, snap directory: the cell pairs sort by (1° group, cell, road). Each group writes its road lists and then its directory when the next group starts; the BTreeMap of all groups goes. manifest.json stays the same; pages.bin holds the objects in another fixed order.
  11. overlays.rs: the memberships become a sorted column of (way ID, relation ID) pairs, which the scan of the ways merges. The map of routes (one entry for each route relation) stays.
  12. work.rs: const OWN_BYTES: u64 = 4 << 30, the budget of the routing bake's own memory that the owner set in Routing bake: bake a continent in bounded memory #3228. Guard::start(budget) starts a thread that reads RssAnon every 100 ms and keeps the peak of the stage. At the first sample above the budget, in a stage that is not exempt, the thread writes "stage NAME used N GiB of own memory, above the budget of 4 GiB" as the last line of standard error and ends the process with status 1, as the step contract asks for an error; the engine removes the partial directory, and outside obc data the work folder stays, as after a kill. Guard::stage(name) starts the next stage; Guard::exempt(name) starts a stage without the check. step.rs marks the stages in this order: import (up to the end of walk 1), partition (from Routing bake: the partition into nested cells, and the roads in cell order #3300 on), emit (the keys, the bounds, walk 2, the turn rules and Buckets::finish with the terrain), way-bases, road-pass, profiles (the profile jobs), writer, overlays; catalog and blocks are exempt. The step prints the peak of each stage.
  13. Tests. lib.rs: one_and_four_threads_give_the_same_package: the fixture of tests/routing.rs with 3 profiles in rayon pools of 1 and 4 threads gives the same bytes of each object and of the manifest. work.rs: a_sample_above_the_budget_names_the_stage (the check of one sample against a budget of 1 byte, without the exit). cgroup.rs: a_cgroup_limit_is_read_from_a_fake_tree.

Files

  • planner/router-build/Cargo.toml: change: rayon.
  • planner/router-build/src/lib.rs: change: the passes, the jobs, the closures, the snap directory.
  • planner/router-build/src/cost.rs: change: parallel way bases, transition.
  • planner/router-build/src/connectivity.rs, landmarks.rs, column.rs: change: columns as stacks, the reverse step, compute and write, pop.
  • planner/router-build/src/overlays.rs: change: the memberships.
  • planner/router-build/src/work.rs, step.rs: change: the page budget, the guard.
  • host/obc-data/src/engine/cgroup.rs: create. host/obc-data/src/engine.rs: change: the module.
  • planner/router-build/README.md: change: the threads, the budget and the guard.

Done when

Out of scope

Built differently

Pull request #3341 built this design with these changes:

  • The disk peak is higher. The work files of all profiles exist together until the writer stage; before, one profile at a time. The work folder peak of "Preparing" rises from 2,757 to 4,613 MiB on Switzerland and from 3,203 to 5,756 MiB on North Rhine-Westphalia. The bake needs about 7 GB of disk for each GB of PBF. Each profile adds 8.125 B for each road, 4 B for each turn and 24 B for each junction (the landmark tables).
  • The cgroup reader walks up the tree. It takes the level with the least free memory (memory.max less its own anon), so a limit on a parent slice counts. It reads cgroup v2 only; on cgroup v1 the budget does not use the cgroup.
  • The thread test uses a ladder graph in lib.rs whose ways differ from chunk to chunk, with a chunk of 8 roads under cfg(test). A second test compares the costs of the chunks with the costs of each road computed alone.
  • A parallel pass returns the first error in chunk order, for each thread count.
  • All package writes happen in a writer stage after the passes, in the order of today.
  • The landmark tables are written by Distances::write. Costing is a wrapper over road_pass for one profile, for the tests. Closures::build of planner/router is gone. The profile-job formula uses the point count of the graph as J.
  • Measured (4 cores, 15 GB RAM): the Switzerland bake takes 367 s (467 s before); the three passes take 27 % of the profile stage before the change, and they are 3.1 times faster on 4 threads than on 1. On North Rhine-Westphalia "Preparing" takes 110 s (265 s before), and 190 s (284 s before) in a memory cgroup of 1.42 GB.
  • Germany did not run: the cloud container has 30 GB of disk. The Germany bake of "Done when" is open.
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