[Haskell-cafe] Why does this program eat RAM?

[Jan-Willem Maessen]

On Sep 5, 2006, at 7:05 AM, Chris Kuklewicz wrote:

> Bulat Ziganshin wrote:
>> Hello Bertram,
>> Tuesday, September 5, 2006, 12:24:57 PM, you wrote:
>>>> A quick hack up to use Data.ByteString uses a lot less ram, though
>>>> profiling still shows 95% of time spent in the building the Map.
>> Data.HashTable may be a faster alternative for Map (if ordering isn't
>> required)
>
> I found Data.HashTable a bit slow (ghc 6.4).  Perhaps HsJudy (see  
> http://cmarcelo.blogspot.com/ and http://judy.sourceforge.net/ and  
> http://www.mail-archive.com/haskell@haskell.org/msg18766.html )

I'd urge programmers to give the version of Data.HashTable in 6.6 a  
try.  It uses a simple multiplicative hash function (a la Knuth)  
which seems to be dramatically better in practice.  It also uses a  
rather simpler hash table implementation which seems to perform  
slightly better in practice (if this isn't true for your application  
I'm keen to know).

As Udo Stenzel points out, we still need to examine the entire string  
in order to hash, and some problems may do better with something like  
a StringMap---I understand many information retrieval applications  
use Trie-like data structures for exactly this reason.

-Jan-Willem Maessen

> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20060913/334220d0/smime.bin