Programming

How to Make Racket Go (Almost) As Fast As C

steloflute 2024. 10. 18. 00:55

How to Make Racket Go (Almost) As Fast As C | Lambda Land

 

How to Make Racket Go (Almost) As Fast As C

I recently wrote about using first-class functions to help make a BF interpreter. This is a follow-up post to describe a nifty solution to a tricky problem that made my program go 2–5× faster and put it about on-par with an interpreter written in pure C

lambdaland.org

 

A basic interpreter works by walking down the AST and evaluating nodes recursively: when the interpreter encounters an expression, it dispatches on the type of expression to decide how to perform the evaluation. Here’s the key insight to get a massive speed bump with very little effort: that dispatch is expensive and can be performed ahead-of-time. We can walk through the code once and precompute all the dispatching work.

This is not a new idea. The first description that I’m aware of comes from Feeley and Lapalme [1]. A name for this technique is making a threaded interpreter. It’s nowhere near as fast as a native code compiler, but interpreters are easy to write, and this is a very simple way to get a very big boost in performance.

 

Using closures for code generation - ScienceDirect

 

Using closures for code generation

https://doi.org/10.1016/0096-0551(87)90012-9Get rights and content

Abstract

This paper describes a new approach to compiling which is based on the extensive use of closures. In this method, a compiled expression is embodied by a closure whose application performs the evaluation of the given expression. For each primitive construct contained in the expression to compile, a closure is generated. As a whole, the compiled expression consists of a network of these closures. In a way, ‘code generation’ is replaced by ‘closure generation’. This method, combined with an efficient closure implementation, produces compiled code which compares favorably (in execution time) with its interpreted counter-part. It can also be used to implement compilers for embedded languages and as it has been implemented in Scheme, it yields a straightforward metacircular compiler for Scheme.