[Haskell-cafe] haskell crypto is reaaaaaaaaaally slow

[David Roundy]

On Wed, Jun 20, 2007 at 06:19:35PM -0500, Derek Elkins wrote:
> On Wed, 2007-06-20 at 16:11 -0700, Anatoly Yakovenko wrote:
> > I don't think the problem with performance of crypto has anything to
> > do with unpacking ByteStrings. If I unpack the bytestrings first, then
> > run the hash, and just time the hash algorithm, i still get 4 seconds
> > with crypto where the C implementation gives me 0.02 seconds.  Thats
> > 200 times slower in haskell, to me it just seems like a bad
> > implementation.  You should be able to stay within an order of
> > magnitude from C with haskell without resorting to weird compiler
> > tricks.
> 
> A list of Word8 is -extremely- inefficient.

To expand on that terse (but very true) statement, a list of Word8
increases the space usage by a factor of probably around an order of
magnitude (two pointers + 1 byte vs 1 byte), completely destroys your
memory access pattern (which becomes random-access rather than sequential),
and introduces additional nonlocal memory accesses.  One would hope that a
hash function would be moderately close to being memory-limited, so we're
talking about a multiple-order-of-magnitude slowdown.

The main benefit of ByteString isn't weird compiler tricks, it's using a
reasonable data structure for the problem (although the weird compiler
tricks help, too).
-- 
David Roundy
Department of Physics
Oregon State University