Scalability issues in the implementation of TEAL data types

[aybehrouz]

Summary

The code which implements Teal data types needs to be refactored to prevent storing unnecessary nil values and to make adding new data types easier.

Scope/Requirements

In the source code we have a struct named TealValue which seems to be created for representing a teal data element. Currently a teal data element can be a byte slice or uint64. TealValue struct has this declaration:

// TealValue contains type information and a value, representing a value in a
// TEAL program
type TealValue struct {
    _struct struct{} `codec:",omitempty,omitemptyarray"`

    Type  TealType `codec:"tt"`
    Bytes string   `codec:"tb"`
    Uint  uint64   `codec:"ui"`
}

Similarly, somewhere else we have a StackValue struct with similar declaration: (I don't know why this struct was created. couldn't we just define a stack of TealValue instead of creating a new StackValue type?)

// stackValue is the type for the operand stack.
// Each stackValue is either a valid []byte value or a uint64 value.
// If (.Bytes != nil) the stackValue is a []byte value, otherwise uint64 value.
type stackValue struct {
    Uint  uint64
    Bytes []byte
}

All these structs contain a field for every possible data type inside them and only one of these fields will be non-nil. In my opinion this is not the right way for representing a teal data element and this representation is not scalable. in the future we may need more Teal data types like []int or float. With the current code, adding them will not be so easy and needs a lot of changes in different parts of the code. Also with more data types every struct will have more nil fields which wastes memory and when the struct is serialized to the ledger will waste the storage space too.

For a situation like this In OO programing we usually define a TealValue (or TealData) super-class and a specific teal data type, for example TealInt, would be a subclass of it. In go language this can be implemented using interfaces, something like this:

//TealValue is our super class
type TealValue interface {
    SayHiLikeATeal()
}

//TealInt is a subclass of TealValue representing an integer data element
type TealInt struct {
    value int
}

func (ti TealInt) Value() int {
    return ti.value
}

func (ti TealInt) SayHiLikeATeal() {
    fmt.Print("Hi! I'm a TealInt!")
}

//TealBytes is a subclass of TealValue representing a byte slice data element
type TealBytes struct {
    value []byte
}

func (tb TealBytes) SayHiLikeATeal() {
    fmt.Print("Hi! I'm a TealBytes!")
}

func (tb TealBytes) Value() []byte {
    return tb.value
}

Then if we want a stack for storing Teal data elements we can simply do it like this:

var stack []TealValue
tb := TealBytes{[]byte{1,2,3}}
ti := TealInt{value: 22}

stack = append(stack, ti, tb)

//we can use polymorphism:
stack[1].SayHiLikeATeal()

//or we can cast a stack element to its original type
stack[0].(TealInt).Value()

//or we can use a type switch (which generally, is not a good thing and makes the code less scalable!)
switch v := stack[1].(type) {
    case TealInt:
        // here v has type TealInt
    case TealBytes:
        // here v has type TealBytes
    default:
        // no match; here v has the same type as i
}

Urgency/Relative Priority

I think these changes should be made as soon as possible.

[jannotti]

codec:omitempty avoids space waste on the blockchain itself. With that in mind, it doesn't seem particularly valuable to save some space in the in-memory representation of a TealValue. For example, this is the state for one value in an app, called "committed".

{
  "committed": {
    "tt": 2,
    "ui": 2000
  }
}

Note that "tb" does not appear.

Given the relatively barebones set of things a TealValue can do, it's not a priority to create an interface with common methods. There's almost nothing that a uinit64 and a byte slice can both do (your "SayHiLikeATeal" example)

[pbennett]

Before ever attempting optimizations like this, keep in mind that in terms of raw performance, this is likely to be far less efficient. I'd recommend writing Go benchmarks with both approaches and comparing. You might be surprised at the difference. Casting and interface operations will be extremely expensive compared to a straight fixed-size union-style struct and simple method calls (which are just static static function calls under the hood). If working with groups of these values you'd also have contiguous chunks of data, all aligned, possibly with significant cache-line advantages.
Interfaces can obviously provide significant advantages but performance needs to be everything during transaction/contract processing.

[aybehrouz]

Thank you for your responses.

codec:omitempty avoids space waste on the blockchain itself.

This is really good news that the msgpack serializer doesn't save those nil values in the blockchain. (ps: also I was wondering about "tt" and "ut" strings... those strings will be saved on the disk or not?)

