Skip to content

D154 — Late reachability proof on long strict searches, and speed-ups that keep the output

Context

A speed review (doc 05 §62, records in bench/records/d154-speed) profiled five hard PCBench boards with gprof, one variant at 20 M work. The A* loop took 27–57 % of CPU, CPU cost-to-go fields 14–33 %. Every board spent its whole budget in the strict first pass, and most of it went to a few failed searches: 77 % of logicbone's budget (15 searches), 84 % of sbc's (108), 91 % of kitspace_d20's (60). Most of those failures exhaust a region from which no path exists. The pre-check of doc 05 §13 proves that cheaply, but run before every strict search (--reach-check 2) it also floods every search that would succeed in a few hundred expansions. On LeeChee_1800, 28 % of the run was the exact inside-board test against a 572-edge outline. The per-class obstacle caches held a full board lattice per class: 1.6 GB per router on Teensy_test_layout.

Decision

  1. Late reachability proof, on by default: RouterOptions::reach_after = 100,000 and reach_after_cap = 10,000 (--reach-after, --reach-after-cap; 0 turns it off or removes the cap). A strict search to a pad that has expanded reach_after states, and had no pre-check, floods forward from its sources and backward from its targets, a cell in turn, over the pre-check's moves. The backward flood follows the reverse of each forward move. When one flood runs out before they meet, there is no path: the search stops as an enclosure ("boxed in", or "boxed in (target)" for the target end) or as a window miss when that region touched the window edge. When they meet, or the floods have visited reach_after_cap cells, the A* continues unchanged. Flood cells are charged at flood_work_pct. --reach-verify covers the proof too.
  2. Same output, less time or memory:
  3. The CPU field sweeps a row at a time and is vectorised (field_cpu; the old sweeps are field_cpu_reference, compared in a test).
  4. The inside-board test reads only the edges of the point's raster row (Obstacles::inside_exact, reference inside_exact_linear, compared in a test).
  5. The per-class caches are LazyCodes, allocated in 4,096-code chunks on first write.
  6. A search's target marks live in a reused buffer.

Alternatives

  • --reach-check 2 everywhere. Doc 05 §13 already measured it: swings both ways, because successful searches pay for the flood. The late proof leaves searches that end within 100,000 expansions alone.
  • No flood cap. It loses on Teensy (1,090 → 1,080 at 20 M) and LeeChee (1,010 → 991). On those boards long searches do succeed, and their floods met only after ~70,000 cells.
  • Earlier trigger (30,000 or 50,000). Without the cap, 30,000 lost 115 connections on LeeChee. With the cap, 50,000 matched 100,000 except on sbc (345 against 341) and cost more CPU on LeeChee.
  • Field only for long searches (--field-after), off. Field time fell, but total CPU rose (LeeChee 18.3 → 25.6 s), because the octile phase spreads over more cells and their legality checks.
  • Ties to the deeper state (--tie-deep), off. Mixed: sbc 341 → 333, Teensy 1,093 → 1,095.
  • -O3 with LTO. About 1 %.
  • A vector heap of structs for the open list. 4–8 % slower than std::priority_queue of pairs, so the queue stays and its container is used for the re-key.

Consequences

Measured (doc 05 §62):

  • Quick tier (1 M work): byte-identical on 30/30 boards, with 22 % less route CPU.
  • Mid tier (20 M work, 8 variants): 7/11 boards byte-identical, and the other four route as many or more (EEZ +21, decelerator +10, LimeSDR +3, logicbone equal). Route CPU falls 29 %.
  • One variant: the old router needs 1.4× (logicbone) to 2.6× (kitspace_d20) the CPU time to reach the same routed count.
  • Wall clock: at 60 s with 8 variants, the mid tier routes 9,349 → 9,401. At 120 s, tier B is clean 29 → 29 and routes 5,197 → 5,198; tier C is clean 16 → 17 and routes 9,529 → 9,537. Route CPU is 4–5 % lower: the boards that finish early mostly finish sooner.
  • Memory: per router, 1.6 → 0.56 GB on Teensy and 1.65 → 0.44 GB on logicbone.
  • Global router: a LeeChee --global run went from 158 s to 7.5 s, which explains doc 05 §19's set-up wart.

The proof covers strict searches only; negotiated (soft) searches and breakout boards (pre-check on every strict search) do not use it. Docs changed: 05 (§19, §62), 07 (§5 field row).