Thinking about what's missing in our library coverage

wren ng thornton wren at
Tue Aug 4 16:24:41 EDT 2009

Don Stewart wrote:
> wren:
>> Don Stewart wrote:
>>>           o bytestring-trie — IntMap for ByteStrings
>>>           o dlist — difference lists
>> Well, if we're looking for a champion, I suggest these two should be  
>> added. Both serve demonstrated needs, both are easy to support, and both  
>> are reinvented over and over again. Because of that reinvention alone,  
>> it'd be nice to canonize a library in order to minimize wasted efforts.
>> (If anyone has complaints about bytestring-trie I'd be more than happy  
>> to hear of and address them.)
> Could you do comparative benchmarks for insertion and lookup into
>    * Data.Map String Int
>    * Data.Map ByteString Int
>    * bytestring-trie
> I don't have a sense for how much better bytestring-trie is.

 From Mark Wotton on 2009.03.01 using Microbench hacked to use Integers 
instead of Ints (to avoid overflow bugs):

* Data.List.lookup [(ByteString, Int)]:
   160.641ns per iteration / 6225.07 per second.

* Data.Map.lookup  (Map ByteString Int):
   0.881ns per iteration / 1135623.22 per second.

* Data.Trie.lookup (Trie Int):
   0.243ns per iteration / 4116930.41 per second.

I'll try to set up a benchmarking suite to test more recent versions and 
other functions in the interface.

Live well,

More information about the Libraries mailing list