The Programming Tug of War

| Programming, Optimization | By: Kevin R. Stravers

I think we’re doing programming wrong in 2019. There’s a constant battle raging between speed and simplicity that we can not ignore.

Both speed and simplicity are incredibly important in our industry and we need to service both. Alas, they tend to be diametrically opposed. As simplicity increases, speed decreases, and vice-versa.

1  So what can we do?

Today I’ll make a case for making optimizations an implementation detail of the compiler, in addition to showing ways we can optimize right now by using a compiler.

The only language I know of where the programmer is a compiler writer is Lisp. Lisp allows you to create macros to process code like data, and we can leverage this to perform optimizations. Here’s our first draft:

 (optimize-X

   (code here ...)

   (more code)

   (and some more))

This sucks because we need to infect the code with ‘optimize-X‘ clauses. We want to separate simplicity and optimization. So instead of this we need a separate compiler pass, a #lang in racket if you will.

2  A little compiler (pattern matcher)

So instead imagine two files, one to describe optimizations, and another to be written as cleanly as you can imagine.

Now to take a concrete example, let’s say we want a struct of arrays but we want to code it like an array of structs.

 (define data (make-structs))

 (for (i data)

   (add-value (struct-X i)))

Here we call add-value for the member ‘X‘, for every item in ‘data‘. Now this is slow, as the offset of the entry ‘X‘ may be very large as the structure contains other data.

In our optimizer we can solve this:

 (match `(make-structs)`

   `(transform-to-soa (make-structs))`

 (match `(for (,i ,x) ,ops ...)

   (if (eq? (type x) 'soa-struct)

     `(for (,i (get-X-array ,x)) ops ...)

     match-value))

The above transforms the structs into a SoA version upon creation, and then transforms any for loops that iterate over the SoA type to instead iterate over a very dense SoA array.

If we want, we could even add SIMD to the iteration.