perf: Skip relaxation iteration early when no rescan candidates remain - #1582
Conversation
davidlattimore
left a comment
There was a problem hiding this comment.
No change in performance for linking wild-riscv, but maybe this optimisation affects other benchmarks, just not that one.
|
I suspect that, for example in the case of call relaxations, there are many call instructions whose address offsets exceed 1MB, which likely prevents |
c92ef1d to
557a05e
Compare
|
In addition to this version, I incorporated some debug output and built Wild debug build for RISC-V to conduct experiments. The relaxation iteration skipping mechanism implemented here utilizes the condition that the address change amount in the next iteration must be less than or equal to the amount reduced ( In my environment, the first iteration successfully reduced 60,960 bytes, leaving 150 remaining relaxation candidates at this point. However, the introduced filtering reduced the candidate count to just 10 sections, and by the end of the next iteration, there were 5 remaining candidates—which were then further reduced to 0 through filtering. In other words, while previous implementations required at least 3 full section scans, this implementation achieves the same result with 2 iterations, with each iteration scanning a smaller portion of the data. However, it is still unclear for me whether section scanning or this filtering has a greater impact on link time. |
davidlattimore
left a comment
There was a problem hiding this comment.
With those changes I now see a speedup:
Benchmark 1 (578 runs): /home/david/save/wild-riscv/run-with env-rand /home/d/wild-builds/2026-02-23.cg1 --no-fork
measurement mean ± σ min … max outliers delta
wall_time 51.9ms ± 1.10ms 49.0ms … 55.6ms 5 ( 1%) 0%
peak_rss 173MB ± 728KB 171MB … 176MB 8 ( 1%) 0%
cpu_cycles 1.21G ± 23.4M 1.12G … 1.33G 16 ( 3%) 0%
instructions 1.53G ± 14.8M 1.49G … 1.63G 13 ( 2%) 0%
cache_references 33.8M ± 503K 31.6M … 36.4M 19 ( 3%) 0%
cache_misses 6.18M ± 103K 5.86M … 6.78M 20 ( 3%) 0%
branch_misses 2.77M ± 32.2K 2.66M … 2.96M 14 ( 2%) 0%
Benchmark 2 (595 runs): /home/david/save/wild-riscv/run-with env-rand target/cg1/wild --no-fork
measurement mean ± σ min … max outliers delta
wall_time 50.4ms ± 1.05ms 46.9ms … 53.5ms 4 ( 1%) ⚡- 2.9% ± 0.2%
peak_rss 169MB ± 758KB 166MB … 171MB 3 ( 1%) ⚡- 2.7% ± 0.0%
cpu_cycles 1.16G ± 24.2M 1.06G … 1.25G 17 ( 3%) ⚡- 3.9% ± 0.2%
instructions 1.48G ± 15.3M 1.41G … 1.55G 17 ( 3%) ⚡- 3.8% ± 0.1%
cache_references 32.3M ± 518K 30.6M … 34.3M 13 ( 2%) ⚡- 4.3% ± 0.2%
cache_misses 5.87M ± 108K 5.46M … 6.30M 14 ( 2%) ⚡- 5.1% ± 0.2%
branch_misses 2.66M ± 34.9K 2.52M … 2.81M 11 ( 2%) ⚡- 4.0% ± 0.1%
Nice!
When all per-file rescan lists from the previous iteration are empty, no section can produce new relaxations regardless of address changes. Detect this before calling
compute_section_and_symbol_addresses()to avoid an unnecessary O(sections + symbols) traversal on the final iteration.