Skip to content

Finding the Right Shape: Implementing BLAS in Haskell

Based on a presentation given in March 2017. The slides contain the full source listings, the simplifier output, and the benchmark plots that this post summarises.

There is an idea, first articulated by Lex Augusteijn in his 1998 paper Sorting Morphisms and later made central to Jeremy Gibbons' 2003 chapter Origami Programming, that has stayed with me ever since: many divide-and-conquer algorithms are determined purely by their recursion pattern. Once you have fixed the right shape for the computation, there are essentially no further design decisions to be made. The algorithm writes itself. Fold the problem on the natural axis and the structure of the computation reveals itself; fold it wrong and you end up writing Fortran by hand, special-casing every traversal, unrolling every loop.

lambda-blas was a six-month attempt to test that claim against an unforgiving benchmark: dense numerical linear algebra. Could the inner loops of BLAS, the de facto reference for dense linear algebra since the 1970s, be expressed as simple compositions of folds and unfolds and still run as fast as the reference Fortran? The answer turned out to be yes. The library is lambda-blas and it is public on GitHub.

This was, first and last, an aesthetic project. The performance comparison against Fortran came later, as the empirical defense one is required to mount whenever advocating for functional programming in a procedural world. We will get to it. But it is not what made me sit down to write the library, and it is not the result I find most interesting.

Origami: fold, unfold, map

The framework Gibbons (2003) draws together for working with these recursion patterns sees recursive computation as having, at root, three shapes:

  • fold consumes a recursive structure into a value, by replacing each constructor with an algebra
  • unfold produces a recursive structure from a seed, by generating each constructor from a coalgebra
  • map transforms a recursive structure of one element type into a recursive structure of another, by applying a function pointwise

Almost every divide-and-conquer algorithm in the imperative world turns out, on inspection, to be a fold-after-an-unfold. QuickSort is the textbook example: you unfold a list into a binary tree by partitioning around a pivot, then fold the tree back into a sorted list by concatenation:

qsort :: Ord a => List a -> List a
qsort = fold join . unfold split

split :: Ord a => List a -> TreeF a (List a)
split (In NIL)         = LEAF
split (In (CONS x xs)) = let (ls, gs) = partition (< x) xs
                         in BRANCH ls x gs

join :: TreeF a (List a) -> List a
join LEAF             = In NIL
join (BRANCH l x r)   = l `append` (In (CONS x r))

The intermediate tree is never something you allocate or care about. The compiler can fuse it away entirely, leaving a single recursive algorithm that walks the input list once. The shape of the computation, written at the level of the data, is exactly the shape of the algorithm.

This is the kind of thing that captivates you, the first time you see it. It is also the kind of thing that has to be made rigorous before it can be trusted with a numerical kernel.

The vocabulary of shape: polynomial bifunctors

The framework that makes "find the right shape" actionable in a real compiler is the calculus of initial algebras of polynomial functors, set out in the famous "Bananas, Lenses, Envelopes and Barbed Wire" paper (Meijer, Fokkinga and Paterson 1991) and the textbook Algebra of Programming (Bird and de Moor 1997).

The framework has four moving parts.

Polynomial bifunctors. Every algebraic data type can be built from four type-forming operations:

  • Id(A) = A
  • Const(A,B) = A
  • A × B (product)
  • A + B (sum)

ListF(A,B) = 1 + A × B says "a list shape is either empty, or a head paired with a tail." TreeF(A,B) = 1 + B × A × B says "a tree shape is either a leaf, or a left subtree paired with a value paired with a right subtree." These are base functors; they describe the shape of one layer of a recursive type without committing to what the recursion looks like.

The shape acts on functions, not just values. Each bifunctor F lifts a pair of functions (f, g) to F(f,g) acting on F(A,B) values. For lists this is the familiar bimap: apply f to the head and g to the tail. The lift satisfies two simple laws (which apply to every polynomial bifunctor):

F(id, id)         = id                        (identity)
F(f,g) ∘ F(h,k)   = F(f∘h, g∘k)               (composition)

These two laws are what make fusion work. Two consecutive bimaps can always be merged into one. An identity bimap can always be eliminated. The compiler does not need to be smart; it needs to apply the rules.

Recursive types are fixed points. A recursive type like a list or tree is the least fixed point of its base functor. There is a canonical pair of functions:

in  : F(A, μF.A) → μF.A     (constructor)
out : μF.A → F(A, μF.A)     (destructor)

