3

I'm doing a course project of a blockchain class to test the complexity of a data structure in terms of gas cost. I noticed that the cost of the push of array in solidity keeps the same. If we have a dynamic array, we must have a point where the length of the array will be doubled and the data will be copied. In this case, the gas cost will be larger. How can solidity make cost of push constant? Does solidity make a very large array in the initialization and then the push cost can be constant?

3
  • 1
    I thought arrays in solidity work like lists. Therefore you don't need to copy the entire array when you add an element. Rather you just rewrite pointers.
    – Sky
    Commented Mar 10, 2022 at 8:22
  • Is the list the same as the dynamic array? If yes, the resizing of dynamic array still need to copy the entire array Commented Mar 10, 2022 at 8:35
  • 1
    @hck0711 I get what you are asking now. (No dynamic arrays and lists are not the same). But your question is a good one. Because -as you noted- writing into a dynamic array in Solidity should get expensive in case you fill the space allocated for it. (That one transaction of adding a new element to filled array would cost you near as much as writing all the previous ones, as it has to re-copy all of them). I don't know how solidity does that. But I will upvote your question.
    – Sky
    Commented Mar 10, 2022 at 9:38

1 Answer 1

5

Pushing can only be done on resizable arrays, which live in storage.

Now storage is handled quite differently from the heap, such as in C for example. This is mostly because it is fully accessible (all 2^256 slots of 32 bytes), you won't be running short on "allocated" storage in solidity, you'd most certainly run out of money way before...

So :

if we have a dynamic array, we must have a point where the length of the array will be doubled and the data will be copied

Not necessarily no, this scheme is used as a heuristic to minimize memory allocation which is costly and to optimize memory usage with is actually scarce, but you could rely on a different one. You seem to state it as a rule, which it is not. Now, to understand what happens exactly in solidity when you use .push() you need to understand the storage layout of dynamic arrays as explained here and more specifically the scale of the storage space.

Let's use an example contract such as this one :

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract Example {

  uint256[] myArray;

  function addElement(uint256 value) public {
    myArray.push(value);
  }
}

the dynamic storage array myArray is declared at storage slot 0 (simply because it is the first state variable), this slot will contain the size of the array. Its data will be stored starting at keccak256(0).

In order, the elements of the array will be stored at :

  • Index 0 : keccak256(0)
  • Index 1 : keccak256(0) + 1
  • Index 2 : keccak256(0) + 2
  • ...
  • Index n : keccak256(0) + n

The important bit is that keccak256(x) can be interpreted as a 256 bit address in a memory space with 2^256 slots each of 32 bytes. That's huge ! (2^261 bytes) We are way further than the Megabytes / Gigabytes of physical memory limitations that do require a memory allocator.

To put things into perspectives, 2^261 bytes of "available" memory is enough for 387973554649592116040087854974761818637655473 Yotta Bytes (2^80 bytes) for every living human on earth currently. And that's the limit for a single account storage... The practical limit is of course way less.


I'm actually amazed by this, I used that code to compute it, if anyone spots a mistake :

console.log(
  web3.utils
    .toBN("2")
    .pow(web3.utils.toBN("261"))
    .div(web3.utils.toBN("1024")) // To KiB
    .div(web3.utils.toBN("1024")) // To MiB
    .div(web3.utils.toBN("1024")) // To GiB
    .div(web3.utils.toBN("1024")) // To TiB
    .div(web3.utils.toBN("1024")) // To PiB
    .div(web3.utils.toBN("1024")) // To EiB
    .div(web3.utils.toBN("1024")) // To ZiB
    .div(web3.utils.toBN("1024")) // To YiB
    .div(web3.utils.toBN("7900000000")) // Divide by world population
    .toString()
);

In this context, the decision was made to rely on the extremely low probability of collisions between slots rather than implement a proper memory allocation scheme that would be quite costly in gas and actually useless (like 99.9999999... % of the time).

How can solidity make cost of push constant?

Actually, simply by writing on the next slot : keccak256(arraySlot) + arrayLength

Does solidity make a very large array in the initialization and then the push cost can be constant?

If you want to see it that way, yes… It's more sparse data (values, struct or arrays for examples) in a really, really huge memory space. The storage space is entirely available, but only what is stored on it is really stored in the form of key, value pairs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.