9

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?

  • Note, if you use `TVar IntMap – Daniel Gratzer Jul 16 '13 at 17:08
  • @jozefg what do you mean? – Simon Bergot 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 – Daniel Gratzer 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 Bergot Jul 17 '13 at 16:24
1

The problem with a hash table implementation based directly on an array is that some of operations on it will inevitably require linear time array resizing (i.e., creating a bigger/smaller array and copying all data to it). There are multiple standard algorithms that approach this problem, like Linear Hashing or Cuckoo Hashing.

Not so long ago another algorithm named Hash Array Mapped Trie emerged, which gained a great popularity across functional languages like Clojure, Scala and, of course, Haskell (with the "unordered-containers" and "hamtmap" libraries) due to support of persistent data structures.

Not long ago I released an STM-specialized containers library based on that algorithm named "stm-containers", which should fit your task perfectly. You can also check out an introductory blog post, covering a motivation behind the library and providing benchmarks.

| improve this answer | |
  • Thanks for replying! I haven't tested your package but it looks interesting. I will check it later, but based on your post I am ready to believe that it fits my initial goal. – Simon Bergot Sep 2 '14 at 7:55
1

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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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