[Ethereum] Dynamic arrays VS mappings when it comes to gas usage

arraysfeesgasmappingsolidity

I'm puzzled what is more efficient to use, from the point of gas consumption (storage and execution), dynamic array or the mapping and element counter.

To be more clear, I'm not asking the basic data structure usage paradigms that we all should know, nor about pros and cons that each have, rather I want to know what is more gas efficient.

Let me give you an example in a sort of pseudo code:

contract DataStorage {

    //mapping and data counter
    mapping (uint256 => uint256) sequentialData1;
    uint256 sequentialData1Counter;

    //dynamic array
    uint256[] sequentialData2;

    function addDataToMapping(uint256 _newData) {
        sequentialData1[sequentialData1Counter++] = _newData;
    }

    function addDataToDynamicArray(uint256 _newData) {
        sequintialData2.push(_newData);
    }
}

Don't think about deleting elements and so on, let's say I just want to add new data to array and be able to access them by index.

Best Answer

There's some difference in behavior but in your example the gas consumption is about the same. An array has to maintain its length and your mapping uses a counter instead. All data in the array is stored continuously and the mapping is spread in the store but that doesn't affect the costs.

Related Solutions

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

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.

Best Answer

Related Solutions

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

Related Topic