5

在 Haskell 中，我有一个容器，例如：

data Container a = Container { length :: Int, buffer :: Unboxed.Vector (Int,a) }

这个容器是一棵扁平的树。它的访问器通过向量(!)执行二进制 ( log(N)) 搜索，以便找到存储的正确存储桶index。

(!) :: Container a -> Int -> a
container ! index = ... binary search ...

由于连续访问可能在同一个桶中，因此可以通过以下方式进行优化：

if `index` is on the the last accessed bucket, skip the search

棘手的一点是last accessed bucket零件。在 JavaScript 中，我只是不纯地修改了容器对象上的隐藏变量。

function read(index,object){

    var lastBucket = object.__lastBucket;

    // if the last bucket contains index, no need to search
    if (contains(object, lastBucket, index))
        var bucket = lastBucket;

    // if it doesn't
    else {
        // then we search the bucket
        var bucket = searchBucket(index,object);

        // And impurely annotate it on the container, so the
        // next time we access it we could skip the search.
        container.__lastBucket = bucket;
    }

    return object.buffer[bucket].value;
}

由于这只是一种优化，并且结果与所采用的分支无关，因此我相信它不会破坏引用透明度。在 Haskell 中，如何不纯地修改与运行时值相关的状态？

~

我想到了两种可能的解决方案。

  1. 一个全局的、可变的 hashmap 链接指向该lastBucket值的指针，并使用 unsafePerformIO 对其进行写入。但是我需要一种方法来获取对象的运行时指针，或者至少是某种唯一的 id（如何？）。

  2. 在 , 中添加一个额外的字段Container，lastBucket :: Int并以某种方式在 中不纯地修改它(!)，并认为该字段是内部的（因为它显然破坏了引用透明度）。

4

2 回答 2

2

使用解决方案（1），我设法得到了以下设计。首先，__lastAccessedBucket :: IORef Int按照@Xicò 的建议，我在我的数据类型中添加了一个字段：

data Container a = Container { 
    length :: Int, 
    buffer :: V.Vector (Int,a), 
    __lastAccessedBucket :: IORef Int }

然后，我必须更新创建一个新的函数，Container以便使用以下方法创建一个新的 IORef unsafePerformIO：

fromList :: [a] -> Container a
fromList list = unsafePerformIO $ do
    ref <- newIORef 0
    return $ Container (L.length list) buffer ref
    where buffer = V.fromList (prepare list)

最后，我创建了两个新函数，findBucketWithHint一个纯函数，它使用guess 搜索索引的桶（即，您认为它可能在的桶），以及一个unsafeFindBucket函数，它在需要性能时替换纯函数，findBucket始终使用最后访问的存储桶作为提示：

unsafeFindBucket :: Int -> Container a -> Int
unsafeFindBucket findIdx container = unsafePerformIO $ do 
    let lastBucketRef = __lastAccessedBucket contianer
    lastBucket       <- readIORef lastBucketRef
    let newBucket     = findBucketWithHint lastBucket findIdx container
    writeIORef lastBucketRef newBucket
    return $ newBucket

有了这个，unsafeFindBucket从技术上讲，它是一个与原始函数具有相同 API 的纯函数findBucket，但在某些基准测试中要快一个数量级。我不知道这有多安全，也不知道它会在哪里导致错误。线程当然是一个问题。

于 2015-08-26T20:03:36.650 回答
2

（这更像是一个扩展的评论而不是一个答案。）

首先，我建议检查这是否不是过早优化的情况。毕竟，O(log n)并没有那么糟糕。

如果这部分确实对性能至关重要，那么您的意图肯定是有效的。通常的警告unsafePerformIO是“只有在你知道自己在做什么时才使用它”，你显然会这样做，它可以帮助同时使事情变得纯粹和快速。确保您遵循docs 中的所有预防措施，特别是设置正确的编译器标志（您可能想要使用pragma OPTIONS_GHC）。

还要确保IO操作是线程安全的。确保这一点的最简单方法是IORef与atomicModifyIORef.

内部可变状态的缺点是，如果从多个线程访问缓存，如果它们查找不同的元素，缓存的性能将会下降。

一种补救措施是显式线程化更新状态，而不是使用内部可变状态。这显然是您想要避免的，但是如果您的程序使用单子，您可以添加另一个单子层，该层会在内部为您保留状态并将查找操作公开为单子操作。

最后，您可以考虑使用展开树而不是数组。你仍然会有（摊销的）O(log n)复杂度，但它们的最大优势是通过设计它们将频繁访问的元素移动到靠近顶部的位置。因此，如果您要访问大小为k的元素的子集，它们很快就会移到顶部，因此查找操作将只是O(log k)（对于单个重复访问的元素来说是常量）。同样，它们在查找时更新结构，但您可以使用相同的方法unsafePerformIO和原子更新IORef来保持外部接口的纯净。

于 2015-08-27T13:38:50.330 回答