haskell
Build Set and Map more efficiently
Use "Builder"s to implement some Set and Map construction functions. As a result, some have become good consumers in terms of list fusion, and all are now O(n) for non-decreasing input.
Fusible Fusible O(n) for O(n) for
before after before after
Set.fromList No Yes Strict incr Non-decr
Set.map - - Strict incr Non-decr
Map.fromList No Yes Strict incr Non-decr
Map.fromListWith Yes Yes Never Non-decr
Map.fromListWithKey Yes Yes Never Non-decr
Map.mapKeys - - Strict incr Non-decr
Map.mapKeysWith - - Never Non-decr
For #1027. Also related to #949.
Benchmarks on GHC 9.6.3:
Set:
Name Time - - - - - - - - Allocated - - - - -
A B % A B %
fromList-asc 48 μs 25 μs -48% 271 KB 256 KB -5%
fromList-asc:fusion 66 μs 22 μs -66% 559 KB 288 KB -48%
fromList-desc 534 μs 539 μs +0% 2.6 MB 2.6 MB +0%
fromList-desc:fusion 564 μs 587 μs +3% 2.9 MB 2.9 MB +0%
map:asc 75 μs 53 μs -30% 559 KB 416 KB -25%
map:desc 576 μs 586 μs +1% 2.8 MB 2.7 MB -5%
Map:
Name Time - - - - - - - - Allocated - - - - -
A B % A B %
fromList-asc 57 μs 31 μs -45% 319 KB 305 KB -4%
fromList-asc:fusion 81 μs 23 μs -71% 703 KB 368 KB -47%
fromList-desc 557 μs 551 μs -1% 3.1 MB 3.1 MB +0%
fromList-desc:fusion 603 μs 603 μs +0% 3.5 MB 3.4 MB -1%
fromListWith-asc 540 μs 30 μs -94% 2.7 MB 272 KB -90%
fromListWith-asc:fusion 578 μs 20 μs -96% 3.1 MB 320 KB -89%
fromListWith-desc 553 μs 578 μs +4% 3.1 MB 3.1 MB +1%
fromListWith-desc:fusion 528 μs 556 μs +5% 3.1 MB 3.1 MB -1%
fromListWithKey-asc 534 μs 28 μs -94% 2.7 MB 288 KB -89%
fromListWithKey-asc:fusion 566 μs 20 μs -96% 3.1 MB 336 KB -89%
fromListWithKey-desc 547 μs 587 μs +7% 3.1 MB 3.2 MB +3%
fromListWithKey-desc:fusion 521 μs 578 μs +10% 3.2 MB 3.2 MB +0%
mapKeys:asc 125 μs 55 μs -55% 862 KB 480 KB -44%
mapKeys:desc 686 μs 611 μs -10% 3.6 MB 3.2 MB -10%
mapKeysWith:asc 707 μs 53 μs -92% 3.2 MB 463 KB -86%
mapKeysWith:desc 666 μs 568 μs -14% 3.2 MB 2.9 MB -10%
Note: You may notice desc fusion cases haven't improved, though they really should. It turns out to be a enumFromThen/fusion issue, and not really a problem with our code. I opened a GHC issue for it: GHC#25259
Hmm.. the failing strictness test is a bit silly. It is defeated by the new fusible definition. Anyway, it gets removed in #1021.
Is there any way to get side by side comparisons of times and allocations? All the befores followed by all the afters is hard to look at.
How do things go when fusion doesn't happen?
Seems to be around the same, perhaps slightly slower. You can see these in the table when there is no fusion. For example, Map's fromList-desc is -1% and fromListWith-desc is +4%.
Is there any way to get side by side comparisons of times and allocations? All the befores followed by all the afters is hard to look at.
Right, I had a script for that. Updated the benchmarks section.
Another benefit of this implementation (which I did not consider before, #351) is that it will allow defining functions like fromFoldable since we are just doing a foldl' now. This will be more efficient in case there is a real list in the way, or if there isn't but list-fusion does not work out optimally.
Going further, we could expose the Builder stuff if there is a demand for it.
Rebased and updated benchmarks.
If there are no concerns, I would like to merge this soon, so that I can consider this fromList the baseline when trying out #1073.