[jhc] Optimization.

[Lemmih]

On Feb 16, 2008 3:13 AM, John Meacham <john at repetae.net> wrote:
>
> On Sat, Feb 16, 2008 at 12:52:30AM +0100, Lemmih wrote:
> > On Sat, Feb 16, 2008 at 12:45 AM, John Meacham <john at repetae.net> wrote:
> > > On Fri, Feb 15, 2008 at 03:34:59PM +0100, Lemmih wrote:
> > >
> > >
> > > > The attached patch is a two-step optimization:
> > >  >  1) Only call 'getType' 100,000,000 times instead of 600,000,000 times.
> > >  >  2) Greatly simplify the actual loop.
> > >  >
> > >  > Without this patch, compiling base-1.0.hl takes 19 minutes. With this
> > >  > patch, compile time is down to 11 minutes.
> > >  > Feedback would be greatly appreciated.
> > >
> > >  I am confused, what in the patch causes getType to be called less? As
> > >  far as I can tell it is just replacing equality checks with 'isFoo'
> > >  predicates.
> >
> > E.Values.isCheap checks whether its argument is atomic. The 'isAtomic'
> > function is very expensive so I moved it down below the four static
> > checks.
>
> Ah, I see now. cool. there are probably other ones in there that can be
> moved around to improve speed.

No, 'isAtomic'/'isCheap' takes less than a single percent right now.
Optimizing it more will be a waste of time.

> isAtomic was very cheap once upon a time.. but now the isFullyConst was added...

Actually, 'isFullyConst' is insignificant. It was 'getType', called
multiple times from 'sortTypeLike' and 'sortKindLike', that took most
of the CPU time.

> It _may_ be possible to have isFullyConst only look one layer deep,
> since an invariant that is supposed to hold is that a constructor can
> only hold atomic arguments, hence any Literals under another one must be
> fully constant.

'isFullyConst' is deliciously fast. It plays right at GHC's strengths.
It compiles to a finely tuned loop that performs essentially no
allocations.
The code is very pretty and easy to understand; let's keep it that way.

> However, I am not sure if that invarient is rigidly enforced through all
> compilation phases. like, there is a progression of transformations
> through normal forms, each one more strict than the last... hmm...
>
> perhaps a way to test would be for isAtomic only look a single layer
> deep but isFullyConst will do a full check. and isAtomic can do a
> 'isFullyConst' check only when -flint mode is enabled. We will probably
> have to go thorugh and change some isAtomics to isFullyConst depending
> on whether the code is known to be in normal form beforehand or not.

The functions 'isAtomic', 'isFullyConst' and 'getType' are
ridiculously cheap right now. They only check constructors without
doing any allocation. With GHC's pointer tagging, this is as fast as
hand tuned C code. Our attention should be diverted elsewhere.

About 60% of the CPU time when compiling the base library goes to
garbage collecting. The majority of garbage is created when converting
from IdMap to IdSet and from 'IdMap a' to 'IdMap (Maybe a)'. Fixing
these issues should give at least a factor of 2 in performance
increase.

-- 
Cheers,
  Lemmih