Thinking about what's missing in our library coverage

Don Stewart dons at galois.com
Tue Aug 4 16:25:24 EDT 2009


wren:
> 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.

Thanks!

A maintainable testsuite (so we can check this again in the future) will
be useful!


More information about the Libraries mailing list