Repository navigation
Open
Description
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:
- First measure where the time goes: for each cut, the phases of the flow, the junctions that each phase visits, and the time of each level of the recursion.
- Then make the work of one cut smaller without a change of the cut. The cut of Routing bake: the partition into nested cells, and the roads in cell order #3300 is the minimal cut on the source side, which is the same for each maximum flow, so a faster flow gives the same cells. The partition SHA-256 of Routing bake: the partition into nested cells, and the roads in cell order #3300 is the proof.
- The candidates are in the Plan, in the order of their cost. Each one stays only when the measurement shows that it helps.
- When no candidate that keeps the cells reaches the target, the pull request reports the measurements and proposes a change of the cells to the owner. It does not build that change.
Rejected: - Defer this to the Europe bake (workstream 8 of EPIC — Scale readiness: 100 concurrent users, long routes, from one region to the world #3000): Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 measures Germany and chooses the level sizes, and it must measure the partition that Europe will use.
- A narrower band between the two sides of a cut (for example the first and the last 45 % of the junctions as the two sides): the flow gets much smaller, but the cells change and can get more border roads. The owner decides this with measured border roads, not this issue.
- Another partition method (for example a multilevel graph partitioner): Routing: hierarchical search and disk storage #3227 chose inertial flow, and its cells are proven by the prototype.
Systems: routing
Contracts: none
Size: S (1 system, 1 file, no contract change, no stored byte changes)
Branch:routing-overlay
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 and280974c9…for North Rhine-Westphalia, for 1 and for 4 threads. The manifest ID of Switzerland is979675e1…. The shared bake folder of the container has the full values and the command of the gate. - For each cut,
Part::flowinplanner/router-build/src/partition.rsruns 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::joinstarts 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
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.- 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.
- Take the counters of step 1 out again, or keep one summary line when the bake log needs it.
- 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
obc test -p planner-router-buildandobc exec cargo clippy -p planner-router-build --all-targets -- -D warnings.- Switzerland and North Rhine-Westphalia give the partition SHA-256 of Routing bake: the partition into nested cells, and the roads in cell order #3300, for 1 and for 4 threads, and Switzerland gives the manifest ID of Routing bake: the partition into nested cells, and the roads in cell order #3300.
- In a cloud container with 4 cores and 15 GB of RAM, the pull request records the time of the partition for Switzerland, North Rhine-Westphalia and the largest region that fits the disk of the container, with the junction count of each. Between each two regions the time grows at most 1.1 times as fast as n log n. The owner chose this mark: n log n is what one sort of the junctions for each level costs, and the flow must not cost more than that order.
- The own peak of the partition is at most 60 B for each junction.
- The pull request gives the estimate for Germany and for Europe from the measured growth. Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310 measures Germany.
- When the mark is not reached with the same cells, the pull request says so, gives the tables of step 1 for the best state, and proposes the next step to the owner.
Out of scope
- A change of the cells, the level sizes or the balance of a cut: the level sizes belong to Proof on Germany: the bake, the level sizes, the download level, the old engine against the new one #3310.
- The Germany and the Europe runs.
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
Labels
No labels
Activity
perf(router-build): take the capacity of an arc from the residuals
test(router-build): the shared bound of the directions of a cut