From: "make_now_just (Hiroya Fujinami) via ruby-core" Date: 2026-09-14T06:55:40+00:00 Subject: [ruby-core:126689] [Ruby Bug#22313] Bytecode compilation is quadratic in the size of a method due to remove_unreachable_chunk Issue #22313 has been reported by make_now_just (Hiroya Fujinami). ---------------------------------------- Bug #22313: Bytecode compilation is quadratic in the size of a method due to remove_unreachable_chunk https://bugs.ruby-lang.org/issues/22313 * Author: make_now_just (Hiroya Fujinami) * Status: Open * Assignee: make_now_just (Hiroya Fujinami) * Target version: 4.0 * ruby -v: ruby 4.0.4 (2026-05-12 revision b89eb1bcbf) +PRISM [arm64-darwin25] * Backport: 3.3: UNKNOWN, 3.4: UNKNOWN, 4.0: UNKNOWN ---------------------------------------- Compiling one large method whose body contains many unconditional jumps takes time quadratic in the size of the method. ## Reproduction ```ruby 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: ```c 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 the 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. -- https://bugs.ruby-lang.org/ ______________________________________________ ruby-core mailing list -- ruby-core@ml.ruby-lang.org To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/