[Haskell-cafe] STM, IO and b-trees

[Ben]

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
merging.

> >  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
>
> Data.Map.Concurrent
> Data.Set.Concurrent
> etc.
>
> 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