removing dynamic code generation

[Russ Cox]

I have been thinking a bit about how to remove dynamic code
generation. The document linked below describes my current thinking.
The short version is that I propose to:
- make func values two words, code ptr and closure frame ptr
- treat all Go functions as having a closure frame ptr as the new
first argument
- implement "f := r.Read" for method values (now it's trivial and cheap)
- allow v.Method(i).Interface() in reflect

Let's discuss here (the doc is read-only).

Russ

https://docs.google.com/document/pub?id=1IXHI5Jr9k4zDdmUhcZImH59bOUK0G325J1FY6hdelcM

[Alan Donovan]

Nice doc; sounds good to me. I too prefer the stack-based approach,
since I suspect the desire to construct closures from C will arise
before too long.

Significant typo: "would not leave space" should read "would leave
space" (I presume).

[Russ Cox]

> Significant typo: "would not leave space" should read "would leave
> space" (I presume).

Indeed. Fixed, thanks.

Russ

[Rémy Oudompheng]

A naïve question: is it possible to use the stack approach and still
not change the existing calling convention?
Meaning:

push arguments
if f.frame != nil {
push f.frame
}
call f.func

or would it be even worse due to the branching and additional housekeeping?

Rémy.

[Russ Cox]

On Wed, Sep 26, 2012 at 2:27 PM, Rémy Oudompheng
<remyoud...@gmail.com> wrote:
> A naïve question: is it possible to use the stack approach and still
> not change the existing calling convention?

It is possible but it would make the stack frame a variable size. For
the most part the Plan 9 toolchain assumes stack frames are fixed
size. We already violate that with go and defer, and I regret the
complication it causes in backtrace implementations. But at least go
and defer rarely block so those calls are never on the stack for long.
It would cause more problems to do that here. It would also break the
symmetry with interface calls.

Russ

[Andrew Gerrand]

On 26 September 2012 13:14, Russ Cox <r...@golang.org> wrote:
> - implement "f := r.Read" for method values (now it's trivial and cheap)

SGTM.

(Blake says: "Woah! Yes! That would be amazing!")

[Daniel Morsing]

Right off the top of my head, there's a semipredicate problem when you
want to do the new method syntax with a nil receiver. The frame
pointer in the func struct would be nil, and we'd not push it onto the
stack, even though it is the value that we want.

[Evan Shaw]

On Thu, Sep 27, 2012 at 6:14 AM, Russ Cox <r...@golang.org> wrote:
> I have been thinking a bit about how to remove dynamic code
> generation. The document linked below describes my current thinking.
> The short version is that I propose to:
> - make func values two words, code ptr and closure frame ptr
> - treat all Go functions as having a closure frame ptr as the new
> first argument
> - implement "f := r.Read" for method values (now it's trivial and cheap)
> - allow v.Method(i).Interface() in reflect
>
> Let's discuss here (the doc is read-only).

The sad thing is that putting a func value inside an interface will
start causing an allocation. But I suppose lots of those (like
http.HandlerFuncs) will be one-time initialization things, so maybe
it's not that bad.

- Evan

[Ian Lance Taylor]

On Wed, Sep 26, 2012 at 11:14 AM, Russ Cox <r...@golang.org> wrote:
> I have been thinking a bit about how to remove dynamic code
> generation. The document linked below describes my current thinking.
> The short version is that I propose to:
> - make func values two words, code ptr and closure frame ptr
> - treat all Go functions as having a closure frame ptr as the new
> first argument
> - implement "f := r.Read" for method values (now it's trivial and cheap)
> - allow v.Method(i).Interface() in reflect

You kind of skated over an interesting point in your proposal: every
ordinary function will take an extra unused initial argument, but
every method will not.

I haven't looked closely at the gc implementation, but it appears that
it allocates an entire stack frame for a function and then stores
arguments in the right slots, rather than, say, pushing arguments on
the stack as it goes. That is good for this proposal, because it
means that the only cost is burning an extra stack slot per function
call. No additional instructions are required.

So overall it looks good to me.

I will have to think about what to do in gccgo. For me adding a new
first argument is not nearly free. But in any case there should be no
major difficulty for gccgo here.

Ian

[Rob Pike]

The terminology in the document confused me on first reading. The arg
field isn't args, it's variables. Moreover, it's referred to as a
frame pointer, which it is, but it's not the function's frame it
refers to but sort of an idealization of the caller's frame. The
presentation could be clearer.

-rob

[Robert Griesemer]

Agreed. I would call it "context" instead of "frame pointer".

- gri

[Robert Griesemer]

[this time sending also to golang-dev]

Overall this sounds great to me. Some comments:

1) If the context were passed in a register, I don't understand the need for assembly stubs when calling Go functions directly from C: If the calls are direct function calls, the called functions don't access the context (register) and thus it doesn't matter that C doesn't set it up. What am I missing? (I understand that it would preclude closure-like Go function values written in C, but that doesn't seem that important). Using a register for the context does seem attractive to me since it's an "optimization by design": at least with naive code generation, it should remove an indirection in closures each time the context is accessed. But perhaps the register optimizer takes care of that.

2) I am strongly in favor of "method values".

3) This is not directly related to this proposal, but the implementation opens the door for the "dual" or "inverse" of method values, which is single-method interfaces accepting functions that satisfy the interface method ("function interfaces"?). With method values I can write:

type T interface { m(x int) string }

var x T

var f := x.m // method value, f is a function

The inverse operation would be to assign a function f to a single method interface:

x = T(f) // f is a func(x int) string; an explicit conversion is used to highlight the operation (perhaps there's a better syntax)

This is the natural conclusion of the idea that a single-method interface and a function/closure value are essentially the same. Given that out library is using a lot of single-method interfaces, I see a lot of potential for simpler code where we can use an in-line closure as opposed to an out-of-line object and method declaration.

To summarize: I think we should go forward with this proposal (and also consider 3), perhaps at a later stage).

- gri

On Wed, Sep 26, 2012 at 11:14 AM, Russ Cox <r...@golang.org> wrote:

[Russ Cox]

Replying to three different messages.

On Wed, Sep 26, 2012 at 5:55 PM, Rob Pike <r...@golang.org> wrote:
> The terminology in the document confused me on first reading. The arg
> field isn't args, it's variables. Moreover, it's referred to as a
> frame pointer, which it is, but it's not the function's frame it
> refers to but sort of an idealization of the caller's frame. The
> presentation could be clearer.

Agreed. I took Robert's suggestion of calling the arg field a context pointer.

On Wed, Sep 26, 2012 at 6:14 PM, Robert Griesemer <g...@golang.org> wrote:
> 1) If the context were passed in a register, I don't understand the need for
> assembly stubs when calling Go functions directly from C:

