样式 vs 性能：使用向量

Question

样式 vs 性能：使用向量

14

这里是代码：

{-# LANGUAGE FlexibleContexts #-}

import Data.Int
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Generic as V

{-# NOINLINE f #-} -- Note the 'NO'
--f :: (Num r, V.Vector v r) => v r -> v r -> v r
--f :: (V.Vector v Int64) => v Int64 -> v Int64 -> v Int64
--f :: (U.Unbox r, Num r) => U.Vector r -> U.Vector r -> U.Vector r
f :: U.Vector Int64 -> U.Vector Int64 -> U.Vector Int64
f = V.zipWith (+) -- or U.zipWith, it doesn't make a difference

main = do
    let iters = 100
        dim = 221184
        y = U.replicate dim 0 :: U.Vector Int64
    let ans = iterate ((f y)) y !! iters
    putStr $ (show $ U.sum ans)

我使用了ghc 7.6.2和-O2编译，运行时间为1.7秒。

我尝试了几个不同的版本：f：

f x = U.zipWith (+) x
f x = (U.zipWith (+) x) . id
f x y = U.zipWith (+) x y

版本1与原始版本相同，而版本2和3的运行时间少于0.09秒（对f进行内联也没有改变任何内容）。

我还注意到，如果我使f成为多态函数（使用上述三种签名之一），即使使用“快速”定义（即2或3），它的运行时间也会变慢...恰好为1.7秒。这让我想知道是否由于（缺乏）类型推断而导致了原始问题，尽管我明确给出了Vector类型和元素类型的类型。

我还有兴趣添加模q的整数：

newtype Zq q i = Zq {unZq :: i}

就像添加Int64一样，如果我编写一个指定每个类型的函数：

h :: U.Vector (Zq Q17 Int64) -> U.Vector (Zq Q17 Int64) -> U.Vector (Zq Q17 Int64)

如果我不使用任何多态，我的性能会提高一个数量级。

h :: (Modulus q) => U.Vector (Zq q Int64) -> U.Vector (Zq q Int64) -> U.Vector (Zq q Int64)

但我至少应该能够删除特定的幻影类型！它应该被编译掉，因为我正在处理一个newtype。

以下是我的问题：

减速来自哪里？
f的第2版和第3版中发生了什么会以任何方式影响性能？对我来说，这似乎是一个bug，因为（相当于）编码风格会影响性能。除了Vector之外，还有其他例子可以部分应用函数或其他风格选择影响性能吗？
为什么多态会使我减速一个数量级，而与多态所在的位置无关（即在向量类型、Num类型、两者或幻影类型中）？我知道多态会使代码变慢，但这太离谱了。有没有绕过它的方法？

编辑1

我在Vector库页面上提交了问题。我找到了一个GHC问题与此问题相关。

编辑2

在从@kqr的答案中获得一些见解后，我重写了问题。以下是原始内容供参考。

--------------原始问题--------------------

这是代码：

{-# LANGUAGE FlexibleContexts #-}

import Control.DeepSeq
import Data.Int
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Generic as V

{-# NOINLINE f #-} -- Note the 'NO'
--f :: (Num r, V.Vector v r) => v r -> v r -> v r
--f :: (V.Vector v Int64) => v Int64 -> v Int64 -> v Int64
--f :: (U.Unbox r, Num r) => U.Vector r -> U.Vector r -> U.Vector r
f :: U.Vector Int64 -> U.Vector Int64 -> U.Vector Int64
f = V.zipWith (+)

main = do
    let iters = 100
        dim = 221184
        y = U.replicate dim 0 :: U.Vector Int64
    let ans = iterate ((f y)) y !! iters
    putStr $ (show $ U.sum ans)

我使用 ghc 7.6.2 和 -O2 进行了编译，运行时间为1.7秒。

我尝试了几个不同版本的 f:

f x = U.zipWith (+) x
f x = (U.zipWith (+) x) . U.force
f x = (U.zipWith (+) x) . Control.DeepSeq.force)
f x = (U.zipWith (+) x) . (\z -> z `seq` z)
f x = (U.zipWith (+) x) . id
f x y = U.zipWith (+) x y

第一种版本与原始版本相同，第二个版本运行时间为0.111秒，版本3-6在不到0.09秒内运行（并且对 f 进行 INLINING 没有任何改变）。

因此，数量级的减速似乎是由于惰性引起的，因为 force 帮助了，但我不确定惰性来自哪里。非装箱类型不允许是惰性的，对吗？

我尝试编写了一个 iterate 的严格版本，认为向量本身必须是惰性的:

{-# INLINE iterate' #-}
iterate' :: (NFData a) => (a -> a) -> a -> [a]
iterate' f x =  x `seq` x : iterate' f (f x)

但是使用点无关的版本 f 并没有起到帮助的作用。

我还注意到另外一件事情，可能只是巧合：如果我将 f 泛型化（使用上述三个签名之一），即使使用“快速”定义，也会变慢...恰好为1.7秒。这让我想知道原始问题是否由于（缺少）类型推断而导致，尽管所有东西都应该被很好地推断出来。

以下是我的问题：

减速来自哪里？
为什么与 force 组合有帮助，而使用严格的 iterate 却没有帮助？
为什么 U.force 比 DeepSeq.force 更差？我不知道 U.force 应该做什么，但它听起来很像 DeepSeq.force，并且似乎具有类似的效果。
为什么泛型化会使我变慢一个数量级，而不受泛型化的影响（即在向量类型、Num 类型或两者中的任何一个中）？
为什么版本5和6，它们都不应该具有任何严格性影响，与严格函数一样快？

正如 @kqr 指出的那样，问题似乎并不是严格性。因此，我编写函数的方式导致使用通用的 zipWith 而不是特定于 Unboxed 的版本。这只是 GHC 和 Vector 库之间的偶然事件，还是有更普遍的东西可以在这里说吗？

- crockeea

3是一个有点奇怪的问题，不是吗？你可以在这里阅读关于Vector.force的内容（http://hackage.haskell.org/package/vector-0.10.9.1/docs/Data-Vector-Unboxed.html），它与`DeepSeq.force`不同。 - ollanta

它在这里做了某些有用的事情。它是什么？ - crockeea

其实不完全是这样，O2 在那里时会做某些事情，但也在 id 存在时做同样的事情。我的意思是第三个问题有误导性，因为 Vector.force 和 DeepSeq.force 是两个无关的函数，除了当应用于向量时它们的名称和类型签名相同。 - ollanta

@Eric 您所谓的“保持多态”是指“这样您可以独立地研究性能影响”吗？那很有趣，如果您能深入探究，我相信您会学到很多知识，但由于您正在积极破坏向量的重写规则，这对实际用途并不怎么有帮助。关于分析性能，您通常需要手动添加成本中心（例如使用此链接中介绍的 scc-pragma），或者稍微调整代码以获得所需的详细信息。在这里查看核心和正在触发的规则可能是最有用的。祝好运！ - jberryman

1

为什么你说跨多个模块的函数不能被内联呢？这肯定是不正确的。 INLINE 命令的主要功能之一就是导出接口文件中的展开代码，因为这对于内联是必需的。当然，在一些情况下函数无法被内联，但模块边界并不是障碍。 - John L

显示剩余8条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kqr · Accepted Answer

虽然我没有你想要的明确答案，但有两件事可能会对你有所帮助。

第一件事是，x `seq` x在语义和计算上与只写x是相同的。维基百科关于seq的说明如下：

“关于seq的一个普遍误解是，seq x会“评估”x。嗯，有点像。seq并不仅仅因为存在于源文件中就会评估任何东西，它只是引入了一个人工数据依赖，使一个值依赖于另一个值：当seq的结果被评估时，第一个参数也必须（有点像；见下文）被评估。”

举个例子，假设x :: Integer，那么seq x b的行为基本上像if x == 0 then b else b——无条件等于b，但同时强制求值x。特别地，表达式x `seq` x是完全冗余的，始终具有与只写x完全相同的效果。

第一段话的意思是，写seq a b并不意味着a会在此时此刻立即被评估，它意味着a将在需要评估b时被评估。这可能发生在程序的后面，也可能根本不会发生。从这个角度来看，很明显seq x x是多余的，因为它只是说：“尽快评估x当x需要评估时。”当然，如果你只是写了x，那么这就是会发生的。

这对你有两个影响：

你的“严格”iterate'函数并没有比没有seq更严格。实际上，我很难想象iterate函数如何能变得比现在更严格。你不能使列表的尾部变得严格，因为它是无限的。你唯一能做的就是强制求值“累加器”f x，但这样做在我的系统上并没有给出任何显著的性能提升。

取消划掉。你的严格iterate'与我的感叹号模式版本完全相同。请参见评论。
写(\z -> z `seq` z)并不能给你一个严格的恒等函数，我想这就是你想要的。实际上，常见的恒等函数就是你能得到的最严格的函数——它将在需要时立即评估其结果。

然而，我看了一下GHC为之生成的核心代码。

U.zipWith (+) y

并且

U.zipWith (+) y . id

我的未经训练的眼睛只能发现一个重大区别。第一个使用了简单的（这里可能涉及到你的多态巧合——如果GHC选择了通用的，那么它当然会表现得像代码是多态的！）而后者将这个单一的函数调用分解成了近90行的状态单子代码和解包机器类型。

状态单子代码看起来几乎像你在命令式语言中编写的循环和破坏性更新，所以我认为它非常适合运行的机器。如果我不是这么匆忙，我会花更长时间去看看它是如何工作的，以及为什么GHC突然决定需要一个紧密的循环。我附上生成的核心文件，不仅为了自己，也为了任何想要查看的人[2]。

[1]: 沿途强制执行累加器：（这就是你已经做的事情，我误解了代码！）

{-# LANGUAGE BangPatterns #-}
iterate' f !x = x : iterate f (f x)

[2]: 核心代码 U.zipWith (+) y . id 的翻译。