performance - 如何提高 zipWith 在 Haskell 中的性能

Question

我已经用 Data.Clustering.Hierarchical 写了一个 Clustering 的代码，但是它很慢。

我尝试分析和更改一些代码，但我不知道为什么 zipWith 花费这么多时间？ (即使我将列表更改为矢量。)

import Data.Clustering.Hierarchical
import qualified Data.Vector.Primitive as DV
import System.Random
import Control.Monad


main = do
    vectorList <- genTestdata
    let cluster = dendrogram SingleLinkage vectorList getVectorDistance  
    putStrLn $ show cluster

genZero x 
    | x<5 = x
    |otherwise = 0

genVector::IO (DV.Vector Int)
genVector = do
    listRandom <- mapM (\x -> randomRIO (1,30) ) [1..20]
    let intOut = DV.fromList $ map genZero listRandom
    return intOut

genTestdata = do 
    r <- sequence  $ map (\x -> liftM (\y -> (x,y)) genVector) [1..1000]
    return r

getExp2 v1 v2 = d*d
    where
        d = v1 - v2

getExp v1 v2
    | v1 == v2 = 0
    | otherwise = getExp2 v1 v2

tfoldl  d = DV.foldl1' (+) d

changeDataType:: Int -> Double
changeDataType d = fromIntegral d

getVectorDistance::(a,DV.Vector Int)->(a, DV.Vector Int )->Double
getVectorDistance v1 v2 = fromIntegral $ tfoldl dat
    where
        l1 = snd v1
        l2 = snd v2
        dat = DV.zipWith getExp l1 l2

要构建它，请使用:ghc -prof -fprof-auto -rtsopts -O2 log_cluster.hs

使用 log_cluster.exe +RTS -p 运行

我机器上的分析结果如下——注意 getVectorDistance.dat 的结果:

> log_cluster.exe +RTS -p -RTS

total time  =        8.43 secs   (8433 ticks @ 1000 us, 1 processor)
total alloc = 1,614,252,224 bytes  (excludes profiling overheads)

COST CENTRE            MODULE  %time %alloc
getVectorDistance.dat  Main     49.4   37.8  <------
tfoldl                 Main      5.7    0.0
getExp                 Main      4.5    0.0
getExp2                Main      0.5    1.5

Answer 1

采纳我评论中的建议，以下是运行相同代码的时间安排:

user:~/explorations$ ghc -O2 log_cluster.hs -rtsopts
[1 of 1] Compiling Main             ( log_cluster.hs, log_cluster.o )
Linking log_cluster ...
user:~/explorations$ time ./log_cluster
101000

real    0m0.127s
user    0m0.120s
sys     0m0.000s

当使用分析构建时:

user:~/explorations$ ghc -prof -fprof-auto -O2 log_cluster.hs -rtsopts
[1 of 1] Compiling Main             ( log_cluster.hs, log_cluster.o )
Linking log_cluster ...
user:~/explorations$ time ./log_cluster
101000

real    0m2.937s
user    0m2.920s
sys     0m0.000s

因此，经过分析的构建速度慢了大约 25 倍，这是一个相当大的开销。

在这一点上，我猜你的程序运行缓慢的原因是你构建它是为了分析。如果非分析构建也太慢，您可能需要使用一些更复杂的分析技术。

当然这有点推测，因为您提供的代码无法编译，所以我不得不填补一些空白。

编辑:明确地说，我的立场是添加 SCC 注释(无论是手动还是自动)限制了 ghc 可以执行的优化。它们应用得越自由，剖析代码和未剖析代码之间的差异就越大。这可能会产生误导性的配置文件，因为在配置文件代码中显示为瓶颈的函数可能不会如此。我认为这就是这里发生的事情。

如果分析结果如此扭曲，OP 非常合理地询问如何找到瓶颈。我希望对于这个例子，DV.zipWith 实际上是一个瓶颈，因为它是唯一做重要工作的函数(见下面的测试生成代码)，但是手动检查核心(通过编译生成-ddump-simpl -ddump-to-file -dsuppress-coercions) 显示 getVectorDistance 产生了一个很好的未装箱循环，中间向量完全融合了。我怀疑如果不采取英勇措施，它能否得到显着改善。 (见注2)

一般来说，使用分析的最佳方法是从顶部开始向下钻取。您可以在顶层附近手动添加一些 SCC 注释，或者使用 -fprof-auto-exported，最好只指定一些靠近顶层的关键模块，以获得一个粗略的想法。从那里您可以进一步深入，通过向更多模块添加注释，手动添加更多 SCC 注释，或者，如果您幸运的话，切换到 -fprof-auto。不幸的是，仅使用 -fprof-auto-exported 对该示例没有太大帮助，除非您还添加了 module Main (main, getVectorDistance) 语句。

另一种方法是使用不同的分析方法。你可以使用例如ghc-events-analyze分析您的代码。这涉及手动添加一些跟踪语句并对事件日志进行后处理，但它通常对编译器优化的干扰要小得多。在纯代码中，有时很难弄清楚在哪里放置语句以便正确评估它们，我的 chronograph包可以处理这个(它还不支持 ghc-events-analyze 格式，但我会尽快添加)。

我希望这是完整代码的缩减示例。希望这些技术之一将有助于找到可以更容易改进的瓶颈。

注意 1:如果数据生成代码与您的完整程序相似，则几乎可以肯定它会被加速。 System.Random 是出了名的慢，使用 mwc-random或 mersenne-random .我也对使用 DV.fromList 有点怀疑，但它可能会被融合掉。

注意 2:当使用 -prof -fprof-auto 编译时，核心不是那么好。不是对两个向量进行拆箱循环，而是首先创建一个新向量，然后循环遍历该新向量以计算总和。所以你有额外的分配、额外的内存压力和两次遍历而不是一次。这就是配置文件版本明显变慢的原因，也是我认为配置文件具有误导性的原因:DV.zipWith 的时间显着膨胀。