
thanks for the detailed response!
On 8/20/07, Thomas Conway
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