thanks for the detailed response! On 8/20/07, Thomas Conway <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
