ABI - AVM Support - Alternative substring

[chaihoang]

• Have an alternative substring method that takes parameters start index and length as opposed to end index (consider whether these should be stacked parameters or immediates)

[jannotti]

Today, we have substring which takes two immediate values, a start and end, and extracts those bytes. Since immediates are only one byte (so they can only hold up to 255) and they must be hardcoded, we also have substring3 which takes its arguments from the stack (also a start and end).

When decoding ABI encoded types, it will be very common to extract 1, 2, 4, and 8 byte substrings, and convert them integers. With substring3 that involves a lot of constants that take code space (one for the start and end). That is, code that looks like:

txn ApplicationArgs 1
int 312
int 316
substring3
btoi
txn ApplicationArgs 1
int 356
int 360
substring3
btoi
add

is the most compact way to pull out two uint32s and add them. This consumes about 27 bytes of code space, and 11 units of cost.

getbyte works well for extracting a single byte and converting it to an int. We should add similar for 2, 4, 8 byte extractions . The above becomes

txn ApplicationArgs 1
int 312
get4bytes
txn ApplicationArgs 1
int 356
get4bytes
add

which consumes about 17 bytes of space, and 7 units of cost. This plan would add get2bytes get4bytes and get8bytes. An alternative plan would be to only add getbytes n, yielding:

txn ApplicationArgs 1
int 312
getbytes 4
txn ApplicationArgs 1
int 356
getbytes 4
add

which would be two extra bytes. This isn't so much more space, but it seems overly general, as it seems to support 5 or 9 (?!) byte integers.

Beyond this, there does not seem to be a strong need for a substring like opcode that takes a length (rather than end position), nor for extracting short strings (and not converting them to a uint64). substring seems fine for that, even if a little math is required. This issue is to shorten code that we expect to be very common.

[jeapostrophe]

@jannotti 's getNbytes is a valuable function. I think the proposed name suggests it produces bytes, but his version produces a number. I don't have a strong preference for any particular name, but I think a function like this is great. I'd describe it as get_int_from_bytes : (N:Int) -> (offset:Int) -> Int where the N were hard-coded into the opcode. This function, if it were in pseudo-C, would be int get_bytes_from_int<N>( bytes bs, int offset ) { return (int)(bs[offset : offset + N]) }

However, I do thing it would be valuable to have a different substring for arbitrary byte ranges, that used offset and length rather than start and end.

First, substring(start, end) contains duplicate information in that the end is necessarily larger than start if it won't trap, so substring(offset, len) will be able to describe the same operations and more, since offset (start) might be 8 bits but offset+len (end) might be more.

