Feature #22182: Poor man's escape analysis

• Status: Open
• Assignee: -
• Target version: -

[mame (Yusuke Endoh)]

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?

[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?

[byroot (Jean Boussier)]

What do you think?

This proposal makes me think of a poor's man escape analysis (just an expression, I don't mean it pejoratively).

Escape analysis is of course pretty hard to do in Ruby, but has a lot of potential.

I wonder if instead of using specialized instruction for a select few methods, it wouldn't be possible to do it in the JITs using method annotations and "alternates".

e.g. we already have Primitive.attr! :leaf and such to add annotations on method, perhaps we could have Primitive.attr! :return_fresh or similar to mark that a method return a fresh new object.

We also have with_jit do to define multiple implementations of the same method.

My understanding of the JITs is limited, but it sounds like with these two existing features we could have the JIT detect that in ary.uniq.sort.reverse we're always passing a fresh object that doesn't escape, and have it dispatch to rb_ary_fresh_uniq, rb_ary_fresh_sort, rb_ary_fresh_reverse etc.

And in theory the interpreter could probably do the same?

[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.)

[byroot (Jean Boussier)]

Primitive.attr! looks elegant, but you'd still have to handle FRESH-flagged objects carefully either way

No, I think in that case there wouldn't be a FRESH flag on objects at all, only on methods.

The JIT logic would "simply" be:

if chained_call? && previously_called_method.return_fresh? && method_to_call.has_fresh_version?
  method_to_call.fresh_version.call
else
  # classic path
end

e.g. array.uniq.reverse, if uniq is tagged :return_fresh and reverse has a registered "fresh alternative" then the alternative is called. I see no need to mark objects (aside from hiding them from ObjectSpace.each_objects, but is that even necessary?).

and I suspect that a method written in Ruby could have more subtle escape routes.

I wasn't suggesting to implement these in Ruby, I'm pretty sure they'd need to be in C still. I was merely pointing at the existing mechanism to allow registering multiple versions of the same method (I only know of this capacity from the surface, I'm not aware of its specific limitations).

[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.

[duerst (Martin Dürst)]

What about methods such as gsub/gsub!, where the return value of gsub! is nil if there is no change? That may create a problem if e.g. multiple gsubs are chained and converted to gsub!s.

[byroot (Jean Boussier)]

@duerst (Martin Dürst) 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)

[alanwu (Alan Wu)]

From my perspective as a JIT dev: this will probably be profitable for a good while, though it does incur some maintenance burden for everyone. The JIT looks to the interpreter and the stock implementation of core methods for guidance on the precise semantics to replicate, so there is some default bias against additional complexity.

On the other hand, it's not fair for us to say, "just wait for proper allocation elision in ZJIT", because there's real gains today available through the approach in OP. It seems that for soundness, the additional machinery can be ignored (correct me if I'm wrong). The complexity will come from when the JIT starts to elide allocation. As the JIT wants a Ruby version of the collection methods for analysis, we'd have 3 copies of the collection methods: the original C implementation, the "fresh" variant, and the Ruby version for the JIT. The JIT only needs the Ruby version to remove the allocation, so the "fresh" variant provides less value for its maintenance burden, in that world. It'd still provide value for interpreter-only users.

So, if we want to be minimalist, we wait for JIT development. If we can stomach the addition complexity, we can add the fresh variants. The good news when it comes to complexity is that it seems fairly easy to delete all the "fresh" machinery down the line.

[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.

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:

VALUE
some_func(VALUE obj)
{
  return some_func_fresh(dup(obj))
}

Which should limit the duplicated logic (but that's just a hunch).

[mame (Yusuke Endoh)]

@alanwu (Alan Wu) Thank you for the comments.

I don't think having two variants for some frequently-used methods is a big deal, as @byroot (Jean Boussier) said.

The bigger headache for me was flagged objects escaping, but I have a flagless version working locally (trade-off: an intermediate object grabbed via each_object could be observed getting mutated), with roughly the same performance.

That said, as expected, neither version (flagged one and flagless one) moves macro benchmarks like yjit-bench.
My impressions:

• those benchmarks already avoid writing, in their hot loops, the kind of slow code that this optimization speeds up, and
• they have only a handful of bottleneck patterns, so optimizing anything else doesn't move the total.

I think this optimization is actually worthwhile in casually-written batch scripts, but TBH that is hard to demonstrate convincingly with a real-world case.

FWIW, if ZJIT's allocation elision is likely within, say, five years, I wouldn't mind waiting for it.

[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.

[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.

[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?

[byroot (Jean Boussier)]

we could estimate the gain by benchmarking with a patch that ignores them

Yes that's exactly what I did: https://github.com/Shopify/ruby/commit/bb0cee8daba4b70cedb40b36af05d796956475d6, but that doesn't undo all the constants in rack or all the .freeze in erubis. https://bugs.ruby-lang.org/issues/20205#note-34

it only works over Ruby code, there's a long tail of collection methods to port to Ruby before we reach full efficacy.

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

[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.