Bug #22313
open
Bytecode 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