Haskell:涉及大列表的计算中意外的时间复杂性
作为中间结果，我处理的是一个列表A=B，它是长度L的K个列表。计算B元素的时间复杂度由参数M控制，理论上是线性的。理论上，我期望A的计算时间复杂度为O(K*L*M)。但是，事实并非如此，我不明白为什么？
这是一个简单完整的草图程序，展示了我解释过的问题。
import System.Random (randoms, mkStdGen)
import Control.Parallel.Strategies (parMap, rdeepseq)
import Control.DeepSeq (NFData)
import Data.List (transpose)
type Point = (Double, Double)
fmod :: Double -> Double -> Double
fmod a b | a < 0 = b - fmod (abs a) b
| otherwise = if a < b then a
else let q = a / b in b * (q - fromIntegral (floor q))
standardMap :: Double -> Point -> Point
standardMap k (q, p) = (fmod (q + p) (2 * pi), fmod (p + k * sin(q)) (2 * pi))
trajectory :: (Point -> Point) -> Point -> [Point]
trajectory map initial = initial : (trajectory map $ map initial)
justEvery :: Int -> [a] -> [a]
justEvery n (x:xs) = x : (justEvery n $ drop (n-1) xs)
justEvery _ [] = []
subTrace :: Int -> Int -> [a] -> [a]
subTrace n m = take (n + 1) . justEvery m
ensemble :: Int -> [Point]
ensemble n = let qs = randoms (mkStdGen 42)
ps = randoms (mkStdGen 21)
in take n $ zip qs ps
ensembleTrace :: NFData a => (Point -> [Point]) -> (Point -> a) ->
Int -> Int -> [Point] -> [[a]]
ensembleTrace orbitGen observable n m =
parMap rdeepseq ((map observable . subTrace n m) . orbitGen)
main = let k = 100
l = 100
m = 100
orbitGen = trajectory (standardMap 7)
observable (p, q) = p^2 - q^2
initials = ensemble k
mean xs = (sum xs) / (fromIntegral $ length xs)
result = (map mean)
$ transpose
$ ensembleTrace orbitGen observable l m
$ initials
in mapM_ print result我是用
$ ghc -O2 stdmap.hs -threaded并与
$ ./stdmap +RTS -N4 > /dev/null在intel Q6600上，Linux3.6.3-1-ARCH，GHC7.6.1，得到了程序代码中参数K，L，M (k，l，m)的不同集合的结果。
(K=200,L=200,N=200) -> real 0m0.774s
user 0m2.856s
sys 0m0.147s
(K=2000,L=200,M=200) -> real 0m7.409s
user 0m28.102s
sys 0m1.080s
(K=200,L=2000,M=200) -> real 0m7.326s
user 0m27.932s
sys 0m1.020s
(K=200,L=200,M=2000) -> real 0m10.581s
user 0m38.564s
sys 0m3.376s
(K=20000,L=200,M=200) -> real 4m22.156s
user 7m30.007s
sys 0m40.321s
(K=200,L=20000,M=200) -> real 1m16.222s
user 4m45.891s
sys 0m15.812s
(K=200,L=200,M=20000) -> real 8m15.060s
user 23m10.909s
sys 9m24.450s我不太明白这样一个纯粹的缩放的问题可能在哪里。如果我正确理解列表是懒惰的，不应该被构造，因为它们是在头尾方向消耗的？从测量中可以看出，过度的实时消费和过度的系统时间消耗之间存在着相关性，因为过剩将在系统帐户上。但是，如果有内存管理浪费时间，这仍然应该是线性的K，L，M。
帮助!
编辑
我根据Daniel提出的建议对代码进行了修改，这确实解决了M的糟糕缩放问题，正如所指出的那样，通过在弹道中强制严格的评估，我们避免了大块的构造。我理解它背后的性能改进，但我仍然不理解原始代码的糟糕的扩展，因为(如果我正确理解的话) thunk的构造的时空复杂性应该是线性的吗？
此外，我仍然难以理解与K(集合的大小)有关的坏比例。我使用改进的K=8000和K=16000代码执行了两个额外的度量，保持L=200、M=200。扩展到K=8000是预期的，但是对于K=16000来说，它已经异常了。问题似乎在于overflowed SPARKS的数量，K=8000为0，K=16000为7802。这可能反映在糟糕的并发性中，我将其量化为一个商Q = (MUT cpu time) / (MUT real time)，理想情况下它等于CPU的数量。而K= 8000的Q4，K= 16000的Q2。请帮助我理解这个问题的根源和可能的解决办法。
K = 8000:
$ ghc -O2 stmap.hs -threaded -XBangPatterns
$ ./stmap +RTS -s -N4 > /dev/null
56,905,405,184 bytes allocated in the heap
503,501,680 bytes copied during GC
53,781,168 bytes maximum residency (15 sample(s))
6,289,112 bytes maximum slop
151 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 27893 colls, 27893 par 7.85s 1.99s 0.0001s 0.0089s
Gen 1 15 colls, 14 par 1.20s 0.30s 0.0202s 0.0558s
Parallel GC work balance: 23.49% (serial 0%, perfect 100%)
TASKS: 6 (1 bound, 5 peak workers (5 total), using -N4)
SPARKS: 8000 (8000 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)
INIT time 0.00s ( 0.00s elapsed)
MUT time 95.90s ( 24.28s elapsed)
GC time 9.04s ( 2.29s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 104.95s ( 26.58s elapsed)
Alloc rate 593,366,811 bytes per MUT second
Productivity 91.4% of total user, 360.9% of total elapsed
gc_alloc_block_sync: 315819和
K = 16000:
$ ghc -O2 stmap.hs -threaded -XBangPatterns
$ ./stmap +RTS -s -N4 > /dev/null
113,809,786,848 bytes allocated in the heap
1,156,991,152 bytes copied during GC
114,778,896 bytes maximum residency (18 sample(s))
11,124,592 bytes maximum slop
300 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 135521 colls, 135521 par 22.83s 6.59s 0.0000s 0.0190s
Gen 1 18 colls, 17 par 2.72s 0.73s 0.0405s 0.1692s
Parallel GC work balance: 18.05% (serial 0%, perfect 100%)
TASKS: 6 (1 bound, 5 peak workers (5 total), using -N4)
SPARKS: 16000 (8198 converted, 7802 overflowed, 0 dud, 0 GC'd, 0 fizzled)
INIT time 0.00s ( 0.00s elapsed)
MUT time 221.77s (139.78s elapsed)
GC time 25.56s ( 7.32s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 247.34s (147.10s elapsed)
Alloc rate 513,176,874 bytes per MUT second
Productivity 89.7% of total user, 150.8% of total elapsed
gc_alloc_block_sync: 814824回答 2
Stack Overflow用户
发布于 2012-11-09 01:37:15
M.A.D.关于fmod的观点很好，但没有必要向C发出呼叫，我们可以更好地留在Haskell地带(链接线程所涉及的票证是同时修复的)。
fmod :: Double -> Double -> Double
fmod a b | a < 0 = b - fmod (abs a) b
| otherwise = if a < b then a
else let q = a / b in b * (q - fromIntegral (floor q))是否默认类型会导致调用floor :: Double -> Integer (以及由此导致的fromIntegral :: Integer -> Double)。现在，Integer是一个比较复杂的类型，操作缓慢，从Integer到Double的转换也比较复杂。原始代码(参数为k = l = 200和m = 5000)生成了统计数据。
./nstdmap +RTS -s -N2 > /dev/null
60,601,075,392 bytes allocated in the heap
36,832,004,184 bytes copied during GC
2,435,272 bytes maximum residency (13741 sample(s))
887,768 bytes maximum slop
9 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 46734 colls, 46734 par 41.66s 20.87s 0.0004s 0.0058s
Gen 1 13741 colls, 13740 par 23.18s 11.62s 0.0008s 0.0041s
Parallel GC work balance: 60.58% (serial 0%, perfect 100%)
TASKS: 4 (1 bound, 3 peak workers (3 total), using -N2)
SPARKS: 200 (200 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)
INIT time 0.00s ( 0.00s elapsed)
MUT time 34.99s ( 17.60s elapsed)
GC time 64.85s ( 32.49s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 99.84s ( 50.08s elapsed)
Alloc rate 1,732,048,869 bytes per MUT second
Productivity 35.0% of total user, 69.9% of total elapsed在我的机器上(-N2，因为我只有两个物理核)。只需更改代码以使用类型签名floor q :: Int，就可以将其归结为
./nstdmap +RTS -s -N2 > /dev/null
52,105,495,488 bytes allocated in the heap
29,957,007,208 bytes copied during GC
2,440,568 bytes maximum residency (10481 sample(s))
893,224 bytes maximum slop
8 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 36979 colls, 36979 par 32.96s 16.51s 0.0004s 0.0066s
Gen 1 10481 colls, 10480 par 16.65s 8.34s 0.0008s 0.0018s
Parallel GC work balance: 68.64% (serial 0%, perfect 100%)
TASKS: 4 (1 bound, 3 peak workers (3 total), using -N2)
SPARKS: 200 (200 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)
INIT time 0.01s ( 0.01s elapsed)
MUT time 29.78s ( 14.94s elapsed)
GC time 49.61s ( 24.85s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 79.40s ( 39.80s elapsed)
Alloc rate 1,749,864,775 bytes per MUT second
Productivity 37.5% of total user, 74.8% of total elapsed经过的时间减少约20%，穆特时间减少13%。还不错。如果我们查看您通过优化获得的floor代码，我们可以看到原因：
floorDoubleInt :: Double -> Int
floorDoubleInt (D# x) =
case double2Int# x of
n | x <## int2Double# n -> I# (n -# 1#)
| otherwise -> I# n
floorDoubleInteger :: Double -> Integer
floorDoubleInteger (D# x) =
case decodeDoubleInteger x of
(# m, e #)
| e <# 0# ->
case negateInt# e of
s | s ># 52# -> if m < 0 then (-1) else 0
| otherwise ->
case TO64 m of
n -> FROM64 (n `uncheckedIShiftRA64#` s)
| otherwise -> shiftLInteger m efloor :: Double -> Int只使用机器转换，而floor :: Double -> Integer需要昂贵的decodeDoubleInteger和更多的分支。但是在这里调用floor时，我们知道所有涉及到的Double都是非负的，因此floor与truncate相同，后者直接映射到机器转换double2Int#，所以让我们尝试一下，而不是floor
INIT time 0.00s ( 0.00s elapsed)
MUT time 29.29s ( 14.70s elapsed)
GC time 49.17s ( 24.62s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 78.45s ( 39.32s elapsed)非常小的减少(不出所料，fmod并不是真正的瓶颈)。为了进行比较，请调用C：
INIT time 0.01s ( 0.01s elapsed)
MUT time 31.46s ( 15.78s elapsed)
GC time 54.05s ( 27.06s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 85.52s ( 42.85s elapsed)速度有点慢(毫不奇怪，您可以在调用C采取的时间内执行一些原始操作)。
但那不是大鱼游的地方。糟糕的是，只选择轨迹中的每个m-th元素都会导致大块，导致大量的分配，并且在时间到来时需要很长时间来评估。因此，让我们消除这个漏洞，并严格规定轨迹：
{-# LANGUAGE BangPatterns #-}
trajectory :: (Point -> Point) -> Point -> [Point]
trajectory map !initial@(!a,!b) = initial : (trajectory map $ map initial)这大大减少了分配和GC时间，因此也减少了MUT时间：
INIT time 0.00s ( 0.00s elapsed)
MUT time 21.83s ( 10.95s elapsed)
GC time 0.72s ( 0.36s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 22.55s ( 11.31s elapsed)使用原始的fmod，
INIT time 0.00s ( 0.00s elapsed)
MUT time 18.26s ( 9.18s elapsed)
GC time 0.58s ( 0.29s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 18.84s ( 9.47s elapsed)使用floor q :: Int，并且在测量精度范围内，truncate q :: Int的时间相同(truncate的分配数字要低一点)。
问题似乎在于溢出火花的数量，K=8000为0，K=16000为7802。这可能反映在错误的并发性上。
是的(据我所知，这里更正确的术语是并行性而不是并发性)，但是有一个火花池，当火花池满了时，在下一个线程轮到它时，就不会对任何线程的火花进行评估，然后在父线程没有并行的情况下进行计算。在这种情况下，这意味着经过一个初始的并行阶段，计算回到顺序。
火花池的大小显然约为8K (2^13)。
如果您通过顶部观察CPU负载，您将看到从(close to 100%)*(number of cores)下降到一个低得多的值过一段时间(对我来说，-N2是100%，-N4是130%)。
解决办法是避免火花过多，让每个火花做更多的工作。用快速和肮脏的修改
ensembleTrace orbitGen observable n m =
withStrategy (parListChunk 25 rdeepseq) . map ((map observable . subTrace n m) . orbitGen)我回到了-N2的200%，几乎整个运行和良好的生产力，
INIT time 0.00s ( 0.00s elapsed)
MUT time 57.42s ( 29.02s elapsed)
GC time 5.34s ( 2.69s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 62.76s ( 31.71s elapsed)
Alloc rate 1,982,155,167 bytes per MUT second
Productivity 91.5% of total user, 181.1% of total elapsed对于-N4，它也很好(即使在挂钟上稍微快一点--不是很多，因为所有的线程基本上都是一样的，而且我只有两个物理内核)，
INIT time 0.00s ( 0.00s elapsed)
MUT time 99.17s ( 26.31s elapsed)
GC time 16.18s ( 4.80s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 115.36s ( 31.12s elapsed)
Alloc rate 1,147,619,609 bytes per MUT second
Productivity 86.0% of total user, 318.7% of total elapsed从现在起火花池不会溢出。
正确的解决方法是将块的大小作为一个参数，根据轨迹和可用核的数量计算，这样火花的数量就不会超过池的大小。
Stack Overflow用户
发布于 2012-11-08 23:41:19
在做了一些快速分析之后，我发现这些是一系列的违反者：
ghc --make -O2 MainNonOpt.hs -threaded -prof -auto-all -caf-all -fforce-recomp
./MainNonOpt +RTS -N4 -p > /dev/null
>>>
COST CENTRE MODULE %time %alloc
fmod Main 46.3 33.3
standardMap Main 28.5 0.0
trajectory Main 23.8 66.6令人惊讶的是，fmod有大量的分配，考虑到它主要是一个数值函数。因此，下一步是注释fmod，看看问题在哪里：
fmod :: Double -> Double -> Double
fmod a b | a < 0 = {-# SCC "negbranch" #-} b - fmod (abs a) b
| otherwise = {-# SCC "posbranch" #-} if a < b then a
else let q = {-# SCC "division" #-} a / b in {-# SCC "expression" #-} b * (q - {-# SCC "floor" #-} fromIntegral (floor q))这使我们：
ghc --make -O2 MainNonOpt.hs -threaded -prof -caf-all -fforce-recomp
./MainNonOpt +RTS -N4 -p > /dev/null
COST CENTRE MODULE %time %alloc
MAIN MAIN 61.5 70.0
posbranch Main 16.6 0.0
floor Main 14.9 30.0
expression Main 4.5 0.0
negbranch Main 1.9 0.0因此，使用floor的位是导致问题的原因之一。环顾四周之后，我们发现Prelude并没有尽其所能地实现一些双重RealFrac函数(参见这里)，这可能会导致一些装箱/取消装箱。
因此，通过遵循链接中的建议，我使用了一个修改后的楼层版本，这也使得对fromIntegral的调用变得不必要：
floor' :: Double -> Double
floor' x = c_floor x
{-# INLINE floor' #-}
foreign import ccall unsafe "math.h floor"
c_floor :: Double -> Double
fmod :: Double -> Double -> Double
fmod a b | a < 0 = {-# SCC "negbranch" #-} b - fmod (abs a) b
| otherwise = {-# SCC "posbranch" #-} if a < b then a
else let q = {-# SCC "division" #-} a / b in {-# SCC "expression" #-} b * (q - ({-# SCC "floor" #-} floor' q))编辑：正如Daniel所指出的，不需要内联C代码来提高性能。类似的Haskell函数已经存在。无论如何，我都会留下答案，供进一步参考。
这确实有区别。在我的机器上，对于k=l=200，M=5000是非优化版本和优化版本的编号：
非优化：
real 0m20.635s
user 1m17.321s
sys 0m4.980s优化：
real 0m14.858s
user 0m55.271s
sys 0m3.815strajectory函数可能有类似的问题，您可以像上面使用的那样使用分析来指出问题。
在Haskell中进行分析的一个很好的起点可以在真实世界的本章中找到。
https://stackoverflow.com/questions/13293587
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号