Optimized forwarding callers and callees#10510
Merged
tenderlove merged 8 commits intoruby:masterfrom Jun 18, 2024
Merged
Conversation
e12e759 to
19040d6
Compare
ko1
reviewed
Apr 12, 2024
2929a9d to
192b1b8
Compare
This comment has been minimized.
This comment has been minimized.
2964451 to
93c71fe
Compare
46ef870 to
063df23
Compare
bef7c28 to
84a07fe
Compare
jeremyevans
reviewed
May 29, 2024
Contributor
jeremyevans
left a comment
There was a problem hiding this comment.
I think this is a good approach and we should merge this.
|
|
||
| if (RTEST(splat)) { | ||
| to -= 1; // clobber the splat array | ||
| CHECK_VM_STACK_OVERFLOW0(cfp, to, RARRAY_LEN(splat)); |
Contributor
There was a problem hiding this comment.
We try to avoid stack overflow for large splats by combining all arguments into a hidden ruby array and calling the method with a splatted version of that array. Do you think that could be implemented here?
Member
Author
There was a problem hiding this comment.
I'm not sure. My answer is probably, but with some work.
This particular case is to handle call sites like this:
def delegates(...)
b = [1, 2, 3]
callee(*b, ...)
end
delegates(4, 5, 6)We'd have to be smart enough to evacuate 4, 5, 6 to an array rather than memcopy'ing b on to the stack. Seems possible, just need to add code to do it.
ko1
reviewed
Jun 3, 2024
ko1
reviewed
Jun 3, 2024
ko1
reviewed
Jun 3, 2024
6d234be to
83a1cd8
Compare
31d3ecb to
d43476d
Compare
This patch optimizes forwarding callers and callees. It only optimizes methods that only take `...` as their parameter, and then pass `...` to other calls.
Calls it optimizes look like this:
```ruby
def bar(a) = a
def foo(...) = bar(...) # optimized
foo(123)
```
```ruby
def bar(a) = a
def foo(...) = bar(1, 2, ...) # optimized
foo(123)
```
```ruby
def bar(*a) = a
def foo(...)
list = [1, 2]
bar(*list, ...) # optimized
end
foo(123)
```
All variants of the above but using `super` are also optimized, including a bare super like this:
```ruby
def foo(...)
super
end
```
This patch eliminates intermediate allocations made when calling methods that accept `...`.
We can observe allocation elimination like this:
```ruby
def m
x = GC.stat(:total_allocated_objects)
yield
GC.stat(:total_allocated_objects) - x
end
def bar(a) = a
def foo(...) = bar(...)
def test
m { foo(123) }
end
test
p test # allocates 1 object on master, but 0 objects with this patch
```
```ruby
def bar(a, b:) = a + b
def foo(...) = bar(...)
def test
m { foo(1, b: 2) }
end
test
p test # allocates 2 objects on master, but 0 objects with this patch
```
How does it work?
-----------------
This patch works by using a dynamic stack size when passing forwarded parameters to callees.
The caller's info object (known as the "CI") contains the stack size of the
parameters, so we pass the CI object itself as a parameter to the callee.
When forwarding parameters, the forwarding ISeq uses the caller's CI to determine how much stack to copy, then copies the caller's stack before calling the callee.
The CI at the forwarded call site is adjusted using information from the caller's CI.
I think this description is kind of confusing, so let's walk through an example with code.
```ruby
def delegatee(a, b) = a + b
def delegator(...)
delegatee(...) # CI2 (FORWARDING)
end
def caller
delegator(1, 2) # CI1 (argc: 2)
end
```
Before we call the delegator method, the stack looks like this:
```
Executing Line | Code | Stack
---------------+---------------------------------------+--------
1| def delegatee(a, b) = a + b | self
2| | 1
3| def delegator(...) | 2
4| # |
5| delegatee(...) # CI2 (FORWARDING) |
6| end |
7| |
8| def caller |
-> 9| delegator(1, 2) # CI1 (argc: 2) |
10| end |
```
The ISeq for `delegator` is tagged as "forwardable", so when `caller` calls in
to `delegator`, it writes `CI1` on to the stack as a local variable for the
`delegator` method. The `delegator` method has a special local called `...`
that holds the caller's CI object.
Here is the ISeq disasm fo `delegator`:
```
== disasm: #<ISeq:delegator@-e:1 (1,0)-(1,39)>
local table (size: 1, argc: 0 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 1] "..."@0
0000 putself ( 1)[LiCa]
0001 getlocal_WC_0 "..."@0
0003 send <calldata!mid:delegatee, argc:0, FCALL|FORWARDING>, nil
0006 leave [Re]
```
The local called `...` will contain the caller's CI: CI1.
Here is the stack when we enter `delegator`:
```
Executing Line | Code | Stack
---------------+---------------------------------------+--------
1| def delegatee(a, b) = a + b | self
2| | 1
3| def delegator(...) | 2
-> 4| # | CI1 (argc: 2)
5| delegatee(...) # CI2 (FORWARDING) | cref_or_me
6| end | specval
7| | type
8| def caller |
9| delegator(1, 2) # CI1 (argc: 2) |
10| end |
```
The CI at `delegatee` on line 5 is tagged as "FORWARDING", so it knows to
memcopy the caller's stack before calling `delegatee`. In this case, it will
memcopy self, 1, and 2 to the stack before calling `delegatee`. It knows how much
memory to copy from the caller because `CI1` contains stack size information
(argc: 2).
Before executing the `send` instruction, we push `...` on the stack. The
`send` instruction pops `...`, and because it is tagged with `FORWARDING`, it
knows to memcopy (using the information in the CI it just popped):
```
== disasm: #<ISeq:delegator@-e:1 (1,0)-(1,39)>
local table (size: 1, argc: 0 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 1] "..."@0
0000 putself ( 1)[LiCa]
0001 getlocal_WC_0 "..."@0
0003 send <calldata!mid:delegatee, argc:0, FCALL|FORWARDING>, nil
0006 leave [Re]
```
Instruction 001 puts the caller's CI on the stack. `send` is tagged with
FORWARDING, so it reads the CI and _copies_ the callers stack to this stack:
```
Executing Line | Code | Stack
---------------+---------------------------------------+--------
1| def delegatee(a, b) = a + b | self
2| | 1
3| def delegator(...) | 2
4| # | CI1 (argc: 2)
-> 5| delegatee(...) # CI2 (FORWARDING) | cref_or_me
6| end | specval
7| | type
8| def caller | self
9| delegator(1, 2) # CI1 (argc: 2) | 1
10| end | 2
```
The "FORWARDING" call site combines information from CI1 with CI2 in order
to support passing other values in addition to the `...` value, as well as
perfectly forward splat args, kwargs, etc.
Since we're able to copy the stack from `caller` in to `delegator`'s stack, we
can avoid allocating objects.
I want to do this to eliminate object allocations for delegate methods.
My long term goal is to implement `Class#new` in Ruby and it uses `...`.
I was able to implement `Class#new` in Ruby
[here](ruby#9289).
If we adopt the technique in this patch, then we can optimize allocating
objects that take keyword parameters for `initialize`.
For example, this code will allocate 2 objects: one for `SomeObject`, and one
for the kwargs:
```ruby
SomeObject.new(foo: 1)
```
If we combine this technique, plus implement `Class#new` in Ruby, then we can
reduce allocations for this common operation.
Co-Authored-By: John Hawthorn <john@hawthorn.email>
Co-Authored-By: Alan Wu <XrXr@users.noreply.github.com>
This commit adds `sendforward` and `invokesuperforward` for forwarding parameters to calls Co-authored-by: Matt Valentine-House <matt@eightbitraptor.com>
This should make the diff more clean
"super" CC's are "orphans", meaning there is no class CC table that points at them. Since they are orphans, we should mark the class reference so that if the cache happens to be used, the class will still be alive
Putting these calls next to each other lets the compiler combine "packed ci" checks
d43476d to
7eef045
Compare
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This patch optimizes forwarding callers and callees. It only optimizes methods that only take
...as their parameter, and then pass...to other calls.Calls it optimizes look like this:
All variants of the above but using
superare also optimized, including a bare super like this:This patch eliminates intermediate allocations made when calling methods that accept
.... We can observe allocation elimination like this:How does it work?
This patch works by using a dynamic stack size when passing forwarded parameters to callees. The caller's info object (known as the "CI") contains the stack size of the parameters, so we pass the CI object itself as a parameter to the callee. When forwarding parameters, the forwarding ISeq uses the caller's CI to determine how much stack to copy, then copies the caller's stack before calling the callee. The CI at the forwarded call site is adjusted using information from the caller's CI.
I think this description is kind of confusing, so let's walk through an example with code.
Before we call the delegator method, the stack looks like this:
The ISeq for
delegatoris tagged as "forwardable", so whencallercalls in todelegator, it writesCI1on to the stack as a local variable for thedelegatormethod. Thedelegatormethod has a special local called...that holds the caller's CI object.Here is the ISeq disasm fo
delegator:The local called
...will contain the caller's CI: CI1.Here is the stack when we enter
delegator:The CI at
delegateeon line 5 is tagged as "FORWARDING", so it knows to memcopy the caller's stack before callingdelegatee. In this case, it will memcopy 1 and 2 to the stack before callingdelegatee. It knows how much memory to copy from the caller becauseCI1contains stack size information (argc: 2).Before executing the
sendinstruction, we push...on the stack. Thesendinstruction pops..., and because it is tagged withFORWARDING, it knows to memcopy (using the information in the CI it just popped):Instruction 001 puts the caller's CI on the stack.
sendis tagged with FORWARDING, so it reads the CI and copies the callers stack to this stack:The "FORWARDING" call site combines information from CI1 with CI2 in order to support passing other values in addition to the
...value, as well as perfectly forward splat args, kwargs, etc.Since we're able to copy the stack from
callerin todelegator's stack, we can avoid allocating objects.I want to do this to eliminate object allocations for delegate methods. My long term goal is to implement
Class#newin Ruby and it uses....I was able to implement
Class#newin Rubyhere.
If we adopt the technique in this patch, then we can optimize allocating objects that take keyword parameters for
initialize.For example, this code will allocate 2 objects: one for
SomeObject, and one for the kwargs:If we combine this technique, plus implement
Class#newin Ruby, then we can reduce allocations for this common operation.