Project

General

Profile

Actions

Bug #22313

closed

Bytecode compilation is quadratic in the size of a method due to remove_unreachable_chunk

Bug #22313: Bytecode compilation is quadratic in the size of a method due to remove_unreachable_chunk

Added by make_now_just (Hiroya Fujinami) 2 months ago. Updated about 1 month ago.

Status:
Closed
Target version:
ruby -v:
ruby 4.0.4 (2026-05-12 revision b89eb1bcbf) +PRISM [arm64-darwin25]
[ruby-core:126689]

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):

  5000 units:  0.25 s
 10000 units:  1.08 s
 20000 units:  4.38 s

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 Actions #1

  • Description updated (diff)

Updated by make_now_just (Hiroya Fujinami) about 1 month ago Actions #3

  • 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

Actions

Also available in: PDF Atom