id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc	os	architecture	failure	difficulty	testcase	blockedby	blocking	related
3065	Reorder tests in quot to improve code	simonpj		"[SLPJ: capturing an email thread in a ticket]

Krasimir Angelov found that this function:
{{{
a `quot` b
    | b == 0                     = divZeroError
    | a == minBound && b == (-1) = overflowError
    | otherwise                  =  a `quotInt` b
}}}
is expanded to:
{{{
a `quot` b =
   if b == 0
     then divZeroError
     else if a == minBound
              then if b == (-1)
                       then overflowError
                       else a `quotInt` b
              else a `quotInt` b
}}}
Then the compiler sees that b is a constant and computes that b == 0
is False and b == (-1) is also False so it could eliminate two If
statements. The result is:
{{{
a `quot` b =
   if a == minBound
     then a `quotInt` b
     else a `quotInt` b
}}}
and this is exactly what we get. I bet that if the original function was:
{{{
a `quot` b
    | b == 0                     = divZeroError
    | b == (-1) && a == minBound = overflowError   -- Note the changed order here
    | otherwise                  =  a `quotInt` b
}}}
then we would get what we want. I think that it is much more often to
have division where the divisor is known so we will get the best code
in this case.

Shortly afterwards, Bertram Felgenhauer tried it out.  It works, and it has the desired effect. It's not always a win though; the nofib prime sieve benchmark suffers.

For a patch, see
  http://int-e.home.tlink.de/haskell/ghc-libraries-base-tune-division.patch
(SLPJ: I've attached it to the ticket too)

Nofib results extract:
{{{
------------------------------------------------------------------------
        Program           Size    Allocs   Runtime   Elapsed
------------------------------------------------------------------------
           fish          -0.7%     -5.3%      0.05      0.04
         primes          -0.0%    +28.5%    +25.6%    +25.5%
   wheel-sieve2          -0.0%     -0.3%    -17.9%    -18.6%
------------------------------------------------------------------------
            Min          -0.9%     -5.3%    -17.9%    -18.6%
            Max          +0.1%    +28.5%    +25.6%    +25.5%
 Geometric Mean          -0.2%     +0.2%     -0.0%     +0.2%
}}}
'primes' is an outlier - the other slowdowns are below 3%

What happens in 'primes' is that 'mod' no longer gets inlined;
apparently it now looks bigger to the compiler than before.

Using -funfolding-use-threshold=10 brings the benchmark back to its
original speed, despite the extra comparison before doing the
division.

In 'wheel-sieve2', the first different optimization choice I see is
again a 'mod' that is no longer inlined; this leads to a change in other
inlining choices that result in a speedup for reasons that I have not
investigated.


"	bug	new	lowest	7.6.2	libraries/base	6.10.1			bertram.felgenhauer@… kr.angelov@… dterei	Unknown/Multiple	Unknown/Multiple	Runtime performance bug	Unknown