research!rsc: Go Data Structures: Interfaces https://research.swtch.com/interfaces
How Interfaces Work in Go https://www.tapirgames.com/blog/golang-interface-implementation
This article will introduce the internal implementation of interface types by the official Go compiler.
The explanations in this article aren't precisely in accordance with the official Go compiler and runtime implementation. The main intention of this article is to explain the theory, instead of concrete implementations. This article also ignores many details, including:
All interface types have the same internal definition:
type _interface struct {
dynamicTypeInfo *_implementation
dynamicValue unsafe.Pointer // unsafe.Pointer means
// *ArbitraryType in Go.
}
The internal _implementation
type is declared like
type _implementation struct {
itype *_type // the interface type.
dtype *_type // the dynamic type, which must implement itype.
methods []*_func // the methods which are defined on dtype
// and each of them implements a
// corresponding method declared in itype.
}
From the definitions, we know that each interface value contains two pointer fields. The dynamicValue
field stores the dynamic value information, and the dynamicTypeInfo
field stores the implementation information. dynamicTypeInfo.itype
stores the type information of the interface value and dynamicTypeInfo.dtype
stores the type information of the dynamic value.
The dynamicTypeInfo
field of an interface value may be nil
, which means nothing is stored in the interface value. For this case, the dynamicValue
field must be also nil
. We can also say the dynamic value of the interface value is untyped nil
for this case.
For the official Go compiler and runtime, a non-nil dynamicValue
field value may store
Surely, it is not essential to make the exception for pointer dynamic values. This is just a compiler optimization. We can get why it is an optimization in following sections. (BTW, about more current and future optimizations in the official interface implementation, please read this article.)
Other involved internal types are declared like:
type _func struct {
name string
methodSig uint // two methods with the same signature have
// the same signature id. Receiver parameter
// doesn't contribute to this signature.
funcSig uint // receiver parameter accounts to this signature.
// other information ...
}
type _type struct {
name string // type name
id uint32 // each type has unique id
flags uint32 // comparable? isPointer?
size uintptr // value size in bytes
kind uint8 //
methods []*_func // the methods are sorted
// by methodSig and name.
// more information ...
}
const (
// flags
TypeFlag_Comparable = 1 << 0
TypeFlag_IsPointer = 1 << 1
TypeFlag_IsString = 1 << 2
)
func (t *_type) IsComparable() bool {
return t.flags & TypeFlag_Comparable != 0
}
func (t *_type) IsPointer() bool {
return t.flags & TypeFlag_IsPointer != 0
}
func (t *_type) IsString() bool {
return t.flags & TypeFlag_IsString != 0
}
Some fields of above types are not listed, for they are unrelated to this article.
Here is the function to get an _implementation
value from an interface type and a non-interface type:
// global table
var cachedImpls = map[uint64]*_implementation{}
// itype must be an interface type and
// dtype must be a non-interface type.
// Return nil if dtype doesn't implement itype.
// Must not return nil if dtype implements itype.
func getImpl (itype *_type, dtype *_type) *_implementation {
var key = uint64(itype.id) << 32 | uint64(dtype.id)
var impl = cachedImpls[key]
if impl == nil {
// for each (dtype, itype) pair, the implementation
// method table is only calculated most once at
// run time. The calculation result will be cached.
var numMethods = len(itype.methods)
var methods = make([]*_func, numMethods)
// find every implemented methods.
// The methods of itype and dtype are both sorted
// by methodSig and name.
var n = 0
var i = 0
for _, im := range itype.methods {
for i < len(dtype.methods) {
tm := dtype.methods[i]
i++
// Here, for simplicity, assume
// all methods are exported.
if tm.methodSig < im.methodSig {
continue
}
if tm.methodSig > im.methodSig {
// im method is not implemented
return nil
}
if tm.name < im.name {
continue
}
if tm.name > im.name {
// im method is not implemented
return nil
}
methods[n] = tm
n++
break
}
}
// dtype doesn't implement all methods of itype
if n < numMethods {
return nil
}
// dtype implements itype.
// create and cache the implementation.
impl = &_implementation{
dtype: dtype,
itype: itype,
methods: methods,
}
cachedImpls[key] = impl
}
return impl
}
This function will be called in the value conversions explained in following sections.
In any Go program, at run time, all _implementation
values are cached and stored in a global map and all _type
values are stored in a global immutable array.
As the blank interface type interface{}
is used popular in Go programming, the official Go compiler uses a different and more efficient underlying definition for the blank interface than other interface types:
// blank interface
struct {
dynamicType *_type // the dynamic type
dynamicValuePtr unsafe.Pointer // points to the dynamic value
}
To make the explainations simpler, following sections will treat blank interface types as general interface types.
Here is the internal function to convert a non-interface value to an interface type:
// To call this function, compilers must assure
// 1. itype is an interface type.
// 2. dtype is nil or a non-interface type and implements itype.
// p must be nil if dtype is nil.
// p is a pointer stores the address of a value of dtype if dtype
// is not a pointer type. p stores the value of a value of dtype
// if dtype is a pointer type.
func t2i (itype *_type, dtype *_type, p unsafe.Pointer) _interface {
// dtype is nil means the non-interface value is untyped nil
if dtype == nil {
return _interface {
dynamicValue: nil,
dynamicTypeInfo: nil,
}
}
// the pointer dynamic value optimization, no need to
// allocate the extra memory block.
if dtype.IsPointer() {
return _interface {
dynamicValue: p,
dynamicTypeInfo: getImpl(dtype, itype),
}
}
// for non-pointer dynamic value, runtime must
// allocate an extra memory block to store a copy
// of the non-pointer value.
var t = memoryAlloc(dtype)
memoryCopy(t, p, dtype.size)
return _interface {
dynamicValue: t,
dynamicTypeInfo: getImpl(dtype, itype),
}
}
Compilers will insert a call of this function before
Here is the internal function to convert an interface value to an interface type:
// To call this function, compilers must assure
// 1. itype is an interface type.
// 2. the dynamic value of ivalue is untyped nil
// or the dynamic type of ivalue implements ivalue.
// (the method set of the dynamic type of ivalue must
// must be a super set of the method set of itype).
func i2i (itype *_type, ivalue _interface) _interface {
// the dynamic value of ivalue is untyped nil.
if ivalue.dynamicTypeInfo == nil {
return _interface {
dynamicValue: nil,
dynamicTypeInfo: nil,
} // <=> return ivalue
}
// compilers should avoid calling this function
// for this case.
if ivalue.dynamicTypeInfo.itype == itype {
return ivalue // return a copy of ivalue.
}
// Convert the dynamic value of ivalue to itype.
// Here, the returned interface value and ivalue
// will share the same extra memory block which
// stores the dyanmic value if the dynamic value
// is not a pointer.
return _interface {
dynamicValue: ivalue.dynamicValue,
dynamicTypeInfo: getImpl(
ivalue.dynamicTypeInfo.dtype,
itype,
), // here, the getImpl call never return nil.
}
}
Compilers will call this function before
Compilers should translate converting an interface value to its own type as a no-op.
In an interface value assignment, the destination value must be an interface value, and the type of the source value must implement the destination interface type. The source value may be either a non-interface value or an interface value. As above two sections mentioned, compilers will convert the source value to the destination interface type before the assignment. So in the final assignment, the source value and the destination value have the same type, the destination interface type.
For the current official Go compiler/runtime, there are just two copies for the two fields, dynamicValue
and dynamicTypeInfo
, in the final assignment. So if the dynamic value is non-pointer, the underlying dynamic value memory block, which address is stored in the dynamicValue
field, will be shared between the destination and source interface values. However, this should be viewed as an optimization. Other compilers may not adopt this optimization.
There are three comparison circumstances involving interface values:
nil
.A good compiler should treat the three circumstances differently to get better program performance. Here, for simplicity, we assume non-interface and untyped nil
values will be converted to interface{}
type before making the comparisons. So all comparisons involving interface values can be viewed as comparing two interface values.
Here is the internal function to compare two interface values:
func iCompare (ivalue1 _interface, ivalue2 _interface) bool {
// untyped nil is only equal to untyped nil.
if ivalue1.dynamicTypeInfo == nil {
return ivalue2.dynamicTypeInfo == nil
}
if ivalue2.dynamicTypeInfo == nil {
return false
}
// panic on incomparable dynamic values.
if ! ivalue1.dynamicTypeInfo.dtype.IsComparable() {
panic(ivalue1.dynamicTypeInfo.dtype.name +
" is incomparable")
}
if ! ivalue2.dynamicTypeInfo.dtype.IsComparable() {
panic(ivalue2.dynamicTypeInfo.dtype.name +
" is incomparable")
}
// return false if dynamic type is not the same.
if ivalue1.dynamicTypeInfo.dtype !=
ivalue2.dynamicTypeInfo.dtype {
return false
}
// optimization: early return.
if ivalue1.dynamicValue == ivalue2.dynamicValue {
return true
}
// special case: string comparison
if ivalue1.dynamicTypeInfo.dtype.IsString() {
return stringCompare(
*(*string)(ivalue1.dynamicValue),
*(*string)(ivalue2.dynamicValue),
)
}
// general case: compare all bytes in dynamic value
// memory blocks one by one.
return memoryCompare(
ivalue1.dynamicValue,
ivalue2.dynamicValue,
ivalue1.dynamicTypeInfo.dtype.size,
)
}
This article will not explain how two strings are compared.
Here is the internal function to assert an interface value to a non-interface type:
// To call this function, compilers must assure
// 1. dtype is a non-interface type.
// 2. outP is nil or stores the address of a value of dtype.
// 3. outOk is nil or stores the address of a bool value.
func assertI2T (ivalue _interface, dtype *_type,
outP *unsafe.Pointer, outOk *bool) {
// dynamic value is untype nil.
if ivalue.dynamicTypeInfo == nil {
// if okay is not present, panic.
if outOk == nil {
panic("interface is nil, not " + dtype.name)
}
// return (zero value, false)
*outOk = false
if outP != nil {
if dtype.IsPointer() {
*outP = nil
} else {
memoryReset(*outP, dtype.size)
}
}
return
}
// assersion fails.
if ivalue.dynamicTypeInfo.dtype != dtype {
// if ok is not present, panic.
if outOk == nil {
panic("interface is " +
ivalue.dynamicTypeInfo.dtype.name +
", not " + dtype.name)
}
// return (zero value, false)
*outOk = false
if outP != nil {
if dtype.IsPointer() {
*outP = nil
} else {
memoryReset(*outP, dtype.size)
}
}
return
}
// assersion succeeds.
if outOk != nil {
*outOk = true
}
if outP == nil {
return
}
// copy dynamic value.
if dtype.IsPointer() {
*outP = ivalue.dynamicValue
} else {
memoryCopy(*outP, ivalue.dynamicValue, dtype.size)
}
}
Here is the internal function to assert an interface value to an interface type:
// To call this function, compilers must assure
// 1. itype is an interface type.
// 2. outI is nil or stores the address of a value of itype.
// 3. outOk is nil or stores the address of a bool value.
func assertI2I (ivalue _interface, itype *_type,
outI *_interface, outOk *bool) {
// dynamic value is untype nil.
if ivalue.dynamicTypeInfo == nil {
// if ok is not present, panic.
if outOk == nil {
panic("interface is nil, not " + itype.name)
}
*outOk = false
if outI == nil {
*outI = _interface {
dynamicValue: nil,
dynamicTypeInfo: nil,
}
}
return
}
// check whether or not the dynamic type implements itype
var impl = getImpl(itype, ivalue.dynamicTypeInfo.dtype)
// assersion fails.
if impl == nil {
// if ok is not present, panic.
if outOk == nil {
panic("interface is " +
ivalue.dynamicTypeInfo.dtype.name +
", not " + itype.name)
}
// return (zero value, false)
*outOk = false
if outI != nil {
*outI = _interface {
dynamicValue: nil,
dynamicTypeInfo: nil,
}
}
return
}
// assersion succeeds.
if outI == nil {
*outOk = true
}
if outI != nil {
*outI = _interface {
dynamicValue: ivalue.dynamicValue,
dynamicTypeInfo: impl,
}
}
}
If the type of the interface value is the asserted interface type, compilers should simply return the interface value.
For an interface value i
, a call of its nth method (by the order after sorted)
... = i.Method_n(...)
will be translated to
if i.dynamicTypeInfo == nil {
panic("runtime error: nil pointer dereference")
}
if i.dynamicTypeInfo.dtype.IsPointer() {
... = _call(i.dynamicTypeInfo.methods[n], i.dynamicValue, ...)
} else {
... = _call(i.dynamicTypeInfo.methods[n],
*(*unsafe.Pointer)(i.dynamicValue), ...)
}
Please visit Go 101 for more articles on Go language.
Golang Interfaces Explained - Alex Edwards https://www.alexedwards.net/blog/interfaces-explained
Posted on: 6th August 2019Filed under: golang tutorial
Logging, interfaces, and allocation · Don't Panic http://commaok.xyz/post/interface-allocs/
This post is about some new compiler optimizations scheduled for Go 1.9, but I want to start with logging.
A couple of weeks ago, Peter Bourgon started a thread on golang-dev about standardizing logging. Logging is pervasive, so performance came up quickly. The go-kit log package uses structured logging, centered on this interface:
type Logger interface {
Log(keyvals ...interface{}) error
}
Sample call:
logger.Log("transport", "HTTP", "addr", addr, "msg", "listening")
Note that everything that goes into a logging call gets converted into an interface. This means that it allocates a lot.
Compare with another structured logger, zap. Zap has uglier call sites, specifically to avoid using interfaces, in order to be zero-allocation:
logger.Info("Failed to fetch URL.",
zap.String("url", url),
zap.Int("attempt", tryNum),
zap.Duration("backoff", sleepFor),
)
The arguments to logger.Info
have type logger.Field
. logger.Field
is a kind of union-ish struct that includes a type and a field each for a string
, an int
, and an interface{}
. Thus interfaces are not necessary to pass the most common kinds of values.
Enough about logging. Why does converting a concrete value to an interface sometime allocate?
Interfaces are represented as two words, a type pointer and a value pointer. Russ Cox wrote a lovely explanation of this, which I will not attempt to repeat. Just go read it.
His post is slightly out of date, however. He points out an obvious optimization: When the value is pointer-sized or smaller, we can just put the value directly into the second interface word. However, with the advent of concurrent garbage collection, that optimization got eliminated. Now the second word in the interface is always a pointer.
Consider:
fmt.Println(1)
Before Go 1.4, this code did not allocate, because the value 1
could be put directly into the second interface word.
That is, the compiler treated it something like this:
fmt.Println({int, 1})
where {typ, val}
represents the two words in an interface.
As of Go 1.4, this code started allocating, because 1
is not a pointer, and the second word must contain a pointer. So instead the compiler+runtime conspired to turn it into something roughly like:
i := new(int) // allocates!
*i = 1
fmt.Println({int, i})
This was painful, and there was much wringing of hands and gnashing of teeth.
The first significant optimization to remove allocations was added a bit later. It kicked in when the resulting interface did not escape. In that case, the temporary value could be put on the stack instead of the heap. Using our example code above:
i := new(int) // now doesn't allocate, as long as e doesn't escape
*i = 1
var e interface{} = {int, i}
// do things with e that don't make it escape
Unfortunately, many interfaces do escape, including those used in calls to fmt.Println
and in our logging examples above.
Happily, Go 1.9 will bring a few more optimizations, in part inspired by the logging conversation. (Unless those optimizations get reverted in the next six months, which is always a possibility.)
The first optimization is to not allocate to convert a constant to an interface. So fmt.Println(1)
will no longer allocate. The compiler puts the value 1
in a readonly global, roughly like this:
var i int = 1 // at the top level, marked as readonly
fmt.Println({int, &i})
This is possible because constants are immutable, and will thus be the same every time the interface conversion is reached, including recursively and concurrently.
This was inspired directly by the logging discussion. In structured logging, many of the arguments are constants– almost certainly all the keys, and probably a few of the values. Recall the go-kit example:
logger.Log("transport", "HTTP", "addr", addr, "msg", "listening")
This code drops from 6 allocations to 1, because five of the arguments are constant strings.
The second new optimization is to not allocate to convert bools and bytes to interfaces. This optimization works by adding a global [256]byte
array called staticbytes
to every binary, where staticbytes[b] = b
for all b. When the compiler wants to put a bool or uint8 or other single-byte value into an interface, instead of allocating, it calculates a pointer into this array. That is:
var staticbytes [256]byte = {0, 1, 2, 3, 4, 5, ...}
i := uint8(1)
fmt.Println({uint8, &staticbytes[i]})
There is a third new optimization proposed that is still under review, which is to not allocate to convert common zero values in an interface. It applies to integers, floats, strings, and slices. This optimization works by checking at runtime whether the value is 0
(or ""
or nil
). If so, it uses a pointer to an existing large chunk of zeroed memory rather than allocating some memory and zeroing it.
If all goes well, Go 1.9 should eliminate a fair number of allocations during interface conversions. But it won't eliminate all of them, which leaves performance still on the table as the logging discussion continues.
The interplay between implementation decisions and APIs is interesting.
Picking an API requires thinking about the performance consequences. It is not an accident that io.Reader
requires/allows callers to bring their own buffer.
Performance is in no small part a consequence of the implementation decisions. We have seen in this post that the implementation details of interfaces can substantially alter what code allocates.
And yet those very implementation decisions depend on what kind of code people write. The compiler and runtime authors want to optimize real, common code. For example, the decision to in Go 1.4 to keep interface values at two words instead of changing them to three, which made fmt.Println(1)
allocate, was based on looking at the kind of code people wrote.
Since the kind of code people write is often shaped heavily by the APIs they use, we have the kind of organic feedback loop that is fascinating and sometimes challenging to manage.
Not a terribly deep observation, perhaps, but there is one takeaway: If you're designing an API and worrying about performance, keep in mind not just what the existing compiler and runtime actually do, but what they could do. Write code for the present, but design APIs for the future.
And if you're not sure, ask. It worked (a bit) for logging.
手机扫一扫
移动阅读更方便
你可能感兴趣的文章