How does Go interface dispatch work?
Qwertie
traditional vtable dispatch.
There have been some suggestions in older posts that Go code is slow
like dynamic languages - is Go still highly unoptimized? If interface
dispatch is not optimized, does there exist a theoretically fast
dispatch technique for go interfaces?
Rob 'Commander' Pike
On May 25, 2010, at 2:25 PM, Qwertie wrote:
> I'm curious how much slower Go interface dispatch is compared to
> traditional vtable dispatch.
It's essentially the same. Method dispatch on an interface variable
is the same as a vtable dispatch.
> There have been some suggestions in older posts that Go code is slow
> like dynamic languages - is Go still highly unoptimized? If interface
> dispatch is not optimized, does there exist a theoretically fast
> dispatch technique for go interfaces?
The relatively expensive operation is assignment to an interface value
- but even it is pretty cheap. The first time a concrete type hits an
interface type, it builds a hash table entry that points to a vtable.
Second and subsequent assignments of the same type will do a much
cheaper hash lookup to find the vtable. But the method dispatch
itself is always equivalent to a vtable lookup.
For the detail-obsessed, this program:
package main
type X interface { m() }
type C int
func (c C) m() {}
func main() {
var c C = 3
var x X = c // line 10
x.m() // line 11
}
Produces this code from 6g:
--- prog list "main" ---
0002 (x.go:11) TEXT main+0(SB),$64-0
0003 (x.go:9) MOVL $3,AX
0004 (x.go:10) MOVQ $type."".X+0(SB),(SP)
0005 (x.go:10) MOVQ $type."".C+0(SB),8(SP)
0006 (x.go:10) MOVL AX,16(SP)
0007 (x.go:10) CALL ,runtime.ifaceT2I+0(SB)
0008 (x.go:10) LEAQ 24(SP),SI
0009 (x.go:10) LEAQ x+-24(SP),DI
0010 (x.go:10) MOVSQ ,
0011 (x.go:10) MOVSQ ,
0012 (x.go:11) LEAQ x+-24(SP),BX
0013 (x.go:11) MOVQ 8(BX),BP
0014 (x.go:11) MOVQ BP,(SP)
0015 (x.go:11) MOVQ (BX),BX
0016 (x.go:11) MOVQ 32(BX),BX
0017 (x.go:11) CALL ,BX
0018 (x.go:11) RET ,
You can see that line 10, which assigns to the interface, calls a
helper function (ifaceT2I) that converts the type to an interface. It
will build the object the first time C and X are connected. Line 11
is essentially an vtable call: it pushes the receiver on the stack and
then does an indirect function call.
-rob
Evan Shaw
Russ blogged about the implementation of interfaces:
http://research.swtch.com/2009/12/go-data-structures-interfaces.html
So did Ian:
http://www.airs.com/blog/archives/281
- Evan
Ian Lance Taylor
For reference, here is the same code from gccgo for 32-bit x86. This
includes the support for discontiguous stacks, which 6g also generates
but is now shown in the sample code above. This also includes some
reference counting code which I expect to go away.
.loc 1 8 0
cmpl %gs:48, %esp
jb .L7
.L6:
.loc 1 8 0
pushl %ebp
movl %esp, %ebp
pushl %ebx
subl $36, %esp
.loc 1 10 0
leal -12(%ebp), %eax
.loc 1 9 0
movl $3, -12(%ebp)
.loc 1 10 0
movl %eax, 12(%esp)
movl $4, 8(%esp)
movl $__go_imt_I1_mFee__N9_go.main.C, 4(%esp)
movl $__go_tdn_go.main.C, (%esp)
call __go_new_interface_object
movl %eax, %ebx
.loc 1 11 0
movl 4(%eax), %eax
movl 8(%ebx), %edx
movl %edx, (%esp)
call *(%eax)
.loc 1 12 0
movl %ebx, (%esp)
movl $__go_tdn_go.main.X, 4(%esp)
call __go_decrement_refcount
addl $36, %esp
popl %ebx
popl %ebp
ret
.L7:
.loc 1 8 0
pushl $0
pushl $56
call __morestack
ret
jmp .L6
The method call is effectively these two instructions:
movl 4(%eax), %eax
...
call *(%eax)
__go_imt_I1_mFee__N9_go.main.C is the method table for
interface { m() } for the type C. __go_tdn_go.main.C is the type
descriptor for the type C.
Ian
⚛
> The relatively expensive operation is assignment to an interface value
> - but even it is pretty cheap. The first time a concrete type hits an
> interface type, it builds a hash table entry that points to a vtable.
> Second and subsequent assignments of the same type will do a much
> cheaper hash lookup to find the vtable.
Why hash-table? It seems unnecessarily more expensive than an
alternative implementation.
Joseph Stewart
Why hash-table? It seems unnecessarily more expensive than an
alternative implementation.
⚛
I don't think that was funny. Considering that you could simply take a
look at the assembly code in Ian Lance Taylor's post ...
The compiler knows all the information necessary to build the
interface-object involved in the conversion. Because of this, the fact
that Go *currently* performs some runtime computation and caching to
create the interface-object seems a little odd.
roger peppe
http://research.swtch.com/2009/12/go-data-structures-interfaces.html
in particular:
``Go's dynamic type conversions mean that it isn't reasonable for the
compiler or linker to precompute all possible itables: there are too
many (interface type, concrete type) pairs, and most won't be
needed.''
Ian Lance Taylor
gccgo does precompute the tables that it knows that it needs.
However, there is also a dynamic component: an arbitrary type may be
converted to an arbitrary interface, and in that case the method table
must be built at runtime. gccgo does this as well.
Ian
⚛
OK, that was my understanding as well.
On another note, let me paste a piece of code from the aforementioned
link:
type Stringer interface {
String() string;
}
func ToString(any interface{}) string {
if v, ok := any.(Stringer); ok {
return v.String();
}
switch v := any.(type) {
case int:
return strconv.Itoa(v);
case float:
return strconv.Ftoa(v, 'g', -1);
}
return "???";
}
Well, what I see there are pointless inefficiencies. Why not declare
it like "func ToString(s Stringer) string"? In the fmt package, why
not declare "Printf" like "func Printf(format string, a ...Stringer)
(n int, errno os.Error)"? It is beyond my comprehension why you are
using "...interface{}" there.
While it is true that the hash-table is a good solution for checking/
converting "interface{}" to "Stringer", it is in my opinion pointless
in this case. A more sane approach is to straightforwardly export the
requirement that "ToString" and "Printf" expect something that is
string-able. This would in the end most likely lead to more cases in
which the compiler can use a precomputed table.
roger peppe
> While it is true that the hash-table is a good solution for checking/
> converting "interface{}" to "Stringer", it is in my opinion pointless
> in this case. A more sane approach is to straightforwardly export the
> requirement that "ToString" and "Printf" expect something that is
> string-able. This would in the end most likely lead to more cases in
> which the compiler can use a precomputed table.
built-in types do not have a String method.
it's useful to be able to print ints, structs, pointers etc
without wrapping each one in a Stringer type.
chris dollin
While it is true that the hash-table is a good solution for checking/
converting "interface{}" to "Stringer", it is in my opinion pointless
in this case. A more sane approach is to straightforwardly export the
requirement that "ToString" and "Printf" expect something that is
string-able. This would in the end most likely lead to more cases in
which the compiler can use a precomputed table.
But int and float are not stringable (that is, they cannot be
converted to Stringer). In another message, the Go team said
it was deliberate that the built-in types had no methods defined
on them. And I know I'd like to be able to pass integers and
strings -- and indeed any type I'd happen to make up -- to
members of the Printf family.
What resolution of this conflict should we choose?
Chris
--
Chris "allusive" Dollin
⚛
Yes. But that does *not* mean that ints, pointers, etc cannot be
adapted to make it work - "adapting" means "slightly changing the
language if required".
Steven
⚛
var x, y, z
Printf("...", PrintType(x), PrintValue(y), PrintGoValue(z));
Russ Cox
> adapted to make it work - "adapting" means "slightly changing the
> language if required".
The blog post attempts to describe Go as it exists,
not Go as others might wish it to exist.
Russ