#15131 closed bug (fixed)

Speed up certain Foldable NonEmpty methods

Reported by: dfeuer Owned by:
Priority: normal Milestone: 8.6.1
Component: Core Libraries Version: 8.2.2
Keywords: Cc: nomeata, YitzGale, mpickering
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D4677
Wiki Page:

Description

Yitzchak Gale pointed out on Reddit that some Foldable methods are allowed to take default definitions for NonEmpty when they probably shouldn't. The biggest problem appears to be foldr1, which ends up with a fairly atrocious definition. Yitz seems to think we should also provide a custom definition of null, to avoid relying on optimizations, but at present there is no obvious need for that. He doesn't mention this, but the definition of length should be changed. Indeed, the default definition of length would be better than the custom definition we currently have. I also noticed that we don't mark foldl1 INLINE. At present its unfolding is optimized, so its foldr is not exposed. Thus, for example,

foldl1 (+) $ 1 :| [2..n]

won't fuse. We can certainly mark foldl1 INLINE to fix this (INLINABLE doesn't do the trick), but it would be nice to know if there's another way.

Change History (7)

comment:1 Changed 19 months ago by dfeuer

Differential Rev(s): Phab:D4677
Status: newpatch

I've put together a patch, Phab:D4677, to make foldr1 decent and length slightly better. I'll wait for feedback from mpickering and/or nomeata before mucking about with inlining.

comment:2 Changed 19 months ago by YitzGale

I just gave one or two examples in the reddit thread, but really all the methods need review.

I'm not convinced about the default length being better. Perhaps switch the order, List.length as + 1. Does GHC not inline primitive +? And you do an extra +0. But if I'm wrong, the clear explanatory comment is highly appreciated.

Why not just put the obvious trivial explicit implementation for every method? It would make the code cleaner and easier to read, without having to look up the default and then scratch your head about what gets optimized.

Note that for historical reasons several methods for List are still implemented via foldl. That is in very rare cases better than foldl', in many cases the same because GHC optimizes it, and in some cases worse. My opinion is that NonEmpty should always behave the same as List, whatever that may be. It's worth it to add one extra operation to the NonEmpty implementation so that we can refer to the List implementation and not hard-code a copy of it.

Here's my alternative "patch" (sorry I don't know how to offer an alternative patch on Phab):

instance Foldable NonEmpty where
    elem x (a :| as) = x == a || x `List.elem` as
    foldl f z (a :| as) = List.foldl f (f z a) as
    foldl' f z (a :| as) = let z' = f z a in z' `seq` List.foldl' f z' as
    foldl1 f (a :| as) = List.foldl f a as
    foldr f z ~(a :| as) = f a (List.foldr f z as)
    foldr1 f ~(a :| as) = List.foldr f a as
    length (_ :| as) = List.length as + 1
    maximum (a :| as) = max a (List.maximum as)
    minimum (a :| as) = min a (List.minimum as)
    null _ = False
    product (a :| as) = a * List.product as
    sum (a :| as) = a + List.sum as
    toList ~(a :| as) = a : as

EDIT: Made a few edits to the above code. Among other things: Leave fold at default because List does. But the default for foldMap is silly for NonEmpty.

EDIT2: removed the lazy patterns from the foldl* methods as mentioned on Phab.

EDIT3: Never mind, my foldMap was wrong. I don't see any way to do better than default after all for foldMap.

Last edited 19 months ago by YitzGale (previous) (diff)

comment:3 Changed 19 months ago by dfeuer

Yours has to hold on to the "and then add one" while calculating the length of the list. Same goes for max and min. I'll look more later.

comment:4 in reply to:  3 Changed 19 months ago by YitzGale

Replying to dfeuer:

Yours has to hold on to the "and then add one" while calculating the length of the list.

Are you sure GHC doesn't inline the +1? In any case, this is slightly better:

length (_ :| as) = List.foldl' (\c _ -> c+1) 1 as

Same goes for max and min.

Yes, and also for product and sum, but I did that purposely. I want the semantics to be the same as for List, which is a bit weird because it uses foldl. And I don't want to hard-code a copy of the foldl here. I want it to be fixed automatically if we every get around to fixing it for List.

comment:5 Changed 19 months ago by dfeuer

GHC isn't clever enough to reassociate a recursively calculated sum, no. The foldl' definition you give ends up looking just the same as the default. As for sum, etc., I don't really think we should write worse code today because maybe some year the definition for lists will improve while the default definition doesn't. You can push for those changes separately, and in due course we can adjust this instance again if necessary.

comment:6 Changed 18 months ago by Ben Gamari <ben@…>

In b7139869/ghc:

Improve some Foldable methods for NonEmpty

* `length` is improved by using the default definition,
  while `foldr1` is improved by using a custom one.

* Several methods had useless lazy pattern matches
  (i.e., the functions were actually strict in those arguments).
  Remove `~`s to clarify.

Reviewers: hvr, bgamari, mpickering, nomeata

Reviewed By: bgamari

Subscribers: ygale, rwbarton, thomie, carter

GHC Trac Issues: #15131

Differential Revision: https://phabricator.haskell.org/D4677

comment:7 Changed 18 months ago by bgamari

Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.