Skip to content

Routing bake: the time of the partition grows about as n log n #3381

Open

Description

@timohueser

Status: approved

Part of #3227.
Depends on: #3300

TL;DR

Goal: The partition of #3300 gives the same cells in a time that grows about as n log n with the junction count n. Germany takes minutes and Europe about one to two hours on 4 cores, as #3227 assumes.
Problem: The time of the partition grows about as n^1.8. Scaled from the two measured regions, Germany takes 30 to 70 minutes and Europe about 17 hours [est]. The partition runs again at each new OSM cut, so this stops the Europe bake.
Decision:

Facts

  • Measured in a cloud container with 4 cores and 15 GB of RAM, after the review fixes of pull request Routing bake: the partition into nested cells, and the roads in cell order #3366: Switzerland, 3.09 million junctions, 73.8 s on 4 threads and 160.9 s on 1 thread; North Rhine-Westphalia, 3.99 million junctions, 116.1 s. So 1.29 times the junctions take 1.57 times the time. The prototype of Routing: hierarchical search and disk storage #3227 took 52 s for Switzerland.
  • The partition SHA-256 is 612ae937… for Switzerland and 280974c9… for North Rhine-Westphalia, for 1 and for 4 threads. The manifest ID of Switzerland is 979675e1…. The shared bake folder of the container has the full values and the command of the gate.
  • For each cut, Part::flow in planner/router-build/src/partition.rs runs a maximum flow for each of the four directions. The sources are the first quarter of the junctions along the direction and the sinks are the last quarter. Each phase searches from the border of the sources through each junction that it can reach, which is about half of the part. The number of phases grows with the hop distance across the part.
  • A phase does not stop its search at the level of the first sink. With that stop the cut stayed the same, but Switzerland took 371.5 s, because each phase then pushed flow on the shortest paths only.
  • The first cut of a region runs on one thread: rayon::join starts after it. The four directions of one cut run one after the other, with one set of work arrays.
  • The partition holds 36 B for each junction and 6 B for each arc, about 52 B for each junction. The gate of Routing bake: the partition into nested cells, and the roads in cell order #3300 is 60 B for each junction.
  • The value of a cut is small against the part: the largest cells of level 4 have 208 to 237 entering border roads on the two regions.

Plan

  1. partition.rs: count, for each cut and each direction, the phases, the junctions that all phases visit together, and the time; print one line for each level of the recursion at the end of the partition. Run Switzerland and North Rhine-Westphalia and put the two tables into the pull request. They show which of the next steps can help.
  2. Try the candidates in this order. After each one, the partition SHA-256 of both regions must be the value of Routing bake: the partition into nested cells, and the roads in cell order #3300, for 1 and for 4 threads. Keep a candidate only when the time of both regions falls.
    • Fewer visits in a phase. Search from the two sides at once, or keep the levels of the last phase and repair only what a push changed, so that a phase does not walk the whole band again.
    • Fewer junctions in the flow. Before the flow of a cut, join each chain of junctions with two neighbours into one arc, with the smallest capacity of the chain. A junction of a chain goes to the side that the minimal cut on the source side gives it in the full graph; a test with chains of unequal capacities checks this against the flow on the full graph.
    • Stop a direction early. A direction whose flow passes the best cut value of the directions before it cannot win: stop it. The order of the directions and the tie rule between them stay, so the chosen direction stays.
    • The four directions of the first cuts at the same time. Only when the three candidates before it are not enough, and only inside the gate of 60 B for each junction at the peak: the pull request gives the peak.
  3. Take the counters of step 1 out again, or keep one summary line when the bake log needs it.
  4. Tests. partition.rs: each kept candidate gets a test that compares its cut with the cut of the plain flow on small graphs with ties, chains, islands and parallel roads. The tests of Routing bake: the partition into nested cells, and the roads in cell order #3300 stay as they are.

Files

  • planner/router-build/src/partition.rs: change: the flow of a cut, its tests.
  • planner/router-build/README.md: change: the time of the partition, if it names one.

Done when

Out of scope

Progress

Pull request #3387 is a partial step, merged into routing-overlay. The mark is not reached.

  • Kept: the levels of a phase start above those of the phases before it, so no phase walks its junctions again to reset them. Switzerland takes 59.7 s (73.8 s before) and North Rhine-Westphalia 98.2 s (116.1 s before), on 4 cores; the partition SHA-256 of both regions is that of Routing bake: the partition into nested cells, and the roads in cell order #3300, for 1 and for 4 threads. The own peak is about 52 B for each junction.
  • Dropped, because the time rose: one search tree kept through the whole flow; chains of junctions with two neighbours joined into one arc.
  • Not built: "stop a direction early" is in Routing bake: the partition into nested cells, and the roads in cell order #3300 already. The four directions at the same time need about 66 B for each junction, above the gate of 60 B.
  • Against the mark: from Switzerland to North Rhine-Westphalia the time grows 1.65 times; the mark allows 1.44. The first cut of a region runs on one thread and its work grows (134 phases against 227). From depth 1 down, the work grows 1.02 times as fast as n log n, inside the mark. The two regions differ in shape, so the estimates from them are weak: Germany about 31 minutes, Europe about 12 hours.
  • Next step, with the owner: the four directions of a cut at the same time. It keeps the cut, and on the first cut of North Rhine-Westphalia the four directions take 54.5 s one after the other against 17.5 s for the slowest one. It needs a gate of about 66 B for each junction.
  • Not measured: a third, larger region and the full Switzerland bake (disk).

Pull request #3487 is a second partial step, merged into routing-overlay. The mark is not reached.

  • Built: two directions of a cut run at the same time. The owner allowed 66 B for each junction on 2026-11-15; four directions at the same time need about 92 B. A direction stops when its flow passes the smallest cut of the directions that finished, so the chosen cut does not change. The capacity array is gone: a direction takes the capacity of an arc from the residuals of the arc and its twin. The need is 48 B for each junction and 6 B for each arc, about 64 B for each junction. The measured own peak is 63.7 B for each junction on Switzerland and 63.8 B on North Rhine-Westphalia.
  • The same cells: the partition SHA-256 is the same before and after, for 1 and for 4 threads, on both regions (the extracts of 2026-11-13).
  • Time on 4 threads: Switzerland takes 40.2 s (51.2 s before) and North Rhine-Westphalia 72.1 s (90.1 s before). On 1 thread the time does not change. The first cut takes 16.4 s on Switzerland (23.1 s before) and 33.6 s on North Rhine-Westphalia (51.5 s before): it still uses 2 of the 4 cores.
  • Against the mark: from Switzerland to North Rhine-Westphalia the time grows 1.79 times (1.76 before); the mark allows 1.44. Weak estimates from the two regions: Germany about 38 minutes, Europe about 48 hours.
  • Next step, with the owner: pull request perf(router-build): two directions of a cut at the same time in the partition #3487 names the options.

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