Issue #22182 has been updated by byroot (Jean Boussier).

String has no spare flag bits

[Feature #22137] will free one bit on T_STRING if accepted, but I was planning to use it to record whether a string contains NUL bytes or not (repeated `null_check` are costly). Given you need a flag on at least 3 distinct types, it might make sense to use `RUBY_FL_UNUSED6` or `RUBY_FL_UNUSED10`? ---------------------------------------- Feature #22182: Optimize method chains by destructively updating intermediate objects https://bugs.ruby-lang.org/issues/22182#change-117967 * Author: mame (Yusuke Endoh) * Status: Open ---------------------------------------- This is an experimental optimization idea that speeds up typical method chains by destructively updating their intermediate objects. Intuitively, it works like this: * `str.strip.upcase` runs like `str.strip.upcase!` * `ary.map {}.select {}` runs like `ary.map {}.select! {}` * `"foo" + str + str` runs like `"foo" << str << str` As a bonus: * `foo(**opts.merge(default))` passes the merged hash to the callee as-is, without `Hash#dup` ## Microbenchmarks 1-second measurement windows, average of 5 alternating rounds (µs/call). |Code|Before|After|Speedup|Setup| |--|--|--|--|--| |`str + str + str`| 0.127 µs | 0.088 µs | 1.44x |`str = "x" * 100`| |`ary + ary + ary`| 0.645 µs | 0.304 µs | 2.12x |`ary = (0..99).to_a`| |`"foo" + str`| 0.083 µs | 0.056 µs | 1.50x |`str = "bar"`| |`ary.map { it+1 }.select { it.even? }`| 6.86 µs | 6.64 µs | 1.03x |`ary = (0..99).to_a`| |`str.strip.upcase`| 0.099 µs | 0.090 µs | 1.10x |`str = " foo "`| |`"#{a}#{b}".strip`| 0.110 µs | 0.103 µs | 1.07x |`a = "abcdefgh"; b = "ijklmnop"`| |`ary.uniq.sort.reverse`| 38.7 µs | 36.4 µs | 1.06x |`ary = (0..999).map { it % 500 }.shuffle`| |`foo(**opts.merge(default))`| 0.557 µs | 0.489 µs | 1.14x |`def foo(**kw) = kw; opts = (0...10).to_h { [:"o#{it}", it] }; default = (0...10).to_h { [:"d#{it}", it] }`| Allocations go down as well (e.g. `str + str + str` goes from 2 objects to 1). ## How it works In one sentence: a limited form of escape analysis, specialized for method chains. We introduce flags (`STR_FRESH` / `ARY_FRESH` / `HASH_FRESH`) for `String` / `Array` / `Hash` objects whose only reference is guaranteed to be a single value-stack slot. Since no one else can observe a flagged object, the next operation may reuse it destructively. A few instructions are added. The typical one is `opt_plus_fresh`. For example, `str1 + str2 + str3` compiles and runs as: ``` getlocal str1 getlocal str2 opt_plus_fresh # concatenate into a new String and set STR_FRESH on it; since it will # almost certainly be appended to, allocate with extra (2x) capacity getlocal str3 opt_plus # if the receiver has STR_FRESH, append in place instead of # allocating a new object ``` `ary.map {}.select {}` compiles and runs as: ``` getlocal ary send :map (callinfo: VM_CALL_FRESH_PROD) # if the method cache resolved to the built-in # Array#map, set ARY_FRESH on the resulting array send :select (callinfo: VM_CALL_FRESH_CONS) # if the method cache resolved to the built-in # Array#select and the receiver has ARY_FRESH, # call the select!-style destructive implementation ``` There are also a few instructions that create objects with the FRESH flag set (`newarray_fresh`, `duparray_fresh`, `dupstring_fresh`, `concatstrings_fresh`). These make `"foo" + str`, `[1, 2, 3].sort` and `"#{a}#{b}".strip` destructive as well. ## PoC implementation Implemented by Claude Code (Fable 5). Still a proof of concept. https://github.com/ruby/ruby/pull/17685 9 commits: 1. Add the STR_FRESH / ARY_FRESH / HASH_FRESH object flags (+ clearing in ObjectSpace.each_object) 2. Preparatory refactoring: extract str_enc_buf_new0() from str_enc_new() 3. String#+ chains: reuse the intermediate in place (opt_plus_fresh / dupstring_fresh) 4. Array#+ chains: same 5. Built-in String chains: apply destructive counterparts to fresh receivers (strip.downcase, sub with arguments, interpolated heads, ...) — also introduces the common machinery (unconditional callinfo bits + fresh_producer/fresh_consumer method entry bits + the table) 6. Built-in Array chains (map/select/... + take/drop + split/to_a/flat_map/sort_by/set-operation producers + literal heads like `[3,1,2].sort`) 7. Built-in Hash chains (merge/transform_values/select/reject/compact) 8. Hand over fresh splat / kw-splat operands (`f(*xs.map {})` / `foo(**opts.merge(default))` skip the defensive copy — a runtime generalization of the existing `VM_CALL_ARGS_SPLAT_MUT` / `KW_SPLAT_MUT`) 9. Minimal YJIT support (+ chains are also fused in JITed code; built-in send chains stay inactive but sound. Same for ZJIT.) ## Implementation notes This optimization needs delicate care so that FRESH-flagged objects never leak into ordinary code. Optimization is therefore applied only in very restricted situations: * Only chains that use known method names (`map`, `select`, ...) are optimized. (This prevents a leak through e.g. `ary.map {}.tap { it }`.) * Optimization applies only while none of those `String`/`Array`/`Hash` methods are redefined. * `ObjectSpace.each_object` clears the FRESH flag of every object it yields. * A receiver passed to `method_missing` has its FRESH flag cleared. * In case a target method is redefined in the middle of a chain, a consumer site whose call cache was invalidated clears the receiver's FRESH flag. There may be other paths through which a FRESH object can leak; please let me know if you spot one. In principle this should almost never slow down ordinary code: the only cost is one FRESH flag test in `opt_plus` for String and Array. Indeed, a plain `str + str` (not optimized) measured 0.071 µs both before and after the patch (1.00x). Fixnum `+`, standalone `merge` / `sort`, `foo(**h)` etc. all measured 0.98-1.03x. ## Limitations String has no spare flag bits, so the PoC reuses STR_PRECOMPUTED_HASH == STR_FRESH: the bit is read as STR_PRECOMPUTED_HASH on frozen strings and as STR_FRESH on unfrozen ones. Under `frozen-string-literal: true`, `"foo" + str` is currently not optimized (perhaps improvable?). YJIT support is provisional. `+` chains are fused in JITed code too, but the destructive reuse in built-in send chains only happens in interpreted execution. In particular, with a JIT enabled, Array chains are disabled entirely (YJIT redefines `Array#map` / `Array#select` in Ruby, which trips the redefinition detection, unfortunate). Only prism is supported for now (parse.y is not). There are probably other things I have missed. ## Discussion Ordinary code does not get slower, and some code skips intermediate allocations entirely, so I believe this is essentially all upside. That said, keeping FRESH objects from leaking makes this a fairly intricate and delicate optimization, so I would like to hear from VM and JIT developers. Whether this shows up in "macro" benchmarks is questionable: code like `"foo" + str + str + str`, where the optimization shines, has traditionally been avoided, and the intermediate objects it eliminates would almost certainly have been collected by minor GC anyway, so they rarely amount to real GC pressure. Still, having common idioms like `"foo" + str` or `ary.uniq.sort.reverse` get 1.1-1.5x faster is a nice thing, and reducing the general uneasiness about "this creates an intermediate array" seems worthwhile, IMO. What do you think? -- https://bugs.ruby-lang.org/

Issue #22182 has been updated by mame (Yusuke Endoh). Subject changed from Optimize method chains by destructively updating intermediate objects to Poor man's escape analysis Thanks for your comment. I stole "poor man's escape analysis" for the ticket subject. :-)

specialized instruction for a select few methods

The current PoC doesn't add a specialized instruction per method. It only prepares `_fresh` variants of three kinds of instructions: the object-producing ones (`dupstring` etc.), the general `send` instruction, and the existing specialized instruction `opt_plus`. (To be precise, it adds a `FRESH` flag for `send` callinfo, instead of adding `send_fresh` opcode.) On the JIT: I think it's doable in principle. In my PoC, the bytecode compiler (prism_compile.c) emits `_fresh` variant instructions instead of normal ones; a JIT could do the same conversion during machine-code generation. But I'm not sure which is better. `Primitive.attr!` looks elegant, but you'd still have to handle FRESH-flagged objects carefully either way, and I suspect that a method written in Ruby could have more subtle escape routes. (Writing this, I actually found one in the current PoC: in `ary.map { $obj = (grab map's accumulator array via each_object) }.select { ... }`, the block leaks the FRESH-flagged object. `Array#map` needs to set the FRESH flag as soon as it allocates the result array.) ---------------------------------------- Feature #22182: Poor man's escape analysis https://bugs.ruby-lang.org/issues/22182#change-117971 * Author: mame (Yusuke Endoh) * Status: Open ---------------------------------------- This is an experimental optimization idea that speeds up typical method chains by destructively updating their intermediate objects. Intuitively, it works like this: * `str.strip.upcase` runs like `str.strip.upcase!` * `ary.map {}.select {}` runs like `ary.map {}.select! {}` * `"foo" + str + str` runs like `"foo" << str << str` As a bonus: * `foo(**opts.merge(default))` passes the merged hash to the callee as-is, without `Hash#dup` ## Microbenchmarks 1-second measurement windows, average of 5 alternating rounds (µs/call). |Code|Before|After|Speedup|Setup| |--|--|--|--|--| |`str + str + str`| 0.127 µs | 0.088 µs | 1.44x |`str = "x" * 100`| |`ary + ary + ary`| 0.645 µs | 0.304 µs | 2.12x |`ary = (0..99).to_a`| |`"foo" + str`| 0.083 µs | 0.056 µs | 1.50x |`str = "bar"`| |`ary.map { it+1 }.select { it.even? }`| 6.86 µs | 6.64 µs | 1.03x |`ary = (0..99).to_a`| |`str.strip.upcase`| 0.099 µs | 0.090 µs | 1.10x |`str = " foo "`| |`"#{a}#{b}".strip`| 0.110 µs | 0.103 µs | 1.07x |`a = "abcdefgh"; b = "ijklmnop"`| |`ary.uniq.sort.reverse`| 38.7 µs | 36.4 µs | 1.06x |`ary = (0..999).map { it % 500 }.shuffle`| |`foo(**opts.merge(default))`| 0.557 µs | 0.489 µs | 1.14x |`def foo(**kw) = kw; opts = (0...10).to_h { [:"o#{it}", it] }; default = (0...10).to_h { [:"d#{it}", it] }`| Allocations go down as well (e.g. `str + str + str` goes from 2 objects to 1). ## How it works In one sentence: a limited form of escape analysis, specialized for method chains. We introduce flags (`STR_FRESH` / `ARY_FRESH` / `HASH_FRESH`) for `String` / `Array` / `Hash` objects whose only reference is guaranteed to be a single value-stack slot. Since no one else can observe a flagged object, the next operation may reuse it destructively. A few instructions are added. The typical one is `opt_plus_fresh`. For example, `str1 + str2 + str3` compiles and runs as: ``` getlocal str1 getlocal str2 opt_plus_fresh # concatenate into a new String and set STR_FRESH on it; since it will # almost certainly be appended to, allocate with extra (2x) capacity getlocal str3 opt_plus # if the receiver has STR_FRESH, append in place instead of # allocating a new object ``` `ary.map {}.select {}` compiles and runs as: ``` getlocal ary send :map (callinfo: VM_CALL_FRESH_PROD) # if the method cache resolved to the built-in # Array#map, set ARY_FRESH on the resulting array send :select (callinfo: VM_CALL_FRESH_CONS) # if the method cache resolved to the built-in # Array#select and the receiver has ARY_FRESH, # call the select!-style destructive implementation ``` There are also a few instructions that create objects with the FRESH flag set (`newarray_fresh`, `duparray_fresh`, `dupstring_fresh`, `concatstrings_fresh`). These make `"foo" + str`, `[1, 2, 3].sort` and `"#{a}#{b}".strip` destructive as well. ## PoC implementation Implemented by Claude Code (Fable 5). Still a proof of concept. https://github.com/ruby/ruby/pull/17685 9 commits: 1. Add the STR_FRESH / ARY_FRESH / HASH_FRESH object flags (+ clearing in ObjectSpace.each_object) 2. Preparatory refactoring: extract str_enc_buf_new0() from str_enc_new() 3. String#+ chains: reuse the intermediate in place (opt_plus_fresh / dupstring_fresh) 4. Array#+ chains: same 5. Built-in String chains: apply destructive counterparts to fresh receivers (strip.downcase, sub with arguments, interpolated heads, ...) — also introduces the common machinery (unconditional callinfo bits + fresh_producer/fresh_consumer method entry bits + the table) 6. Built-in Array chains (map/select/... + take/drop + split/to_a/flat_map/sort_by/set-operation producers + literal heads like `[3,1,2].sort`) 7. Built-in Hash chains (merge/transform_values/select/reject/compact) 8. Hand over fresh splat / kw-splat operands (`f(*xs.map {})` / `foo(**opts.merge(default))` skip the defensive copy — a runtime generalization of the existing `VM_CALL_ARGS_SPLAT_MUT` / `KW_SPLAT_MUT`) 9. Minimal YJIT support (+ chains are also fused in JITed code; built-in send chains stay inactive but sound. Same for ZJIT.) ## Implementation notes This optimization needs delicate care so that FRESH-flagged objects never leak into ordinary code. Optimization is therefore applied only in very restricted situations: * Only chains that use known method names (`map`, `select`, ...) are optimized. (This prevents a leak through e.g. `ary.map {}.tap { it }`.) * Optimization applies only while none of those `String`/`Array`/`Hash` methods are redefined. * `ObjectSpace.each_object` clears the FRESH flag of every object it yields. * A receiver passed to `method_missing` has its FRESH flag cleared. * In case a target method is redefined in the middle of a chain, a consumer site whose call cache was invalidated clears the receiver's FRESH flag. There may be other paths through which a FRESH object can leak; please let me know if you spot one. In principle this should almost never slow down ordinary code: the only cost is one FRESH flag test in `opt_plus` for String and Array. Indeed, a plain `str + str` (not optimized) measured 0.071 µs both before and after the patch (1.00x). Fixnum `+`, standalone `merge` / `sort`, `foo(**h)` etc. all measured 0.98-1.03x. ## Limitations String has no spare flag bits, so the PoC reuses STR_PRECOMPUTED_HASH == STR_FRESH: the bit is read as STR_PRECOMPUTED_HASH on frozen strings and as STR_FRESH on unfrozen ones. Under `frozen-string-literal: true`, `"foo" + str` is currently not optimized (perhaps improvable?). YJIT support is provisional. `+` chains are fused in JITed code too, but the destructive reuse in built-in send chains only happens in interpreted execution. In particular, with a JIT enabled, Array chains are disabled entirely (YJIT redefines `Array#map` / `Array#select` in Ruby, which trips the redefinition detection, unfortunate). Only prism is supported for now (parse.y is not). There are probably other things I have missed. ## Discussion Ordinary code does not get slower, and some code skips intermediate allocations entirely, so I believe this is essentially all upside. That said, keeping FRESH objects from leaking makes this a fairly intricate and delicate optimization, so I would like to hear from VM and JIT developers. Whether this shows up in "macro" benchmarks is questionable: code like `"foo" + str + str + str`, where the optimization shines, has traditionally been avoided, and the intermediate objects it eliminates would almost certainly have been collected by minor GC anyway, so they rarely amount to real GC pressure. Still, having common idioms like `"foo" + str` or `ary.uniq.sort.reverse` get 1.1-1.5x faster is a nice thing, and reducing the general uneasiness about "this creates an intermediate array" seems worthwhile, IMO. What do you think? -- https://bugs.ruby-lang.org/

Issue #22182 has been updated by mame (Yusuke Endoh). Ah, I see. You were suggesting removing an object flag entirely. I thought the flag was necessary to hide fresh objects from reflection like `each_object`, as you said, but if we don't have to handle such a pathological case, then maybe the flag isn't necessary. We'd no longer need to check the flag (so probably faster), and we wouldn't have to worry about flagged objects leaking either, so it could be quite a bit simpler. ---------------------------------------- Feature #22182: Poor man's escape analysis https://bugs.ruby-lang.org/issues/22182#change-117975 * Author: mame (Yusuke Endoh) * Status: Open ---------------------------------------- This is an experimental optimization idea that speeds up typical method chains by destructively updating their intermediate objects. Intuitively, it works like this: * `str.strip.upcase` runs like `str.strip.upcase!` * `ary.map {}.select {}` runs like `ary.map {}.select! {}` * `"foo" + str + str` runs like `"foo" << str << str` As a bonus: * `foo(**opts.merge(default))` passes the merged hash to the callee as-is, without `Hash#dup` ## Microbenchmarks 1-second measurement windows, average of 5 alternating rounds (µs/call). |Code|Before|After|Speedup|Setup| |--|--|--|--|--| |`str + str + str`| 0.127 µs | 0.088 µs | 1.44x |`str = "x" * 100`| |`ary + ary + ary`| 0.645 µs | 0.304 µs | 2.12x |`ary = (0..99).to_a`| |`"foo" + str`| 0.083 µs | 0.056 µs | 1.50x |`str = "bar"`| |`ary.map { it+1 }.select { it.even? }`| 6.86 µs | 6.64 µs | 1.03x |`ary = (0..99).to_a`| |`str.strip.upcase`| 0.099 µs | 0.090 µs | 1.10x |`str = " foo "`| |`"#{a}#{b}".strip`| 0.110 µs | 0.103 µs | 1.07x |`a = "abcdefgh"; b = "ijklmnop"`| |`ary.uniq.sort.reverse`| 38.7 µs | 36.4 µs | 1.06x |`ary = (0..999).map { it % 500 }.shuffle`| |`foo(**opts.merge(default))`| 0.557 µs | 0.489 µs | 1.14x |`def foo(**kw) = kw; opts = (0...10).to_h { [:"o#{it}", it] }; default = (0...10).to_h { [:"d#{it}", it] }`| Allocations go down as well (e.g. `str + str + str` goes from 2 objects to 1). ## How it works In one sentence: a limited form of escape analysis, specialized for method chains. We introduce flags (`STR_FRESH` / `ARY_FRESH` / `HASH_FRESH`) for `String` / `Array` / `Hash` objects whose only reference is guaranteed to be a single value-stack slot. Since no one else can observe a flagged object, the next operation may reuse it destructively. A few instructions are added. The typical one is `opt_plus_fresh`. For example, `str1 + str2 + str3` compiles and runs as: ``` getlocal str1 getlocal str2 opt_plus_fresh # concatenate into a new String and set STR_FRESH on it; since it will # almost certainly be appended to, allocate with extra (2x) capacity getlocal str3 opt_plus # if the receiver has STR_FRESH, append in place instead of # allocating a new object ``` `ary.map {}.select {}` compiles and runs as: ``` getlocal ary send :map (callinfo: VM_CALL_FRESH_PROD) # if the method cache resolved to the built-in # Array#map, set ARY_FRESH on the resulting array send :select (callinfo: VM_CALL_FRESH_CONS) # if the method cache resolved to the built-in # Array#select and the receiver has ARY_FRESH, # call the select!-style destructive implementation ``` There are also a few instructions that create objects with the FRESH flag set (`newarray_fresh`, `duparray_fresh`, `dupstring_fresh`, `concatstrings_fresh`). These make `"foo" + str`, `[1, 2, 3].sort` and `"#{a}#{b}".strip` destructive as well. ## PoC implementation Implemented by Claude Code (Fable 5). Still a proof of concept. https://github.com/ruby/ruby/pull/17685 9 commits: 1. Add the STR_FRESH / ARY_FRESH / HASH_FRESH object flags (+ clearing in ObjectSpace.each_object) 2. Preparatory refactoring: extract str_enc_buf_new0() from str_enc_new() 3. String#+ chains: reuse the intermediate in place (opt_plus_fresh / dupstring_fresh) 4. Array#+ chains: same 5. Built-in String chains: apply destructive counterparts to fresh receivers (strip.downcase, sub with arguments, interpolated heads, ...) — also introduces the common machinery (unconditional callinfo bits + fresh_producer/fresh_consumer method entry bits + the table) 6. Built-in Array chains (map/select/... + take/drop + split/to_a/flat_map/sort_by/set-operation producers + literal heads like `[3,1,2].sort`) 7. Built-in Hash chains (merge/transform_values/select/reject/compact) 8. Hand over fresh splat / kw-splat operands (`f(*xs.map {})` / `foo(**opts.merge(default))` skip the defensive copy — a runtime generalization of the existing `VM_CALL_ARGS_SPLAT_MUT` / `KW_SPLAT_MUT`) 9. Minimal YJIT support (+ chains are also fused in JITed code; built-in send chains stay inactive but sound. Same for ZJIT.) ## Implementation notes This optimization needs delicate care so that FRESH-flagged objects never leak into ordinary code. Optimization is therefore applied only in very restricted situations: * Only chains that use known method names (`map`, `select`, ...) are optimized. (This prevents a leak through e.g. `ary.map {}.tap { it }`.) * Optimization applies only while none of those `String`/`Array`/`Hash` methods are redefined. * `ObjectSpace.each_object` clears the FRESH flag of every object it yields. * A receiver passed to `method_missing` has its FRESH flag cleared. * In case a target method is redefined in the middle of a chain, a consumer site whose call cache was invalidated clears the receiver's FRESH flag. There may be other paths through which a FRESH object can leak; please let me know if you spot one. In principle this should almost never slow down ordinary code: the only cost is one FRESH flag test in `opt_plus` for String and Array. Indeed, a plain `str + str` (not optimized) measured 0.071 µs both before and after the patch (1.00x). Fixnum `+`, standalone `merge` / `sort`, `foo(**h)` etc. all measured 0.98-1.03x. ## Limitations String has no spare flag bits, so the PoC reuses STR_PRECOMPUTED_HASH == STR_FRESH: the bit is read as STR_PRECOMPUTED_HASH on frozen strings and as STR_FRESH on unfrozen ones. Under `frozen-string-literal: true`, `"foo" + str` is currently not optimized (perhaps improvable?). YJIT support is provisional. `+` chains are fused in JITed code too, but the destructive reuse in built-in send chains only happens in interpreted execution. In particular, with a JIT enabled, Array chains are disabled entirely (YJIT redefines `Array#map` / `Array#select` in Ruby, which trips the redefinition detection, unfortunate). Only prism is supported for now (parse.y is not). There are probably other things I have missed. ## Discussion Ordinary code does not get slower, and some code skips intermediate allocations entirely, so I believe this is essentially all upside. That said, keeping FRESH objects from leaking makes this a fairly intricate and delicate optimization, so I would like to hear from VM and JIT developers. Whether this shows up in "macro" benchmarks is questionable: code like `"foo" + str + str + str`, where the optimization shines, has traditionally been avoided, and the intermediate objects it eliminates would almost certainly have been collected by minor GC anyway, so they rarely amount to real GC pressure. Still, having common idioms like `"foo" + str` or `ary.uniq.sort.reverse` get 1.1-1.5x faster is a nice thing, and reducing the general uneasiness about "this creates an intermediate array" seems worthwhile, IMO. What do you think? -- https://bugs.ruby-lang.org/

Issue #22182 has been updated by byroot (Jean Boussier). @duerst the proposal isn't to literally subtitute `gusb` for `gsub!`, but to call a hidden, alternative implementation of `gsub` that mutates in place (or have `gsub` being able to know it was called in such fashion) ---------------------------------------- Feature #22182: Poor man's escape analysis https://bugs.ruby-lang.org/issues/22182#change-118063 * Author: mame (Yusuke Endoh) * Status: Open ---------------------------------------- This is an experimental optimization idea that speeds up typical method chains by destructively updating their intermediate objects. Intuitively, it works like this: * `str.strip.upcase` runs like `str.strip.upcase!` * `ary.map {}.select {}` runs like `ary.map {}.select! {}` * `"foo" + str + str` runs like `"foo" << str << str` As a bonus: * `foo(**opts.merge(default))` passes the merged hash to the callee as-is, without `Hash#dup` ## Microbenchmarks 1-second measurement windows, average of 5 alternating rounds (µs/call). |Code|Before|After|Speedup|Setup| |--|--|--|--|--| |`str + str + str`| 0.127 µs | 0.088 µs | 1.44x |`str = "x" * 100`| |`ary + ary + ary`| 0.645 µs | 0.304 µs | 2.12x |`ary = (0..99).to_a`| |`"foo" + str`| 0.083 µs | 0.056 µs | 1.50x |`str = "bar"`| |`ary.map { it+1 }.select { it.even? }`| 6.86 µs | 6.64 µs | 1.03x |`ary = (0..99).to_a`| |`str.strip.upcase`| 0.099 µs | 0.090 µs | 1.10x |`str = " foo "`| |`"#{a}#{b}".strip`| 0.110 µs | 0.103 µs | 1.07x |`a = "abcdefgh"; b = "ijklmnop"`| |`ary.uniq.sort.reverse`| 38.7 µs | 36.4 µs | 1.06x |`ary = (0..999).map { it % 500 }.shuffle`| |`foo(**opts.merge(default))`| 0.557 µs | 0.489 µs | 1.14x |`def foo(**kw) = kw; opts = (0...10).to_h { [:"o#{it}", it] }; default = (0...10).to_h { [:"d#{it}", it] }`| Allocations go down as well (e.g. `str + str + str` goes from 2 objects to 1). ## How it works In one sentence: a limited form of escape analysis, specialized for method chains. We introduce flags (`STR_FRESH` / `ARY_FRESH` / `HASH_FRESH`) for `String` / `Array` / `Hash` objects whose only reference is guaranteed to be a single value-stack slot. Since no one else can observe a flagged object, the next operation may reuse it destructively. A few instructions are added. The typical one is `opt_plus_fresh`. For example, `str1 + str2 + str3` compiles and runs as: ``` getlocal str1 getlocal str2 opt_plus_fresh # concatenate into a new String and set STR_FRESH on it; since it will # almost certainly be appended to, allocate with extra (2x) capacity getlocal str3 opt_plus # if the receiver has STR_FRESH, append in place instead of # allocating a new object ``` `ary.map {}.select {}` compiles and runs as: ``` getlocal ary send :map (callinfo: VM_CALL_FRESH_PROD) # if the method cache resolved to the built-in # Array#map, set ARY_FRESH on the resulting array send :select (callinfo: VM_CALL_FRESH_CONS) # if the method cache resolved to the built-in # Array#select and the receiver has ARY_FRESH, # call the select!-style destructive implementation ``` There are also a few instructions that create objects with the FRESH flag set (`newarray_fresh`, `duparray_fresh`, `dupstring_fresh`, `concatstrings_fresh`). These make `"foo" + str`, `[1, 2, 3].sort` and `"#{a}#{b}".strip` destructive as well. ## PoC implementation Implemented by Claude Code (Fable 5). Still a proof of concept. https://github.com/ruby/ruby/pull/17685 9 commits: 1. Add the STR_FRESH / ARY_FRESH / HASH_FRESH object flags (+ clearing in ObjectSpace.each_object) 2. Preparatory refactoring: extract str_enc_buf_new0() from str_enc_new() 3. String#+ chains: reuse the intermediate in place (opt_plus_fresh / dupstring_fresh) 4. Array#+ chains: same 5. Built-in String chains: apply destructive counterparts to fresh receivers (strip.downcase, sub with arguments, interpolated heads, ...) — also introduces the common machinery (unconditional callinfo bits + fresh_producer/fresh_consumer method entry bits + the table) 6. Built-in Array chains (map/select/... + take/drop + split/to_a/flat_map/sort_by/set-operation producers + literal heads like `[3,1,2].sort`) 7. Built-in Hash chains (merge/transform_values/select/reject/compact) 8. Hand over fresh splat / kw-splat operands (`f(*xs.map {})` / `foo(**opts.merge(default))` skip the defensive copy — a runtime generalization of the existing `VM_CALL_ARGS_SPLAT_MUT` / `KW_SPLAT_MUT`) 9. Minimal YJIT support (+ chains are also fused in JITed code; built-in send chains stay inactive but sound. Same for ZJIT.) ## Implementation notes This optimization needs delicate care so that FRESH-flagged objects never leak into ordinary code. Optimization is therefore applied only in very restricted situations: * Only chains that use known method names (`map`, `select`, ...) are optimized. (This prevents a leak through e.g. `ary.map {}.tap { it }`.) * Optimization applies only while none of those `String`/`Array`/`Hash` methods are redefined. * `ObjectSpace.each_object` clears the FRESH flag of every object it yields. * A receiver passed to `method_missing` has its FRESH flag cleared. * In case a target method is redefined in the middle of a chain, a consumer site whose call cache was invalidated clears the receiver's FRESH flag. There may be other paths through which a FRESH object can leak; please let me know if you spot one. In principle this should almost never slow down ordinary code: the only cost is one FRESH flag test in `opt_plus` for String and Array. Indeed, a plain `str + str` (not optimized) measured 0.071 µs both before and after the patch (1.00x). Fixnum `+`, standalone `merge` / `sort`, `foo(**h)` etc. all measured 0.98-1.03x. ## Limitations String has no spare flag bits, so the PoC reuses STR_PRECOMPUTED_HASH == STR_FRESH: the bit is read as STR_PRECOMPUTED_HASH on frozen strings and as STR_FRESH on unfrozen ones. Under `frozen-string-literal: true`, `"foo" + str` is currently not optimized (perhaps improvable?). YJIT support is provisional. `+` chains are fused in JITed code too, but the destructive reuse in built-in send chains only happens in interpreted execution. In particular, with a JIT enabled, Array chains are disabled entirely (YJIT redefines `Array#map` / `Array#select` in Ruby, which trips the redefinition detection, unfortunate). Only prism is supported for now (parse.y is not). There are probably other things I have missed. ## Discussion Ordinary code does not get slower, and some code skips intermediate allocations entirely, so I believe this is essentially all upside. That said, keeping FRESH objects from leaking makes this a fairly intricate and delicate optimization, so I would like to hear from VM and JIT developers. Whether this shows up in "macro" benchmarks is questionable: code like `"foo" + str + str + str`, where the optimization shines, has traditionally been avoided, and the intermediate objects it eliminates would almost certainly have been collected by minor GC anyway, so they rarely amount to real GC pressure. Still, having common idioms like `"foo" + str` or `ary.uniq.sort.reverse` get 1.1-1.5x faster is a nice thing, and reducing the general uneasiness about "this creates an intermediate array" seems worthwhile, IMO. What do you think? -- https://bugs.ruby-lang.org/

Issue #22182 has been updated by byroot (Jean Boussier).

copies of the collection methods: the original C implementation, the "fresh" variant

That is likely the biggest downside, but I suspect that in many cases, the original and "fresh" implementations could share most of their code, which is already the case for some methods in the PoC, e.g. ```c VALUE rb_ary_fresh_sort(VALUE ary) { rb_ary_sort_bang(ary); return ary; } ``` I suspect in most cases we'll be able to have the original version be something like: ```c VALUE some_func(VALUE obj) { return some_func_fresh(dup(obj)) } ``` Which should limit the duplicated logic (but that's just a hunch). ---------------------------------------- Feature #22182: Poor man's escape analysis https://bugs.ruby-lang.org/issues/22182#change-118101 * Author: mame (Yusuke Endoh) * Status: Open ---------------------------------------- This is an experimental optimization idea that speeds up typical method chains by destructively updating their intermediate objects. Intuitively, it works like this: * `str.strip.upcase` runs like `str.strip.upcase!` * `ary.map {}.select {}` runs like `ary.map {}.select! {}` * `"foo" + str + str` runs like `"foo" << str << str` As a bonus: * `foo(**opts.merge(default))` passes the merged hash to the callee as-is, without `Hash#dup` ## Microbenchmarks 1-second measurement windows, average of 5 alternating rounds (µs/call). |Code|Before|After|Speedup|Setup| |--|--|--|--|--| |`str + str + str`| 0.127 µs | 0.088 µs | 1.44x |`str = "x" * 100`| |`ary + ary + ary`| 0.645 µs | 0.304 µs | 2.12x |`ary = (0..99).to_a`| |`"foo" + str`| 0.083 µs | 0.056 µs | 1.50x |`str = "bar"`| |`ary.map { it+1 }.select { it.even? }`| 6.86 µs | 6.64 µs | 1.03x |`ary = (0..99).to_a`| |`str.strip.upcase`| 0.099 µs | 0.090 µs | 1.10x |`str = " foo "`| |`"#{a}#{b}".strip`| 0.110 µs | 0.103 µs | 1.07x |`a = "abcdefgh"; b = "ijklmnop"`| |`ary.uniq.sort.reverse`| 38.7 µs | 36.4 µs | 1.06x |`ary = (0..999).map { it % 500 }.shuffle`| |`foo(**opts.merge(default))`| 0.557 µs | 0.489 µs | 1.14x |`def foo(**kw) = kw; opts = (0...10).to_h { [:"o#{it}", it] }; default = (0...10).to_h { [:"d#{it}", it] }`| Allocations go down as well (e.g. `str + str + str` goes from 2 objects to 1). ## How it works In one sentence: a limited form of escape analysis, specialized for method chains. We introduce flags (`STR_FRESH` / `ARY_FRESH` / `HASH_FRESH`) for `String` / `Array` / `Hash` objects whose only reference is guaranteed to be a single value-stack slot. Since no one else can observe a flagged object, the next operation may reuse it destructively. A few instructions are added. The typical one is `opt_plus_fresh`. For example, `str1 + str2 + str3` compiles and runs as: ``` getlocal str1 getlocal str2 opt_plus_fresh # concatenate into a new String and set STR_FRESH on it; since it will # almost certainly be appended to, allocate with extra (2x) capacity getlocal str3 opt_plus # if the receiver has STR_FRESH, append in place instead of # allocating a new object ``` `ary.map {}.select {}` compiles and runs as: ``` getlocal ary send :map (callinfo: VM_CALL_FRESH_PROD) # if the method cache resolved to the built-in # Array#map, set ARY_FRESH on the resulting array send :select (callinfo: VM_CALL_FRESH_CONS) # if the method cache resolved to the built-in # Array#select and the receiver has ARY_FRESH, # call the select!-style destructive implementation ``` There are also a few instructions that create objects with the FRESH flag set (`newarray_fresh`, `duparray_fresh`, `dupstring_fresh`, `concatstrings_fresh`). These make `"foo" + str`, `[1, 2, 3].sort` and `"#{a}#{b}".strip` destructive as well. ## PoC implementation Implemented by Claude Code (Fable 5). Still a proof of concept. https://github.com/ruby/ruby/pull/17685 9 commits: 1. Add the STR_FRESH / ARY_FRESH / HASH_FRESH object flags (+ clearing in ObjectSpace.each_object) 2. Preparatory refactoring: extract str_enc_buf_new0() from str_enc_new() 3. String#+ chains: reuse the intermediate in place (opt_plus_fresh / dupstring_fresh) 4. Array#+ chains: same 5. Built-in String chains: apply destructive counterparts to fresh receivers (strip.downcase, sub with arguments, interpolated heads, ...) — also introduces the common machinery (unconditional callinfo bits + fresh_producer/fresh_consumer method entry bits + the table) 6. Built-in Array chains (map/select/... + take/drop + split/to_a/flat_map/sort_by/set-operation producers + literal heads like `[3,1,2].sort`) 7. Built-in Hash chains (merge/transform_values/select/reject/compact) 8. Hand over fresh splat / kw-splat operands (`f(*xs.map {})` / `foo(**opts.merge(default))` skip the defensive copy — a runtime generalization of the existing `VM_CALL_ARGS_SPLAT_MUT` / `KW_SPLAT_MUT`) 9. Minimal YJIT support (+ chains are also fused in JITed code; built-in send chains stay inactive but sound. Same for ZJIT.) ## Implementation notes This optimization needs delicate care so that FRESH-flagged objects never leak into ordinary code. Optimization is therefore applied only in very restricted situations: * Only chains that use known method names (`map`, `select`, ...) are optimized. (This prevents a leak through e.g. `ary.map {}.tap { it }`.) * Optimization applies only while none of those `String`/`Array`/`Hash` methods are redefined. * `ObjectSpace.each_object` clears the FRESH flag of every object it yields. * A receiver passed to `method_missing` has its FRESH flag cleared. * In case a target method is redefined in the middle of a chain, a consumer site whose call cache was invalidated clears the receiver's FRESH flag. There may be other paths through which a FRESH object can leak; please let me know if you spot one. In principle this should almost never slow down ordinary code: the only cost is one FRESH flag test in `opt_plus` for String and Array. Indeed, a plain `str + str` (not optimized) measured 0.071 µs both before and after the patch (1.00x). Fixnum `+`, standalone `merge` / `sort`, `foo(**h)` etc. all measured 0.98-1.03x. ## Limitations String has no spare flag bits, so the PoC reuses STR_PRECOMPUTED_HASH == STR_FRESH: the bit is read as STR_PRECOMPUTED_HASH on frozen strings and as STR_FRESH on unfrozen ones. Under `frozen-string-literal: true`, `"foo" + str` is currently not optimized (perhaps improvable?). YJIT support is provisional. `+` chains are fused in JITed code too, but the destructive reuse in built-in send chains only happens in interpreted execution. In particular, with a JIT enabled, Array chains are disabled entirely (YJIT redefines `Array#map` / `Array#select` in Ruby, which trips the redefinition detection, unfortunate). Only prism is supported for now (parse.y is not). There are probably other things I have missed. ## Discussion Ordinary code does not get slower, and some code skips intermediate allocations entirely, so I believe this is essentially all upside. That said, keeping FRESH objects from leaking makes this a fairly intricate and delicate optimization, so I would like to hear from VM and JIT developers. Whether this shows up in "macro" benchmarks is questionable: code like `"foo" + str + str + str`, where the optimization shines, has traditionally been avoided, and the intermediate objects it eliminates would almost certainly have been collected by minor GC anyway, so they rarely amount to real GC pressure. Still, having common idioms like `"foo" + str` or `ary.uniq.sort.reverse` get 1.1-1.5x faster is a nice thing, and reducing the general uneasiness about "this creates an intermediate array" seems worthwhile, IMO. What do you think? -- https://bugs.ruby-lang.org/

