#8638: Optimize by demoting "denormalized" Integers (i.e. J# -> S#)
--------------------------------------------+------------------------------
Reporter: hvr | Owner: hvr
Type: feature request | Status: closed
Priority: normal | Milestone: 7.8.1
Component: libraries (other) | Version: 7.7
Resolution: fixed | Keywords: integer-
Operating System: Unknown/Multiple | gmp
Type of failure: Runtime performance bug | Architecture:
Test Case: | Unknown/Multiple
Blocking: | Difficulty: Unknown
| Blocked By:
| Related Tickets: #8647
--------------------------------------------+------------------------------
Changes (by simonpj):
* status: patch => closed
* resolution: => fixed
Comment:
Thanks. I committed two patches below. I'll close this one since you
have opened a new ticket for #8647.
Simon
{{{
commit 301269aef0fb331bf272de4f6592eb71471a3b16
Author: Herbert Valerio Riedel
---------------------------------------------------------------
301269aef0fb331bf272de4f6592eb71471a3b16
GHC/Integer/Type.lhs | 92
++++++++++++++++++++++++++++++++------------------
1 file changed, 59 insertions(+), 33 deletions(-)
}}}
and
{{{
commit 3c93d7f61821345f29b9ee8a99346fa464d708a4
Author: Simon Peyton Jones
---------------------------------------------------------------
3c93d7f61821345f29b9ee8a99346fa464d708a4 GHC/Integer/Type.lhs | 50 +++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 41 insertions(+), 9 deletions(-) diff --git a/GHC/Integer/Type.lhs b/GHC/Integer/Type.lhs index c206462..77d529a 100644 --- a/GHC/Integer/Type.lhs +++ b/GHC/Integer/Type.lhs @@ -152,21 +152,52 @@ toBig i@(J# _ _) = i -- | Demote 'J#' to 'S#' if possible. See also 'smartJ#'. toSmall :: Integer -> Integer -toSmall i@(S# _) = i -toSmall (J# 0# _) = S# 0# -toSmall (J# 1# mb#) | isTrue# (v ># 0#) = S# v +toSmall i@(S# _) = i +toSmall (J# s# mb#) = smartJ# s# mb# + + +-- | Smart 'J#' constructor which tries to construct 'S#' if possible +smartJ# :: Int# -> ByteArray# -> Integer smartJ# 0# _ = S# 0# smartJ# +1# mb# | isTrue# (v ># 0#) = S# v where v = indexIntArray# mb# 0# -toSmall (J# -1# mb#) | isTrue# (v <# 0#) = S# v +smartJ# (-1#) mb# | isTrue# (v <# 0#) = S# v where v = negateInt# (indexIntArray# mb# 0#) -toSmall i = i - --- | Smart 'J#' constructor which tries to construct 'S#' if possible -smartJ# :: Int# -> ByteArray# -> Integer -smartJ# s# mb# = toSmall (J# s# mb#) +smartJ# s# mb# = J# s# mb# \end{code} +Note [Use S# if possible] +~~~~~~~~~~~~~~~~~~~~~~~~~ +It's a big win to use S#, rather than J#, whenever possible. Not only +does it take less space, but (probably more important) subsequent +operations are more efficient. See Trac #8638. + +'smartJ#' is the smart constructor for J# that performs the necessary +tests. When returning a nested result, we always use smartJ# strictly, +thus + let !r = smartJ# a b in (# r, somthing_else #) to avoid creating +a thunk that is subsequently evaluated to a J#. +smartJ# itself does a pretty small amount of work, so it's not worth +thunking it. + +We call 'smartJ#' in places like quotRemInteger where a big input might +produce a small output. + +Just using smartJ# in this way has good results: + + Program Size Allocs Runtime Elapsed TotalMem +-------------------------------------------------------------------------------- + gamteb +0.1% -19.0% 0.03 0.03 +0.0% + kahan +0.2% -1.2% 0.17 0.17 +0.0% + mandel +0.1% -7.7% 0.05 0.05 +0.0% + power +0.1% -40.8% -32.5% -32.5% +0.0% + symalg +0.2% -0.5% 0.01 0.01 +0.0% +-------------------------------------------------------------------------------- + Min +0.0% -40.8% -32.5% -32.5% -5.1% + Max +0.2% +0.1% +2.0% +2.0% +0.0% + Geometric Mean +0.1% -1.0% -2.5% -2.5% -0.1% %********************************************************* %* * @@ -200,6 +231,7 @@ quotRemInteger (J# s1 d1) (J# s2 d2) (# s3, d3, s4, d4 #) -> let !q = smartJ# s3 d3 !r = smartJ# s4 d4 in (# q, r #) + -- See Note [Use S# if possible] {-# NOINLINE divModInteger #-} divModInteger :: Integer -> Integer -> (# Integer, Integer #) }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8638#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler