Proposal: Allow gunfold for Data.Map, Data.IntMap, etc.
ekmett at gmail.com
Thu Aug 30 02:57:53 CEST 2012
This might pay off as well, but I am leery that its a rather tricky
balancing act and will take a lot of profiling to find the right balance in
practical performance vs. asymptotic bounds.
Should we split the notion of improving the performance of fromList into a
that simply exposes synergies with this one?
On Wed, Aug 29, 2012 at 8:02 PM, Johan Tibell <johan.tibell at gmail.com>wrote:
> On Wed, Aug 29, 2012 at 4:54 PM, Edward Kmett <ekmett at gmail.com> wrote:
> > We should be able to fuse this "try to construct linearly, but fall back
> > N-log-N" version of fromList in one pass even for normal uses of
> > e.g. assume that you are constructing a sorted tree until you find a key
> > of order, then take the tree you've built so far and union it
> > with the slower constructed fromList of the remainder. That way you don't
> > have to retain the storage for both the list and the map, and we only
> > the list once.
> Could you instead of falling back to the slower fromList just keep
> building new trees and then union them all in the end. Real world data
> is often is semi-sorted order. I guess we would need to detect some
> worst case scenarios (i.e. sorted in reverse order) and fall back to
> the slower fromList in those cases.
> -- Johan
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Libraries