Roadmap for a fast interpreter in G

Rationale

Prior discussions, studies, and experiments have been reported here:

• Measuring Michelson execution and typechecking : https://hackmd.io/@yrg/Sk38xc2Uv
• Optimizing the gas monitoring and update: https://hackmd.io/@yrg/rkLwB17wD
• Optimizing the interpretation loop: https://hackmd.io/@yrg/H1KC0PSdv

Summary

With these preliminary studies, we have learned that:

1. Gas monitoring and update have a really important cost on the interpreter efficiency. Fortunately, a sequence of optimizations could reduce this cost by a factor of ~10.
2. An interpretation loop can produce an Lwt computation efficiently if instructions are written in a first-order-delimited-continuation-passing style and with a stack where the top is distinguished. Moving from the original style to this new one could reduce the cost of interpretation by a factor of ~3.5. The well-typed and tagless approach is still compatible with this style.

Our current estimation of speed-up is a factor from 5 to 8. Notice that this estimation cannot be trusted as long as we do not have a serious benchmarking process.

Milestones

Optimization of the gas monitoring and check for exhaustion

• !2327 (merged) Optimize gas counting. Status:
• !2328 (merged) Use a layered context to optimize the update of the gas counter. Status:
  • @paracetamolo wants a more general refactoring of the context but this seems orthogonal to this project.
• !2329 (merged) !2330 (merged) Use saturated arithmetic to represent gas quantities. Status:
  • No problem detected so far.
• !2335 (closed) (as a commit) Pay gas in advance for sequences of instructions of statically known cost. Status:
  • Canceled: for the moment, there is no proof that this improves smart contract execution.
  • Need a slightly different method to decompose the cost model: @igarnier.
  • Probably need a cache to make sure that this does not penalize contracts with no loop.

Optimization of the interpretation loop

• !2723 (merged) Implement a new interpretation loop by migrating to a new instruction datatype Status:
  • Done.
• !2723 (merged) Implement zero-cost logging Status:
  • Done.

Optimization of the parser/typechecker aka the elaboration of Michelson scripts

• !2723 (merged) Migrate the elaboration to the new IR Status:
  • Done.

Validation

• Implement a robust benchmarking process for Michelson scripts
• Update the cost model
• Check that PayGas insertion really improve efficiency. Try to cache its result otherwise.

Communication

• Write a blog post about this work

Next milestones

• For H: Introduce lazy elaboration (see https://hackmd.io/O_0TMVU5SCKWoldnJzsNng)
• For I: Discover and introduce super-instructions in the new intermediate representation.
• For J: Introduce a native compiler for Michelson.