21

我将使用以下示例程序演示该问题

{-# LANGUAGE BangPatterns #-}

data Point = Point !Double !Double

fmod :: Double -> Double -> Double
fmod a b | a < 0     = b - fmod (abs a) b 
         | otherwise = if a < b then a 
                       else let q = a / b 
                            in b * (q - fromIntegral (floor q :: Int))

standardMap :: Double -> Point -> Point
standardMap k (Point q p) = 
   Point (fmod (q + p) (2 * pi)) (fmod (p + k * sin(q)) (2 * pi))

iterate' gen !p = p : (iterate' gen $ gen p)

main = putStrLn 
     . show 
     . (\(Point a b) -> a + b) 
     . head . drop 100000000 
     . iterate' (standardMap k) $ (Point 0.15 0.25)
    where k = (cos (pi/3)) - (sin (pi/3))

这standardMap k是参数化函数，k=(cos (pi/3))-(sin (pi/3))是一个参数。ghc -O3 -fllvm如果我用我的机器上的执行时间来编译这个程序42s，但是，如果我k以这种形式编写，0.5 - (sin (pi/3))则执行时间等于21s，如果我编写k = 0.5 - 0.5 * (sqrt 3)它只需要12s.

结论是k在每次调用 时都会重新评估standardMap k。

为什么这没有优化？

Archlinux 上的 PS 编译器 ghc 7.6.3

编辑

对于那些关心standardMap这里的奇怪属性的人来说，这是一个更简单、更直观的例子，它展示了同样的问题

{-# LANGUAGE BangPatterns #-}

data Point = Point !Double !Double

rotate :: Double -> Point -> Point
rotate k (Point q p) = 
   Point ((cos k) * q - (sin k) * p) ((sin k) * q + (cos k) * p)

iterate' gen !p = p : (iterate' gen $ gen p)

main = putStrLn 
     . show 
     . (\(Point a b) -> a + b) 
     . head . drop 100000000 
     . iterate' (rotate k) $ (Point 0.15 0.25)
   where --k = (cos (pi/3)) - (sin (pi/3))
         k = 0.5 - 0.5 * (sqrt 3)

编辑

在我问这个问题之前，我已经尝试过k严格，就像唐建议的那样，但ghc -O3我没有看到有什么不同。如果程序是用ghc -O2. 我错过了这一点，因为我没有尝试所有可能的标志组合与程序的所有可能版本。

那么影响这种情况的-O3和有什么区别呢？-O2

我应该更喜欢-O2一般吗？

编辑

正如 Mike Hartl 和其他人所观察到的，如果rotate k更改为rotate $ k或standardMap kinto standardMap $ k，则性能会有所提高，尽管这不是最好的（Don 的解决方案）。为什么？

4

2 回答 2

16

与往常一样，检查核心。

使用 ghc -O2，k 被内联到循环体中，它作为顶级函数浮出：

