Re: [jhc] Optimization.

On Feb 16, 2008 3:13 AM, John Meacham wrote:

On Sat, Feb 16, 2008 at 12:52:30AM +0100, Lemmih wrote:

...

On Sat, Feb 16, 2008 at 12:45 AM, John Meacham 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