Second, when I compile a field reference (i.e. x.f), it turns into a substring where I am basically compiling (typeof(x.f))(*x+offset(x.f)) and the type may not always be a number... it might be another struct. (I store all values that are not numbers as their bytes, so the cast doesn't do anything except determine how much memory to read.) In other words, I may not be read 2, 4, or 8 bytes and I'm not converting them to an integer.

Third, when I compile an array reference (i.e. a[i]), it turns into a substring where I am doing substring (a + elem_size * i) (a + elem_size * (i + 1)) It is tedious to duplicate the computation of the offset and then add one more element size to it. I basically do size; idx; *; dup; size; +; substring3. My ideal would be array_ref, array_ref2, array_ref3 which would take the element size and the index --- one as immediates, one with the size as an immediate, and one with both on the stack.

Fourth, my last use case is "drop all but the first byte". I use this to compile disjoint unions (i.e. a struct { uint8 tag; union { .... } } where the tag determines which union to use. This is really painful for code size because the argument to substring is always 1 and then the other argument is the rest... if the rest is large, I may need to add an integer constant. It would be awesome to be able to just have a drop/take opcode on bytestrings.

Finally, and maybe you have a different task for this, ideally I'd have dual versions of all these, where I have a source bytes, a change I want to make, and I get a new bytes. I'd use this for modifying a struct field or array element. (The disjoint union is a really simple case a concat. But if I'm greedy, I'd want prepend1 that added a single immediate byte to the start of a bytestring. prepend1 N would be two bytes while bytes "b"; swap; concat is at least five, I think.)

[jannotti]

I agree about that get4bytes is poorly named. I was trying to generalize the naming around getbyte (which returns an int), but the confusion is worse. How about we use extract for these kinds of operations that are like substring, but operate based on lengths, rather than end positions, and then switch to "bit width" naming.

extract16bits, extract32bits, extract64bits (Changing to naming by bits instead of bytes to decrease the confusion)

These would now be specializations of the more general opcodes (that you make a good case for):

extract and extract3 - These operate exactly like substring and substring3 except they use lengths. So they do not convert to ints.

There's an argument for substring2 and extract2, which would get the start from the stack, but the end/length as an immediate. You asked for that with array_ref but not earlier. Why?

Since extract with a 0 length is pointless, I am tempted to make extract2 and extract3 treat an immediate 0 as meaning "until the end" which gives you your enum tag handling. (I would not have 0 mean "end" in extract3 since that is a computed value, and having different meanings for a computed value sounds like a source of bugs. But you don't need it, you'd always use extract 1 0 or perhaps int <location>; extract2 0)

I'm not totally sold on arrayref. With the additions above, it just saves one multiply, right?

The final paragraph looks to be asking for a splice kind of thing. It would take a string, a start, a length, and a second string to insert as a replacement for that location/length segment? I can see the need, let's iron this stuff out and then make a splice that fits in well with what we end up with.

As an aside, it seems that you often want opcodes that take immediates in order to save a single byte per use. intc_X (for X <= 3) is intended to get common integers onto the stack with a single byte, obviating those savings. But it only works for 4 integers per program. I wonder if expanding that to 8 would be a better use of opcodes that having two or more of so many. It would be interesting to see how many small constants are used in typical programs (especially with these proposed changes which eliminate many of them).

[jeapostrophe]

I'm on board.

There's an argument for substring2 and extract2, which would get the start from the stack, but the end/length as an immediate. You asked for that with array_ref but not earlier. Why?

To me, the stack versions are for when a value is only known dynamically vs statically. (The size is, of course, an issue too, but that's relatively rare for me because, other than arrays, my data structures tend not to actually be very large.) And, only in the case of an array element reference do I not actually know what I'm accessing. And it's most commonly the case that I know the type of the array (i.e. the size of each element) but not which index I'm getting.

Since extract with a 0 length is pointless, I am tempted to make extract2 and extract3 treat an immediate 0 as meaning "until the end" which gives you your enum tag handling. (I would not have 0 mean "end" in extract3 since that is a computed value, and having different meanings for a computed value sounds like a source of bugs. But you don't need it, you'd always use extract 1 0 or perhaps int <location>; extract2 0)

I'm fine with this. Although I think a more hardcore thing would be to make it so extractUntilTheEnd and extractNPlus1 N (a) are totally different opcodes, (b) share the same leading byte, and (c) extractNPlus1 N is actually written extract N where it is a compile-time error for N to be 0.

I'm not totally sold on arrayref. With the additions above, it just saves one multiply, right?

I believe that in the new world, I'd be writing int size; *; extract (len=size) (offset=stack 0) (bs=stack 1) rather than array_ref (size=len) (index=stack 0) (bs=stack 1) which saves a multiply and the int constant space

The final paragraph looks to be asking for a splice kind of thing. It would take a string, a start, a length, and a second string to insert as a replacement for that location/length segment? I can see the need, let's iron this stuff out and then make a splice that fits in well with what we end up with.

Sounds great

As an aside, it seems that you often want opcodes that take immediates in order to save a single byte per use. intc_X (for X <= 3) is intended to get common integers onto the stack with a single byte, obviating those savings. But it only works for 4 integers per program. I wonder if expanding that to 8 would be a better use of opcodes that having two or more of so many. It would be interesting to see how many small constants are used in typical programs (especially with these proposed changes which eliminate many of them).

I looked at my corpus of 806 TEAL programs.

Here are all the constants in them with a count:
find . -name '*.teal' -exec grep int {} \; | sort | uniq -c | sort:
https://gist.github.com/jeapostrophe/c08a4ec4985fb22f3587af3f9a9ec989

That doesn't include constants that are embedded in opcodes.

I took the same corpus and figured out how many unique constants each application has most commonly:
find . -name '*.teal' -printf 'grep int %p | sort | uniq | wc -l\n' | sh | sort | uniq -c | sort -n
https://gist.github.com/jeapostrophe/97d637978f988a911e8f1838fc29d9fb

8 and 9 are the most common. I'd go with 4 bits and give 16 constants. FWIW, I calculated the same for constant bytes and it's similar.

[jannotti]

Since extract with a 0 length is pointless, I am tempted to make extract2 and extract3 treat an immediate 0 as meaning "until the end" which gives you your enum tag handling. (I would not have 0 mean "end" in extract3 since that is a computed value, and having different meanings for a computed value sounds like a source of bugs. But you don't need it, you'd always use extract 1 0 or perhaps int <location>; extract2 0)

I'm fine with this. Although I think a more hardcore thing would be to make it so extractUntilTheEnd and extractNPlus1 N (a) are totally different opcodes, (b) share the same leading byte, and (c) extractNPlus1 N is actually written extract N where it is a compile-time error for N to be 0.

I certainly think rest could be a pseudo-op that assembles to extract 0. I don't know if I'd go as far as not allowing extract 0 to appear explicitly, and documenting them as though they are separate opcodes.

I'm not totally sold on arrayref. With the additions above, it just saves one multiply, right?

I believe that in the new world, I'd be writing int size; *; extract (len=size) (offset=stack 0) (bs=stack 1) rather than array_ref (size=len) (index=stack 0) (bs=stack 1) which saves a multiply and the int constant space

oh, because the thing you're multiplying would be an immediate in array_ref?

array_ref only works once you've extracted the array into its own byte string, right? If it's embedded at some offset, you're back to calculating something off of that. I guess you often do that to simplify accessing several elements.

I looked at my corpus of 806 TEAL programs.

Here are all the constants in them with a count:
find . -name '*.teal' -exec grep int {} \; | sort | uniq -c | sort:
https://gist.github.com/jeapostrophe/c08a4ec4985fb22f3587af3f9a9ec989

That doesn't include constants that are embedded in opcodes.

I took the same corpus and figured out how many unique constants each application has most commonly:
find . -name '*.teal' -printf 'grep int %p | sort | uniq | wc -l\n' | sh | sort | uniq -c | sort -n
https://gist.github.com/jeapostrophe/97d637978f988a911e8f1838fc29d9fb

8 and 9 are the most common. I'd go with 4 bits and give 16 constants. FWIW, I calculated the same for constant bytes and it's similar.

This is nice data, especially the second gist. In these, you're using more constants than you will need once extract exists though, right? Also, we should exclude constants that appear only once, since pushint and pushbyte use the same space as one block constant and a one byte reference. (And the new assembler optimizes this for you.)

Funny place for you to "hide" more constant space - pass in more foreign accounts, apps, asas than you need, with constant data in there. (I mean, no, don't do that. That's gross.)

[jeapostrophe]

I believe that in the new world, I'd be writing int size; *; extract (len=size) (offset=stack 0) (bs=stack 1) rather than array_ref (size=len) (index=stack 0) (bs=stack 1) which saves a multiply and the int constant space

oh, because the thing you're multiplying would be an immediate in array_ref?

Correct

array_ref only works once you've extracted the array into its own byte string, right? If it's embedded at some offset, you're back to calculating something off of that. I guess you often do that to simplify accessing several elements.

You are correct. The best-case for me would to have an addressing mode like X86 gives that is A + B*C : A + B*C + D. In this case, my most common situation will be when everything is known at compile-time, except for B.

This is nice data, especially the second gist. In these, you're using more constants than you will need once extract exists though, right?

I believe so

Also, we should exclude constants that appear only once, since pushint and pushbyte use the same space as one block constant and a one byte reference. (And the new assembler optimizes this for you.)

That's awesome

Funny place for you to "hide" more constant space - pass in more foreign accounts, apps, asas than you need, with constant data in there. (I mean, no, don't do that. That's gross.)

That actually won't work because the contract would need to duplicate the value into itself to verify that the correct constants were sent and not other things. One thing that might work would be to have a big byte string and put the common constants into known scratch slots. That's basically doing what the existing intc is doing except by-hand and consuming scratch space