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