"As fast as C" has been buzzing around Haskell circles, so I figured I'd write a short blog post on a benchmark I stumbled on that's actually faster than its equivalent in Rust for small inputs. I have good things to say about both languages, so stick around.

Part I: The Benchmarks

The task is simple, if contrived: given a string, return all proper suffixes of a string. That is, if given "tails", we should return "ails", "ils", "ls", and "s".

The Haskell is simple, though advanced. I am quite convinced that it is the fastest solution available (using String, at least). Note that it is more general than the Rust code.

import Data.Functor.Foldable
suffix :: [a] -> [[a]]
suffix = hylo algebra coalgebra . drop 1
algebra :: ListF [a] [[a]] -> [[a]]
algebra Nil         = []
algebra (Cons x xs) = x:xs
coalgebra :: [a] -> ListF [a] [a]
coalgebra []     = Nil
coalgebra (x:xs) = Cons (x:xs) xs

The Rust is similarly simple, though I am less confident that it is the fastest possible implementation; note that it must return a vector of owned Strings so as to be comparable to the Haskell.

pub fn suffix_vec(s: &str) -> Vec {
    let mut vec = Vec::new();
    for (j, _) in s.char_indices().skip(1) {
        vec.push((&s[j..]).to_string());
    }
    vec
}

The code to benchmark both of these is available here (or on github).

The results are quite dramatic on both ends:

Part II: Analysis

First, we see why treating Strings as linked lists of Chars is a bad idea. An O(n) algorithm becomes... not O(n).

Second, I think this is an apt illustration of why I like Rust despite Haskell being my main squeeze. Rust is the first language I've learned where you can do things that you couldn't in Haskell (here, distinguishing references and values).

But these results are nonetheless surprising. Not only is it generally held that C/Rust are fast on an order not touchable by higher-level languages, but also the fact that the overlap occurs in an entirely reasonable domain (most words are strings of length between 5 and 20) and results in Haskell code over four times faster on the lower end and around 1.5 faster on the upper end.

A small bit of this is the use of the hylomorphism. With pattern matching alone, Haskell is slower on short strings. I think it hints at an undervalued aspect of performance: abstractions.

Another bit is Haskell's much-derided laziness. I'm not sure how much this contributes, but I suspect that GHC is able to optimize away some of the control flow, while Rust allocates for the loop in all cases.

So what to conclude? Unfortunately, we can't make any sweeping statements. Despite Rust's signal deficiency here, it's hard to imagine an application where this particular function would be called repeatedly. Moreover, if I'm right and the performance is due to optimizing away lists, it's hard to imagine this being replicated on larger strings with something like Text.

Of course, that's not the whole story: it's easy to imagine being blindsided by a similar function, especially as code complexity grows. Given that Rust is a systems programming language, I hope to see its performance to catch up to Haskell as things progress.