With that in mind, it doesn't seem particularly valuable to save some space in the in-memory representation of a TealValue.

I do not agree. Almost all the data of smart contracts' state is packed inside these structs. This would be a real problem in case u need to cache some parts of the state storage in the memory. What if we need to add some new teal data types in the future? If we want to add only a float and an []int this struct will look like this:

type TealValue struct {
    _struct struct{} `codec:",omitempty,omitemptyarray"`

    Type  TealType `codec:"tt"`
    Bytes string   `codec:"tb"`
    Uint  uint64   `codec:"ui"`
        Float float64
        Integers []int 
}

With this struct, for example, for keeping a single integer in the memory we need to use at least 32 bytes of RAM.

Given the relatively barebones set of things a TealValue can do, it's not a priority to create an interface with common methods. There's almost nothing that a uinit64 and a byte slice can both do

Even if there is no shared code, still I prefer the OO design pattern because it makes the code cleaner and more readable. For example, in the OO design we can write:

func add(a, b TealInt) TealInt

its obvious that this function only works for Teal integers, but in the current design we have to write:

func add(a,b TealValue) TealValue

The caller of this function may think that he can safely use it for adding any TealValue. (for example two []byte)

However, If u don't like the OO design pattern I recommend to completely get rid of TealValue and its similar structs. This way, the nil values will go away and I guess u would be able to get rid of TealType too. In case u needed to store different types in a data structure u could simply use interface{} type:

var stack interface{} //instead of var stack StackValue

You can simply store a []byte or an uint64 in this stack.

@pbennett

Casting and interface operations will be extremely expensive compared to a straight fixed-size union-style struct and simple method calls (which are just static static function calls under the hood).

Dynamic type checking has some run time overhead but its not considerable. If this is not the case, then programming languages like python or ruby which use duck typing are a disaster for performance. If you have any code that shows the performance impact of this, I would like to see it and I would appreciate it if u could share it with us.

[pbennett]

It looks like they've improved the cost significantly (https://stackoverflow.com/questions/28024884/does-a-type-assertion-type-switch-have-bad-performance-is-slow-in-go - see comparisons between original 2015 results and 2019 results) - but I still don't see the point of this change. Floating point isn't something you typically ever want to use and an integer and sized block of bytes should basically be able to handle everything.
I don't see what an abstraction buys here when all you need is two basic on-chain types. Now, whether you can do what you need in TEAL - that's another issue..

[aybehrouz]

Thanks for sharing that interesting link.

Even if the results of 2015 were still correct, I don't think using interfaces could have a considerable impact on performance. Of course, dynamic type checking can make execution time of a single instruction like x++ several times slower, but in a real application only a tiny fraction of execution time is spent for executing such instructions. In a synthetic benchmark, you can make a long loop that only executes x++ and u may be able to see the performance impact, but I'm sure the iterator of that loop can't be a 32 bit integer or it will end so fast that the execution time can't be measured. How many times you've seen a loop with a 64 bit iterator in your codes? Also note that type checking will not cause extra memory accesses because type information is cached when the variable is cached itself.

Floating point isn't something you typically ever want to use and an integer and sized block of bytes should basically be able to handle everything.

Theoretically u can do any computations with a []byte u don't need an int either. but that doesn't mean we don't need an int. In some financial or scientific formulas we need to compute sqrt(x) or log(x). without having float data type computing those formulas will not be easy.

[tsachiherman]

As @jannotti mentioned above, the TealValue is a disk-persisted value ( and that's why it's "decorated" with the codec declaration ). These declarations are used to construct a decoder/encoder msgpack that serialize that data structure efficiently. The stackValue on the other hand is purely in-memory data type and would never get serialized.

The idea here, and in your PR here are good, but I think that these aren't mature enough. There is much more that is needed before we could truly use these. We're working on another change, and I think that you'll find that some of the ideas that you've been preaching for were implemented there.

The draft PR that you've started working on seems to be far away from completion. It's completely understandable that some PRs takes longer to work on; however, in these cases, I'd ask you to close the PR for now and re-open it once it's ready for review ( just so that we won't have too many abandoned PRs ).

Same apply for this issue; I generally try to close issues that aren't going to be tackled any time soon. If it's ok with you, I'd like to close this as well.