Out of curiosity, I've tested a few Hashtable implementations: http://zufaellige-reflektion.blogspot.com/2011/04/associative-arrays-showdow... Are there any clues why Haskell's Data.HashTable doesn't perform better? I would have expected a similar performance like with F# on the Mono 2.0 platform. Thanks, Frank
The hashtable in base is used very little by the Haskell community, partly due to it being IO heavy and partly a result of its known performance issues that no one seems motivated to address. I suggest you look at the unordered-containers package which is rather new but positioned to become the de facto standard. Currently, many people needing a key/value mapping lean on Data.Map from the containers package (a balanced tree). Cheers, Thomas On Tue, Apr 5, 2011 at 5:53 PM, Frank Kuehnel <vincef13@mac.com> wrote:
Out of curiosity, I've tested a few Hashtable implementations: http://zufaellige-reflektion.blogspot.com/2011/04/associative-arrays-showdow... Are there any clues why Haskell's Data.HashTable doesn't perform better? I would have expected a similar performance like with F# on the Mono 2.0 platform. Thanks, Frank
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
Actually, Data.HashTable got some good attention recently from Simon Marlow (modifying the GC), and Johan Tibell and others looking at containers performance in general: http://stackoverflow.com/questions/3058529/curious-about-the-hashtable-probl... http://blog.johantibell.com/2011/03/video-of-my-hashing-based-containers.htm... Certainly, being in IO limits the utility of a hashtable library (since it isn't thread safe or persistent by default), but that doesn't mean the structure gets neglected. Johan, what's your thoughts on the status? -- Don On Tue, Apr 5, 2011 at 8:31 PM, Thomas DuBuisson <thomas.dubuisson@gmail.com> wrote:
The hashtable in base is used very little by the Haskell community, partly due to it being IO heavy and partly a result of its known performance issues that no one seems motivated to address. I suggest you look at the unordered-containers package which is rather new but positioned to become the de facto standard. Currently, many people needing a key/value mapping lean on Data.Map from the containers package (a balanced tree).
Cheers, Thomas
On Tue, Apr 5, 2011 at 5:53 PM, Frank Kuehnel <vincef13@mac.com> wrote:
Out of curiosity, I've tested a few Hashtable implementations: http://zufaellige-reflektion.blogspot.com/2011/04/associative-arrays-showdow... Are there any clues why Haskell's Data.HashTable doesn't perform better? I would have expected a similar performance like with F# on the Mono 2.0 platform. Thanks, Frank
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
On Tue, Apr 5, 2011 at 8:37 PM, Don Stewart <dons00@gmail.com> wrote:
Actually, Data.HashTable got some good attention recently from Simon Marlow (modifying the GC), and Johan Tibell and others looking at containers performance in general:
Ah, I guess my knowledge is dated, thanks for the info. Cheers, Thomas
Hi Frank, You can try out the new Data.HashMap data structure by running cabal install unordered-containers from a shell and then import qualified Data.HashMap.Strict as Map in your Haskell program. It's currently the fastest *persistent* (i.e. purely functional) Haskell map implementation I know of. (Full disclosure: I wrote it.) The Git repo is here: http://github.com/tibbe/unordered-containers If you want a fast mutable hash table Gregory Collins (CCed) have been working on a few implementations that beat Data.Hashtable by a large margin. I don't know if they're ready for general use yet (i.e. they haven't been released on Hackage yet). Cheers, Johan
On Wed, Apr 6, 2011 at 10:23 AM, Johan Tibell <johan.tibell@gmail.com> wrote:
If you want a fast mutable hash table Gregory Collins (CCed) have been working on a few implementations that beat Data.Hashtable by a large margin. I don't know if they're ready for general use yet (i.e. they haven't been released on Hackage yet).
Hi all, The code: a) isn't finished b) needs to go through my employer's open-source releasing process But yes, it currently beats Data.Hashtable by something like 4-6x. I could work on it with some more urgency if people were interested. G -- Gregory Collins <greg@gregorycollins.net>
On 6 April 2011 20:37, Gregory Collins <greg@gregorycollins.net> wrote:
On Wed, Apr 6, 2011 at 10:23 AM, Johan Tibell <johan.tibell@gmail.com> wrote:
If you want a fast mutable hash table Gregory Collins (CCed) have been working on a few implementations that beat Data.Hashtable by a large margin. I don't know if they're ready for general use yet (i.e. they haven't been released on Hackage yet).
Hi all,
The code:
a) isn't finished b) needs to go through my employer's open-source releasing process
But yes, it currently beats Data.Hashtable by something like 4-6x. I could work on it with some more urgency if people were interested.
I'm very interested! A mutable hashtable is a key data structure in berp, the python compiler that I am writing. Cheers, Bernie.
participants (6)
-
Bernie Pope -
Don Stewart -
Frank Kuehnel -
Gregory Collins -
Johan Tibell -
Thomas DuBuisson