Qi Compiler Sync July 28 2023

Deforestation

Qi Compiler Sync July 28 2023

Adjacent meetings: Previous | Up | Next

Summary

We looked into the deforestation optimization.

Background

The groundwork for the optimizing Qi compiler has been laid, but we haven't actually written any optimizations yet. That's what we started looking into this time around.

Deforestation

We found this writeup to be a great starting point as it surveys a lot of different options for this optimization:

https://www.ccs.neu.edu/home/amal/course/7480-s12/deforestation-notes.pdf

The approaches surveyed are in order of precedence, with the latest one (at the time of writing) being "Stream Fusion." This approach involves defining a stream data type that could be used to rewrite stages of map, filter, foldl, foldr, zip, ... as an operation performed in one stage, and is the approach used in GHC, the Haskell compiler.

It did appear though that this approach may rely on assuming that some other optimizations are already present in the host language and we're not sure which of those are implemented in Racket, so, we'll aim to begin by writing out the optimized Racket code that would be produced by this optimization and see if it's actually faster than the unoptimized Racket version. Depending on the result, we may explore some of the other approaches surveyed in that article. Another possibility is to implement any missing optimizations in the stream fusion approach at the Qi compiler level.

Next Steps

(Some of these are carried over from last time)

• Write this as a nonlocal benchmark implemented in Racket: sum (map square (upto 1 n)) (example from the linked writeup above)
• Manually implement the optimized Racket version and see if it's faster
• Manually implement the optimized Racket version from one of the other approaches and see if it's faster
• Review the results and decide on an approach to implement in the compiler
• Add docs for syntax-spec and put it on the package index.
• Review other bindings cases that we could support next (e.g. selective binding, packing values, and binding exceptions in try).

Attendees

Jair, Michael, Sid