Proposal: add 'findLess' and variants to containers

[Twan van Laarhoven]

On 16/02/12 20:37, Johan Tibell wrote:
> Hi,
>
> First, thanks for writing such a detailed proposal.
>
> I don't have strong feelings one way or the other. Like always I'm
> worried about API growth. How about performance? Can these functions
> be implemented efficiently outside the library?

I also did some performance tests, comparing an implementation that uses only 
the exposed API (split,findMin) to one that uses the constructors. The benchmark 
code is attached, it is mostly copy-pasted from benchmarks/Map.hs. Here is a 
general idea of the results (ghc 7.0.4 on windows 7) :

     benchmarking GE split absent  (based on exposed library)
     mean: 298.6235 us, lb 295.8455 us, ub 301.4016 us, ci 0.950
     std dev: 14.43998 us, lb 12.51990 us, ub 19.21979 us, ci 0.950

     benchmarking GE custom absent
     mean: 45.04386 us, lb 44.62368 us, ub 45.42206 us, ci 0.950
     std dev: 2.075708 us, lb 1.874807 us, ub 2.362928 us, ci 0.950

The results on other benchmarks are similar: A custom implementation is 4-6 
times faster.

I haven't yet compared the performance for Set yet (which I expect will be 
similar), nor for IntMap (where I have no clue).


Besides the question of whether these functions can be implemented efficiently 
outside the library, I think you should also ask whether they can be implemented 
in a way that is obviously correct. I argued in the proposal that this is not 
the case, which is another argument for adding them.


Twan
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: findGE-Map.hs
URL: <http://www.haskell.org/pipermail/libraries/attachments/20120217/ff38f752/attachment.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Map_FindGE.hs
URL: <http://www.haskell.org/pipermail/libraries/attachments/20120217/ff38f752/attachment.asc>