Skip to content

Optimized forwarding callers and callees#10510

Merged
tenderlove merged 8 commits intoruby:masterfrom
tenderlove:speed-forward
Jun 18, 2024
Merged

Optimized forwarding callers and callees#10510
tenderlove merged 8 commits intoruby:masterfrom
tenderlove:speed-forward

Conversation

@tenderlove
Copy link
Copy Markdown
Member

@tenderlove tenderlove commented Apr 11, 2024

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:

def bar(a) = a
def foo(...) = bar(...) # optimized
foo(123)
def bar(a) = a
def foo(...) = bar(1, 2, ...) # optimized
foo(123)
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:

def foo(...)
  super
end

This patch eliminates intermediate allocations made when calling methods that accept .... We can observe allocation elimination like this:

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

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

SomeObject.new(foo: 1)

If we combine this technique, plus implement Class#new in Ruby, then we can reduce allocations for this common operation.

@matzbot matzbot requested a review from a team April 11, 2024 23:49
@tenderlove tenderlove force-pushed the speed-forward branch 2 times, most recently from 2929a9d to 192b1b8 Compare April 12, 2024 18:48
@launchable-app

This comment has been minimized.

@tenderlove tenderlove force-pushed the speed-forward branch 11 times, most recently from 2964451 to 93c71fe Compare April 19, 2024 16:36
@tenderlove tenderlove force-pushed the speed-forward branch 2 times, most recently from 46ef870 to 063df23 Compare April 24, 2024 22:24
@tenderlove tenderlove force-pushed the speed-forward branch 6 times, most recently from bef7c28 to 84a07fe Compare May 28, 2024 16:09
Copy link
Copy Markdown
Contributor

@jeremyevans jeremyevans left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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));
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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?

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

@tenderlove tenderlove force-pushed the speed-forward branch 8 times, most recently from 6d234be to 83a1cd8 Compare June 7, 2024 20:00
@tenderlove tenderlove force-pushed the speed-forward branch 2 times, most recently from 31d3ecb to d43476d Compare June 17, 2024 20:18
tenderlove and others added 8 commits June 18, 2024 08:36
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants