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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
