dc53a3e8fd (master): Avoid quadratic compilation of and/or chains
0 views
Skip to first unread message
TSUYUSATO Kitsune
3:11 AM (14 hours ago) 3:11 AM
to ruby...@g.ruby-lang.org
TSUYUSATO Kitsune 2026-09-05 07:39:51 +0000 (Sat, 05 Sep 2026)
New Revision: dc53a3e8fd
https://github.com/ruby/ruby/commit/dc53a3e8fd
Log:
Avoid quadratic compilation of and/or chains
The value-context NODE_AND / NODE_OR compiled nd_2nd recursively, so a
chain such as `a && b && c` gave each operator its own end label. The
peephole optimizer then collapsed that chain of labels, walking the
whole chain from every branch, which is quadratic in the chain length:
compiling 8000 operators spent about 0.9 s in iseq_peephole_optimize.
Fold a run of the same operator into a single shared end label so every
branch targets it directly, as compile_branch_condition already does
for the condition context. The peephole pass then has nothing to
thread and compilation is linear. The produced bytecode is unchanged:
disasm is byte-identical across left-associative, parenthesized, and
mixed and/or chains.
Modified files:
compile.c
New Revision: dc53a3e8fd
https://github.com/ruby/ruby/commit/dc53a3e8fd
Log:
Avoid quadratic compilation of and/or chains
The value-context NODE_AND / NODE_OR compiled nd_2nd recursively, so a
chain such as `a && b && c` gave each operator its own end label. The
peephole optimizer then collapsed that chain of labels, walking the
whole chain from every branch, which is quadratic in the chain length:
compiling 8000 operators spent about 0.9 s in iseq_peephole_optimize.
Fold a run of the same operator into a single shared end label so every
branch targets it directly, as compile_branch_condition already does
for the condition context. The peephole pass then has nothing to
thread and compilation is linear. The produced bytecode is unchanged:
disasm is byte-identical across left-associative, parenthesized, and
mixed and/or chains.
Modified files:
compile.c
Reply all
Reply to author
Forward
0 new messages