Use 64 bits for gas calculations

[chriseth]

Gas calculations in the interpreter are performed on 256 bits on even using bigints. We might change some places to just using unsigned (or better fixed to a certain bit size) because the block gas limit is certainly small enough.

[gcolvin]

Not only gas, but memory use and many calculations in the interpreter use arbitrary-precision bigint where 64 bits would do. The full memory and gas calculations are performed on every instruction rather that only those that affect memory. Also, a variable-length STL vector for the stack is used rather than a fixed-length array. These changes will get the interpreter running as well as it can with it's current design.

[chfast]

The interpreter will not pass some of the official tests after the change.

Related EIP: ethereum/EIPs#92.

[gcolvin]

Greg Colvin @gcolvin 00:10
I've started committing improvements to existing interpreter. https://github.com/gcolvin/libethereum/blob/develop/libevm/VM.cpp
"Interpreter speedups. Eliminate unecessary bigint. Eliminate gas and memory counting overhead for operations that don't need it. Parameterize size of machine word. Slightly faster with 64-bit word, but fails more tests of extreme parameters. More improvements to come."

Bob Summerwill @bobsummerwill 00:40
^ Cool. Pull request them up when you're ready

Greg Colvin @gcolvin 00:41
Have achieved about a 3X speedup so far. I see two big impediments to the next round of improvement.

First, the available backends for boost::multiprecision are optimized for very large numbers. So for our 256-bit numbers we use 320 bits to allow for a header. That means our numbers won't fit evenly in cache lines and memory pages. Plus boost does not support exchange with external binary formats. So we need to make a fixed-size replacement that uses only 256- (64-, 128-, or 512-) bits, and has fast support for external formats.

Second, the JUMP instruction is a computed goto: it takes its argument off of the stack. Usually the destination is fixed, pushed (slowly, see above) from the code preceding the jump. But because the destination might not be fixed it must be validated against a table of valid destinations. The overhead is bad enough that in the following loop about half the time is spent in the loop execution itself.
for (int i = 0; i < 100000; ++i) {
rand1 = 0xffe7649d5eca8417 * rand1 + 0xf47ed85c4b9a6379;
rand2 = 0xf8e5dd9a5c994bba * rand2 + 0xf91d87e4b8b74e55;
rand3 = 0xff97f6f3b29cda52 * rand3 + 0xf393ada8dd75c938;
rand4 = 0xfe8d437c45bb3735 * rand3 + 0xf47d9a7b5428ffec;
}

Better wide integers requires coding the usual tricky algorithms for arithmetic operations, plus all the other functions required of a boost::multiprecision backend. Then it can be plugged into the classes in libdevcore/common.h to speed up our extra-wide integers in the interpreter and elsewhere.

Dealing with computed JUMP addresses without a table search is harder. Faster loading of the jump adress from the bytecode array will help, but a search for a valid destination seems unavoidable.

Greg Colvin @gcolvin 00:47
Can't pull them @bobsummerwill. The spec allows for and the tests try to do things like allocate 2^256-1 bytes of memory or units of gas just to see what happens. The old interpreter used arbitrary-precision bigints to slowly but gracefully refuse. In places the new interpreter gives up sooner (2^63 should be more than enough gas for anybody...) and the tests cry foul. So it's bigger change than just my code.
ethereum/EIPs#92

[gcolvin]

This is confusing, to me anyway. The work has become just a small part of the now ongoing ethereum/libethereum#234. So it's not really a Duplicate. And the question of whether to allow this at all got added later as ethereum/EIPs#92 and ethereum/EIPs#106. And in my confusion @chriseth and I have been bouncing titles and tags for a couple weeks. I've changed the title back to gas calculation, as that's as much as I did before starting the pull request. I don't recall why I bounced between Active back to In Progress, or even really know what the difference is, so I've set it back to Active as Christian had it.

[bobsummerwill]

I think this is all done now, eh?