Ruby

Bug #22313

Updated by make_now_just (Hiroya Fujinami) 16 days ago

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` jump and `leave` leave it visits, and both the number of those calls and label_no grow linearly with the method, so `MEMZERO` 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.

Back