[Haskell-cafe] STM, IO and b-trees
midfield at gmail.com
Tue Aug 21 16:34:07 EDT 2007
thanks for the detailed response!
On 8/20/07, Thomas Conway <drtomc at gmail.com> wrote:
> something like
> type PagePtr t = TVar (Address, Maybe t)
> data Node = Node (PagePtr Node) [(Key,PagePtr Node)] | Leaf [(Key,Data)]
so you're storing the data in the pages?
> Yes, except you might want to be clever about flushing dirty pages more lazily.
> My implementation isn't crash-proof (i.e. doesn't support crash
> recovery - the environment in which my code operated means that if
> something bad happens, I can rebuild from external data).
unfortunately i need crash recovery (though i can sacrifice
durability.) i can't see how to do this with the IO / STM divide
except by using a transaction log and eager updates. but if i'm going
to do that anyways, i am thinking maybe i should go back to the
original plan, which was to use a simple, immutable on-disk structure
(flat file plus index) with a transaction log + cache and occasional
> > probably use the trick where the STM transaction returns
> > an IO action which you then perform. probably use ordinary page-level
> > locks to deal with concurrency on IO -- STM doesn't help.
> Maybe. See the SPJ video on STM. His basic point is that STM helps get
> rid of the stupid concurrency bugs, leaving just the "more
> interesting" ones for you to deal with. :-)
i'm not sure i understand what you're saying here. i don't see how to
synchronize IO actions with STM -- there's a wall between them. in
the IO monad i only seem to be able to use MVars and the like.
> Yes, I've chatted with Andrew Bromage about the need for
> I have a concurrent hash table which works very nicely. Think
> class Hashable t where
> hash :: t -> Word64
> type HashTable k v = TArray Word64 [(k,v)]
ah, this works nicely, probably the simplest thing to implement. but
how do you do in-order traversals?
> Yes. There's a tech report version which includes details of deletion
> which IIRC the one you mention does not. citeseer... google....
do you mean "relaxed balancing made simple" by ottman and soisalon-soininen?
thanks again for all the advice!
take care, Ben
More information about the Haskell-Cafe