Issue #22182 has been updated by alanwu (Alan Wu).
The bigger headache for me was flagged objects escaping...
Yeah, that is a tricky part of this that'd be nice to not carry. I'm glad we seem to agree that `ObjectSpace.each_object` isn't high priority to keep stable: when ZJIT remove allocations, they won't show in `each_object`. Technically a behavior change. :p
FWIW, if ZJIT's allocation elision is likely within, say, five years, I wouldn't mind waiting for it.
It seems we should be able to have the analysis ready as soon as next release, but since it only works over Ruby code, there's a long tail of collection methods to port to Ruby before we reach full efficacy. We might also need some loop optimizations (fusion, hoisting, etc.) before we can match or surpass the C implementation in speed. Also, ZJIT only looks at hot code, so it's not a complete overlap with the approach here.
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.
I heard from some experienced JIT author that in terms of direct contribution to speed, allocation removal by itself doesn't rank very high. It's one of those passes that works best when combined with other optimizations. This makes sense to me because there is work to speed up GC allocation itself like <https://github.com/ruby/ruby/pull/17717>. Definitely still valuable, though. ---------------------------------------- Feature #22182: Poor man's escape analysis https://bugs.ruby-lang.org/issues/22182#change-118109 * 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/