更新:
我的编译命令是ghc -O2 Montecarlo.hs
。我的随机版本是random-1.1
,ghc版本是8.6.4
,我的系统是macOS Big Sur 11.1(英特尔芯片)。我用来测试速度的命令是time ./Montecarlo 10000000
,返回的结果是real 0m17.463s, user 0m17.176s, sys 0m0.162s
。
以下是一个使用Monte Carlo计算的Haskell程序pi
。但是,当输入为1000万时,该程序将运行20秒。以相同逻辑编写的C程序仅花费了0.206秒。为什么会这样,我如何加快速度?谢谢你们。
这是Haskell版本:
import System.Random
import Data.List
import System.Environment
montecarloCircle :: Int -> Double
montecarloCircle x
= 4*fromIntegral
(foldl' (\x y -> if y <= 1 then x+1 else x) 0
$ zipWith (\x y -> (x**2 + y**2))
(take x $ randomRs (-1.0,1) (mkStdGen 1) :: [Double])
(take x $ randomRs (-1.0,1) (mkStdGen 2) :: [Double]) )
/ fromIntegral x
main = do
num <- getArgs
let n = read (num !! 0)
print $ montecarloCircle n
这是C版本:
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#define N 10000000
#define int_t long // the type of N and M
// Rand from 0.0 to 1.0
double rand01()
{
return rand()*1.0/RAND_MAX;
}
int main()
{
srand((unsigned)time(NULL));
double x,y;
int_t M = 0;
for (int_t i = 0;i < N;i++)
{
x = rand01();
y = rand01();
if (x*x+y*y<1) M++;
}
double pi = (double)4*M/N;
printf("%lf\n", pi);
}
可以预料,在数值应用程序中,Haskell代码的运行速度通常比用经典命令式语言(例如C / C ++ / Fortran)编写的等效代码慢2到5倍。但是,Haskell代码慢100倍是非常出乎意料的!
在运行Linux内核5.3,GLIBC 2.28,GCC 8.3,GHC 8.2.2,GHC random-1.1的Intel Celeron N2840 64位CPU上使用较旧的笔记本电脑,可以得到以下时间:
C代码,gcc -O3:950毫秒 Haskell代码,ghc -O3:104秒
因此,实际上,使用这些配置,Haskell代码的运行速度比C代码慢大约100倍。
首先要说明的是,随机数生成之上的π计算算法看起来非常简单,因此运行时可能主要是2 * 1000万伪随机数的生成。此外,我们有充分的理由期望Haskell和C正在使用完全不相关的随机数生成算法。
因此,不必将Haskell与C进行比较,我们可以比较这两种语言正使用的随机数生成算法,以及它们各自的实现。
在C语言中,语言标准没有指定srand()
应该使用哪个算法功能,但是它往往是古老,简单且快速的算法。
另一方面,传统上,在Haskell,我们看到很多关于效率低下的抱怨StdGen
,例如2006年的情况:
https://gitlab.haskell.org/ghc/ghc/-/issues/427
Haskell领先的照明专家之一提到的StdGen
速度可能会提高30倍。
幸运的是,已经有了帮助。这篇最近的博客文章解释了新的Haskell random-1.2软件包如何StdGen
使用一种完全不同的算法(称为splitmix)解决速度不足的问题。
伪随机数生成(PRNG)领域是一个相当活跃的领域。通常,算法会被更新更好的算法所淘汰。出于视角考虑,这是一篇有关该主题的相对较新的(2018)评论论文。
使用另一台性能稍强的计算机,该计算机具有Intel Core i5-4440 3GHz 64位cpu,运行Linux内核5.10,GLIBC 2.32,GCC 10.2,以及至关重要的Haskell软件包random-1.2:
C代码,gcc -O3:164毫秒 Haskell代码,ghc -O3:985毫秒
因此,Haskell现在“慢”了6倍,而不是100倍。
而且,我们仍然必须解决Haskell必须使用x**2+y**2
vs进行获取的不公平性x*x+y*y
,这个细节在使用random-1.1之前并没有多大关系。这给了我们379毫秒!因此,我们回到了通常的2X-5X棒球场,以进行Haskell与C速度的比较。
请注意,如果我们要求Haskell可执行文件在运行统计信息的情况下运行,则会得到以下输出:
$ time q66441802.x + RTS -s -RTS 10000000 3.1415616 925,771,512字节分配在堆中 ... 分配速率每MUT秒2,488,684,937字节 生产率99.3%的总用户,99.3%的总已用 实数0m0,379s的 用户0m0,373s sys 0分0,004秒
因此发现Haskell在此过程中分配了接近1 GB的内存,这有助于了解速度差异。
我们注意到,C代码使用单个随机序列,而Haskell代码使用两个随机序列,其中两个调用mkStdGen
使用数字1和2作为种子。这不仅不公平,而且不正确。设计PRNG算法的应用数学家会非常注意确保任何一个系列具有正确的统计属性,但基本上不能保证不同系列之间可能存在的相关性。甚至没有将种子用作单个全局序列的偏移量,这是闻所未闻的。
在以下代码中已修复此问题,该代码不会显着改变性能:
computeNorms :: [Double] -> [Double]
computeNorms [] = []
computeNorms [x] = []
computeNorms (x:y:xs2) = (x*x + y*y) : (computeNorms xs2)
monteCarloCircle :: Int -> Double
monteCarloCircle nn =
let
randomSeed = 1
gen0 = mkStdGen randomSeed
-- use a single random serie:
uxys = (randomRs (-1.0, 1.0) gen0) :: [Double]
norms = take nn (computeNorms uxys)
insiderCount = length $ filter (<= 1.0) norms
in
(4.0::Double) * ((fromIntegral insiderCount) / (fromIntegral nn))
新的Haskell random-1.2软件包已在最近的SO问题中提到,尽管是在新的monadic接口的上下文中。
假设练习的目的是评估C语言和Haskell语言的相对运行速度,则基本上有两种可能性:
一种是避免完全使用PRNG,因为使用了不同的算法。
另一种方法是通过手动在两种语言中提供一种和相同的算法来控制随机数的生成。例如,可以使用由Pierre L'Ecuyer设计的公开可用的MRG32k3a算法。候选Haskell MRG32k3a在此处实现(截至2021年3月)。留给读者练习。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句