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 |