[Haskell-cafe] weak references & caches

[Thomas Conway]

Hi All,

I'm hacking some (external) B-Tree code, and amongst the numerous
interesting problems I've come up against[*], is to do with managing
which pages/nodes are in memory and which are not.

We use TVars to point from one (in-memory version of a) page to
another, so we have a type like the following:

data Node
    = Leaf [(Key,Value)]
    | Node NodePtr [(Key,NodePtr)]

type NodePtr = TVar (Maybe Address, Maybe Node)

type Address = Integer

Addresses are just page numbers or file offsets, or similar.

NodePtr is the interesting bit - the following table summarizes what
the combination of values mean:

explain (Just addr, Nothing) = "An external node we have not read in yet"
explain (Nothing, Just node) = "A new node for which we have not yet
allocated a page"
explain (Just addr, Just node) = "A node we've read in"
explain (Nothing, Nothing) = "Emit nasal daemons"

Now, we want a cache to hang on to nodes that we've read in to hold
them in memory, to save repeatedly reading them off disk
unnecessarily. But more than that, we want to make sure that when we
create a NodePtr pointing to a particular Address, that all references
to this particular address go through the same NodePtr, otherwise in a
concurrent situation we could well end up with two copies of the page
in memory, both recieving updates leading to havoc. At the same time,
we'd like to be able to evict pages according to some policy (the
Oracle hot-list cold-list cache is attractive, if implemented
carefully).

So one scheme that comes to mind is to keep a table mapping addresses
to (Weak NodePtr). When we ask for a node, first we consult the cache
(if we have one) and get the NodePtr right back. If the addressed node
is not in the cache then we check the table to see if there is/was a
known NodePtr for that address. If there is none then we can allocate
a new one and stick it in the table, and if it is there then we return
it.  This is also nice because we can attach finalizers to the (Weak
NodePtr)s to write them out if dirty.

So the question is, is there a simpler scheme (though this one isn't
tooooo bad), and more importantly, is this likely to be horribly slow?
How efficient is dereferencing a weak reference, and what is the
likely impact on performance of having 10^3-10^5 weak references
around?

cheers,
Tom
[*]Film at 11. I'm planning to write it all up, maybe for a
conference, maybe just for the Monad Reader, or something.