如何不纯地修改与对象关联的状态

在Haskell中，我有一个这样的容器:

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

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

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

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

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中，如何不纯粹地修改与运行时值相关的状态?

我已经考虑了两种可能的解决方案。

一个全局的，可变的哈希映射，链接指针到lastBucket值，并使用unsafePerformIO对其进行写操作。但是我需要一种方法来获得对象的运行时指针，或者至少是某种类型的唯一id(如何?)。
在Container, lastBucket :: Int中添加一个额外的字段，并且在(!)中以某种方式不纯粹地修改它，并认为该字段是内部的(因为它明显破坏了引用透明度)

使用解决方案(1)，我设法得到以下设计。首先，我向我的数据类型添加了一个__lastAccessedBucket :: IORef Int字段，如@Xicò:

所示

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

然后，我必须更新创建新Container的函数，以便使用unsafePerformIO创建新的IORef:

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，一个纯函数，它用猜测搜索索引的桶(即，您认为它可能在哪里的桶)，以及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在技术上是一个与原始findBucket函数具有相同API的纯函数，但在某些基准测试中速度要快一个数量级。我不知道这有多安全，在哪里会导致bug。线程当然是一个问题。

^{(这是一个扩展的评论而不是一个答案)}

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

如果这部分确实对性能至关重要，那么您的意图绝对是有效的。通常对unsafePerformIO的警告是"只有在你知道自己在做什么的情况下才使用它"，你显然知道，它可以帮助你同时使事情变得纯净和快速。请确保遵循文档中的所有注意事项，特别是设置正确的编译器标志(您可能希望使用OPTIONS_GHC pragma)。

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

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

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

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

相关内容

最新更新

热门标签：