Main.main7 :: Main.Point -> Main.Point
Main.main7 =
  \ (ds_dAa :: Main.Point) ->
    case ds_dAa of _ { Main.Point q_alG p_alH ->
    case q_alG of _ { GHC.Types.D# x_s1bt ->
    case p_alH of _ { GHC.Types.D# y_s1bw ->
    case Main.$wfmod (GHC.Prim.+## x_s1bt y_s1bw) 6.283185307179586
    of ww_s1bi { __DEFAULT ->
    case Main.$wfmod
           (GHC.Prim.+##
              y_s1bw
              (GHC.Prim.*##
                 (GHC.Prim.-##
                    (GHC.Prim.cosDouble# 1.0471975511965976)
                    (GHC.Prim.sinDouble# 1.0471975511965976))
                 (GHC.Prim.sinDouble# x_s1bt)))
           6.283185307179586
    of ww1_X1bZ { __DEFAULT ->
    Main.Point (GHC.Types.D# ww_s1bi) (GHC.Types.D# ww1_X1bZ)

表示 sin 和 cos 调用不会在编译时进行评估。结果是会发生更多的数学运算：

$ time ./A
3.1430515093368085
real    0m15.590s

如果严格要求，至少不会每次都重新计算：

main = putStrLn
     . show
     . (\(Point a b) -> a + b)
     . head . drop 100000000
     . iterate' (standardMap k) $ (Point 0.15 0.25)

    where
      k :: Double
      !k = (cos (pi/3)) - (sin (pi/3))

导致：

ipv_sEq =
                      GHC.Prim.-##
                        (GHC.Prim.cosDouble# 1.0471975511965976)
                        (GHC.Prim.sinDouble# 1.0471975511965976) } in

以及运行时间：

$ time ./A
6.283185307179588
real    0m7.859s

我认为现在已经足够好了。我还将解包编译指示添加到 Point 类型。

如果您想推断不同代码安排下的数值性能，您必须检查核心。

使用您修改后的示例。它遇到同样的问题。k是内联的rotate。GHC 认为它真的很便宜，而在这个基准测试中它更贵。

天真地，ghc-7.2.3 -O2

$ time ./A
0.1470480616244365

real    0m22.897s

并k在每次调用旋转时进行评估。

严格：k一种强制不共享的方法。

$ time ./A
0.14704806100839019

real    0m2.360s

在 Point 构造函数上使用 UNPACK 编译指示：

$ time ./A
0.14704806100839019

real    0m1.860s
于 2013-09-06T11:08:01.033 回答
5

我不认为这是重复评价。

首先，我切换到“do”符号并在“k”的定义上使用了“let”，我认为这应该有所帮助。不 - 仍然很慢。

然后我添加了一个跟踪调用 - 只被评估一次。甚至检查了快速变体实际上是在产生一个 Double。

然后我打印出两种变体。初始值存在细微差别。

调整“慢”变体的值使其具有相同的速度。我不知道你的算法是做什么用的——它会对起始值非常敏感吗？

import Debug.Trace (trace)

...

main = do
    -- is -0.3660254037844386
    let k0 = (0.5 - 0.5 * (sqrt 3))::Double
    -- was -0.3660254037844385
    let k1 = (cos (pi/3)) - (trace "x" (sin (pi/3))) + 0.0000000000000001;
    putStrLn (show k0)
    putStrLn (show k1)
    putStrLn
     . show
     . (\(Point a b) -> a + b)
     . head . drop 100000000
     . iterate' (standardMap k1) $ (Point 0.15 0.25)

编辑：这是带有数字文字的版本。它为我显示了 23 秒和 7 秒的运行时间。我编译了两个不同版本的代码，以确保我没有做一些愚蠢的事情，比如不重新编译。

main = do
    -- -0.3660254037844386
    -- -0.3660254037844385
    let k2 = -0.3660254037844385
    putStrLn
     . show
     . (\(Point a b) -> a + b)
     . head . drop 100000000
     . iterate' (standardMap k2) $ (Point 0.15 0.25)

EDIT2：我不知道如何从 ghc 获取操作码，但比较两个 .o 文件的 hexdump 显示它们相差一个字节 - 大概是文字。所以它不能是运行时。

EDIT3：尝试打开分析，这让我更加困惑。除非我遗漏了一些东西，否则唯一的区别是调用次数fmod（准确地说是 fmod.q）的小差异。

“5”配置文件是用于恒定结尾“5”，与“6”相同。

        Fri Sep  6 12:37 2013 Time and Allocation Profiling Report  (Final)

           constant-timings-5 +RTS -p -RTS

        total time  =       38.34 secs   (38343 ticks @ 1000 us, 1 processor)
        total alloc = 12,000,105,184 bytes  (excludes profiling overheads)

COST CENTRE MODULE  %time %alloc

standardMap Main     71.0    0.0
iterate'    Main     21.2   93.3
fmod        Main      6.3    6.7


                                                          individual     inherited
COST CENTRE     MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN            MAIN                     50           0    0.0    0.0   100.0  100.0                                  
 main           Main                    101           0    0.0    0.0     0.0    0.0                                  
 CAF:main1      Main                     98           0    0.0    0.0     0.0    0.0                                  
  main          Main                    100           1    0.0    0.0     0.0    0.0                                  
 CAF:main2      Main                     97           0    0.0    0.0     1.0    0.0                                  
  main          Main                    102           0    1.0    0.0     1.0    0.0                                  
   main.\       Main                    110           1    0.0    0.0     0.0    0.0                                  
 CAF:main3      Main                     96           0    0.0    0.0    99.0  100.0                                  
  main          Main                    103           0    0.0    0.0    99.0  100.0                                  
   iterate'     Main                    104   100000001   21.2   93.3    99.0  100.0                                  
    standardMap Main                    105   100000000   71.0    0.0    77.9    6.7                                  
     fmod       Main                    106   200000001    6.3    6.7     6.9    6.7                                                                                                
      fmod.q    Main                    109    49999750    0.6    0.0     0.6    0.0                                                                                                
 CAF:main_k     Main                     95           0    0.0    0.0     0.0    0.0                                                                                                
  main          Main                    107           0    0.0    0.0     0.0    0.0                                                                                                
   main.k2      Main                    108           1    0.0    0.0     0.0    0.0                                                                                                
 CAF            GHC.IO.Handle.FD         93           0    0.0    0.0     0.0    0.0                                                                                                
 CAF            GHC.Conc.Signal          90           0    0.0    0.0     0.0    0.0                                                                                                
 CAF            GHC.Float                89           0    0.0    0.0     0.0    0.0                                                                                                
 CAF            GHC.IO.Encoding          82           0    0.0    0.0     0.0    0.0                                                                                                
 CAF            GHC.IO.Encoding.Iconv    66           0    0.0    0.0     0.0    0.0 


        Fri Sep  6 12:38 2013 Time and Allocation Profiling Report  (Final)

           constant-timings-6 +RTS -p -RTS

        total time  =       22.17 secs   (22167 ticks @ 1000 us, 1 processor)
        total alloc = 11,999,947,752 bytes  (excludes profiling overheads)

COST CENTRE MODULE  %time %alloc

standardMap Main     48.4    0.0
iterate'    Main     38.2   93.3
fmod        Main     10.9    6.7
main        Main      1.4    0.0
fmod.q      Main      1.0    0.0


                                                          individual     inherited
COST CENTRE     MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN            MAIN                     50           0    0.0    0.0   100.0  100.0
 main           Main                    101           0    0.0    0.0     0.0    0.0
 CAF:main1      Main                     98           0    0.0    0.0     0.0    0.0
  main          Main                    100           1    0.0    0.0     0.0    0.0
 CAF:main2      Main                     97           0    0.0    0.0     1.4    0.0
  main          Main                    102           0    1.4    0.0     1.4    0.0
   main.\       Main                    110           1    0.0    0.0     0.0    0.0
 CAF:main3      Main                     96           0    0.0    0.0    98.6  100.0
  main          Main                    103           0    0.0    0.0    98.6  100.0
   iterate'     Main                    104   100000001   38.2   93.3    98.6  100.0
    standardMap Main                    105   100000000   48.4    0.0    60.4    6.7
     fmod       Main                    106   200000001   10.9    6.7    12.0    6.7
      fmod.q    Main                    109    49989901    1.0    0.0     1.0    0.0
 CAF:main_k     Main                     95           0    0.0    0.0     0.0    0.0
  main          Main                    107           0    0.0    0.0     0.0    0.0
   main.k2      Main                    108           1    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Handle.FD         93           0    0.0    0.0     0.0    0.0
 CAF            GHC.Conc.Signal          90           0    0.0    0.0     0.0    0.0
 CAF            GHC.Float                89           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding          82           0    0.0    0.0     0.0    0.0
 CAF            GHC.IO.Encoding.Iconv    66           0    0.0    0.0     0.0    0.0

EDIT4：下面的链接是两个操作码转储（感谢@Tom Ellis）。虽然我看不懂它们，但它们似乎具有相同的“形状”。据推测，长随机字符字符串是内部标识符。我刚刚重新编译了两者，-O2 -fforce-recomp并且时间差异是真实的。 https://gist.github.com/anonymous/6462797

于 2013-09-06T11:00:13.883 回答