Go functions are okay; it's only Go closures that need assembly help,
to stuff the register. I revised the text.

On Wed, Sep 26, 2012 at 4:00 PM, Ian Lance Taylor <ia...@google.com> wrote:
> You kind of skated over an interesting point in your proposal: every
> ordinary function will take an extra unused initial argument, but
> every method will not.

You are very good at zeroing in on flaws in my thinking. You're right
that the new method value/closure unification (t.M) implies that
methods do not take the unused initial argument. Unfortunately, the
existing method expression/function unification (T.M) implies that
they do, so we have a contradiction. It's not terrible but it does
imply that one of these requires a wrapper. However, needing to
rethink the method calling convention might not be all bad. Right now
interface calls to non-pointer receivers are made through a wrapper.
If we have to revise something about methods we might want to look
first at making that wrapper cheaper.

I will shelve the proposal for now until I can spend more time
thinking about how method calls should look.

Russ

[Dave Cheney]

From the arm point of view, closures need a cache flush to make the
transition from dcache to icache. Sadly, like most things, this is a
syscall on arm, which makes them expensive. This is one reason why go
tool api is very slow on arm (rubber band powered cpus is another, but
I digress).

You are correct that passing the closure context on the stack will
mean revising all the asm, I think this is a reasonable price to pay,
and you've already been working behind the scenes to make this process
manageable with your asmlint tool.

> But in another way a func value is just a more limited form of an interface value: it’s like an interface with a single unnamed method.

Interestingly, this is similar to the way Java 8 will implement
closures behind the scenes.

This is an excellent proposal, reducing the cost of closures, and
introducing method values sounds wonderful.

Dave

[minux]

On Thu, Sep 27, 2012 at 10:42 AM, Russ Cox <r...@golang.org> wrote:

On Wed, Sep 26, 2012 at 4:00 PM, Ian Lance Taylor <ia...@google.com> wrote:
> You kind of skated over an interesting point in your proposal: every
> ordinary function will take an extra unused initial argument, but
> every method will not.

You are very good at zeroing in on flaws in my thinking. You're right
that the new method value/closure unification (t.M) implies that
methods do not take the unused initial argument. Unfortunately, the
existing method expression/function unification (T.M) implies that
they do, so we have a contradiction. It's not terrible but it does
imply that one of these requires a wrapper. However, needing to
rethink the method calling convention might not be all bad. Right now
interface calls to non-pointer receivers are made through a wrapper.
If we have to revise something about methods we might want to look
first at making that wrapper cheaper.

