0

当第一次搜索我的代码慢的地方时，我真的很惊讶，没想到会这样，幂（或乘法）可以更快，所以移位代码中的某些东西真的很慢。

（整数）供电代码

{-# OPTIONS_GHC -O2 #-}

import System.Environment(getArgs)

main = do
  [a,b] <- getArgs
  let c = ( read a::Integer ) ^ ( read b::Int )
  print ( mod c 2 )

移位示例代码

{-# OPTIONS_GHC -O2 #-}

import Data.Bits
import System.Environment(getArgs)

main = do
  [a,b] <- getArgs
  let c = shift ( read a::Integer ) ( read b::Int )
  print( mod c 2 )

我在旧的和最新的haskell上运行：

c:\ghc\ghc-6.10.4\bin>cmd /v:on /c "echo !TIME! & pow.exe 33 40000000 & echo !TIME!"
1:24:29,02
1
1:24:41,48
-- 12.46 秒。用于供电

c:\ghc\ghc-6.10.4\bin>cmd /v:on /c "echo !TIME! & shift.exe 3 200000000 & echo !TIME!"
1:27:08,76
0
1:27:22,06
-- 13.30 秒。换班

c:\ghc\ghc-7.6.3\bin>cmd /v:on /c "echo !TIME! & pow.exe 33 40000000 & echo !TIME!"
2:19:29,39
1
2:19:37,06
-- 7.67 秒。用于供电（因此供电有所改善）

c:\ghc\ghc-7.6.3\bin>cmd /v:on /c "echo !TIME! & shift.exe 3 200000000 & echo !TIME!"
2:20:49,61
0
2:20:49,69
-- 0.08 秒。换档（这意味着加速大约 150 倍）

甚至（这里是 20 亿位移位）：
c:\ghc\ghc-7.6.3\bin>cmd /v:on /c "echo !TIME! & shift.exe 3 2000000000 & echo !TIME!"
3:07:22,05
0
3:07:22,56
-- 0.51 秒。

在运行中，数字相当大，运行时间很长。在第一个代码中我们计算 33^40000000 (mod 2)，在第二个代码中计算 3*2^200000000 (mod 2)。mod 操作（或其他东西）必须看到非 0 时间（因为在这种情况下，haskell 不会计算它）。如前所述，供电速度更快，还要注意在这种情况下 33^40000000 大于 3*2^200000000。此外，在内存使用方面，您可以看到 3^200000000 也是在最新的 haskell 上计算的，因此这里没有深度优化技巧。

是否有可能在这个旧的 haskell 版本中获得加速？我对双向移动（大整数）感兴趣，我们可以假设我们以 64 位的倍数（或 63 或 32 或 31；haskell 上整数表示中单词的大小）的倍数进行移动，所以有没有环绕。

尝试计算 2^n 然后执行乘法（或除法）以进行移位，但它并没有在旧的 haskell 上加速。

使用 -v 标志运行编译器的更新
开始打印：（我也可以发布其余的）格拉斯哥 Haskell 编译器，版本 6.10.4，用于 Haskell 98，由 GHC 版本 6.10.1 引导的阶段 2 使用包配置文件：C :\ghc\ghc-6.10.4\package.conf 隐藏包 base-3.0.3.1 以避免与更高版本的 base-4.1.0.0 连接包 ghc-prim 映射到 ghc-prim-0.1.0.0 连接包整数映射到 integer-0.1.0.1 嵌入包 base 映射到 base-4.1.0.0 嵌入包 rts 映射到 rts-1.0 嵌入包 haskell98 映射到 haskell98-1.0.1.0 嵌入包 syb 映射到syb-0.1.0.1 嵌入包 template-haskell 映射到 template-haskell-2.3.0.1 嵌入包 dph-seq 映射到 dph-seq-0.3 嵌入包 dph-par 映射到 dph-par-0.3 Hsc静态标志：-static

4

1 回答 1

2

我的猜测是旧版本的 GHC 没有专门的Integer班次实现，因此回退到默认的 Haskell 实现，请参阅Data.Bits：

shift x i | i >= 0    = x * 2^i
          | otherwise = x `div` 2^(-i)

但是，当前版本具有用于左移和右移的基于 GMP 的primops ，请参阅包中的模块shiftLInteger和shiftRInteger函数。GHC.Integer.Typeinteger-gmp

于 2013-09-02T12:54:29.357 回答