Hi, I'm looking for information on Haskell's viability for heavy integer math. My (very) naive tests show Haskell lagging behind C even when doing heavy (manual) inlining, compiling with special optimizations (funbox-strict-fields) and using continuation-passing-style when possible. Of course, being a beginner myself, I don't really know how good my code is. For reference, I wrote a simple MD5 implementation. It's as fast as the one in Happstack (Happstack.Crypto.MD5), which on my computer runs around 2.77 times slower then the base version from GNU coreutils (md5sum). GHC primitives appear as the next logical step in my tests, however I've been having problems using fixed sizes for integers (Word32# comes with no prim-ops defined?). Do you have any insights on this? Is it reasonable to expect Haskell integer performance to reach the levels of C with current implementations? Which are the limiting factors? Thanks!
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 8/6/10 23:32 , Sebastián E. Peyrott wrote:
Do you have any insights on this? Is it reasonable to expect Haskell integer performance to reach the levels of C with current implementations? Which are the limiting factors?
Integer, or Int? In theory Integer should use Int when possible under the covers, but that may not always do what you expect --- and Integer, being arbitrary precision, will never be as fast as native Int math. - -- brandon s. allbery [linux,solaris,freebsd,perl] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.10 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkxc3HIACgkQIn7hlCsL25VWIgCePL5sZCEL87WWoVQXJIUlgC1d PUwAmQEqtanpLJHa7amkz7GP9qH5rkBg =SoCp -----END PGP SIGNATURE-----
I meant fixed precision integers (such as Int). Sorry I wasn't clear about that. On Sat, Aug 7, 2010 at 1:09 AM, Brandon S Allbery KF8NH <allbery@ece.cmu.edu> wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On 8/6/10 23:32 , Sebastián E. Peyrott wrote:
Do you have any insights on this? Is it reasonable to expect Haskell integer performance to reach the levels of C with current implementations? Which are the limiting factors?
Integer, or Int? In theory Integer should use Int when possible under the covers, but that may not always do what you expect --- and Integer, being arbitrary precision, will never be as fast as native Int math.
- -- brandon s. allbery [linux,solaris,freebsd,perl] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.10 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
iEYEARECAAYFAkxc3HIACgkQIn7hlCsL25VWIgCePL5sZCEL87WWoVQXJIUlgC1d PUwAmQEqtanpLJHa7amkz7GP9qH5rkBg =SoCp -----END PGP SIGNATURE----- _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
2010/8/7 Sebastián E. Peyrott <pseus7@gmail.com>:
Hi, I'm looking for information on Haskell's viability for heavy integer math. My (very) naive tests show Haskell lagging behind C even
Relevant links : Benefits of the LLVM code generator (lots of other relevant posts on Dons' blog) http://donsbot.wordpress.com/2010/02/21/smoking-fast-haskell-code-using-ghcs... Archive of threads about loop unrolling : http://www.haskell.org/pipermail/glasgow-haskell-users/2009-March/thread.htm... (Also check some of the links in "You might also be interested in:") http://efreedom.com/Question/1-2978979/Haskell-math-performance David.
Thanks for the links. I had already seen Don's post, but I have yet to try the LLVM backend. I'll do so as soon as a stable GHC version with it is out. The Haskell math performance link is interesting. If I'm not mistaken, the OP achieved C levels of performance by switching to Data.Vector and keeping data structures as close to C as possible. That seems reasonable. However, for the example I gave earlier (an MD5 implementation), I don't see a way to use Data.Vector. The algorithm performs repeated operations on 4 32-bit integers and that's it. The implementation in Happstack is as close to C as possible, yet it's still slower. My own too. I've been trying to read the generated Core and assembly but I don't really have any experience doing that. I can see most fields are unboxed and inlining appears to be working. I see repeated calls to GHC.Prim.narrow32Word# too. In the generated assembly I see many operations with literal '$4294967295'. Could that be the culprit? I have uploaded the generated Core for the main MD5 computation (RFC1321, section 3.4) here: http://pastebin.com/e51njdcS The actual computation starts at line 1507. Please note this is not from the version in Happstack but rather from my own. You can find RFC1321 here: http://tools.ietf.org/html/rfc1321 If you feel talking about Core and assembly is perhaps not suitable for Haskell-beginners, I'll move this discussion to Haskell-cafe. Thanks. 2010/8/7 David Virebayre <dav.vire+haskell@gmail.com>:
2010/8/7 Sebastián E. Peyrott <pseus7@gmail.com>:
Hi, I'm looking for information on Haskell's viability for heavy integer math. My (very) naive tests show Haskell lagging behind C even
Relevant links :
Benefits of the LLVM code generator (lots of other relevant posts on Dons' blog) http://donsbot.wordpress.com/2010/02/21/smoking-fast-haskell-code-using-ghcs...
Archive of threads about loop unrolling : http://www.haskell.org/pipermail/glasgow-haskell-users/2009-March/thread.htm...
(Also check some of the links in "You might also be interested in:") http://efreedom.com/Question/1-2978979/Haskell-math-performance
David.
I just tried the LLVM code generator from GHC HEAD. I must say I am impressed. Now my simple MD5 is just 1.8 times slower, rather 2.77. Still not as efficient as I would like, but hey... I'll have a look at the generated assembly. 2010/8/7 Sebastián E. Peyrott <pseus7@gmail.com>:
Thanks for the links. I had already seen Don's post, but I have yet to try the LLVM backend. I'll do so as soon as a stable GHC version with it is out.
The Haskell math performance link is interesting. If I'm not mistaken, the OP achieved C levels of performance by switching to Data.Vector and keeping data structures as close to C as possible. That seems reasonable. However, for the example I gave earlier (an MD5 implementation), I don't see a way to use Data.Vector. The algorithm performs repeated operations on 4 32-bit integers and that's it. The implementation in Happstack is as close to C as possible, yet it's still slower. My own too.
I've been trying to read the generated Core and assembly but I don't really have any experience doing that. I can see most fields are unboxed and inlining appears to be working. I see repeated calls to GHC.Prim.narrow32Word# too. In the generated assembly I see many operations with literal '$4294967295'. Could that be the culprit?
I have uploaded the generated Core for the main MD5 computation (RFC1321, section 3.4) here: http://pastebin.com/e51njdcS The actual computation starts at line 1507. Please note this is not from the version in Happstack but rather from my own. You can find RFC1321 here: http://tools.ietf.org/html/rfc1321
If you feel talking about Core and assembly is perhaps not suitable for Haskell-beginners, I'll move this discussion to Haskell-cafe.
Thanks.
2010/8/7 David Virebayre <dav.vire+haskell@gmail.com>:
2010/8/7 Sebastián E. Peyrott <pseus7@gmail.com>:
Hi, I'm looking for information on Haskell's viability for heavy integer math. My (very) naive tests show Haskell lagging behind C even
Relevant links :
Benefits of the LLVM code generator (lots of other relevant posts on Dons' blog) http://donsbot.wordpress.com/2010/02/21/smoking-fast-haskell-code-using-ghcs...
Archive of threads about loop unrolling : http://www.haskell.org/pipermail/glasgow-haskell-users/2009-March/thread.htm...
(Also check some of the links in "You might also be interested in:") http://efreedom.com/Question/1-2978979/Haskell-math-performance
David.
participants (3)
-
Brandon S Allbery KF8NH -
David Virebayre -
Sebastián E. Peyrott