#8638: Optimize by demoting "denormalized" Integers (i.e. J# -> S#) --------------------------------------------+------------------------------ Reporter: hvr | Owner: hvr Type: feature request | Status: new Priority: normal | Milestone: 7.8.1 Component: libraries (other) | Version: 7.7 Resolution: | 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: --------------------------------------------+------------------------------ Description changed by hvr: Old description:

In the course of a recent [discussion on reddit](http://www.reddit.com/r/haskell/comments/1twtvm/the_problem_with_integer/) it was highlighted, that `integer-gmp` doesn't try to demote `J#` to the more efficient `S#` if even though they would fit.

The attached proof-of-concept patch introduces a "smart" `J#` constructor which constructs a `S#` instead if possible:

{{{ #!hs -- | 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 where v = indexIntArray# mb# 0# toSmall (J# -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#) }}}

And replaces a couple of `J#`-constructions which are likely to produce a `S#`-fitting `Integer`. A `nofib` comparison for vanilla GHC HEAD vs patched GHC HEAD is attached for further discussion.

New description: In the course of a recent [[http://www.reddit.com/r/haskell/comments/1twtvm/the_problem_with_integer/|recent reddit discussion]] it was highlighted, that `integer-gmp` doesn't try to demote `J#` result-values to the more efficient `S#` even though they would fit into a machine word. The attached proof-of-concept patch introduces a "smart" `J#` constructor which constructs a `S#` value instead (if possible): {{{ #!hs -- | 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 where v = indexIntArray# mb# 0# toSmall (J# -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#) }}} The patch replaces a couple of `J#`-invocations which are likely to produce a `S#`-fitting `Integer`. A `nofib` comparison for vanilla GHC HEAD vs. patched GHC HEAD is attached for further discussion. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8638#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8638: Optimize by demoting "denormalized" Integers (i.e. J# -> S#) --------------------------------------------+------------------------------ Reporter: hvr | Owner: hvr Type: feature request | Status: infoneeded Priority: normal | Milestone: 7.8.1 Component: libraries (other) | Version: 7.7 Resolution: | 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: --------------------------------------------+------------------------------ Changes (by simonpj): * status: patch => infoneeded Comment: Interesting. In general it seems like a good idea. Although making the test has a cost, if you get a win, it's a big win. I'd first like to know why `mandel` started allocating nearly 50% more store. (I use `-ticky` for answering this kind of question.) Maybe investigating that will show how the patch can be improved further. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8638#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8638: Optimize by demoting "denormalized" Integers (i.e. J# -> S#) --------------------------------------------+------------------------------ Reporter: hvr | Owner: hvr Type: feature request | Status: infoneeded Priority: normal | Milestone: 7.8.1 Component: libraries (other) | Version: 7.7 Resolution: | 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: --------------------------------------------+------------------------------ Comment (by hvr): Replying to [comment:4 hvr]:

I'm not sure yet why `mandel` allocates more as I couldn't see find any significant use of `Integer`s in the implementation. After some profiling I found out that swapping out the implementation of `magnitude` inside `Mandel.diverge` with a more naive one had a ''huge'' effect on the allocation.

Ok, found the culprit; `magnitude` uses `scaleFloat` which in turn uses `decodeFloat`/`encodeFloat`. I removed the `smartJ#` I put into `decodeFloat` and the allocation-delta for the `mandel`-benchmark went back to more or less 0. As the main purpose of `decodeFloat` seems to be to be used in combination with `encodeFloat` I guess there's actually little benefit trying to demote the significant to `S#` anyway... I'll attach the new nofib report shortly. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8638#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8638: Optimize by demoting "denormalized" Integers (i.e. J# -> S#) --------------------------------------------+------------------------------ Reporter: hvr | Owner: hvr Type: feature request | Status: patch Priority: normal | Milestone: 7.8.1 Component: libraries (other) | Version: 7.7 Resolution: | 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: --------------------------------------------+------------------------------ Comment (by simonpj): Great. Now, what's happening in `symalg` and `kahan` (+4.7 and 6.7% resp)? Working on these small deltas seems tiresome, but what is a small delta in one program can be a massive one in another. It's not that we must have uniform improvement; just that we like to know ''why'' something gets worse, and deem it an acceptable compromise. What is puzzling to me is that I don't think `smartJ#` does ''any'' allocation (apart from its result) so I don't see why allocation should ever increase. Thanks Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8638#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8638: Optimize by demoting "denormalized" Integers (i.e. J# -> S#) --------------------------------------------+------------------------------ Reporter: hvr | Owner: hvr Type: feature request | Status: infoneeded Priority: normal | Milestone: 7.8.1 Component: libraries (other) | Version: 7.7 Resolution: | 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: --------------------------------------------+------------------------------ Comment (by hvr): Replying to [comment:7 simonpj]:

Great. Now, what's happening in `symalg` and `kahan` (+4.7 and 6.7% resp)?

Thunks are happening... (see below)

What is puzzling to me is that I don't think `smartJ#` does ''any'' allocation (apart from its result) so I don't see why allocation should ever increase.

...because I missed the fact that `(# smartJ# ... , smartJ# ... #)` creates a thunk (there was even a source code comment about that pitfall in `quotRemInteger#`) However, I replaced all `smartJ#`-in-`(#,#)` occurences (incl. `decodeDouble`) by `let !x = smartJ# ... in (# x, ... #)` constructs, and the results look better now: {{{ 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% }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8638#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8638: Optimize by demoting "denormalized" Integers (i.e. J# -> S#) --------------------------------------------+------------------------------ Reporter: hvr | Owner: hvr Type: feature request | Status: patch Priority: normal | Milestone: 7.8.1 Component: libraries (other) | Version: 7.7 Resolution: | 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: --------------------------------------------+------------------------------ Comment (by simonpj): Terrific, thanks. I'll commit. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8638#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler