Interfaces holding integers and memory allocations

[Arnaud Delobelle]

Hi

The context for this question is that I am working on a pure Go implementation of Lua [1] (as a personal project).  Now that it is more or less functionally complete, I am using pprof to see what the main CPU bottlenecks are, and it turns out that they are around memory management.  The first one was to do with allocating and collecting Lua "stack frame" data, which I improved by having add-hoc pools for such objects.

The second one is the one that is giving me some trouble. Lua is a so-called "dynamically typed" language, i.e. values are typed but variables are not.  So for easy interoperability with Go I implemented Lua values with the type

    // Go code

    type Value interface{}

The scalar Lua types are simply implemented as int64, float64, bool, string with their type "erased" by putting them in a Value interface.  The problem is that the Lua runtime creates a great number of short lived Value instances.  E.g.

    -- Lua code

    for i = 0, 1000000000 do

        n = n + i

    end    

When executing this code, the Lua runtime will put the values 0 to 1 billion into the register associated with the variable "i" (say, r_i).  But because r_i contains a Value, each integer is converted to an interface which triggers a memory allocation.  The critical functions in the Go runtime seem to be convT64 and mallocgc.

I am not sure how to deal with this issue.  I cannot easily create a pool of available values because Go presents say Value(int64(1000)) as an immutable object to me, so I cannot keep it around for later use to hold the integer 1001.  To be more explicit

    // Go code

    i := int64(1000)

    v := Value(i) // This triggers an allocation (because the interface needs a pointer)

    // Here the Lua runtime can work with v (containing 1000)

    j := i + 1

    // Even though v contains a pointer to a heap location, I cannot modify it

    v := Value(j) // This triggers another allocation

    // Here the Lua runtime can work with v (containing 1001)

I could perhaps use a pointer to an integer to make a Value out of.  This would allow reuse of the heap location.

    // Go code

    p :=new(int64) // Explicit allocation

    vp := Value(p)

    i :=int64(1000)

    *p = i // No allocation

    // Here the Lua runtime can work with vp (contaning 1000)

    j := i + 1

    *p = j // No allocation

    // Here the Lua runtime can work with vp (containing 1001)

But the issue with this is that Go interoperability is not so good, as Go int64 now map to (interfaces holding) *int64 in the Lua runtime.

However, as I understand it, in reality interfaces holding an int64 and an *int64 both contain the same thing (with a different type annotation): a pointer to an int64.

Imagine that if somehow I had a function that can turn an *int64 to a Value holding an int64 (and vice-versa):

    func Int64PointerToInt64Iface(p *int16) interface{} {

        // returns an interface that has concrete type int64, and points at p

    }

    func int64IfaceToInt64Pointer(v interface{}) *int64 {

        // returns the pointer that v holds

    }

 then I would be able to "pool" the allocations as follows:

    func NewIntValue(n int64) Value {

        v = getFromPool()

        if p == nil {

            return Value(n)

        }

        *p = n

        return Int64PointerToint64Iface(p)

    }

    func ReleaseIntValue(v Value) {

        addToPool(Int64IPointerFromInt64Iface(v))

    }

    func getFromPool() *int64 {

        // returns nil if there is no available pointer in the pool

    }

    func addToPool(p *int64) {

        // May add p to the pool if there is spare capacity.

    }

I am sure that this must leak an abstraction and that there are good reasons why this may be dangerous or impossible, but I don't know what the specific issues are.  Could someone enlighten me?

Or even better, would there be a different way of modelling Lua values that would allow good Go interoperability and allow controlling heap allocations?

If you got to this point, thank you for reading!

Arnaud Delobelle

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

[ben...@gmail.com]

Nice project!

It's a pity Go doesn't have C-like unions for cases like this (though I understand why). In my implementation of AWK in Go, I modelled the value type as a pseudo-union struct, passed by value:

type value struct {
    typ valueType // Type of value (Null, Str, Num, NumStr)
    s   string    // String value (for typeStr)
    n   float64   // Numeric value (for typeNum and typeNumStr)
}

Code here: https://github.com/benhoyt/goawk/blob/22bd82c92461cedfd02aa7b8fe1fbebd697d59b5/interp/value.go#L22-L27

Initially I actually used "type Value interface{}" as well, but I switched to the above primarily to model the funky AWK "numeric string" concept. However, I seem to recall that it had a significant performance benefit too, as passing everything by value avoided a number of allocations.

Lua has more types to deal with, but you could try something similar. Or maybe include int64 (for bool as well) and string fields, and everything else falls back to interface{}? It'd be a fairly large struct, so not sure it would help ... you'd have to benchmark it. But I'm thinking something like this:

type Value struct {

    typ valueType

    i int64 // for typ = bool, integer

    s string // for typ = string

    v interface{} // for typ = float, other

}

-Ben

[Keith Randall]

Unfortunately for you, interfaces are immutable. We can't provide a means to create an interface from a pointer, because then the user can modify the interface using the pointer they constructed it with (as you were planning to do).

You could use a modifiable reflect.Value for this.

var i int64  = 77

v := reflect.ValueOf(&i).Elem()

At this point, v now has .Type() of int64, and is settable.

Note that to get the value you can't do v.Interface().(int64), as that allocates. You need to use v.Int().

Of course, reflection has its own performance gotchas. It will solve this problem but may surface others.

[Arnaud Delobelle]

Hi Ben, that's an interesting idea. I considered it at the start but
didn't go for it in the end (I can't remember why exactly, probably
because that would make it quite a big struct for Lua). There is a
possibility that I could adapt it a bit and have something like

type Value struct {
scalar uint64
iface interface{}
}

The type could be always obtained from the iface field (it would be
its concrete type), but the value could be encoded in the scalar field
for a few types such as int64, float64, bool. There would be no
storage overhead for int64 and floa64, as the extra 8 bytes used for
the scalar field are saved by having a "constant" iface field. The
overhead for other non-scalar values would be only 8 bytes.

I would need some reusable "dummy" interface values for the types
encoded in the scalar:

var (
dummyInt64 interface{} = int64(0)
dummyFloat64 interface{} = float64(0)
dummyBool interface{} = false
)

Then I could create Value instances like this:

func IntValue(n int64) Value {
return Value{uint64(n), dummyInt64}
}

func FloatValue(f float64) Value {
return Value{*(*uint64)(unsafe.Pointer(&f)), dummyFloat64}
}

func BoolValue(b bool) Value {
var s uint64
if b {
s = 1
}
return Value{s, dummyBool}
}

func StringValue(s string) Value {
return Value{iface: s}
}

func TableValue(t Table) Value {
return Value{iface: t}
}

We could obtain the type of Values like this:

type ValueType uint8

const (
IntType ValueType = iota
FloatType
BoolType
StringType
TableType
)

func (v Value) Type() ValueType {
switch v.iface.(type) {
case int64:
return IntType
case float64:
return FloatType
case bool:
return BoolType
case string:
return StringType
case Table:
return TableType
default:
panic("invalid type")
}
}

Methods like this could extract the concrete value out a Value instance:

func (v Value) AsInt() int64 {
return int64(v.scalar)
}

func (v Value) AsFloat() float64 {
return *(*float64)(unsafe.Pointer(&v.scalar))
}

func (v Value) AsBool() bool {
return v.scalar != 0
}

func (v Value) AsString() string {
return v.iface.(string)
}

func (v Value) AsTable() Table {
return v.iface.(Table)
}

Interoperability with Go code is not as good but still OK. There is
no need to maintain a pool of reusable values, which is a bonus. I'll
have to see how much modification to the codebase it requires, but
that sounds interesting.

--
Arnaud

> --
> You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/163s0WdXYIU/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/dcd07f38-1ead-4359-90f3-f6b514c7d541n%40googlegroups.com.

[Arnaud Delobelle]

(sorry about the code formatting gone wrong, I replied in gmail it it seems to have removed all indentation!)

[Axel Wagner]

FWIW, not that you *should* do it, but you *could* enact your original plan using unsafe:

https://play.golang.org/p/W9Ntzxif_ol

I don't think it's advisable though - among other things, the compiler might well conclude that `i` doesn't change in this code and eliminate the repeated loads at some point in the future, for example.

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/841a70b9-ee31-40e9-9841-adc70c008962n%40googlegroups.com.

[Arnaud Delobelle]

Ah interesting, I guess that could mean I would need to switch to using reflect.Value as the "value" type in the Lua runtime.  I am unclear about the performance consequences, but I guess I could try to measure that.

Also, looking at the implementation of reflect, its seems like the Value type I suggested in my reply to Ben [1] is a "special purpose" version of reflect.Value - if you squint at it from the right angle!

-- 

Arnaud

[1]

    type Value struct {
        scalar uint64
        iface interface{}
    }

[Arnaud Delobelle]

Just an update (in case anyone is interested!).  I went for the approach described below of having a Value type holding a scalar for quick access to values that fit in 64 bits (ints, floats, bools) and an interface fo for the rest.

    type Value struct {
        scalar uint64
        iface interface{}
    }

That significantly decreased memory management pressure on the program for many workloads, without having to manage a pool of say integer values.  It also had the consequence of speeding up many arithmetic operations.  Thanks all for your explanations and suggestions!

-- 

Arnaud

[ben...@gmail.com]

Nice! Do you have any benchmarks on how much faster the "scalar" version is than the non-scalar?

[Arnaud Delobelle]

Luckily, I have the "no scalar" version with a build tag.  Here is a simple benchmark:

func BenchmarkValue(b *testing.B) {

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

                sv := IntValue(0)

                for i := 0; i < 1000; i++ {

                    iv := IntValue(int64(i))

                sv, _ = add(nil, sv, iv) // add is the "real" lua runtime function that adds two numeric values.

        }

    }

}

Results with the "scalar" version

$ go test -benchmem -run=^$ -bench '^(BenchmarkValue)$' ./runtime

goos: darwin

goarch: amd64

pkg: github.com/arnodel/golua/runtime

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

BenchmarkValue-8          122995              9494 ns/op               0 B/op          0 allocs/op

PASS

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

Results without the "scalar" version (noscalar build tag)

$ go test -benchmem -run=^$ -tags noscalar  -bench '^(BenchmarkValue)$' ./runtime

goos: darwin

goarch: amd64

pkg: github.com/arnodel/golua/runtime

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

BenchmarkValue-8           37407             32357 ns/op           13768 B/op       1721 allocs/op

PASS

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

That looks like a pretty big improvement :)

The improvement is also significant in real workloads but not.so dramatic (given they don't spend all their time manipulating scalar values!)

[ben...@gmail.com]

Wow -- yes, that's pretty significant! (Though point taken about "real workloads".) Thanks for sharing this.

[Kyle Nusbaum]

Sorry to revive a dead thread.

I have also been playing with an interpreter and found that increasing the size of runtime.staticuint64s helps with the convT64 issue a lot.
https://github.com/golang/go/blob/aa8262d800f0cba2e4d4472a7e344eb60481b0ff/src/runtime/iface.go#L493-L526

I'm guessing that such a small static array is sufficient in most Go programs, but in interpreters that are constantly putting integers into interfaces, it might be worth wasting a MiB or 2 to cover a larger range.

For me it made a huge difference.

This is only helpful if you're willing to modify Go's runtime package, of course.

-- Kyle