Improve fromList for Data.Map and Data.Set

[treeowl]

Currently, we try to be very efficient about lists that ascend from the start for most of their length. This seems a tad specific. I suspect what we'd really like to use is an algorithm more like that of Data.List.sort. That is, break up the input into ascending and descending segments, convert each segment, and use union to join the segments together. Unfortunately, the current code is not structured in a way that makes this terribly easy.

Another (less serious) problem is that fromAscListWithKey and fromDescListWithKey preprocess their input lists to squash duplicates. When there aren't any duplicates, this allocates a bunch of short-lived conses. It would be nice to find a way to avoid this, but it's probably not terribly important. I made a brief attempt, but it got horrible pretty quickly.

Another (more serious?) problem is that Data.Map.fromAscList is defined in terms of fromAscListWithKey, which in the lazy case seems rather likely to produce an avoidable space leak. (Fixed in #332)

[meooow25]

Considering this resolved after #1042.

That is, break up the input into ascending and descending segments, convert each segment, and use union to join the segments together.

I did experiment with unioning multiple ascending segments, but it made the worst case slower.

containers/containers/src/Data/Set/Internal.hs

Lines 1648 to 1651 in 32c80d8

	-- More complicated implementations are possible, such as repeatedly
	-- accumulating runs of increasing elements in Stacks (not just once) and
	-- union-ing with an accumulated Set, but this makes the worst case somewhat
	-- slower (~10%).

Another (less serious) problem is that fromAscListWithKey and fromDescListWithKey preprocess their input lists to squash duplicates. When there aren't any duplicates, this allocates a bunch of short-lived conses.

This is fixed by #1083.