with in ∘ out = id and out ∘ in = id (Lambek's lemma). Fold, unfold, and map fall out as the obvious operations:

fold   :: Bifunctor f => (f a b -> b) -> Rec (f a) -> b
fold g  = g . bimap id (fold g) . out

unfold :: Bifunctor f => (b -> f a b) -> b -> Rec (f a)
unfold g = In . bimap id (unfold g) . g

Fold is the unique homomorphism from the initial algebra into any other algebra of the same shape. That uniqueness is the fusion theorem: any function expressible as a fold is fully determined by its algebra, and any algebra rewrite is a semantics-preserving program rewrite. This is why foldr f z . map g = foldr (f . g) z is a theorem, not a heuristic.

Rewrite rules mechanize the calculus. GHC lets library authors declare equational rewrites as compiler pragmas:

{-# RULES
"bimap/id"     bimap id id = id
"bimap/bimap"  forall f g h k z. bimap f g (bimap h k z)
                                 = bimap (f . h) (g . k) z
#-}

These are not heuristics. They are theorems, expressed in a syntax the compiler can apply.

A test case: BLAS

BLAS is a hostile environment for any kind of high-level abstraction. The reference Fortran implementations are towers of special cases: one branch when increment is one, another when both increments are one, manual loop unrolling by five, separate handling for negative strides. The sdot reference implementation is sixty lines of mutable indices and GOTO-style control flow. None of it is hard, exactly; it is just the price of writing the code you have to write when you cannot trust the compiler to find the right shape for you.

The functional version is two and a half lines:

dot :: Num a => Int -> [a] -> Int -> [a] -> Int -> a
dot n u incu v incv =
    foldl' (+) 0 $ zipWith (*) (sample n u incu) (sample n v incv)

Read it as origami: take the elements you want from each vector (sample is an unfold), zip them into pairs (a map of products), and fold the result with sum. The shape is exposed at the surface. There is no special case for inc = 1. There is no manual unrolling. There is no separate code path for negative increments (sample handles direction internally). What the compiler does with this specification is the question the rest of the project tries to answer.

What did not work, and why

The first implementation represented vectors as Haskell's built-in lazy lists and relied on short-cut fusion (Gill, Launchbury and Peyton Jones 1993): list-producing functions are written as builds, list-consuming functions are written as right folds, and a single rewrite rule collapses any producer-consumer pair:

{-# RULES "foldr/build"
      forall f z g.  foldr f z (build g) = g f z #-}

The fusion fired. The compiled code did not allocate intermediate lists. And sdot ran five to fifteen times slower than the unsafe Fortran call for realistically sized vectors. It was competitive only for toy examples.

Inspecting the GHC simplifier output for the fused loop made the problem clear. Three things stood out.

  1. Linked-list dereferencing is not free. Even after fusion, each step of the loop chased a pointer to the next cons cell. Fortran was indexing into a contiguous unboxed array; my Haskell was walking a linked list of boxed pairs.
  2. Strided access made it worse. When incu /= 1, I implemented sampling as drop (inc - 1) between elements. On a list, drop is O(inc) per step, making the total cost O(n × inc) instead of O(n).
  3. abs desugaring leaked into the inner loop. GHC compiled abs incx as an if-then-else, adding a branch per element.

The first two are the real story. Linked lists are the wrong shape for dense numerical work. They were never going to be fast no matter how good the fusion. Even with all intermediates eliminated, the final representation was still a chain of pointers.

But there is a deeper, more interesting problem too. Short-cut fusion is built around foldr, and BLAS reductions are inherently left-folds: an accumulator-strict sum, a running max-index, a sum of squares. Right-fold fusion forces the structure into memory before reduction; left-fold fusion can be made to work, but only by twisting the rewrite rules into shapes the compiler often fails to spot. The list, considered as an initial algebra, is fundamentally biased toward consumption-from-the-right.

The shape was wrong. Not the implementation of the shape, the shape itself.

The right shape: streams as final coalgebras

A list is a least fixed point. It is initial data. An initial algebra is, almost by definition, a concrete value in memory. You build a list by allocating cons cells; you take it apart by reading those cells. Fusion can collapse pipelines that produce and then consume a list, but as soon as the list itself crosses a function boundary it has to be made manifest. You cannot fuse with something that already exists.

Stream fusion (Coutts, Leshchinskiy and Stewart 2007) takes the dual view. Instead of representing a sequence as initial data, it represents it as a final coalgebra: an existentially-hidden seed state plus a step function that produces the next element when asked.

data Stream a = forall s. Stream (s -> Step a s) s

data Step a s = Done
              | Skip      s
              | Yield  a  s

Stream is the co-Church encoding of the greatest fixed point of StreamF(A,B) = 1 + B + A × B. The three branches of Step correspond exactly to the three summands.

The trick is what GHC does with this representation when it inlines. When a stream consumer (a fold) inlines a stream producer, the producer's step function gets pasted directly into the consumer's loop body. The existential seed type s becomes a local variable. The Step constructors become tags in a case expression. After GHC's case-of-case and constructor-specialization passes, the intermediate Stream value never exists at runtime. There is no heap allocation, no boxing, no virtual dispatch. The fused code is a single tight loop that looks just like the hand-rolled version.

This is the substantive difference between short-cut fusion and stream fusion. Short-cut fuses the use of a list while leaving the list itself intact. Stream fusion eliminates the data structure entirely, by using a representation that is already virtual.

There is a second benefit that turned out to matter for BLAS: streams fuse left-folds and right-folds equally well. The consumer drives demand by repeatedly calling the step function, and it does not care which direction the implicit fold runs in. For an accumulator-strict reduction like sdot, that is exactly what is needed.

The right shape for a vector, it turns out, is corecursive, not recursive. Once you have that, the Gibbons thesis comes back into focus: the surface code does not change. dot is still foldl' (+) 0 $ zipWith (*) .... Only the underlying representation moves from initial to final.

The second implementation

The second λ-blas implementation switched the underlying representation from [a] to Data.Vector.Storable, which uses a contiguous unboxed memory layout under the hood and exposes a generalized-stream-fusion API (Mainland, Leshchinskiy and Peyton Jones 2013).

import qualified Data.Vector.Storable as V

dot :: (V.Storable a, Num a)
    => Int -> V.Vector a -> Int -> V.Vector a -> Int -> a
{-# INLINE dot #-}
dot !n sx !incx sy !incy =
    V.foldl' (+) 0 $
        V.zipWith (*) (sampleElems n sx incx)
                      (sampleElems n sy incy)

sampleElems is the strided-access function that replaces the broken list drop. For positive increments it reduces to a stream that yields every inc-th element of the underlying array via direct indexing. For negative increments it reverses the indexing direction. Either way the cost per element is O(1), so the total cost is O(n) regardless of inc. The list version had been O(n × inc).

Under the hood, the Stream type that Data.Vector actually uses is the monadic generalization of the one I sketched earlier:

data Stream m a = forall s. Stream (s -> m (Step a s)) s

For the BLAS code m is specialized to Identity — an operationally trivial wrapper that the simplifier inlines away completely. The return Done and return (Yield x s') in the step function become Identity constructors that case-of-case and constructor-specialization eliminate. The same machinery covers effectful pipelines when you need them (m ~ IO, m ~ ST s), but for the pure linear-algebra kernels the monad parameter is type-level scaffolding with zero runtime cost.

This is what Mainland, Leshchinskiy and Peyton Jones (2013) generalized over the original pure Stream from Coutts, Leshchinskiy and Stewart (2007): the same fusion infrastructure now serves both pure and effectful streams, and pure code pays nothing for the generality.

The full Numerical.BLAS.Single module covers thirteen distinct Level-1 operations, each implemented as a polymorphic function with single- and double-precision aliases (sdot/ddot, snrm2/dnrm2, and so on). They divide into two camps.

Nine of them are origami in the strict sense: dot, scal, copy, swap, asum, iamax, axpy, rot, and rotm. Each is three to ten lines of point-free Haskell composed of V.foldl', V.zipWith, V.map, and the strided-access helpers. No special case for inc. No manual unrolling. No pragmas beyond INLINE. Generalized stream fusion does the work.

The remaining four are reference implementations: faithful ports of the Netlib originals with explicit recursion and pattern matching where the mathematics demanded it. nrm2 uses a Cholesky-style scaled sum-of-squares (the classic slassq algorithm) to avoid overflow when elements span many orders of magnitude. sdsdot does mixed-precision accumulation with hand-written recursive loops for the unequal-increment case. rotg and rotmg generate Givens rotation matrices through case analysis on magnitudes and signs, with rotmg using a bisection-style rescaler to keep the diagonal within safe limits.

Origami wins where the mathematics composes as a pipeline. Where the kernel demands overflow guarding, mixed precision, or geometric case analysis, a faithful reference implementation is the honest answer. The boundary between the two is itself part of what the project shows.

On performance

Functional programming has a persistent reputation among non-practitioners as too slow, too abstract, too academic to be practical. As someone who has spent two decades writing provably correct software for commercial-scale pharmacovigilance, metabolic modeling, and supply-chain optimization, I can report that none of that is true. Functional programming is conceptually clear and stripped to the bones. That has been my experience, year after year, in domains where correctness is non-negotiable.

The aesthetics I may not be able to convince you of. The performance I can at least provide evidence for.

The list-based version had clocked in at five to fifteen times slower than the unsafe Fortran call for realistic problem sizes, competitive only on toy examples. The stream-based version landed within a constant factor of unsafe Fortran for all problem sizes I measured, and beat the safe Fortran call (the one with the FFI overhead) for vectors with fewer than about a thousand elements. Two specific results from the benchmark deck:

  1. For sdot(n, u, 1, v, 1) with n from 1 to 10,000, the stream-based λ-blas execution time tracks the unsafe Fortran call within roughly 100% across the entire range. The relative execution time stays near unity instead of climbing to 1500%.
  2. For sdot(100, u, inc, v, inc) with inc varying from -100 to +100, the stream-based version is constant in inc. The list-based version had been linear in inc, climbing to roughly 100× slower at |inc| = 100. The change of representation collapsed an entire dimension of the cost function.

The full benchmark plots are in the presentation slides.

So the empirical defense holds for the dimension where evidence is straightforward. lambda-blas matches Fortran on the benchmark Fortran was designed for. But the result I find more satisfying is the one I started with, the one no benchmark can prove: the surface code is foldl' (+) 0 $ zipWith (*) ..., two and a half lines, with no branches and no special cases. The shape is right. The compiler does the rest.

An aside, on the Haskell community

Years before this project, at ICFP 2008, I happened to be seated next to a stranger. On the breaks between talks we got to talking about musical instruments. At the time I was thinking about building a violin, and we discussed wood selection and the geometry of the body. It was only at the afternoon break that my colleagues informed me I had been talking to Phil Wadler. Which explained, in retrospect, the ring of nervous-looking graduate students arrayed at a polite distance.

I mention this because the FP community has an unusual property among technical communities: the people who built the foundations are, by and large, still around, still approachable, and still happy to talk about violins.

What I took away

The thesis I started with — Augusteijn's, restated — held empirically. The version of dot that runs at Fortran speed and the version of dot that reads as a one-line origami specification are the same artifact, parameterized only by the choice of fixed point. That parameter is the entire optimization. The conceptual clarity and the performance are not separate concerns at war with each other.

Two things changed how I think about performance work in a high-level language as a result.

Universal-property thinking earned its keep. I was able to swap lists for streams without rewriting the code because my operations were already expressed as fold, unfold, and map. The categorical framing made the data representation a parameter of the implementation rather than something baked into it. When I needed to move from a least fixed point to a greatest, the user-facing API barely changed.

GHC's rewrite rules deserve more credit than they get. They are not a hack bolted onto the optimizer. They are a principled mechanism for expressing semantic equivalences, with category theory underwriting the correctness of the rules and the simplifier turning them into native code that competes with what a careful human would write.

The library is on GitHub under the BSD-3-Clause license. Documentation, benchmarks, and the test harness that pinned the implementation to byte-equivalence with Fortran BLAS are all there.

With thanks to David Balaban, Nicholas Frisby, Gary Howard, and David Spivak for conversations during the work.

References

Augusteijn, L. (1998). Sorting Morphisms. In: S. D. Swierstra, P. R. Henriques and J. N. Oliveira (eds.), Advanced Functional Programming, LNCS 1608, Springer-Verlag, pp. 1–27.

Bird, R. and de Moor, O. (1997). The Algebra of Programming. Prentice Hall.

Coutts, D., Leshchinskiy, R. and Stewart, D. (2007). Stream Fusion: From Lists to Streams to Nothing at All. Proceedings of ICFP '07, pp. 315–326.

Gibbons, J. (2003). Origami Programming. In: J. Gibbons and O. de Moor (eds.), The Fun of Programming, Palgrave Macmillan, pp. 41–60.

Gill, A., Launchbury, J. and Peyton Jones, S. (1993). A Short Cut to Deforestation. Proceedings of FPCA '93, pp. 223–232.

Mainland, G., Leshchinskiy, R. and Peyton Jones, S. (2013). Exploiting Vector Instructions with Generalized Stream Fusion. Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming.

Meijer, E., Fokkinga, M. and Paterson, R. (1991). Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. Functional Programming Languages and Computer Architecture, pp. 124–144.

Peyton Jones, S., Tolmach, A. and Hoare, T. (2001). Playing by the Rules: Rewriting as a Practical Optimisation Technique in GHC. Haskell Workshop 2001.

Wadler, P. (1990). Recursive Types For Free. Manuscript.

Comments & reactions