Issue #22182 has been updated by byroot (Jean Boussier).

those benchmarks already avoid writing, in their hot loops, the kind of slow code that this optimization speeds up

That's a very common problem, it's the same issue with `--enable-frozen-string-literal` which doesn't show much gain because all the performance sensitive code already runs with `# frozen_string_literal: true` (or use constants). I similarly toyed with some poor man's escape analysis to elude `MatchData` allocation when using `case when /regexp/` or `=~` without accessing the `MatchData, but similarly, almost all hotspots now use `Regexp#match?`. In the end, these optimizations allow to write nicer, more natural code, but they rarely significantly speedup existing code, so they're hard to justify. ---------------------------------------- Feature #22182: Poor man's escape analysis https://bugs.ruby-lang.org/issues/22182#change-118105 * Author: mame (Yusuke Endoh) * Status: Open ---------------------------------------- This is an experimental optimization idea that speeds up typical method chains by destructively updating their intermediate objects. Intuitively, it works like this: * `str.strip.upcase` runs like `str.strip.upcase!` * `ary.map {}.select {}` runs like `ary.map {}.select! {}` * `"foo" + str + str` runs like `"foo" << str << str` As a bonus: * `foo(**opts.merge(default))` passes the merged hash to the callee as-is, without `Hash#dup` ## Microbenchmarks 1-second measurement windows, average of 5 alternating rounds (µs/call). |Code|Before|After|Speedup|Setup| |--|--|--|--|--| |`str + str + str`| 0.127 µs | 0.088 µs | 1.44x |`str = "x" * 100`| |`ary + ary + ary`| 0.645 µs | 0.304 µs | 2.12x |`ary = (0..99).to_a`| |`"foo" + str`| 0.083 µs | 0.056 µs | 1.50x |`str = "bar"`| |`ary.map { it+1 }.select { it.even? }`| 6.86 µs | 6.64 µs | 1.03x |`ary = (0..99).to_a`| |`str.strip.upcase`| 0.099 µs | 0.090 µs | 1.10x |`str = " foo "`| |`"#{a}#{b}".strip`| 0.110 µs | 0.103 µs | 1.07x |`a = "abcdefgh"; b = "ijklmnop"`| |`ary.uniq.sort.reverse`| 38.7 µs | 36.4 µs | 1.06x |`ary = (0..999).map { it % 500 }.shuffle`| |`foo(**opts.merge(default))`| 0.557 µs | 0.489 µs | 1.14x |`def foo(**kw) = kw; opts = (0...10).to_h { [:"o#{it}", it] }; default = (0...10).to_h { [:"d#{it}", it] }`| Allocations go down as well (e.g. `str + str + str` goes from 2 objects to 1). ## How it works In one sentence: a limited form of escape analysis, specialized for method chains. We introduce flags (`STR_FRESH` / `ARY_FRESH` / `HASH_FRESH`) for `String` / `Array` / `Hash` objects whose only reference is guaranteed to be a single value-stack slot. Since no one else can observe a flagged object, the next operation may reuse it destructively. A few instructions are added. The typical one is `opt_plus_fresh`. For example, `str1 + str2 + str3` compiles and runs as: ``` getlocal str1 getlocal str2 opt_plus_fresh # concatenate into a new String and set STR_FRESH on it; since it will # almost certainly be appended to, allocate with extra (2x) capacity getlocal str3 opt_plus # if the receiver has STR_FRESH, append in place instead of # allocating a new object ``` `ary.map {}.select {}` compiles and runs as: ``` getlocal ary send :map (callinfo: VM_CALL_FRESH_PROD) # if the method cache resolved to the built-in # Array#map, set ARY_FRESH on the resulting array send :select (callinfo: VM_CALL_FRESH_CONS) # if the method cache resolved to the built-in # Array#select and the receiver has ARY_FRESH, # call the select!-style destructive implementation ``` There are also a few instructions that create objects with the FRESH flag set (`newarray_fresh`, `duparray_fresh`, `dupstring_fresh`, `concatstrings_fresh`). These make `"foo" + str`, `[1, 2, 3].sort` and `"#{a}#{b}".strip` destructive as well. ## PoC implementation Implemented by Claude Code (Fable 5). Still a proof of concept. https://github.com/ruby/ruby/pull/17685 9 commits: 1. Add the STR_FRESH / ARY_FRESH / HASH_FRESH object flags (+ clearing in ObjectSpace.each_object) 2. Preparatory refactoring: extract str_enc_buf_new0() from str_enc_new() 3. String#+ chains: reuse the intermediate in place (opt_plus_fresh / dupstring_fresh) 4. Array#+ chains: same 5. Built-in String chains: apply destructive counterparts to fresh receivers (strip.downcase, sub with arguments, interpolated heads, ...) — also introduces the common machinery (unconditional callinfo bits + fresh_producer/fresh_consumer method entry bits + the table) 6. Built-in Array chains (map/select/... + take/drop + split/to_a/flat_map/sort_by/set-operation producers + literal heads like `[3,1,2].sort`) 7. Built-in Hash chains (merge/transform_values/select/reject/compact) 8. Hand over fresh splat / kw-splat operands (`f(*xs.map {})` / `foo(**opts.merge(default))` skip the defensive copy — a runtime generalization of the existing `VM_CALL_ARGS_SPLAT_MUT` / `KW_SPLAT_MUT`) 9. Minimal YJIT support (+ chains are also fused in JITed code; built-in send chains stay inactive but sound. Same for ZJIT.) ## Implementation notes This optimization needs delicate care so that FRESH-flagged objects never leak into ordinary code. Optimization is therefore applied only in very restricted situations: * Only chains that use known method names (`map`, `select`, ...) are optimized. (This prevents a leak through e.g. `ary.map {}.tap { it }`.) * Optimization applies only while none of those `String`/`Array`/`Hash` methods are redefined. * `ObjectSpace.each_object` clears the FRESH flag of every object it yields. * A receiver passed to `method_missing` has its FRESH flag cleared. * In case a target method is redefined in the middle of a chain, a consumer site whose call cache was invalidated clears the receiver's FRESH flag. There may be other paths through which a FRESH object can leak; please let me know if you spot one. In principle this should almost never slow down ordinary code: the only cost is one FRESH flag test in `opt_plus` for String and Array. Indeed, a plain `str + str` (not optimized) measured 0.071 µs both before and after the patch (1.00x). Fixnum `+`, standalone `merge` / `sort`, `foo(**h)` etc. all measured 0.98-1.03x. ## Limitations String has no spare flag bits, so the PoC reuses STR_PRECOMPUTED_HASH == STR_FRESH: the bit is read as STR_PRECOMPUTED_HASH on frozen strings and as STR_FRESH on unfrozen ones. Under `frozen-string-literal: true`, `"foo" + str` is currently not optimized (perhaps improvable?). YJIT support is provisional. `+` chains are fused in JITed code too, but the destructive reuse in built-in send chains only happens in interpreted execution. In particular, with a JIT enabled, Array chains are disabled entirely (YJIT redefines `Array#map` / `Array#select` in Ruby, which trips the redefinition detection, unfortunate). Only prism is supported for now (parse.y is not). There are probably other things I have missed. ## Discussion Ordinary code does not get slower, and some code skips intermediate allocations entirely, so I believe this is essentially all upside. That said, keeping FRESH objects from leaking makes this a fairly intricate and delicate optimization, so I would like to hear from VM and JIT developers. Whether this shows up in "macro" benchmarks is questionable: code like `"foo" + str + str + str`, where the optimization shines, has traditionally been avoided, and the intermediate objects it eliminates would almost certainly have been collected by minor GC anyway, so they rarely amount to real GC pressure. Still, having common idioms like `"foo" + str` or `ary.uniq.sort.reverse` get 1.1-1.5x faster is a nice thing, and reducing the general uneasiness about "this creates an intermediate array" seems worthwhile, IMO. What do you think? -- https://bugs.ruby-lang.org/

