On Thu, Aug 06, 2009 at 08:22:28AM +0100, Simon Peyton-Jones wrote:
On 03 August 2009 20:29, Ross Paterson wrote: | On Mon, Jul 20, 2009 at 02:33:52PM -0400, Louis Wasserman wrote: | > Among other things, I manually deforested the stable sorting algorithm, | > resulting in a moderate performance gain on simply using Data.List.sortBy. | | That's not supposed to be necessary, because toList is supposed to fuse | with list consumers. Unfortunately it doesn't in cases like this because | it doesn't get inlined, even if we add an INLINE pragma, due to GHC bug | #2353. If the GHC bug isn't fixed, I think the next best thing would | be to force the inlining of toList with a RULES pragma in Data.Foldable.
I will look into this during August. Add yourself to the cc list for #2353 if interested.
OK, I'll add INLINE toList to Data.Foldable and wait till it starts working. (If it doesn't, I can add RULES to unconditionally force the expansion.) In any case we won't need to manually deforest Data.Sequence.sortBy. The naive version will (soon) be just as fast: sortBy :: (a -> a -> Ordering) -> Seq a -> Seq a sortBy cmp xs = fromList2 (length xs) (Data.List.sortBy cmp (toList xs))