Introduce storage cache

[chriseth]

Suggested by @puellavulnerata - it might be a good idea to cache storage access in memory.

A simple cache based on a conflict free hash table in memory could already provide a gigantic benefit. Storage read has been changed from 50 to 200 gas since Solidity was designed (actually memory costs were assumed to be much higher at that point, too), so this might be feasile.

Storage reads could be replaced by the following code:

function sloadCached(key) -> value
{
  // Cache consists of a sequence of 256 key-value pairs,
  // where least significant byte determines position in cache.
  let cachePos := add(0x100, mul(and(key, 0xff), 0x40))
  if eq(mload(cachePos), key) {
    value := mload(add(cachePos, 0x20))
  } else {
    value := sload(key)
    mstore(cachePos, key)
    mstore(add(cachePos, 0x20), value)
  }
}

Storage writes have to invalidate the cache. Furthermore, external function calls have to clear the full cache.

[chriseth]

Preliminary analysis shows that a cache hit costs 130 gas, while a cache miss is 355 gas (including the 200 gas to read from storage).

Also the implementation above has to consider the special case of "unset" cache entries.

[androlo]

On a related note, there is an idea from @Arachnid about netting gas costs, which would mean lower cost for storage access when an address is zero by the time a transaction is done. Found it in this thread: ethereum/EIPs#718 (comment). Not sure if it has gotten any traction but seems related.

Also linking a related issue about costly writes: #2908

[chriseth]

This has been implemented on EVM level now.