How to clear large arrays without blowing the gas limit?

Question

As posted by redditor ethererik in the post GovernMental's 1100 ETH jackpot payout is stuck because it uses too much gas, 1,100 ethers are stuck in limbo because the payout of this GovernMental pyramid scheme requires the clearing out of the arrays containing creditor addresses and amounts. This array has grown as each creditor added their ethers to this pyramid scheme. The code that clears the arrays in question follows:

creditorAddresses = new address[](0);
creditorAmounts = new uint[](0);

What is the best way to clear large arrays without blowing the gas limit?

Here is the stalled contract on live.ether.camp (link from romanmandeleil).

Here is a link to the smart contract code, and to the website.

Answer 1

The best way is simply not to clear them. In many (most?) situations, the array varies in size over time, and emptied slots will eventually be filled again. Instead of shortening the array, keep a separate count of live elements:

uint numElements = 0;
uint[] array;

function insert(uint value) {
    if(numElements == array.length) {
        array.length += 1;
    }
    array[numElements++] = value;
}

function clear() {
    numElements = 0;
}

This means that deleted elements remain in the array, but are ignored, since you can use numElements in place of array.length everywhere.

This also conserves gas on the whole; deleting and reinserting an item to an array costs 5k (deletion) - 10k (refund) + 20k (reinsertion) = 10k net gas, plus another 10k to update the array length twice. Overwriting, in contrast, costs only 5k gas, plus the same 10k to update the numElements variable twice.

In cases where the array is erased only once, and won't grow again, a more sensible alternative may be to spawn a new contract for the life of the event, and have it kill itself at the end, which will refund gas for all live storage elements to the caller.