Teal and Memory Efficiency

As I can understand, in stateful contracts state is represented with key-value pairs and for storing a variable, the name of that variable would be the “key” and the pair would be stored in the state. This official example from developer docs shows this:

int 0
byte "MyLocalKey"
int 50
app_local_put 

This is really an inefficient method. With this method the name of variables will be stored in the state too. In a map data structure always a copy of keys need to be stored in the memory. For example, if the map data structure is implemented using a hash table, the keys need to be stored to be able to detect hash collisions.

The point is, Algorand’s VM should have a random access memory like all other conventional machines (besides its stack). The data should be stored and loaded using addresses and the mapping between names of variables and their address can be done in compiler/assembler using symbol tables. There is no need for storing names in the memory.

In other words, state data in a contract should be represented by an array and not a map (key-value pair). and programmer will be responsible for remembering the index of his variables. (actually compiler will do this). The code would be something like this:

define my_var
int 0 
int my_var    //assembler will replace my_var with its index/address
int 50
app_local_put

@aybehrouz,

While I can’t argue that it would be more efficient from runtime perspective, I do recognize that there are few advantages as well -

  • TEAL code is cleaner and less ambiguous ( at least in my view )
  • The extra cost of storing maps compared to arrays is (hopefully!) not an issue.
  • Most applications have low number of keys.
  • programmer can still use indices as the key ( i.e. 0, 1, 2, 3 … ), and low-level optimization could serialize that as an array instead of a map.
  • The runtime gains between looking into array vs. accessing a map are by order of few magnitudes smaller than (for example) reading the account data from disk. So, even if all the algorand TEAL scripts would get modified to be implemented as you’ve suggested, the performance gains would not be measurable on any “real” deployed network.
1 Like

Thank you for your answer

In terms of runtime gains, using arrays will decrease the execution time of TEAL scripts for sure. (just compare the cost of a map lookup to other TEAL opcodes) but I don’t know how much of block processing time is devoted to execution of TEAL scripts. If other operations (like retrieving users data) are much more time consuming, then you are right and the runtime gains won’t be considerable.

But my problem with this design is not runtime, it’s memory usage… As I mentioned before a map always needs to store its keys. usually the implantation of a map is something like this:

h = hash(key)
if data[h].key == key
	return data[h].value
else
// resolve the collision

So in a map if we don’t store the keys we can not detect and resolve collisions of the hash function. and by using a map in TEAL, we are actually storing the variable names in the state storage. state storage really is a critical resource and its not wise to waste it by storing some arbitrary variable names a programmer has chosen for readability of his code…

@aybehrouz,

I’m not sure if you concern here is about memory or storage, as these presents different challenges.

In terms of memory ( RAM ) consumption, you’re correct that loading the entire set of keys into memory is inefficient; however, the account along with it’s application data is being loaded from disk on every evaluation, so I don’t think the memory is the issue here.

As for the disk persistence, I agree that storing large amount of data ( as in key names ) is a complete waste of storage space and should be discouraged. I personally hold the opinion that the cost function should be such that would encourage developers of picking a suitable naming scheme.

1 Like