performance - 如何在Haskell中改善zipWith的性能

我已经编写了用于使用Data.Clustering.Hierarchical进行集群的代码，但是速度很慢。我尝试分析和更改一些代码，但是我不知道为什么zipWith花费这么多时间？ （即使我将列表更改为矢量。）import Data.Clustering.Hierarchicalimport qualified Data.Vector.Primitive as DVimport System.Randomimport Control.Monadmain = do vectorList <- genTestdata let cluster = dendrogram SingleLinkage vectorList getVectorDistance putStrLn $ show clustergenZero x | x<5 = x |otherwise = 0genVector::IO (DV.Vector Int)genVector = do listRandom <- mapM (\x -> randomRIO (1,30) ) [1..20] let intOut = DV.fromList $ map genZero listRandom return intOutgenTestdata = do r <- sequence $ map (\x -> liftM (\y -> (x,y)) genVector) [1..1000] return rgetExp2 v1 v2 = d*d where d = v1 - v2getExp v1 v2 | v1 == v2 = 0 | otherwise = getExp2 v1 v2tfoldl d = DV.foldl1' (+) dchangeDataType:: Int -> DoublechangeDataType d = fromIntegral dgetVectorDistance::(a,DV.Vector Int)->(a, DV.Vector Int )->DoublegetVectorDistance 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 -RTStotal time = 8.43 secs (8433 ticks @ 1000 us, 1 processor)total alloc = 1,614,252,224 bytes (excludes profiling overheads)COST CENTRE MODULE %time %allocgetVectorDistance.dat Main 49.4 37.8 <------tfoldl Main 5.7 0.0getExp Main 4.5 0.0getExp2 Main 0.5 1.5 最佳答案 采纳我意见中的建议，以下是运行相同代码的时间：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_cluster101000real 0m0.127suser 0m0.120ssys 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_cluster101000real 0m2.937suser 0m2.920ssys 0m0.000s因此，概要分析的构建速度要慢25倍左右，这是相当可观的开销。在这一点上，我猜测您的程序运行缓慢的原因是您正在构建用于分析的程序。如果未分析的构建也太慢，则可能需要使用一些更复杂的分析技术。当然，由于您提供的代码无法编译，因此这在某种程度上是推测性的，因此我不得不填补一些空白。编辑：明确地说，我的立场是添加SCC注释（无论是手动还是自动）限制了ghc可以执行的优化。应用的范围越宽松，已分析的代码与未分析的代码之间的差异就越大。这可能会导致配置文件产生误导，因为在配置文件代码中显示为瓶颈的功能可能会少一些。我认为这就是这里正在发生的事情。OP非常合理地询问，如果分析结果如此失真，则如何找到瓶颈。我希望在此示例中，DV.zipWith实际上是一个瓶颈，因为它是唯一可以完成重要工作的功能（请参见下面的wrt测试生成代码），但是手动检查内核（通过-ddump-simpl -ddump-to-file -dsuppress-coercions编译产生）显示产生一个不错的无框循环，中间向量完全融合了。我怀疑如果不采取英勇措施就可以大大改善这一状况。 （见注2）通常，使用概要分析的最佳方法是从顶部开始然后向下钻取。您可以在顶层附近手动添加一些getVectorDistance批注，或使用最好仅为几个关键的顶层模块指定的SCC来大致了解。从那里您可以进行进一步的挖掘，方法是将注释添加到更多模块，手动添加更多的-fprof-auto-exported注释，或者，如果您感到幸运，可以切换到SCC。不幸的是，除非您还添加了-fprof-auto语句，否则仅使用-fprof-auto-exported对该示例无济于事。一种替代方法是使用其他配置文件方法。您可以使用例如ghc-events-analyze配置文件代码。这涉及手动添加一些跟踪语句并对事件日志进行后处理，但是通常对编译器优化的影响要小得多。在纯代码中，有时很难弄清楚放置语句的位置，以便对其进行正确的评估，我的chronograph包可以处理此问题（它尚不支持ghc-events-analyze格式，但我将添加它不久）。我希望这是完整代码的精简示例。希望这些技术之一将有助于找到可以更轻松地改进的瓶颈。注意1：如果与完整程序类似，则几乎可以加快数据生成代码的速度。 module Main (main, getVectorDistance)非常慢，请使用mwc-random或mersenne-random。我对使用System.Random也有些怀疑，但可能会混淆掉它。注意2：使用DV.fromList编译时，核心效果不佳。代替在两个向量上进行无框循环，首先创建一个新向量，然后循环遍历该新向量以计算总和。因此，您有额外的分配，额外的内存压力以及两次遍历而不是一次遍历。这就是为什么配置文件版本明显慢的原因，也是我认为配置文件具有误导性的原因：-prof -fprof-auto的时间大大膨胀了。关于performance - 如何在Haskell中改善zipWith的性能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25255917/