Bug #22313
closedBytecode compilation is quadratic in the size of a method due to remove_unreachable_chunk
Description
Compiling one large method whose body contains many unconditional jumps takes time quadratic in the size of the method.
Reproduction¶
def build(units)
src = +"def f(x)\n"
units.times do |i|
src << " while x < #{i}\n x = x + 1\n next if x == #{i}\n break if x > #{i}\n end\n return x if x == #{i}\n"
end
src << " x\nend\n"
end
[5_000, 10_000, 20_000].each do |units|
src = build(units)
t = Process.clock_gettime(Process::CLOCK_MONOTONIC)
RubyVM::InstructionSequence.compile(src)
printf("%6d units: %5.2f s\n", units, Process.clock_gettime(Process::CLOCK_MONOTONIC) - t)
end
On ruby 4.1.0dev (2026-09-14T06:17:27Z master d973aef325) +PRISM [arm64-darwin25] (Apple M1 Pro):
Doubling the method's size quadruples the compile time.
Ruby 4.0.4 behaves the same.
Cause¶
remove_unreachable_chunk in compile.c allocates a counter array sized by the method's label count and clears it on every call:
int *unref_counts = 0, nlabels = ISEQ_COMPILE_DATA(iseq)->label_no;
if (!i) return 0;
unref_counts = ALLOCA_N(int, nlabels);
MEMZERO(unref_counts, int, nlabels);
iseq_peephole_optimize calls it for every unconditional jump and leave it visits, and both the number of those calls and label_no grow linearly with the method, so MEMZERO alone costs O(jumps x labels) per method.
A profile of the reproduction spends most of its compile time in __bzero under iseq_peephole_optimize -> remove_unreachable_chunk.
As a side note, ALLOCA_N is also unbounded: a method with tens of thousands of labels puts hundreds of kilobytes on the C stack per call.
Updated by make_now_just (Hiroya Fujinami) 2 months ago
- Description updated (diff)
Updated by make_now_just (Hiroya Fujinami) 2 months ago
I created a pull request to fix it: https://github.com/ruby/ruby/pull/18823
Updated by make_now_just (Hiroya Fujinami) about 1 month ago
- Status changed from Open to Closed
Applied in changeset git|8993cb5a3c87dcad17904bd8a0b69e235baf03e9.
Make remove_unreachable_chunk linear in method size (#18823)
- Make remove_unreachable_chunk linear in method size
remove_unreachable_chunk allocated and cleared a label_no-sized
counter array on every call, and iseq_peephole_optimize calls it for
every unconditional jump and leave, so compiling a method cost
O(jumps * labels): quadratic in the size of the method.
Keep one scratch table in iseq_compile_data and stamp each entry with
a generation, so a new call invalidates the table by bumping the
generation instead of clearing it. The arrays live in the compile
arena and grow by doubling; a stamp wrap-around falls back to one
full clear. This also removes an unbounded ALLOCA_N sized by
label_no.
The compiled output is unchanged: the reproducer corpus compiles to
byte-identical iseq binaries, and the reproducer drops from 3.6 s to
0.13 s.
[Bug #22313]
- Make unreachable_unref fields local struct
https://github.com/ruby/ruby/pull/18823#issuecomment-5769711739
-
Use ALLOCV_N instead of VLA
-
Add a test case
-
Remove the test case previously added