haskell - 使用矢量的风格与性能

Question

这是代码:

{-# 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 秒(而且 INLINING f 不会改变任何内容)。

我还注意到，如果我制作 f多态(具有上述三个签名中的任何一个)，即使使用“快速”定义(即 2 或 3)，它也会减慢……精确到 1.7 秒。这让我想知道原始问题是否可能是由于(缺乏)类型推断造成的，即使我明确给出了 Vector 类型和元素类型的类型。

我也有兴趣添加整数模 q :

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

如添加 Int64 s，如果我用指定的每种类型编写一个函数，

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 版发生了什么以任何方式影响性能？这对我来说似乎是一个错误，(相当于)编码风格会影响这样的性能。 Vector 之外是否还有其他示例，其中部分应用函数或其他风格选择会影响性能？

为什么多态性使我慢了一个数量级，而与多态性的位置无关(即在向量类型中，在 Num 类型中，两者或幻像类型中)？我知道多态会使代码变慢，但这很 absurd 。它周围有黑客吗？

EDIT 1

I filed a issue with the Vector library page. I found a GHC issue relating to this problem.

EDIT2

I rewrote the question after gaining some insight from @kqr's answer. Below is the original for reference.

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

这是代码:

{-# 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

版本 1 与原始版本相同，版本 2 运行时间为 0.111 秒，版本 3-6 运行时间不到 0.09 秒( INLINING f 不会改变任何内容)。

因此，数量级的放缓似乎是由于 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使用而不是未装箱的特定版本。这只是 GHC 和 Vector 库之间的侥幸，还是这里可以说一些更一般的东西？

Answer 1

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

首先是x `seq` x在语义和计算上都与 x 相同.维基说关于 seq :

A common misconception regarding seq is that seq x "evaluates" x. Well, sort of. seq doesn't evaluate anything just by virtue of existing in the source file, all it does is introduce an artificial data dependency of one value on another: when the result of seq is evaluated, the first argument must also (sort of; see below) be evaluated.

As an example, suppose x :: Integer, then seq x b behaves essentially like if x == 0 then b else b – unconditionally equal to b, but forcing x along the way. In particular, the expression x `seq` x is completely redundant, and always has exactly the same effect as just writing x.

第一段说的是写 seq a b并不意味着 a会在这一瞬间神奇地得到评估，这意味着 a将尽快得到评估 b需要评估。这可能会在程序的后期发生，也可能永远不会发生。当你从那个角度看它时，很明显 seq x x是一种冗余，因为它所说的只是“在需要评估 x 时立即评估 x”。如果你刚刚写了 x，那当然会发生什么。 .

这对你有两个影响:

你的“严”iterate'功能实际上并不比没有 seq 时更严格.事实上，我很难想象 iterate函数可能变得比现在更严格。您不能使列表的尾部严格，因为它是无限的。您可以做的主要事情是强制“累加器”，f x ，但这样做不会显着提高我的系统的性能。 [1]

抓那个。您的严格iterate'与我的 bang 模式版本完全相同。看评论。

写作 (\z -> z `seq` z)没有给你一个严格的身份函数，我认为这就是你想要的。事实上，通用标识函数与您将得到的一样严格——它会在需要时立即评估其结果。

但是，我查看了 GHC 生成的核心

U.zipWith (+) y

和

U.zipWith (+) y . id

我未经训练的眼睛只能发现一个很大的不同。第一个只使用一个普通的 Data.Vector.Generic.zipWith (这就是你的多态巧合可能发挥作用的地方——如果 GHC 选择一个泛型 zipWith，它当然会像代码是多态的一样执行!)而后者将这个单一的函数调用分解成近 90 行状态 monad 代码和未打包的机器类型。

状态 monad 代码看起来几乎就像你用命令式语言编写的循环和破坏性更新，所以我认为它非常适合运行它的机器。如果我不那么着急，我会花更长时间看看它是如何工作的，以及为什么 GHC 突然决定它需要一个紧密的循环。我已经为自己和其他想要查看的人一样附加了生成的核心。 [2]

[1]:沿途强制累加器:(这是你已经在做的，我误解了代码!)

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

[2]: What core U.zipWith (+) y . id gets translated into.