current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 10 down vote favorite
2

I want to implement an in-memory datastore for a web service in Haskell. I want to run transactions in the STM monad.

When I google hash table steam Haskell I only get this: Data. BTree. HashTable. STM. The module name and complexities suggest that this is implemented as a tree. I would think that an array should be more efficient for mutable hash tables.

Is there a reason to avoid using an array for an STM hashtable? Do I gain anything with this steam hash table or should I just use a steam ref to an IntMap?

share|improve this question
    
Note, if you use `TVar IntMap –  jozefg Jul 16 '13 at 17:08
    
@jozefg what do you mean? –  Simon Jul 17 '13 at 8:38
    
Oh sorry, apparently I lost the rest of that, I was going to say you'll get crappy parallelism because modifing Store ! blah and Store ! baz will have to be sequential –  jozefg Jul 17 '13 at 10:13
    
When you say "an in-memory datastore", do you mean something like acid-state? –  Ptharien's Flame Jul 17 '13 at 16:05
    
@Ptharien'sFlame I am looking for something really more simple than that. Actually I am looking for a simple mutable map that runs in the stm monad. I know I have several options for this, and I am trying to evaluate which one is better. –  Simon Jul 17 '13 at 16:24
show 1 more comment

2 Answers

up vote 0 down vote

The implementation you reference is part of a package for implementing a concurrent B-Tree. The HashTable itself is implemented as an array of TVars of Data.Map objects.

The quoted complexity values are worst-case. Remember that hashtables are usually O(N) worst case for lookup, insertion, and deletion. Using Map for the buckets brings it down to O(log(N)).

share|improve this answer
add comment
up vote -1 down vote

I'm going to go out on a limb here so bear with me...

This is NOT a Haskel specific answer, but it is an alternative way of approaching the problem, and one that I do happen to know works exceptionally well in other languages as I've personally used it.

The portable database "SQLite" unknown to many, has an exceptionally useful in memory database mode.

When you open a database, rather than giving the engine a file name that exists on disk, if you open it using the special name ':memory:' the entire data-store will be created directly in ram with no disk persistence.

Initially this data store will be empty, but if you have a source SQlite database on disk, it's a simple matter to load the table definitions SQL from the system tables, then replay them onto the in-memory store, followed by simply copying the data over.

Once you complete this start-up step, all your data is there ready to use, and rather than doing anything complex like hash-maps, dictionaries and messy allocation/de-allocation strategies, you get to simply execute standard SQL statements directly onto the store such as:

select x from y

By doing this, SQLite does ALL the heavy lifting for you, leaving you free just to concentrate on what your service needs to do.

Since SQLite is such a portable, cross platform system there are bindings available for it for Haskel.

I can't comment on the actual Haskel approach as I'm not an active Haskel user (Even though I have used it in the past) but Iv'e used this exact same technique in Java, .NET, PHP, Perl and a few others, and it's worked flawlessly every time

share|improve this answer
    
this doesn't even attempt to answer the question asked: "Is there a reason to avoid using an array for an STM hashtable? Do I gain anything with this steam hash table or should I just use a steam ref to an IntMap?" As asker doesn't seek for tool recommendations at all, this "answer" is totally irrelevant –  gnat Jul 2 at 13:59
1  
ANYTHING the seeks to provide a plausible alternative to any question asked is a viable answer, however if you are unable to see any progression in that, or lack clarity of vision to see outside the small box in which you work demonstrates at best a severe lack of understanding as to what the ethics of software development and craftsmanship stand for. I'll happily take that -1 but I wont retract my answer as IMHO this is still a viable and useful answer in the general context of the problem being approached irrespective of whether or not it directly "SOLVES THE QUESTION" –  shawty Jul 2 at 14:08
    
Sometimes "Thinking Differently" about an approach can yield a far better outcome than just putting an answer down in front of someone. –  shawty Jul 2 at 14:10
    
"Read the question carefully. What, specifically, is the question asking for? Make sure your answer provides that – or a viable alternative..." (How to Answer) –  gnat Jul 2 at 14:25
1  
OP here. @gnat is right. I know about sqllite, and it is outside the scope of my question. Appart from the fact that i had troubles with concurrency with it, writing queries in a type safe way is not something easy to achieve. You would not recommend a sql db for someone asking about a concurrent hashtable in java. It is the same issue here. I realised that stm datastructures are a research topic, and that my question might be too broad. –  Simon Jul 6 at 6:59
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.