The Problem

Recently, some Unison folk noticed that some loops they were running appeared to take time that was quadratic in the number of iterations. This is pretty odd, since it means that each, separate iteration somehow makes the next one more expensive.

Since there was nothing about the loops themselves that was obviously quadratic, a typical culprit to look at is stack growth. For instance, if your loops are just recursive functions, and the language doesn't have proper tail calls, then the stack grows linearly in the number of iterations. So, if something in each iteration is proportional to the stack size, the result is quadratic behavior.

Unison does have proper tail calls, so the stack shouldn't have been growing for these loops. But, it also has operations whose cost is proportional to stack size: abilities. When you use an ability (currently), part of the stack is captured and handed to the ability's handler. Then the handler does something, and resumes execution by copying the stack back into place. This is how the k works when you do something like:

ability Counter where
  inc : {Counter} Nat

incrementer : Nat -> Request {g, Counter} x -> x
incrementer n = cases
  { r }        -> r
  { inc -> k } -> handle k n with incrementer (n Nat.+ 1)

The problematic loops were using abilities, so if the stack were somehow growing, that would explain the issue.

The first guess was that something about the interpreter was inherently growing the stack when abilities were used. But, that turned out not to be the case. Many loops had linear performance, even when using abilities. So, something more specific had to be happening.

The Answer

It turns out, the problem was actually entirely in the surface program. There is a certain way of structuring a handler that will result in stack growth proportional to the number of effects used. It looks like this:

bad : Nat -> '{Ask Nat, Tell Nat} r -> r
bad n th =
  handle provide n th
  with cases
    { r }           -> r
    { tell _ -> k } -> bad n k

The problem with this handler is that every time you tell something, it adds a new, redundant provide handler to the stack. The first time you call it, this is necessary, because th has both Ask and Tell effects. However, provide handles all Ask effects, so k has none. When bad calls itself recursively, it's passing a thunk that only has Tell effects.

If you use this handler with a loop that uses Tell effects, then each iteration will grow the stack, and each subsequent effect will take longer.

The solution is to rework the handlers to only use provide once at the start. Then the use of Tell keeps the stack the same size, and each iteration of the loop has a consistent cost. In this case, the easiest way is to just use two completely separate handlers, but you could bundle them together like:

good : Nat -> '{Ask Nat, Tell nat} r -> r
good n th =
  forget = cases
    { r }           -> r
    { tell _ -> k } -> handle k() with forget
  handle provide n th with forget

Help

Of course, this example is very simple, and one might realize that they shouldn't write it. But there might be more complicated examples that aren't so obvious. (Certainly, I think it wasn't so obvious in the original example that we found.)

So, I've just finished adding a new warning to the Unison type checker that tries to find these cases. Hopefully, if any other occurrences of this pattern are in use and causing performance problems, this warning will help catch them.