不,但您可以使用更好的功能。我不是在谈论V.map (+64)
,这会让事情变得更快,但约nTimes
。我们有三个候选人已经做nTimes
做:
{-# INLINE nTimesFoldr #-}
nTimesFoldr :: Int -> (a -> a) -> a -> a
nTimesFoldr n f x = foldr (.) id (replicate n f) $ x
{-# INLINE nTimesIterate #-}
nTimesIterate :: Int -> (a -> a) -> a -> a
nTimesIterate n f x = iterate f x !! n
{-# INLINE nTimesTail #-}
nTimesTail :: Int -> (a -> a) -> a -> a
nTimesTail n f = go n
where
{-# INLINE go #-}
go n x | n <= 0 = x
go n x = go (n - 1) (f x)
所有版本大约需要8秒,相比40秒钟内你的版本需要。顺便说一下,Joachim的版本也需要8秒。请注意,iterate
版本在我的系统上占用更多内存。尽管GHC有unroll plugin,但在过去的五年里它没有更新(它使用自定义的说明)。
根本没有展开?
但是,在我们绝望之前,GHC实际上试图将所有内容都嵌入其中?让我们用nTimesTail
和nTimes 1
:
module Main where
import qualified Data.Vector.Unboxed as V
{-# INLINE incAll #-}
incAll :: V.Vector Int -> V.Vector Int
incAll = V.map (+ 1)
{-# INLINE nTimes #-}
nTimes :: Int -> (a -> a) -> a -> a
nTimes n f = go n
where
{-# INLINE go #-}
go n x | n <= 0 = x
go n x = go (n - 1) (f x)
main :: IO()
main = do
let size = 100000000 :: Int
let array = V.replicate size 0 :: V.Vector Int
print $ V.sum (nTimes 1 incAll array)
$ stack ghc --package vector -- -O2 -ddump-simpl -dsuppress-all SO.hs
main2 =
case (runSTRep main3) `cast` ...
of _ { Vector ww1_s9vw ww2_s9vx ww3_s9vy ->
case $wgo 1 ww1_s9vw ww2_s9vx ww3_s9vy
of _ { (# ww5_s9w3, ww6_s9w4, ww7_s9w5 #) ->
我们可以停在那儿。 $wgo
是上面定义的go
。即使使用1
GHC也不会展开循环。这是令人不安的,因为1
是一个常数。
拯救模板
但是,唉,它并不是全部。如果C++程序员能够对编译时常量进行以下操作,那么我们应该如此,对吧?
template <int N>
struct Call{
template <class F, class T>
static T call(F f, T && t){
return f(Call<N-1>::call(f,std::forward<T>(t)));
}
};
template <>
struct Call<0>{
template <class F, class T>
static T call(F f, T && t){
return t;
}
};
果然,我们可以与TemplateHaskell*:
-- Times.sh
{-# LANGUAGE TemplateHaskell #-}
module Times where
import Control.Monad (when)
import Language.Haskell.TH
nTimesTH :: Int -> Q Exp
nTimesTH n = do
f <- newName "f"
x <- newName "x"
when (n <= 0) (reportWarning "nTimesTH: argument non-positive")
let go k | k <= 0 = VarE x
go k = AppE (VarE f) (go (k - 1))
return $ LamE [VarP f,VarP x] (go n)
是什么nTimesTH
办?它会创建一个新函数,其中第一个名称f
将应用于第二个名称x
,总计n
次。 n
现在需要一个编译时间常数,它适合我们,因为循环展开,才可能与编译时间常数:
$(nTimesTH 0) = \f x -> x
$(nTimesTH 1) = \f x -> f x
$(nTimesTH 2) = \f x -> f (f x)
$(nTimesTH 3) = \f x -> f (f (f x))
...
是否行得通?它快吗?与nTimes
相比有多快?让我们尝试另一个main
为:
-- SO.hs
{-# LANGUAGE TemplateHaskell #-}
module Main where
import Times
import qualified Data.Vector.Unboxed as V
{-# INLINE incAll #-}
incAll :: V.Vector Int -> V.Vector Int
incAll = V.map (+ 1)
{-# INLINE nTimes #-}
nTimes :: Int -> (a -> a) -> a -> a
nTimes n f = go n
where
{-# INLINE go #-}
go n x | n <= 0 = x
go n x = go (n - 1) (f x)
main :: IO()
main = do
let size = 100000000 :: Int
let array = V.replicate size 0 :: V.Vector Int
let vTH = V.sum ($(nTimesTH 64) incAll array)
let vNorm = V.sum (nTimes 64 incAll array)
print $ vTH == vNorm
stack ghc --package vector -- -O2 SO.hs && SO.exe +RTS -t
True
<<ghc: 52000056768 bytes, 66 GCs, 400034700/800026736 avg/max bytes residency (2 samples), 1527M in use, 0.000 INIT (0.000 elapsed), 8.875 MUT (9.119 elapsed), 0.000 GC (0.094 elapsed) :ghc>>
它得到正确的结果。它有多快?让我们再次用另一个main
:
main :: IO()
main = do
let size = 100000000 :: Int
let array = V.replicate size 0 :: V.Vector Int
print $ V.sum ($(nTimesTH 64) incAll array)
800,048,112 bytes allocated in the heap
4,352 bytes copied during GC
42,664 bytes maximum residency (1 sample(s))
18,776 bytes maximum slop
764 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 1 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.000s 0.049s 0.0488s 0.0488s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.172s ( 0.221s elapsed)
GC time 0.000s ( 0.049s elapsed)
EXIT time 0.000s ( 0.049s elapsed)
Total time 0.188s ( 0.319s elapsed)
%GC time 0.0% (15.3% elapsed)
Alloc rate 4,654,825,378 bytes per MUT second
Productivity 100.0% of total user, 58.7% of total elapsed
好,比较,为8秒。因此,对于TL; DR:如果您有编译时常量,并且您想基于该常量创建和/或修改您的代码,请考虑模板Haskell。
*请注意,这是我写的第一个模板Haskell代码。小心使用。不要使用太大的n
,否则你最终可能会遇到混乱的功能。
您可以使用Template Haskell来引入语法来扩展重复的应用程序。 –
@JoachimBreitner刚刚完成了这个。必须学习模板Haskell。仍在测试我的答案,但似乎要快得多(类似于其他问题)。 – Zeta