Joachim Breitner's Homepage

(This is the third optimization presented in the “faster winter” series, please see that post for background information.)

Today, we will tackle the big bad memory leak that eats up my laptop’s memory.

A quick look at the heap profile (+RTS -h) showed that the memory was filling up with lists. Not very helpful, as lists are everywhere. So I looked through the hot code of the interpreter, eval, step and instr in Wasm.Exec.Eval to see if anything fishy is going on. I found some uses of the list concatenation operator (++) – always a bad sign, as it has to traverse the list on its left completely!

And often the solution is pretty simple: Use difference lists! It’s even simpler than the name makes it sound like. It does not require you to import anything new, and works well everywhere where you assemble a list in multiple stages, but use it, in its full form, only once at the end. The trick is easy:

• In the types, replace [t] with [t] -> [t] (or introduce an alias type DList a = [a] -> [a])
• Replace [] with id
• Replace [x] with (x:)
• Replace xs ++ ys with xs . ys, if ys is also a difference list
• Replace xs ++ ys with xs ys, if ys is a normal list
• To turn the difference list xs into a normal list, write xs []

That’s it, and suddenly you have a list like data structure with constant-time concatenation!

Improvement: Allocations: -9.67% Memory: -99.08% Time: -47.36% (Commit 2e284f8…f9bbe8e)

Memory consumption is now at 60MB. I found some more places where I could use difference lists, and then it was finally at essentially zero, which is what you would expect for the program at hand:

Improvement: Allocations: -0.21% Memory: -96.83% Time: -2.91% (Commit f9bbe8e…bbe8af7)

To be honest, I am not actually sure why this fixed a space leak: Difference lists are not more memory efficient than normal lists! But maybe somehow these lists were more strictly evaluated once they were difference lists? Anyways, I was happy with the result and did not investigate further.