20

I see there're some Solidity examples that are using mapping for storing state, and some are using arrays.

For example this example is using mapping:

struct Campaign {
   ....
}
uint numCampaigns;
mapping (uint => Campaign) campaigns;

and there is an array:

Proposal[] public proposals;
struct Proposal {
   ....
}

I understand that there're little bit different pattern for adding a new value, basically because arrays have the .length attribute. At least if we're comparing to mapping (uint => ...). That's all I see, maybe I'm missing something?

Lets say I have a similar pattern: a contract which operates some structs/documents (contract have functions to add and update such documents). There could be unlimited amount of documents processed by contract. My gut tells me that I should use mapping there, but I can't find any proof. So my questions is which one to choose and when.

25

mapping is generally recommended. For this use case of a contract, which could have an unlimited number of documents, which could be updated, the recommendation holds.

The main advantage of an array is for iteration. But the iteration needs to be limited, not only for speed, but potentially for security. As an extreme example, a permanent Denial-of-Service could be inflicted on a contract if its service involves iterating over an array that an attacker can fill up, such that the cost of iteration and operation permanently exceeds the block gas limit.

A comment by @PaulS suggests that iterating an array of length 50 is relatively efficient; testing the use cases is advised to also identify details such as desired or acceptable gas costs.

Note, for clarity, one should not try to replace all arrays with mappings: mappings can only be used for data in storage.

  • What's a good way around the DoS issue if you still need iteration? – Raine Revere May 8 '16 at 17:24
  • @eth Can you comment on why mappings are recommended? – ComandanteCheth Aug 27 '16 at 12:02
  • 1
    @ComandanteCheth Which part of this answer needs clarification? You can also use both a mapping and array: main danger to watch for with an array is iterating too much. – eth Aug 27 '16 at 21:15
  • 1
    @Raine: You could have a function which takes a starting index and always iterates a fixed number of times, so multiple transactions are used with a different starting index. – eth Aug 27 '16 at 21:20
4

This is a design issue specific to your application. What will you need to do with the documents? For example, if you'll need to get a specific document to do an update, a mapping will be much easier than looping over an array of Documents. Storing documents by some ID would make this easy:

mapping(uint256 => Document);
  • I do some lookups and a lot of reducing in my application. So I use both at the same time. I use an array for iteration and a map for lookup. In reality O(n) walks are actually pretty efficient for < 50 length, so a mapping might be overkill. – Paul S Apr 2 '16 at 17:44
1

It all comes down to the fact that you are using arrays to store these documents and those arrays grow without bound and because you are always going to iterate through the full length of your arrays, you might end up having to spend a tremendous amount of gas just to look up some given document inside the proposals array.

In order to solve this issue, stop using arrays altogether inside of your contract and instead use a slightly different data structure.

The data structure that you should use for storing all these proposals, rather than being an array, it will be a mapping.

A mapping is a reference type that is available to us inside of Solidity. A mapping is like a collection of key/value pairs, so its similar to a JavaScript object, but there are some discrete and definite differences between a mapping and JavaScript object.

So, why is a mapping is going to solve your problem?

It all comes down to the search time for each of these data structures. In the Computer Science discipline, whenever we are trying to find some piece of data inside an array, the best case we can get for running that search is Linear Time. When we say that search inside of the array is linear time that means that for every additional record we add to this array, it will take a slightly larger amount of time to execute the search.

If we have 100 elements in the array, it might take 100 seconds. In other words, the size of the array dictates how long the search is going to take.

That is what is going to get you into trouble with gas prices if you go with arrays.

The big difference between an array and mapping is that doing a search inside of a mapping is what is called in Computer Science discipline, Constant Time.

When we say constant time, it means that no matter how many pieces of data we are storing inside this mapping, its always going to take the same amount of time. So if we have one proposal, it will take one second, but if we have a thousand proposals, it still only takes one second to iterate through these proposals.

Clearly, you definitely want to use mapping here.

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.