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