Solidity – Why Does Gas Cost of Array Push Operation Remain the Same?

arrayssolidity

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?

Best Answer

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.

Related Topic