Storage Pattern considering Gas cost

Question

I was following Are there well-solved and simple storage patterns for Solidity? and ended up creating Mapped Structs with Delete-enabled Index to make sure that my array doesn't grow infinitely, when I just need only few indexes at any instant, but turns out the gas cost doubled after the implementation!

So now I have switched back to Simple List Using Array having index as the id of the element. I will be deleting (basically setting to 0) the array elements but won't be shifting elements.

In this case, is the gas cost going to be fix or is it linear with the size of the array. What if the array's size becomes more than 10K, 100K or more!

Answer 1

You might find the following article of use: http://ieeexplore.ieee.org/application/enterprise/entconfirmation.jsp?arnumber=7884650&icp=false (Free version available at https://arxiv.org/abs/1703.03994 but it may be an earlier version.)

It discusses certain patterns that use excessive gas, especially storage operations in loops. I don't entirely agree with the evaluation, in that I think there are cases when storage operations in loops are appropriate, but certainly there are times when effort is wasted.

I'm rather surprised your tests say that inserting data doesn't depend on the size of the array. I would think each STORE operation consumes substantial gas, period. Are you dealing with an in-memory array or truly storing it?

Answer 2

Did some tests with truffle and looks like the cost of inserting data to the array remains constant and doesn't depend on size of the array. However keep this in mind that if you have a function that needs to traverse the whole array to do some calculations, then gas consumed by the function would increase linearly with the size of the array.

Answer 3

I am the author of Are there well-solved and simple storage patterns for Solidity?.

Doubling is indeed possible if the payloads themselves are quite compact. It's relative, because there is a fixed-cost overhead associated with index maintenance. It's less expensive than a linked-list or other sorting scheme, but more expensive than no reorganization.

Regarding your array that grows indefinitely. You'll find that your append cost is consistent at any scale. SSTORE costs 20,000 to write a word to a new key and 5,000 to overwrite an existing key. This may seem counter-intuitive, but it's true. Avoid anything that resembles for(i=start; i<finish ... because you may be introducing a gas cost that will increase with scale.

You'll find it is not practical for a contract to enumerate the list, e.g. function getNextRecord(... if it must wade through many zeroed out (soft deleted) rows to find it, but contracts can access the table just fine if they know what row they want. The key is O(1), not O(n). The cost to retrieve a record with a known index is the same at any scale. Forget what you know about searching through indexes. The cost is the same.

You'll also find that software clients can read one row at a time. Basically, reads are "free".

Last, but important, software clients can employ any caching strategy they like which means the off-chain database can be cleaned of "deleted" records, while what remains can be verified on the chain by anything that wants to. Have a look over here for more on this: https://blog.b9lab.com/the-joy-of-minimalism-in-smart-contract-design-2303010c8b09

Hope it helps.