使用向量的风格与性能

本文介绍了使用向量的风格与性能的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 以下是代码： 不给你一个严格的身份识别功能，我认为这是你要去的。事实上，普通的身份识别功能与您所得到的一样严格 - 它会在需要时立即评估其结果。 然而，我偷看了核心GHC为 $ b U.zipWith（+）y 和 U.zipWith（+）y。 id 只有一个很大的区别是我的未经训练的眼睛可以发现。第一个使用简单的 Data.Vector.Generic.zipWith （这里是你的多态性巧合可能发挥作用的地方 - 如果GHC选择了一个通用的 zipWith 它当然会表现得好像代码是多态的一样！），而后者已经将这种单一函数调用分解为几乎90行的状态monad代码和未打包的机器类型。 状态monad代码看起来几乎就像循环和破坏性的更新，你会用命令式语言编写，所以我认为它适合它所运行的机器。如果我不那么着急，我会花更长的眼光来看看它是如何工作的，以及为什么GHC突然决定需要一个紧密的循环。我已经将生成的核心附加到了我自己身上，就像任何其他想要查看的人一样。[2] $ b [ 1]：沿途强制累加器:(这是你已经做的，我误解了代码！） { - ＃LANGUAGE BangPatterns＃ - } iterate'f！x = x：iterate f（fx） [2]：什么核心 U.zipWith（+）y。 id 会被翻译成。 Here's the code:{-# LANGUAGE FlexibleContexts #-}import Data.Intimport qualified Data.Vector.Unboxed as Uimport 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 rf :: U.Vector Int64 -> U.Vector Int64 -> U.Vector Int64f = V.zipWith (+) -- or U.zipWith, it doesn't make a differencemain = 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)I compiled with ghc 7.6.2 and -O2, and it took 1.7 seconds to run. I tried several different versions of f:f x = U.zipWith (+) xf x = (U.zipWith (+) x) . idf x y = U.zipWith (+) x yVersion 1 is the same as the original while versions 2 and 3 run in in under 0.09 seconds (and INLINING f doesn't change anything).I also noticed that if I make f polymorphic (with any of the three signatures above), even with a "fast" definition (i.e. 2 or 3), it slows back down...to exactly 1.7 seconds. This makes me wonder if the original problem is perhaps due to (lack of) type inference, even though I'm explicitly giving the types for the Vector type and element type.I'm also interested in adding integers modulo q:newtype Zq q i = Zq {unZq :: i}As when adding Int64s, if I write a function with every type specified, h :: U.Vector (Zq Q17 Int64) -> U.Vector (Zq Q17 Int64) -> U.Vector (Zq Q17 Int64)I get an order of magnitude better performance than if I leave any polymorphismh :: (Modulus q) => U.Vector (Zq q Int64) -> U.Vector (Zq q Int64) -> U.Vector (Zq q Int64)But I should at least be able to remove the specific phantom type! It should be compiled out, since I'm dealing with a newtype.Here are my questions:Where is the slowdown coming from?What is going on in versions 2 and 3 of f that affect performance in any way? It seems like a bug to me that (what amounts to) coding style can affect performance like this. Are there other examples outside of Vector where partially applying a function or other stylistic choices affect performance?Why does polymorphism slow me down an order of magnitude independent of where the polymorphism is (i.e. in the vector type, in the Num type, both, or phantom type)? I know polymorphism makes code slower, but this is ridiculous. Is there a hack around it? 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.--------------ORIGINAL QUESTION--------------------Here's the code:{-# LANGUAGE FlexibleContexts #-}import Control.DeepSeqimport Data.Intimport qualified Data.Vector.Unboxed as Uimport 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 rf :: U.Vector Int64 -> U.Vector Int64 -> U.Vector Int64f = 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)I compiled with ghc 7.6.2 and -O2, and it took 1.7 seconds to run. I tried several different versions of f:f x = U.zipWith (+) xf x = (U.zipWith (+) x) . U.forcef x = (U.zipWith (+) x) . Control.DeepSeq.force)f x = (U.zipWith (+) x) . (\z -> z `seq` z)f x = (U.zipWith (+) x) . idf x y = U.zipWith (+) x yVersion 1 is the same as the original, version 2 runs in 0.111 seconds, and versions 3-6 run in in under 0.09 seconds (and INLINING f doesn't change anything).So the order-of-magnitude slowdown appears to be due to laziness since force helped, but I'm not sure where the laziness is coming from. Unboxed types aren't allowed to be lazy, right?I tried writing a strict version of iterate, thinking the vector itself must be lazy:{-# INLINE iterate' #-}iterate' :: (NFData a) => (a -> a) -> a -> [a]iterate' f x = x `seq` x : iterate' f (f x)but with the point-free version of f, this didn't help at all.I also noticed something else, which could be just a coincidence and red herring:If I make f polymorphic (with any of the three signatures above), even with a "fast" definition, it slows back down...to exactly 1.7 seconds. This makes me wonder if the original problem is perhaps due to (lack of) type inference, even though everything should be inferred nicely.Here are my questions:Where is the slowdown coming from?Why does composing with force help, but using a strict iterate doesn't? Why is U.force worse than DeepSeq.force? I have no idea what U.force is supposed to do, but it sounds a lot like DeepSeq.force, and seems to have a similar effect.Why does polymorphism slow me down an order of magnitude independent of where the polymorphism is (i.e. in the vector type, in the Num type, or both)?Why are versions 5 and 6, neither of which should have any strictness implications at all, just as fast as a strict function?As @kqr pointed out, the problem doesn't seem to be strictness. So something about the way I write the function is causing the generic zipWith to be used rather than the Unboxed-specific version. Is this just a fluke between GHC and the Vector library, or is there something more general that can be said here? 解决方案 While I don't have the definitive answer you want, there are two things that might help you along.The first thing is that x `seq` x is, both semantically and computationally, the same thing as just x. The wiki says about 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.What the first paragraph says is that writing seq a b doesn't mean that a will magically get evaluated this instant, it means that a will get evaluated as soon as b needs to be evaluated. This might occur later in the program, or maybe never at all. When you view it in that light, it is obvious that seq x x is a redundancy, because all it says is, "evaluate x as soon as x needs to be evaluated." Which of course is what would happen anyway if you had just written x.This has two implications for you:Your "strict" iterate' function isn't really any stricter than it would be without the seq. In fact, I have a hard time imagining how the iterate function could become any stricter than it already is. You can't make the tail of the list strict, because it is infinite. The main thing you can do is force the "accumulator", f x, but doing so doesn't give any significant performance increase on my system.[1]Scratch that. Your strict iterate' does exactly the same thing as my bang pattern version. See the comments.Writing (\z -> z `seq` z) does not give you a strict identity function, which I assume is what you were going for. In fact, the common identity function is as strict as you'll get – it will evaluate its result as soon as it is needed.However, I peeked at the core GHC generates forU.zipWith (+) yandU.zipWith (+) y . idand there is only one big difference that my untrained eye can spot. The first one uses just a plain Data.Vector.Generic.zipWith (here's where your polymorphism coincidence might come into play – if GHC chooses a generic zipWith it will of course perform as if the code was polymorphic!) while the latter has exploded this single function call into almost 90 lines of state monad code and unpacked machine types.The state monad code looks almost like the loops and destructive updates you would write in an imperative language, so I assume it's tailored pretty well to the machine it's running on. If I wasn't in such a hurry, I would take a longer look to see more exactly how it works and why GHC suddenly decided it needed a tight loop. I have attached the generated core as much for myself as anyone else who wants to take a look.[2][1]: Forcing the accumulator along the way: (This is what you already do, I misunderstood the code!){-# LANGUAGE BangPatterns #-}iterate' f !x = x : iterate f (f x)[2]: What core U.zipWith (+) y . id gets translated into. 这篇关于使用向量的风格与性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！