Why memory arrays are unresizable?

Question

I don't know the required length of my array before execution of the function.. why technically can't I resize my memory array?

What is the common way to go around of this problem, if you are also facing it.

I could make a storage array, and clear it at the end of the function, but would it take more gas? I also know the upper bound of the required length, so I could allocate a memory array with the upper bound size but 95% of it would be unused most of the time.

To make it clear I'm designing a market, there are n buy and m sell orders, I want to match them, matchedOrders array can be up to the size of max(m,n).

Answer 1

tl;dr You are right that it is not possible currently, but there's no fundamental reason why Solidity couldn't implement the feature in future.

Fully dynamically sized arrays don't sit easily with the EVM's memory model. An arbitrary sized array could exist, but it would have to sit higher in memory than everything else to allow it to grow upwards in an unlimited way. By definition, then, you could have only one of them, and in any case it's difficult for the compiler to arrange this in general.

Actually, dynamically sized arrays are a bit of a luxury to us old-school types. C doesn't have them for example. You have to specifically reserve the memory for the array using malloc() at runtime.

There are basically two scenarios:

1. Arbitrary sized arrays that can grow on demand. Solidity could probably implement these using a linked-list/skip-list structure internally, but this hasn't been done.

2. Dynamically sized arrays that can be created on-the-fly but remain fixed size once created. (This would meet your requirement.) I can't see any particular reason why Solidity couldn't implement this and it should be pretty easy. Again, it just hasn't been done See update below. Incidentally you can do this in the Ethereum LLL language via the alloc expression, so there's no fundamental limitation.

Storage arrays are fundamentally different from memory arrays and indexed by a key=>value mechanism, so it's much easier to make them dynamic. Using a storage array and zeroing it on exit is an interesting idea, but you'll still only get about half the gas back; each element will cost about 10000 gas, which is huge.

In summary, for now, you're either going to have to allocate at least the maximum conceivable size required, or find an algorithm that uses fixed memory size. You are probably going to have to put a cap on n and m in any case to avoid getting into a state where your contract becomes unrunnable due to needing more gas than the prevailing block limit.

---

Update

It turns out that approach 2 above is possible in Solidity. You can use the following syntax to create an arbitrary sized array on-the-fly. It will not be resizable, but ought to meet your requirement.

function bar (uint n, uint m) returns (uint) {
    uint maxnm = n < m ? m : n;
    uint[] memory a = new uint[](maxnm);
    return a[maxnm-1];
}

Answer 2

Memory arrays usually cannot be increased in size because the memory region after them may have already been allocated for other values.

However, they can be decreased in size using inline assembly. For example, this line will decrease the size of the memory array testArray by 1.

assembly { mstore(testArray, sub(mload(testArray), 1)) }

This function will return 122:

function test() public pure returns (uint256)
{
    uint256[] memory testArray = new uint256[](123);
    assembly { mstore(testArray, sub(mload(testArray), 1)) }
    return testArray.length;
}

You should always make sure that the array length does not underflow (go below 0). Also, this only works on dynamically sized memory arrays like ... memory[], but not on statically sized memory arrays like ... memory[10]

Answer 3

The array may be followed by used data. Therefore, an extension of size M to N could mean: allocation of a fresh sled N bytes + copy M bytes of data to that new location.

Up-sizing is likely forbidden because the memory-read and memory-write operations involved are potentially costly, and the programmer should be well-aware of when they are happening. A call to a realloc(...) primitive would mask that information.