Issue #22182 has been updated by mame (Yusuke Endoh). byroot (Jean Boussier) wrote in #note-11:

it's the same issue with `--enable-frozen-string-literal` which doesn't show much gain because all the performance sensitive code already runs with `# frozen_string_literal: true` (or use constants).

As for the magic comments, we could estimate the gain by benchmarking with a patch that ignores them, couldn't we? You are right about constants, though. Well, I wouldn't mind giving up both frozen-string-literal by default and poor man's escape analysis :-p alanwu (Alan Wu) wrote in #note-12:

when ZJIT remove allocations, they won't show in `each_object`. Technically a behavior change. :p

I haven't thought about the impact that seriously, so I am not sure if it is really fine. IMO, `each_object` is for debugging purposes only, but I wonder how people use it in the wild. I have heard that `each_object` is also going to suppress visible objects in the Ractor context.

It seems we should be able to have the analysis ready as soon as next release

That's great! So, once the built-in methods of String and Array are ported to Ruby and the other pieces (loop optimizations etc.) fall into place, can we expect that allocation elision in hot loops will be achieved in the same way as this proposal does? ---------------------------------------- Feature #22182: Poor man's escape analysis https://bugs.ruby-lang.org/issues/22182#change-118111 * Author: mame (Yusuke Endoh) * Status: Open ---------------------------------------- This is an experimental optimization idea that speeds up typical method chains by destructively updating their intermediate objects. Intuitively, it works like this: * `str.strip.upcase` runs like `str.strip.upcase!` * `ary.map {}.select {}` runs like `ary.map {}.select! {}` * `"foo" + str + str` runs like `"foo" << str << str` As a bonus: * `foo(**opts.merge(default))` passes the merged hash to the callee as-is, without `Hash#dup` ## Microbenchmarks 1-second measurement windows, average of 5 alternating rounds (µs/call). |Code|Before|After|Speedup|Setup| |--|--|--|--|--| |`str + str + str`| 0.127 µs | 0.088 µs | 1.44x |`str = "x" * 100`| |`ary + ary + ary`| 0.645 µs | 0.304 µs | 2.12x |`ary = (0..99).to_a`| |`"foo" + str`| 0.083 µs | 0.056 µs | 1.50x |`str = "bar"`| |`ary.map { it+1 }.select { it.even? }`| 6.86 µs | 6.64 µs | 1.03x |`ary = (0..99).to_a`| |`str.strip.upcase`| 0.099 µs | 0.090 µs | 1.10x |`str = " foo "`| |`"#{a}#{b}".strip`| 0.110 µs | 0.103 µs | 1.07x |`a = "abcdefgh"; b = "ijklmnop"`| |`ary.uniq.sort.reverse`| 38.7 µs | 36.4 µs | 1.06x |`ary = (0..999).map { it % 500 }.shuffle`| |`foo(**opts.merge(default))`| 0.557 µs | 0.489 µs | 1.14x |`def foo(**kw) = kw; opts = (0...10).to_h { [:"o#{it}", it] }; default = (0...10).to_h { [:"d#{it}", it] }`| Allocations go down as well (e.g. `str + str + str` goes from 2 objects to 1). ## How it works In one sentence: a limited form of escape analysis, specialized for method chains. We introduce flags (`STR_FRESH` / `ARY_FRESH` / `HASH_FRESH`) for `String` / `Array` / `Hash` objects whose only reference is guaranteed to be a single value-stack slot. Since no one else can observe a flagged object, the next operation may reuse it destructively. A few instructions are added. The typical one is `opt_plus_fresh`. For example, `str1 + str2 + str3` compiles and runs as: ``` getlocal str1 getlocal str2 opt_plus_fresh # concatenate into a new String and set STR_FRESH on it; since it will # almost certainly be appended to, allocate with extra (2x) capacity getlocal str3 opt_plus # if the receiver has STR_FRESH, append in place instead of # allocating a new object ``` `ary.map {}.select {}` compiles and runs as: ``` getlocal ary send :map (callinfo: VM_CALL_FRESH_PROD) # if the method cache resolved to the built-in # Array#map, set ARY_FRESH on the resulting array send :select (callinfo: VM_CALL_FRESH_CONS) # if the method cache resolved to the built-in # Array#select and the receiver has ARY_FRESH, # call the select!-style destructive implementation ``` There are also a few instructions that create objects with the FRESH flag set (`newarray_fresh`, `duparray_fresh`, `dupstring_fresh`, `concatstrings_fresh`). These make `"foo" + str`, `[1, 2, 3].sort` and `"#{a}#{b}".strip` destructive as well. ## PoC implementation Implemented by Claude Code (Fable 5). Still a proof of concept. https://github.com/ruby/ruby/pull/17685 9 commits: 1. Add the STR_FRESH / ARY_FRESH / HASH_FRESH object flags (+ clearing in ObjectSpace.each_object) 2. Preparatory refactoring: extract str_enc_buf_new0() from str_enc_new() 3. String#+ chains: reuse the intermediate in place (opt_plus_fresh / dupstring_fresh) 4. Array#+ chains: same 5. Built-in String chains: apply destructive counterparts to fresh receivers (strip.downcase, sub with arguments, interpolated heads, ...) — also introduces the common machinery (unconditional callinfo bits + fresh_producer/fresh_consumer method entry bits + the table) 6. Built-in Array chains (map/select/... + take/drop + split/to_a/flat_map/sort_by/set-operation producers + literal heads like `[3,1,2].sort`) 7. Built-in Hash chains (merge/transform_values/select/reject/compact) 8. Hand over fresh splat / kw-splat operands (`f(*xs.map {})` / `foo(**opts.merge(default))` skip the defensive copy — a runtime generalization of the existing `VM_CALL_ARGS_SPLAT_MUT` / `KW_SPLAT_MUT`) 9. Minimal YJIT support (+ chains are also fused in JITed code; built-in send chains stay inactive but sound. Same for ZJIT.) ## Implementation notes This optimization needs delicate care so that FRESH-flagged objects never leak into ordinary code. Optimization is therefore applied only in very restricted situations: * Only chains that use known method names (`map`, `select`, ...) are optimized. (This prevents a leak through e.g. `ary.map {}.tap { it }`.) * Optimization applies only while none of those `String`/`Array`/`Hash` methods are redefined. * `ObjectSpace.each_object` clears the FRESH flag of every object it yields. * A receiver passed to `method_missing` has its FRESH flag cleared. * In case a target method is redefined in the middle of a chain, a consumer site whose call cache was invalidated clears the receiver's FRESH flag. There may be other paths through which a FRESH object can leak; please let me know if you spot one. In principle this should almost never slow down ordinary code: the only cost is one FRESH flag test in `opt_plus` for String and Array. Indeed, a plain `str + str` (not optimized) measured 0.071 µs both before and after the patch (1.00x). Fixnum `+`, standalone `merge` / `sort`, `foo(**h)` etc. all measured 0.98-1.03x. ## Limitations String has no spare flag bits, so the PoC reuses STR_PRECOMPUTED_HASH == STR_FRESH: the bit is read as STR_PRECOMPUTED_HASH on frozen strings and as STR_FRESH on unfrozen ones. Under `frozen-string-literal: true`, `"foo" + str` is currently not optimized (perhaps improvable?). YJIT support is provisional. `+` chains are fused in JITed code too, but the destructive reuse in built-in send chains only happens in interpreted execution. In particular, with a JIT enabled, Array chains are disabled entirely (YJIT redefines `Array#map` / `Array#select` in Ruby, which trips the redefinition detection, unfortunate). Only prism is supported for now (parse.y is not). There are probably other things I have missed. ## Discussion Ordinary code does not get slower, and some code skips intermediate allocations entirely, so I believe this is essentially all upside. That said, keeping FRESH objects from leaking makes this a fairly intricate and delicate optimization, so I would like to hear from VM and JIT developers. Whether this shows up in "macro" benchmarks is questionable: code like `"foo" + str + str + str`, where the optimization shines, has traditionally been avoided, and the intermediate objects it eliminates would almost certainly have been collected by minor GC anyway, so they rarely amount to real GC pressure. Still, having common idioms like `"foo" + str` or `ary.uniq.sort.reverse` get 1.1-1.5x faster is a nice thing, and reducing the general uneasiness about "this creates an intermediate array" seems worthwhile, IMO. What do you think? -- https://bugs.ruby-lang.org/

