Runtime cost of type assertions

[Arnaud Delobelle]

Hi there!

Looking at performance bottlenecks for my implementation of Lua in Go ([1]), I found that type assertions can have a significant cost, which feels unnecessary to me.  I couldn't explain it without quite a lot of context, which makes my post quite long - sorry about that!

I have a Value type that holds Lua values:

// A Value is a runtime value.

type Value struct {

    scalar uint64

    iface interface{}

}

As Lua is dynamically typed, values can hold any type.  In the Lua runtime implementation, there are "type assertion" functions to convert a Value to a specific Go type, among which is the Cont interface type ([2]) which represents a continuation:

func (v Value) AsCont() Cont {

    return v.iface.(Cont)

}

This function is called every time a Lua function is called and turns out to be costly when many function calls are made.  I know exactly what types implement the Cont interface, so I tried an other implementation of AsCont as follows:

func (v Value) AsCont2() Cont {

    switch cont := v.iface.(type) {

        case *GoCont:

            return cont

        case *LuaCont:

            return cont

        case *Termination:

            return cont

        default:

            // Only the types above implement the Cont interface

            panic("value is not a continuation")

    }

}

Here is a benchmark comparing AsCont and AsCont2.

func BenchmarkAsCont(b *testing.B) {

    v1 := ContValue(new(GoCont))

    v2 := ContValue(new(LuaCont))

    v3 := ContValue(new(Termination))

    b.ResetTimer()

    for i := 0; i < b.N; i++ {

        _ = v1.AsCont()

        _ = v2.AsCont()

        _ = v3.AsCont()

    }

}

func BenchmarkAsCont2(b *testing.B) {

    v1 := ContValue(new(GoCont))

    v2 := ContValue(new(LuaCont))

    v3 := ContValue(new(Termination))

    b.ResetTimer()

    for i := 0; i < b.N; i++ {

        _ = v1.AsCont2()

        _ = v2.AsCont2()

        _ = v3.AsCont2()

    }

}

$ go test -run='^$' -bench '^(BenchmarkAsCont)' github.com/arnodel/golua/runtime

goos: darwin

goarch: amd64

pkg: github.com/arnodel/golua/runtime

cpu: Intel(R) Core(TM) i7-7820HQ CPU @ 2.90GHz

BenchmarkAsCont-8       52798504                20.96 ns/op

BenchmarkAsCont2-8      433032686                2.866 ns/op

PASS

ok      github.com/arnodel/golua/runtime        2.908s

There's a very significant difference in this benchmark, and in some "real tests" benchmarking Lua code  I get ~15% speedup, which is pretty good.  Now here are my questions.

Question 1: I *think* that the compiler has all the information necessary to implement type assertion to the Cont interface as I have, i.e. it knows only 3 types implement that interface, so could it not do the optimisation on my behalf?

Question 2: Or is it possible that other Go values can be made at runtime that would implement this interface but not be one of the three known types that implement it?

Question 3: Is it possible that there is something dodgy going on with the benchmarks, with some code being optimised away - if so, how can I check that?

Thanks in advance for any insights!

-- 

Arnaud

[1] https://github.com/arnodel/golua

[2] Definition of the Cont interface type:

type Cont interface {

    Push(Value)

    PushEtc([]Value)

    RunInThread(*Thread) (Cont, *Error)

    Next() Cont

    DebugInfo() *DebugInfo

}

[Axel Wagner]

On Tue, Dec 29, 2020 at 4:37 PM Arnaud Delobelle <arn...@gmail.com> wrote:

Question 1: I *think* that the compiler has all the information necessary to implement type assertion to the Cont interface as I have, i.e. it knows only 3 types implement that interface, so could it not do the optimisation on my behalf?

 

Question 2: Or is it possible that other Go values can be made at runtime that would implement this interface but not be one of the three known types that implement it? 

Yes, re 2. `reflect` can create new types at runtime. AFAIK the implementation for interface-type-assertions is basically to look it up in a global hashmap, which is pre-seeded with compile-time known types and then gets filled on each (successful) inteface-type-assertion with the correct method tables. But, I'm handwaving.

Under these assumptions, it might be *possible* to first check against the statically known types and only fall back on the map if none of that matches. But it doesn't seem 100% clear to me that that's always faster.

I think concrete type-assertions will always be faster than interface type-assertions though - for a concrete type-assertions, it's really just comparing the two type-pointers and copying the value (which, in your case, is a pointer itself), whereas for an interface type-assertion, the actual method table must be assembled or looked up.

But, here's a question: If `v.iface` always contains a `Cont` - at least that's what I assume from the fact that you don't use a ,ok assertion - why not just declare it as such, instead of `interface{}`?

Question 3: Is it possible that there is something dodgy going on with the benchmarks, with some code being optimised away - if so, how can I check that?

Sorry, no idea.

 

Thanks in advance for any insights!

-- 

Arnaud

[1] https://github.com/arnodel/golua

[2] Definition of the Cont interface type:

