Bringing Deforestation to Masses

It's been already almost three years since the work on deforestation in the Qi compiler has commenced. And an interesting idea started floating around lately: would it be possible to provide deforestation benefits to more users? Such as users of the threading macro?

As discussed often in this blog, the deforestation progress is something that does not stop. However it takes time before the next Qi release will be finished. Also there are some limitations of the current deforastation interface of the Qi compiler that will need to be addressed (ideally before the release).

For example the add-between procedure yields more elements of the transformed list than what was originally there. The current deforestation interface only allows for either transforming an element or skipping it. There is no way of yielding multiple times.

And before implementing any radically new approach internally in the Qi compiler, porting the deforestation machinery to a new interface - such as the Threading Macros might be an interesting venture. Focusing on single feature allows for quicker testing and if it is successful, the results of our deforestation efforts will be available to more programmers!

Let me introduce Ebb. A drop-in replacement for the threading macros with 100% backwards compatibility and deforestation for many operations on top.

It is not on the package server (yet), however you can install the relevant packages directly from the git repository. Usage as a threading macro replacement is rather simple:

#lang racket/base
(require ebb/threading racket/math)

(~> (range 10) (filter odd? _) (map sqr _))

Of course, you get '(1 9 25 49 81) as expected. But there would be no point in creating a new package for something that already exists. Let's see how fast this threading macro is in Racket REPL:

> (time (void (~> (range 10000000) (filter odd? _) (map sqr _))))
cpu time: 958 real time: 959 gc time: 784

And now require the deforested forms which are provided as nice and handy module ebb/forms:

> (require ebb/forms)
> (time (void (~> (range 10000000) (filter odd? _) (map sqr _))))
cpu time: 174 real time: 174 gc time: 124

That looks quite impressive, doesn't it? With some rigorous testing using the vlibench package, we get a nice picture (pun intended):

In this graph, the "threading" is the original threading module. The "ebb" is, of course ebb/threading with ebb/forms present. The label "qi/list" belongs to current Qi compiler with qi/list present and finally the cryptic name "pacman" is the codename of some latest development in the Qi compiler which may eventually replace the current compiler. As you can see its performance is the same as the original compiler, however the big difference is that it can yield multiple times and therefore it can be used to implement deforested add-between as well.

Isn't it all awesome? Try it yourself and see ya next time for more!