seq can make code slower

Adrian Hey produced a program that goes a little slower when he added "!" annotations to his data constructors. This was a surprise to me, but I understand why now. This bug report just captures the problem so that I don't forget about it. I'm treating it as a "bug" because it really is a performance bug.

The problem turns out to be this. In the attached code, genPush looks like this:

 put  E        = Z    E e0 E
 put (N l e r) = putN l e  r
 put (Z l e r) = putZ l e  r
 put (P l e r) = putP l e  r

With a strict data type, we know that 'r' is evaluated, but putN (although strict) does not know that its argument is evaluated, so it does an extra and unnecessary eval.

There are two difficulties. First, most of the time we don’t want to require that a strict function gets an evaluated argument. E.g. map is strict, but it does its own 'case' on the list arg, and we don't want the caller to have to do that too. What we're trying to catch is the calls to 'seq' when the caller already knows that.

If we could spot these cases, then we could w/w the function to expose the 'seq' to the caller. I'm not sure how we'd explain to the callee that the arg was definitely evaluated.

How to spot the cases? We want to spot function bodies that only 'seq' their argument without doing a proper case or function applications. Sounds like enriching the demand domain (again!).

Simon

The attached code demonstrates the problem. There are two versions of AVL routines..

AVL.hs (no strictness annotation in data type, explicit seqs instead) StrictAVL.hs (uses strictness annotation instead of seqs)

Running BUILD.BAT generates 2 executables..

Lazy.exe    which uses AVL.hs
Strict.exe  which uses StrictAVL.hs

These test the execution times of the genWriteFast and genPush functions defined in modules AVL.hs and StrictAVL.hs respectively.

For genWriteFast the two tests give virtually identical times (as expected). But for some reason the version of genPush using strictness annotation instead of explicit seqs seems to take about 15% longer.

The size of the object file seems a bit bigger too.

The fact that genWriteFast times are the same seems to indicate that my original hypothesis is wrong, but there's something strange about the genPush from StrictAVL.hs.

Trac metadata

Trac field	Value
Version	6.6.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system	Unknown
Architecture	Unknown