type Cont interface {

    Push(Value)

    PushEtc([]Value)

    RunInThread(*Thread) (Cont, *Error)

    Next() Cont

    DebugInfo() *DebugInfo

}

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/efcf0a84-4e7d-4241-9f5a-994774a7f14dn%40googlegroups.com.

[Arnaud Delobelle]

On Tuesday, 29 December 2020 at 16:25:41 UTC axel.wa...@googlemail.com wrote:

On Tue, Dec 29, 2020 at 4:37 PM Arnaud Delobelle <arn...@gmail.com> wrote:

Question 1: I *think* that the compiler has all the information necessary to implement type assertion to the Cont interface as I have, i.e. it knows only 3 types implement that interface, so could it not do the optimisation on my behalf?

 

Question 2: Or is it possible that other Go values can be made at runtime that would implement this interface but not be one of the three known types that implement it? 

Yes, re 2. `reflect` can create new types at runtime. AFAIK the implementation for interface-type-assertions is basically to look it up in a global hashmap, which is pre-seeded with compile-time known types and then gets filled on each (successful) inteface-type-assertion with the correct method tables. But, I'm handwaving.

Under these assumptions, it might be *possible* to first check against the statically known types and only fall back on the map if none of that matches. But it doesn't seem 100% clear to me that that's always faster.

I think concrete type-assertions will always be faster than interface type-assertions though - for a concrete type-assertions, it's really just comparing the two type-pointers and copying the value (which, in your case, is a pointer itself), whereas for an interface type-assertion, the actual method table must be assembled or looked up.

But, here's a question: If `v.iface` always contains a `Cont` - at least that's what I assume from the fact that you don't use a ,ok assertion - why not just declare it as such, instead of `interface{}`?

It doesn't always contain a Cont.  Sometimes it should, which is why this function panics (programming error).  There is also TryCont() which returns a boolean as well and doesn't panic. 

[Arnaud Delobelle]

On Tuesday, 29 December 2020 at 16:25:41 UTC axel.wa...@googlemail.com wrote:

On Tue, Dec 29, 2020 at 4:37 PM Arnaud Delobelle <arn...@gmail.com> wrote:

Question 1: I *think* that the compiler has all the information necessary to implement type assertion to the Cont interface as I have, i.e. it knows only 3 types implement that interface, so could it not do the optimisation on my behalf?

 

Question 2: Or is it possible that other Go values can be made at runtime that would implement this interface but not be one of the three known types that implement it? 

Yes, re 2. `reflect` can create new types at runtime. AFAIK the implementation for interface-type-assertions is basically to look it up in a global hashmap, which is pre-seeded with compile-time known types and then gets filled on each (successful) inteface-type-assertion with the correct method tables. But, I'm handwaving.

Ok, I have just looked at the docs for the reflect package, but I can't see a way to create a type that implements anything but the empty interface.  Is that correct?  In that case, wouldn't it mean that it is known at compile time what types implement a given (non-empty) interface?

Edit: I see that reflect.StructOf allows creation of struct types out of StructField specifications, which have an Anonymous boolean field.  I imagine that the created struct will inherit the methods of embedded types, so it may implement non empty interfaces.  I'm interested in valid use-cases for this, as it seems to be the thing that prevents this optimisation from being possible.

Under these assumptions, it might be *possible* to first check against the statically known types and only fall back on the map if none of that matches. But it doesn't seem 100% clear to me that that's always faster.

I think concrete type-assertions will always be faster than interface type-assertions though - for a concrete type-assertions, it's really just comparing the two type-pointers and copying the value (which, in your case, is a pointer itself), whereas for an interface type-assertion, the actual method table must be assembled or looked up.

 

Yes, that's what I was imagining, and why I decided to try coercion to concrete type instead!

-- 

Arnaud

[Axel Wagner]

On Tue, Dec 29, 2020 at 6:01 PM Arnaud Delobelle <arn...@gmail.com> wrote:

On Tuesday, 29 December 2020 at 16:25:41 UTC axel.wa...@googlemail.com wrote:

On Tue, Dec 29, 2020 at 4:37 PM Arnaud Delobelle <arn...@gmail.com> wrote:

Question 1: I *think* that the compiler has all the information necessary to implement type assertion to the Cont interface as I have, i.e. it knows only 3 types implement that interface, so could it not do the optimisation on my behalf?

 

Question 2: Or is it possible that other Go values can be made at runtime that would implement this interface but not be one of the three known types that implement it? 

Yes, re 2. `reflect` can create new types at runtime. AFAIK the implementation for interface-type-assertions is basically to look it up in a global hashmap, which is pre-seeded with compile-time known types and then gets filled on each (successful) inteface-type-assertion with the correct method tables. But, I'm handwaving.

Ok, I have just looked at the docs for the reflect package, but I can't see a way to create a type that implements anything but the empty interface.  Is that correct?  In that case, wouldn't it mean that it is known at compile time what types implement a given (non-empty) interface?

Edit: I see that reflect.StructOf allows creation of struct types out of StructField specifications, which have an Anonymous boolean field.  I imagine that the created struct will inherit the methods of embedded types, so it may implement non empty interfaces.  I'm interested in valid use-cases for this, as it seems to be the thing that prevents this optimisation from being possible.

