4

In solidity we are not allowed recursive Structs, so I cannot create a recursive data structure with unlimited nodes. Similarly, Solidity Arrays are fixed to the size you initialize them with.

So I am wondering, say I need a smart contract which has a data structure which has no fixed limits? Is this even possible?

I am interested in doing this in just one smart contract. However I am aware that if I have smart contracts deploy new smart contracts then each one can point to the next and have unlimited storage. (Linked list where each smart contract is a node)

But can I do it in just one smart contract?

7

Similarly, Solidity Arrays are fixed to the size you initialize them with.

Solidity arrays are not fixed size. Here's an example snippet from a contract I use to test gas optimization:

contract Gas {

    // this structure must fit into a 256 bit (32 byte) native word of the EVM
    struct IdStruct { 
        uint128 id;                 // zero means invalid.
        uint32  value;             
        uint32  field2;
        uint64  padding;
    }


    uint128 [] itemIds;
    mapping (uint128 => IdStruct) items

As you can see I can have infinite array of items. I can look up any one of them up in O(1) time. I can iterate over all the items. Deletion and insertion are O(1) or O(n) depending if you care about holes in your array or not, and how you track them. There are more complex data structures out there that have O(1) insertions and deletions as well, here. Also google for Ethereum Alarm Clock.

So I am wondering, say I need a smart contract which has a data structure which has no fixed limits? Is this even possible?

It depends what you want to do. If you want to reduce the struct (say take the sum of all the elements value fields), you will be limited by the amount of gas this takes. (I've gotten this down to about 3k gas per element).

If you just need to look up an element, you can potentially have an infinite number of elements. Someone has to pay the gas cost of insertion.

How you structure a lookup system for a large set depends on who pays gas cost for which operation, whether you need to do reduction, filtering, and so on. Like any application, the data structure(s) you need depends on what you are doing. The nuance here is you measure the cost in gas, not in CPU cycles, cache misses, or storage like you would on a modern CPU system. You are currently limited to 4.7M gas per block, and you probably shouldn't use all of that.

It's probably possible, as you hint at above, to spread out a large data set operation over multiple blocks. Haven't tried it yet.

0

Mappings don't start having problems until 10 million values. Mappings are the one key strong asset solidity actually has.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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