[Haskell-cafe] To my boss: The code is cool, but it is about 100 times slower than the old one...

[wren ng thornton]

On 11/29/12 2:17 PM, Ivan Salazar wrote:
> The bad side is that direct translation of algorithms are almost always
> very slow and the work needed to make them perform is very mind bending.

Indeed. The thing is, all algorithms make (implicit) assumptions about 
the cost model of the underlying language. The problem comes about 
because the assumptions made in most algorithms are not valid in 
Haskell. This isn't just an issue of laziness; the entire computational 
model of Haskell (e.g., STG) is radically different from imperative 
languages.

For example, in many cases just passing arguments around (a la the State 
monad) is much faster than using ST and explicit mutation. GHC does a 
lot of clever code reorganization, but mutation breaks countless purity 
laws and so it inhibits the application of these optimizations. 
Unfortunately, the vast majority of algorithms out there assume you're 
working in a language where mutation is essentially free. I'm not 
talking about any significant theoretical issues about using mutation or 
not; I'm just talking about the implicit assumptions that algorithm 
implementers make. If you believe mutation is essentially free then it 
makes sense to create an initial object and then incrementally mutate it 
this way and that until you get to where you want. But, a great deal of 
the time there's nothing actually stopping us from gathering all the 
information and allocating the final result directly. However, if you're 
not used to thinking in those terms, then the conceptual reorganization 
required to see how to gather all the data at once is indeed mind-bending.

-- 
Live well,
~wren