Issue #22182 has been updated by alanwu (Alan Wu).

can we expect that allocation elision in hot loops will be achieved in the same way as this proposal does?

Yes, more or less. The code transforms to something like if you had put a `struct RArray` as a local variable and worked with its component parts. It wouldn't GC allocate at all for paths where the compiler sees all operations on the object.

If "fresh" methods existed, wouldn't they still be useful during that phase?

Of course. As mentioned, they're useful afterwards too. The JIT needs to implement the new dispatch mechanism to take advantage, though. Without the object flag it's easier because we wouldn't need to carefully find all the places that need to untag and add code. ---------------------------------------- Feature #22182: Poor man's escape analysis https://bugs.ruby-lang.org/issues/22182#change-118130 * Author: mame (Yusuke Endoh) * Status: Open ---------------------------------------- This is an experimental optimization idea that speeds up typical method chains by destructively updating their intermediate objects. Intuitively, it works like this: * `str.strip.upcase` runs like `str.strip.upcase!` * `ary.map {}.select {}` runs like `ary.map {}.select! {}` * `"foo" + str + str` runs like `"foo" << str << str` As a bonus: * `foo(**opts.merge(default))` passes the merged hash to the callee as-is, without `Hash#dup` ## Microbenchmarks 1-second measurement windows, average of 5 alternating rounds (µs/call). |Code|Before|After|Speedup|Setup| |--|--|--|--|--| |`str + str + str`| 0.127 µs | 0.088 µs | 1.44x |`str = "x" * 100`| |`ary + ary + ary`| 0.645 µs | 0.304 µs | 2.12x |`ary = (0..99).to_a`| |`"foo" + str`| 0.083 µs | 0.056 µs | 1.50x |`str = "bar"`| |`ary.map { it+1 }.select { it.even? }`| 6.86 µs | 6.64 µs | 1.03x |`ary = (0..99).to_a`| |`str.strip.upcase`| 0.099 µs | 0.090 µs | 1.10x |`str = " foo "`| |`"#{a}#{b}".strip`| 0.110 µs | 0.103 µs | 1.07x |`a = "abcdefgh"; b = "ijklmnop"`| |`ary.uniq.sort.reverse`| 38.7 µs | 36.4 µs | 1.06x |`ary = (0..999).map { it % 500 }.shuffle`| |`foo(**opts.merge(default))`| 0.557 µs | 0.489 µs | 1.14x |`def foo(**kw) = kw; opts = (0...10).to_h { [:"o#{it}", it] }; default = (0...10).to_h { [:"d#{it}", it] }`| Allocations go down as well (e.g. `str + str + str` goes from 2 objects to 1). ## How it works In one sentence: a limited form of escape analysis, specialized for method chains. We introduce flags (`STR_FRESH` / `ARY_FRESH` / `HASH_FRESH`) for `String` / `Array` / `Hash` objects whose only reference is guaranteed to be a single value-stack slot. Since no one else can observe a flagged object, the next operation may reuse it destructively. A few instructions are added. The typical one is `opt_plus_fresh`. For example, `str1 + str2 + str3` compiles and runs as: ``` getlocal str1 getlocal str2 opt_plus_fresh # concatenate into a new String and set STR_FRESH on it; since it will # almost certainly be appended to, allocate with extra (2x) capacity getlocal str3 opt_plus # if the receiver has STR_FRESH, append in place instead of # allocating a new object ``` `ary.map {}.select {}` compiles and runs as: ``` getlocal ary send :map (callinfo: VM_CALL_FRESH_PROD) # if the method cache resolved to the built-in # Array#map, set ARY_FRESH on the resulting array send :select (callinfo: VM_CALL_FRESH_CONS) # if the method cache resolved to the built-in # Array#select and the receiver has ARY_FRESH, # call the select!-style destructive implementation ``` There are also a few instructions that create objects with the FRESH flag set (`newarray_fresh`, `duparray_fresh`, `dupstring_fresh`, `concatstrings_fresh`). These make `"foo" + str`, `[1, 2, 3].sort` and `"#{a}#{b}".strip` destructive as well. ## PoC implementation Implemented by Claude Code (Fable 5). Still a proof of concept. https://github.com/ruby/ruby/pull/17685 9 commits: 1. Add the STR_FRESH / ARY_FRESH / HASH_FRESH object flags (+ clearing in ObjectSpace.each_object) 2. Preparatory refactoring: extract str_enc_buf_new0() from str_enc_new() 3. String#+ chains: reuse the intermediate in place (opt_plus_fresh / dupstring_fresh) 4. Array#+ chains: same 5. Built-in String chains: apply destructive counterparts to fresh receivers (strip.downcase, sub with arguments, interpolated heads, ...) — also introduces the common machinery (unconditional callinfo bits + fresh_producer/fresh_consumer method entry bits + the table) 6. Built-in Array chains (map/select/... + take/drop + split/to_a/flat_map/sort_by/set-operation producers + literal heads like `[3,1,2].sort`) 7. Built-in Hash chains (merge/transform_values/select/reject/compact) 8. Hand over fresh splat / kw-splat operands (`f(*xs.map {})` / `foo(**opts.merge(default))` skip the defensive copy — a runtime generalization of the existing `VM_CALL_ARGS_SPLAT_MUT` / `KW_SPLAT_MUT`) 9. Minimal YJIT support (+ chains are also fused in JITed code; built-in send chains stay inactive but sound. Same for ZJIT.) ## Implementation notes This optimization needs delicate care so that FRESH-flagged objects never leak into ordinary code. Optimization is therefore applied only in very restricted situations: * Only chains that use known method names (`map`, `select`, ...) are optimized. (This prevents a leak through e.g. `ary.map {}.tap { it }`.) * Optimization applies only while none of those `String`/`Array`/`Hash` methods are redefined. * `ObjectSpace.each_object` clears the FRESH flag of every object it yields. * A receiver passed to `method_missing` has its FRESH flag cleared. * In case a target method is redefined in the middle of a chain, a consumer site whose call cache was invalidated clears the receiver's FRESH flag. There may be other paths through which a FRESH object can leak; please let me know if you spot one. In principle this should almost never slow down ordinary code: the only cost is one FRESH flag test in `opt_plus` for String and Array. Indeed, a plain `str + str` (not optimized) measured 0.071 µs both before and after the patch (1.00x). Fixnum `+`, standalone `merge` / `sort`, `foo(**h)` etc. all measured 0.98-1.03x. ## Limitations String has no spare flag bits, so the PoC reuses STR_PRECOMPUTED_HASH == STR_FRESH: the bit is read as STR_PRECOMPUTED_HASH on frozen strings and as STR_FRESH on unfrozen ones. Under `frozen-string-literal: true`, `"foo" + str` is currently not optimized (perhaps improvable?). YJIT support is provisional. `+` chains are fused in JITed code too, but the destructive reuse in built-in send chains only happens in interpreted execution. In particular, with a JIT enabled, Array chains are disabled entirely (YJIT redefines `Array#map` / `Array#select` in Ruby, which trips the redefinition detection, unfortunate). Only prism is supported for now (parse.y is not). There are probably other things I have missed. ## Discussion Ordinary code does not get slower, and some code skips intermediate allocations entirely, so I believe this is essentially all upside. That said, keeping FRESH objects from leaking makes this a fairly intricate and delicate optimization, so I would like to hear from VM and JIT developers. Whether this shows up in "macro" benchmarks is questionable: code like `"foo" + str + str + str`, where the optimization shines, has traditionally been avoided, and the intermediate objects it eliminates would almost certainly have been collected by minor GC anyway, so they rarely amount to real GC pressure. Still, having common idioms like `"foo" + str` or `ary.uniq.sort.reverse` get 1.1-1.5x faster is a nice thing, and reducing the general uneasiness about "this creates an intermediate array" seems worthwhile, IMO. What do you think? -- https://bugs.ruby-lang.org/