C vs Haskell Collatz猜想速度比较 [英] C vs Haskell Collatz conjecture speed comparison
问题描述
最近，我想我会再次尝试一些Haskell，虽然它对于通用简单（就计算而言）任务而言仍然很棒，但它似乎无法将C的速度与类似问题Collatz猜想。我已阅读：
与欧拉项目进行速度比较：C vs Python vs Erlang vs Haskell
你的Haskell代码的一个大问题是你正在分割，而你不在C版本中。
是的，你写了 n％ 2 和 n / 2 ，但编译器用位移和位移来代替它。 GHC遗憾的是还没有被教导要这样做。
如果你自己做替换的话
模块Main其中
导入System.Environment（getArgs）
导入Data.Int（Int32，Int64）
导入Data.Bits
main :: IO（）
main = do
arg< - getArgs
print $ maxCol 0（read（head arg）:: Int64）
col :: Int64 - > Int32
col x = col'x 0
col':: Int64 - > Int32 - > Int32
col'1 n = n
col'x n
| x。& ;. 1 == 0 = col'（x`shiftR` 1）（n + 1）
|否则= col'（3 * x + 1）（n + 1）
maxCol :: Int32 - > Int64 - > Int32
maxCol maxS 2 = maxS
maxCol maxS n
| s> maxS = maxCol s（n - 1）
|否则= maxCol maxS（n - 1）
其中s = col n
位GHC你可以得到相同的速度（0.35s与C的0.32s在我的盒子上限制为1000000）。如果使用LLVM后端进行编译，则甚至不需要按位逐个替换％2 和 / 2 LLVM为你做了这些工作（但是它为你的原始Haskell源代码生成了0.4s的较慢代码，令人惊讶的是 - 通常，LLVM并不比在循环优化时的本地代码生成器更糟糕。）
对于32位的GHC，您无法获得可比较的速度，因为对于这些，64位整数的基本操作通过C调用实现 - 对于快速的64位操作从来没有足够的需求在32位系统上它们被实现为primops;很少有人从事GHC工作，他们花时间去做其他更重要的事情。
TL; DR：Haskell代码可以快速编写，简单的维护只用于计算上简单的任务，并且在性能至关重要时会失去这种特性？
这取决于。您必须了解GHC根据什么类型的输入生成的代码类型，并且您必须避免一些性能陷阱。通过一些练习，可以很容易地获得2倍于此类任务的gcc -O3的速度。
My first real programming experience was with Haskell. For my ad-hoc needs I required a tool that was easy to learn, quick to code and simple to maintain and I can say it did the job nicely.
However, at one point the scale of my tasks became much bigger and I thought that C might suit them better and it did. Maybe I was not skilled enough in terms of [any] programming, but I was not able to make Haskell as speed-efficient as C, even though I heard that proper Haskell is capable of similar performance.
Recently, I thought I would try some Haskell once more, and while it's still great for generic simple (in terms of computation) tasks, it doesn't seem to be able to match C's speed with problems like Collatz conjecture. I have read:
Speed comparison with Project Euler: C vs Python vs Erlang vs Haskell
GHC Optimization: Collatz conjecture
collatz-list implementation using haskell
But from what I see, simple optimization methods, including:
- choosing "tighter" types, like Int64 instead of Integer
- turning GHC optimizations on
- using simple optimization techniques like avoiding unneccessary computation or simpler functions
still don't make Haskell code even close to almost identical (in terms of methodology) C code for really big numbers. The only thing that seems to make its performance comparable to C's [for big-scale problems] is using optimization methods that make the code a long, horrendous monadic hell, which goes against the principles that Haskell (and I) value so much.
Here's the C version:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int32_t col(int64_t n);
int main(int argc, char **argv)
{
int64_t n = atoi(argv[1]), i;
int32_t s, max;
for(i = 2, max = 0; i <= n; ++i)
{
s = col(i);
if(s > max) max = s;
}
printf("%d\n", max);
return 0;
}
int32_t col(int64_t n)
{
int32_t s;
for(s = 0; ; ++s)
{
if(n == 1) break;
n = n % 2 ? 3 * n + 1 : n / 2;
}
return s;
}
and the Haskell version:
module Main where
import System.Environment (getArgs)
import Data.Int (Int32, Int64)
main :: IO ()
main = do
arg <- getArgs
print $ maxCol 0 (read (head arg) :: Int64)
col :: Int64 -> Int32
col x = col' x 0
col' :: Int64 -> Int32 -> Int32
col' 1 n = n
col' x n
| rem x 2 == 0 = col' (quot x 2) (n + 1)
| otherwise = col' (3 * x + 1) (n + 1)
maxCol :: Int32 -> Int64 -> Int32
maxCol maxS 2 = maxS
maxCol maxS n
| s > maxS = maxCol s (n - 1)
| otherwise = maxCol maxS (n - 1)
where s = col n
TL;DR: Is Haskell code quick to write and simple to maintain only for computationally simple tasks and loses this characteristic when performance is crucial?
The big problem with your Haskell code is that you are dividing, which you don't in the C version.
Yes, you wrote n % 2 and n / 2, but the compiler replaces that with shifts and bitwise and. GHC has unfortunately not yet been taught to do that.
If you do the substitution yourself
module Main where
import System.Environment (getArgs)
import Data.Int (Int32, Int64)
import Data.Bits
main :: IO ()
main = do
arg <- getArgs
print $ maxCol 0 (read (head arg) :: Int64)
col :: Int64 -> Int32
col x = col' x 0
col' :: Int64 -> Int32 -> Int32
col' 1 n = n
col' x n
| x .&. 1 == 0 = col' (x `shiftR` 1) (n + 1)
| otherwise = col' (3 * x + 1) (n + 1)
maxCol :: Int32 -> Int64 -> Int32
maxCol maxS 2 = maxS
maxCol maxS n
| s > maxS = maxCol s (n - 1)
| otherwise = maxCol maxS (n - 1)
where s = col n
with a 64-bit GHC you get comparable speed (0.35s vs C's 0.32s on my box for a limit of 1000000). If you compile using the LLVM backend, you don't even need to replace the % 2 and / 2 with bitwise operations, LLVM does that for you (but it produces slower code, 0.4s, for your original Haskell source, surprisingly - normally, LLVM is not worse than the native code generator at loop optimisation).
With a 32-bit GHC, you won't get comparable speed, since with those, the primitive operations on 64-bit integers are implemented through C calls - there never was enough demand for fast 64-bit operations on 32-bit systems for them to be implemented as primops; the few people working on GHC spent their time doing other, more important, things.
TL;DR: Is Haskell code quick to write and simple to maintain only for computationally simple tasks and loses this characteristic when performance is crucial?
That depends. You must have some idea of what sort of code GHC generates from what sort of input, and you must avoid some performance traps. With a bit of practice, it is quite easy to get within say 2× the speed of gcc -O3 for such tasks.
这篇关于C vs Haskell Collatz猜想速度比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
