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) = AConst(A,B) = AA × 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):
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:
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:
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.
- 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.
- Strided access made it worse. When
incu /= 1, I implemented sampling asdrop (inc - 1)between elements. On a list,dropis O(inc) per step, making the total cost O(n × inc) instead of O(n). absdesugaring leaked into the inner loop. GHC compiledabs incxas anif-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.
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:
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:
- For
sdot(n, u, 1, v, 1)withnfrom 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%. - For
sdot(100, u, inc, v, inc)withincvarying from -100 to +100, the stream-based version is constant ininc. The list-based version had been linear ininc, 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.