[Haskell-cafe] Optimization with Strings ?

[David Menendez]

On Thu, Dec 3, 2009 at 12:32 PM, Alec Berryman <alec at thened.net> wrote:
> Emmanuel CHANTREAU on 2009-12-03 13:03:02 +0100:
>
>> In my futur program, it use a lot of binary trees with strings (words)
>> as leaf. There is just arround 1000 words and they will appear a lot of
>> times. The program will possibly consume a lot of process and memory
>> (it is a mathematics proover).
>>
>> I began this program in C++ but haskell has a prety good speed and
>> memory footprint and is easier. But I don't know if it worth to do this
>> optimization: having a dictionary to translate string words in Int.
>>
>> The answer depends on the automatic optimizations in GHC, because GHC
>> could compare quickely two strings if it is the same object, so it
>> depends if program generated by GHC have a dictionary (tree) of strings
>> internaly. Someone knows this ?
>
> I don't know of a library to intern strings, but it's not too hard to
> implement.  I couldn't find the code I wrote to do this, but I looked
> around a bit and this is about what I remember doing:
>
> http://www.haskell.org/pipermail/haskell-cafe/2005-June/010335.html
>
> For the application I was using, interning strings did provide a
> significant reduction in memory, but for whatever reason didn't help
> with speed.

I'd use a trie. Edison provides Data.Edison.Assoc.TernaryTrie, and
there are a few other trie packages at hackage.


-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>