I benchmarked Cartesian product implementations in Haskell, then compared them with C

Like many languages there is a tradeoff between idiomatic code and tightly optimized numeric hot loops. Applying some optimizations I'm able to get the Haskell vector flat version (fastest version on my hardware) from 4.4x slower than C (your article number) to faster 😄. move salt out of inner hot loop, and instead invalidate once per iter (matching C version behavior, ~7% reduction) switch to PrimArray (faster than both Vector.Unboxed and Storable) (1.6x slower than C) flattening inner loop via a pre-computed nval * j offset table (once at start of bench) instead of nested inner loop with nval * j (1.3x slower than C). I think this is a fair optimization you could really do if this was a critical function, in a real program you would memoize this by stride length but in your bench stride is constant. Why does this inner loop flattening trick work? C compiler sees the benchmark test data dims are 5x5, and is able to automatically unroll the hot loop to 5 straight line copies (since it knows stride = 5 at compile time). We can do the same optimization manually at runtime in Haskell via a lookup table, once we know stride = 5. After modifying the C code so that it's unable to loop unroll (data as runtime input instead of const's) it becomes slower than my optimized Haskell code. Haskell flattened inner loop: 0.77x runtime of runtime data C 😎. Of course, C can benefit from this inner loop flattening also, applying the same optimization to C puts C in the lead again by 14% without vectorization, and by 60% with vectorization. Now the Haskell and C are both running the same algorithm, the gap is roughly broken down as 4/5ths auto-vectorization (Haskell doesn't auto-vectorize, and it's a big win on this problem), 1/5th residual. That 14% residual performance gap is a real performance penalty for Haskell, but it's much much smaller. For any real use case where the performance of this function is critical, you will want to reach for hand written SIMD intrinsics anyway rather than relying on the compiler to always get auto-vectorization correct. Intrinsics are available in both C and Haskell. I think what this shows more than anything else is how challenging it really is to write a good benchmark!