blog

Functional programming often gets criticized as being slow, so I wanted to present an example where it is in fact several times faster than the equivalent imperative code¹.

The problem is to count the lengths of Collatz sequences, which you may remember from here. In Rust, this is straightforward:

fn modular(a: i64, b: i64) -> i64 {
    ((a % b) + b) % b
}
pub fn collatz_length(mut i: i64) -> i64 {
    let mut l = 1;
    while i != 1 {
        i = match modular(i, 2) {
            0 => i / 2,
            _ => 3 * i + 1,
        };
        l += 1;
    }
    l
}

This is a thoroughly imperative style - we use a mutable variable to track state, and we use a while loop rather than recursion. Our C code will be similarly simple:

int collatz_c(int n) {
  int l = 0;
  while (n != 1) {
    if (n % 2 == 0)
      n = n / 2;
    else
      n = 3 * n + 1;
    l++;
  }
  return l;
}

The implementation in ATS is notably less straightforward (you may find this section of the manual to be helpful):

#include "share/atspre_staload.hats"
fun collatz_length {n : nat} (n : int(n)) : int =
  let
    fnx loop {n : nat}{l : addr} (pf : !int @ l | n : int(n), res : ptr(l)) : void =
      if n > 1 then
        let
          val () = !res := 1 + !res
        in
          if n mod 2 = 0 then
            loop(pf | n / 2, res)
          else
            loop(pf | 3 * n + 1, res)
        end
    var res: int with pf = 1
    val () = loop(pf | n, addr@res)
  in
    res
  end

Here, we do something that is not possible to do in C - we safely stack-allocate a function argument. In addition, we use recursion, allowing us to model the actual problem².

In practice, this approach leads to dramatically faster code - our ATS code is 1.5 to 2.8 times faster than the equivalent Rust.

While this particular example may be simple-minded, I think it is nonetheless a nice demonstration that functional programming can indeed be faster than imperative.

^{2: In fact, had we write a more conventional implementation using pattern matching and recursion, we'd get about the same performance as Rust without the painful compromise of imperative programming.}