使用向量的样式与性能

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:

1. f x = U.zipWith (+) x
2. f x = (U.zipWith (+) x) . id
3. 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}

当添加Int64s时,如果我编写一个指定每种类型的函数,

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.

这是我的问题:

1. 减速从何而来？
2. 版本2和版本3中的f内容会以任何方式影响性能？对我来说似乎是一个错误(编码风格)会影响这样的性能.在Vector之外是否存在其他部分应用函数或其他样式选择会影响性能的示例？
3. 为什么多态性会使我减慢一个数量级,而与多态性的位置无关(即在向量类型,Num类型,两者或幻像类型中)？我知道多态性会使代码变慢,但这很荒谬.周围有黑客吗？

编辑1

我向Vector库页面提交了一个问题.我发现了与此问题有关的GHC问题.

EDIT2

我从@ 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:

1. f x = U.zipWith (+) x
2. f x = (U.zipWith (+) x) . U.force
3. f x = (U.zipWith (+) x) . Control.DeepSeq.force)
4. f x = (U.zipWith (+) x) . (\z -> z `seq` z)
5. f x = (U.zipWith (+) x) . id
6. 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秒.这让我想知道原始问题是否可能是由于(缺乏)类型推断造成的,即使所有内容都应该很好地推断出来.

这是我的问题:

1. 减速从何而来？
2. 为什么写作有force帮助,但使用严格iterate不？
3. 为什么U.force比这更糟DeepSeq.force？我不知道U.force应该做什么,但听起来很像DeepSeq.force,似乎有类似的效果.
4. 为什么多态性会使我减慢一个数量级,而与多态性的位置无关(即在向量类型,Num类型或两者中)？
5. 为什么版本5和版本6都没有任何严格意义,就像严格的函数一样快？

正如@kqr指出的那样,问题似乎并不严格.所以我编写函数的方式zipWith是使用泛型而不是Unboxed特定的版本.这只是GHC和Vector库之间的侥幸,还是有更普遍的东西可以说？

Answer 1

虽然我没有你想要的明确答案,但有两件事可能对你有帮助.

首先,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.

这有两个含义:

1. 你的"严格" iterate'功能并没有比没有它时更严格的功能seq.事实上,我很难想象这个iterate功能如何变得比现在更严格.你不能严格限制列表的尾部,因为它是无限的.你可以做的主要是强制"累加器",f x但这样做并没有给我的系统带来任何显着的性能提升.[1]

   抓一点.你的严格iterate'与我的爆炸模式版本完全相同.查看评论.

2. 写作(\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]:什么核心U.zipWith (+) y . id被翻译成.