4

它是这个问题的延续。由于向量库似乎没有可融合的 O(1) 更新函数，我想知道是否可以编写一个不涉及unsafeFreeze和的可融合 O(1) 更新函数unsafeThaw。我猜它会使用vector stream表示 - 我不熟悉如何使用stream-unstream因此，这个问题。原因是这将使我们能够在向量上编写一个缓存友好的更新函数，其中只有一个狭窄的向量区域被修改，因此，我们不想遍历整个向量来处理那个狭窄的区域（并且此操作在每个函数调用中可能发生数十亿次 - 因此，保持开销非常低的动机）。转换函数如map处理整个向量 - 所以它们会太慢。

我有一个我想做的玩具示例，但是upd下面的函数使用unsafeThaw和unsafeFreeze- 它似乎没有在核心中被优化，并且也打破了不进一步使用缓冲区的承诺：

module Main where
import Data.Vector.Unboxed as U
import Data.Vector.Unboxed.Mutable as MU
import Control.Monad.ST

upd :: Vector Int -> Int -> Int -> Vector Int
upd v i x = runST $ do
          v' <- U.unsafeThaw v
          MU.write v' i x
          U.unsafeFreeze v'

sum :: Vector Int -> Int
sum = U.sum . (\x -> upd x 0 73) . (\x -> upd x 1 61)

main = print $ Main.sum $ U.fromList [1..3]

我知道如何使用STVector. 如果您想知道为什么要使用这种替代方法，我想尝试这种使用纯向量的方法，以检查GHC使用可熔纯向量流编写时特定算法的转换有何不同（当然，使用单子操作）。

当使用 编写算法时STVector，它似乎不像我希望的那样迭代（我猜当存在大量可变性时，GHC 优化器更难发现循环）。所以，我正在研究这种替代方法，看看我可以在那里得到一个更好的循环。

4

2 回答 2

4

您编写的upd功能看起来不正确，更不用说可熔断了。Fusion 是一种库级别的优化，需要您使用某些原语编写代码。在这种情况下，您想要的不仅仅是融合，而是可以通过批量更新操作（如和）轻松实现的回收。这些操作将融合在一起，甚至在大部分时间都发生在原地。 //update

如果您真的想编写自己的基于破坏性更新的代码，请不要使用unsafeThaw--usemodify

于 2013-06-08T21:36:11.847 回答
3

任何函数都是可熔更新函数；您似乎正试图摆脱向量包试图让您使用的编程模型

module Main where
import Data.Vector.Unboxed as U

change :: Int -> Int -> Int
change 0 n = 73
change 1 n = 61
change m n = n

myfun2 = U.sum . U.imap change .  U.enumFromStepN 1 1 
main = print $ myfun2 30000000

- 这不会创建任何向量，更不用说“更新”它们，如果你研究核心，你会看到。

于 2013-06-08T16:41:12.350 回答