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:
- 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.
- 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.
Edited by Yann Regis-Gianas