IntSet.fromList and its benchmarks

[jwaldmann]

I experimented with IntSet.fromList via binary fold union, see jwaldmann@975781b
(cf. #330 but without computing runs)

I thought I had a huge improvement - but then found that this is due to the benchmarks: all the data is dense (contiguous numbers, even numbers, odd numbers). For these, my implementation cuts runtimes (of fromList) nearly in half. But for sparse data (square numbers, pseudo-random numbers) it does not.

On the other hand it does not increase runtime much so perhaps there's a way to make use of the idea. That's for later.

For now, I suggest that benchmarks be extended by some sparse sets.

[treeowl]

That does sound like a serious benchmark weakness! I would conjecture that the low-hanging fruit for IntSet.fromList is the case where multiple values in a row belong in the same leaf, and that we might also be able to do better (for both sets and maps) by waiting to ascend to a parent until we need to. The general idea is to pass the rest of the list down the tree when inserting a value and return the tail of things that don't go there.

[treeowl]

It would probably be easier to make an attempt on IntMap. IntSet is similar, but with an extra layer of complexity.

[treeowl]

@jwaldmann I just opened #653 to try to be more clever about list conversions for IntMap. The benchmarks there suffer from the same limitations as the IntSet ones, but I also tried square numbers and either way I got serious improvements. I don't, however, trust my benchmarking skills, and I haven't tried any sort of pseudorandom number generation. Do you have the time to take a glance and see if you can duplicate my results? If that works as well as it seems, we should surely use the same approach for IntSet.

[jwaldmann]

"see if I can duplicate" Yes, I will look into it over the next days (not today).

[jwaldmann]

regarding benchmarks and their use of gauge, see vincenthz/hs-gauge#95

[meooow25]

I've added benchmarks for sparse ascending and random input in #1129.