This is the problem I've been thinking since I heard you'd like to use

the extra stack slot approach.

How much effort would it take if we choose to use a register for the

context parameter? (calling Go closure from C is not something we

do frequently, in fact, I think we don't use it in the runtime)

If we choose to go that route, i think we can move the dedicate register

immediately to stack on entry for closure functions, and then the

optimizer won't need to handle that register as special case.

When optimizer improves, we can drop this unnecessary move/push.

[Daniel Morsing]

On Thu, Sep 27, 2012 at 12:14 AM, Robert Griesemer <g...@golang.org> wrote:
> x = T(f) // f is a func(x int) string; an explicit conversion is used to
> highlight the operation (perhaps there's a better syntax)
>

I'm not sure about this. I think the name of the method having to
match in the interface is valuable. For example, the Reader and Writer
interfaces are only distinguished by the name of their single method.
Also, if someone comes along later and extends the interface with new
methods, these conversions will be invalid, and could cause a big
restructuring of a program which could have been avoided if interfaces
were used directly in the first place.

Perhaps unrelated, casting from a single interface method to a
function will throw away type information. I haven't fully thought out
the implications of this, but I'm fairly sure there will be some
wrinkle to the implementation stemming from this property.

However, I favor method to function conversions. Those look very promising.

[minux]

On Thu, Sep 27, 2012 at 3:00 PM, Daniel Morsing <daniel....@gmail.com> wrote:

On Thu, Sep 27, 2012 at 12:14 AM, Robert Griesemer <g...@golang.org> wrote:
> x = T(f) // f is a func(x int) string; an explicit conversion is used to
> highlight the operation (perhaps there's a better syntax)

I'm not sure about this. I think the name of the method having to
match in the interface is valuable. For example, the Reader and Writer
interfaces are only distinguished by the name of their single method.
Also, if someone comes along later and extends the interface with new
methods, these conversions will be invalid, and could cause a big
restructuring of a program which could have been avoided if interfaces
were used directly in the first place.

If you extend interface with new methods, lots of other code will break.

besides, even we use interface here, when interface itself is changed,

you still need to implement the new method of that interface for your object.

I don't think we could extend a single method interface.

[Daniel Morsing]

On Thu, Sep 27, 2012 at 9:19 AM, minux <minu...@gmail.com> wrote:
> If you extend interface with new methods, lots of other code will break.
> besides, even we use interface here, when interface itself is changed,
> you still need to implement the new method of that interface for your
> object.

This change is fairly easy and doesn't impact the structure of the
existing code, beyond what you're using the new method call for. You
will not have to switch the types of the dynamic dispatch mechanism.

> I don't think we could extend a single method interface.

I agree that for the standard library, changing any of the single
method interfaces is crazy. I am thinking about this in the context of
someone with complete control over both the types that implement the
interface, and the interface itself.

[Robert Griesemer]

As minux pointed out already; even w/o "function interfaces" T(f), a lot of code will break if the underlying interface changes, and the code needs to be adjusted. The compiler errors will be very explicit and very clear. It's not a problem for the standard library as you have pointed out yourself. From the point of someone with complete control over all the code it's also not a problem because you're not forced to use the mechanism. Finally, by making the conversion of a function f to a single-method interface T explicit via a conversion T(f), it is very clear what is happening in the code.

That said, there's plenty of stuff that would have to be worked out (for instance, what's the object in the interface (is there one?), etc). Still, closures and (single-method) interfaces are interrelated at a very fundamental level and I believe it's inevitable that this connection reveals itself in a language at some point.

But this is all secondary to Russ' proposal, which is first and formost about an implementation of closures w/o code generation and the primary focus right now.

- gri

[Rémy Oudompheng]

I'm not particularly interested in the
function-as-a-single-method-interface stuff, but if this was to ever
happen, I'd like it be mandatorily qualified. Like:

type Handler interface { Handle(...) }

h := Handler{Handle: handleFunction}

That ensures that code is broken whenever the interface changes
semantics and method names while keeping the signature.

Rémy.

2012/9/27, Robert Griesemer <g...@golang.org>:

[Kyle Lemons]

On Wed, Sep 26, 2012 at 7:42 PM, Russ Cox <r...@golang.org> wrote:

Replying to three different messages.

On Wed, Sep 26, 2012 at 5:55 PM, Rob Pike <r...@golang.org> wrote:
> The terminology in the document confused me on first reading. The arg
> field isn't args, it's variables. Moreover, it's referred to as a
> frame pointer, which it is, but it's not the function's frame it
> refers to but sort of an idealization of the caller's frame. The
> presentation could be clearer.

Agreed. I took Robert's suggestion of calling the arg field a context pointer.

On Wed, Sep 26, 2012 at 6:14 PM, Robert Griesemer <g...@golang.org> wrote:
> 1) If the context were passed in a register, I don't understand the need for
> assembly stubs when calling Go functions directly from C:

Go functions are okay; it's only Go closures that need assembly help,
to stuff the register. I revised the text.

On Wed, Sep 26, 2012 at 4:00 PM, Ian Lance Taylor <ia...@google.com> wrote:
> You kind of skated over an interesting point in your proposal: every
> ordinary function will take an extra unused initial argument, but
> every method will not.

Apologies if I'm misunderstanding something here...

 

You are very good at zeroing in on flaws in my thinking. You're right
that the new method value/closure unification (t.M) implies that
methods do not take the unused initial argument.

I think this is the part I don't understand, as it seems to me like it would work, since methods already had an implied initial argument.  Let me create an example, somewhat contrived...

type Counter struct {

  lock   sync.Mutex

  count int

}

func (c *Counter) Count() int {

  c.lock.Lock()

  defer c.lock.Unlock()

  return c.count

}

func (c *Counter) Increment() int {

  c.lock.Lock()

  defer c.lock.Unlock()

  c.count++

  return c.count

}

func IncrementBy(c *counter, by int) func() int {

  return func() int {

    c.lock.Lock()

    defer c.lock.Unlock()

    c.count += by

    return c.count

  }

}

The (*Counter).Count and (*Counter).Increment methods are, internally, (using a notation {functype, context/receiver} of my own devising) {func(c *Counter) int, nil}, and presumably the compiler will know that such values are unbound and that any call must explicitly specify a receiver.  If, however, you ask for c := new(Counter); m := c.Count; the value would instead be {func(c *Counter) int, c}, and the compiler would know that such values are bound, and need no receiver value at a call site.  The return value of a call IncrementBy(c, n) would be {func(struct{*counter;int}) int, struct{*counter;int}{c, n}} and the compiler would know that this is also already "bound".  The IncrementBy function itself is similarly {func(void*, *counter, int) func() int, nil} but, being a function, the compiler knows that it doesn't need to be bound or "is already bound to nil".

Am I missing something?

[Ian Lance Taylor]

I think that is all correct, but now consider
f := Counter.Increment
That gives f the type func(Counter*) int.

Ian

[Daniel Morsing]

On Thu, Sep 27, 2012 at 8:46 PM, Kyle Lemons <kev...@google.com> wrote:
>
> Am I missing something?
>

It conflicts with receivers of value type, and the issue that Ian mentioned.

[Kyle Lemons]

I think I see the disparity now... I was thinking that you could conflate the context part of the func value with the receiver in a curried method value. The compiler can know and do the right thing at call sites, but it would mess up the types and such:

fmt.Printf("%T", Counter.Increment) // "func(Counter*) int"

fmt.Printf("%T", new(Counter).Increment) // "func() int" even though it's really "func(Counter*) int" with a Counter* passed alongside it.

[roger peppe]

I'm very happy to see this moving forward. I think
it has the potential to make closure creation much
cheaper (sort.Search, for example, has unreasonable
overhead when used in a tight loop). I suspect
closure calls will end up considerably faster too.

For implementation, I wonder if it might be reasonable
use the stack approach, but generate a header/wrapper for any normal
function that's used as a closure - this would strip the
first argument and call the underlying function.
When creating a closure from a normal function, the
closure would point to the function's header, not its body.

Closure functions and method values would not need
the header.

The down side of this is that calling an ordinary function as a closure
would a little more expensive than before. However,
no existing functions would need to change and all the other
benefits of the stack-based approach apply.

[Daniel Morsing]

On Mon, Oct 1, 2012 at 10:10 AM, roger peppe <rogp...@gmail.com> wrote:
> For implementation, I wonder if it might be reasonable
> use the stack approach, but generate a header/wrapper for any normal
> function that's used as a closure - this would strip the
> first argument and call the underlying function.
> When creating a closure from a normal function, the
> closure would point to the function's header, not its body.
>

This would mean adding support for the argument stripping into the
linker. The stack splitting preamble needs to be executed on every
call, so the argument stripping has to happen before the stack split.
Currently the stack splitting is inserted by the linker, so the
stripping has to be put in there as well.

Also, the argument stripping will either have to adjust the frame
pointer or do memory copying. I don't think either of those options
would be desirable.

In order to preserve the current semantics of method to function
conversion, I think Remy's suggestion is the most workable one.
There's still a great deal of uncertainty with all the current options
and I think that's one of the reasons Russ went back to the drawing
board.