10

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?

6
  • Note, if you use `TVar IntMap Commented Jul 16, 2013 at 17:08
  • @jozefg what do you mean? Commented Jul 17, 2013 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 Commented Jul 17, 2013 at 10:13
  • When you say "an in-memory datastore", do you mean something like acid-state? Commented Jul 17, 2013 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. Commented Jul 17, 2013 at 16:24

2 Answers 2

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.

1
  • 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. Commented Sep 2, 2014 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)).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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