Yes, indeed: https://play.golang.org/p/JCcgMvg8f_z

Personally, I'm rather disappointed that reflect doesn't allow better ways to create types with methods at runtime. I think encoding packages could take advantage of that by consuming an IDL and creating behaviorally complete types.

FWIW, promoted methods haven't always been created by reflect, but even then, the compiler didn't do this analysis. AIUI, it was considered prohibitively expensive to analyze all possible interface/type combinations. TinyGo does it, but a) it has different use-cases (in particular, not prioritizing compile time as much) and b) AIUI doesn't fully support reflect, so doesn't have to worry about runtime type-creation.

But I'm not an expert, so don't trust my judgement of how feasible this optimization would be.

 

Under these assumptions, it might be *possible* to first check against the statically known types and only fall back on the map if none of that matches. But it doesn't seem 100% clear to me that that's always faster.

I think concrete type-assertions will always be faster than interface type-assertions though - for a concrete type-assertions, it's really just comparing the two type-pointers and copying the value (which, in your case, is a pointer itself), whereas for an interface type-assertion, the actual method table must be assembled or looked up.

 

Yes, that's what I was imagining, and why I decided to try coercion to concrete type instead!

-- 

Arnaud

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/e6a8cd0f-bf8c-46ee-9435-48394a120cb5n%40googlegroups.com.

[Sebastien Binet]

it's because (well, one of the reasons, rather) we didn't find a great API to create a new type and add methods to it:

- one needs a new typename

- one needs a set of methods that have the receiver type as first argument.

you're a bit in a chicken-and-egg situation because it would be great to be able to create a type with *all* its methods known at the time of the type creation, so a type couldn't "gain" new methods (and thus implement new interfaces) during the course of the execution of a program.

having a kind of "start-new-type", "add new methods", "seal-type" API is error prone.

alternatively, one could use a "type builder" type:

type TypeBuilder struct { .. }

func NewTypeBuilder(name string, kind reflect.Kind) *TypeBuilder { ... }

// still the issue of how to address the receiver (ptr? value?)

// and its type within the 'fct' reflect.Value possibly created

// via a reflect.MakeFunc.

func (bldr *TypeBuilder) AddMethod(name string, fct reflect.Value) { ... }

// Build seals the type and returns the finalized named type.

func (bldr *TypeBuilder) Build() reflect.Type { ... }

but at the time, this kind of API was departing a bit from what we had in reflect.

-s

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfEumXWu%3DictPOTKmw575WRN-NTrFza2hsHuaBQLZ%3DtwxQ%40mail.gmail.com.

[Keith Randall]

Go currently doesn't do any optimizations based on the universe of types seen in the program. This is both because reflect can create new ones, as you mentioned, and also because package plugin can effectively "discover" new ones.

The Go compiler + "go build" are organized to compile one package at a time. There's no global prepass at the moment which could discover such facts anyway. We could add one, and bail if either reflect or plugin are imported, but that seems unlikely to apply in many cases (reflect in particular is imported indirectly by lots of things).

[Arnaud Delobelle]

Thanks for the explanations.  Given reflect and the plugin mechanism, it seems like compile time analysis is not a very attractive option.  It is a shame in my case because I really feel like using an interface is the natural solution to my problem in Go, but the runtime cost of type assertion is too high for me to ignore (which means I can still use interfaces but need to work around type assertion).

Another possibility may be that at the first type assertion x.(I), the runtime learns that the concrete type of x satisfies interface I, so that next time an interface value with the same concrete type as x is coerced to I, it can take a short path.  I don't know enough about the runtime to know whether that is feasible at all!

I don't have any stats, but my personal experience tells me that when you do a type assertion to a non-empty interface, there are only going to be a few concrete types in your program that can satisfy it (although I guess this may become less true with the advent of parametric types).

-- 

Arnaud

[Ian Lance Taylor]

On Wed, Dec 30, 2020 at 9:52 AM Arnaud Delobelle <arn...@gmail.com> wrote:
>
> Thanks for the explanations. Given reflect and the plugin mechanism, it seems like compile time analysis is not a very attractive option. It is a shame in my case because I really feel like using an interface is the natural solution to my problem in Go, but the runtime cost of type assertion is too high for me to ignore (which means I can still use interfaces but need to work around type assertion).

Just to stress what you already know, type assertions to non-interface
types are fast. What is (relatively) slow is type assertions to
interface types. The same guideline applies to type switches. So if
you have a fixed set of possible types, consider using type switches
to all possible types that implement the interface you want, rather
than doing a type assertion to the interface type.

> Another possibility may be that at the first type assertion x.(I), the runtime learns that the concrete type of x satisfies interface I, so that next time an interface value with the same concrete type as x is coerced to I, it can take a short path. I don't know enough about the runtime to know whether that is feasible at all!

The runtime already does this, but the fast path still requires doing
a lookup in a hash table and an atomic load. So it's still going to
be measurably slower than a type assertion to a non-interface type,
which only requires a pointer comparison.

Ian