#8647: Reduce allocations in `integer-gmp` --------------------------------------------+------------------------------ Reporter: hvr | Owner: Type: task | Status: patch Priority: normal | Milestone: 7.8.1 Component: libraries (other) | Version: 7.6.3 Resolution: | Keywords: integer- Operating System: Unknown/Multiple | gmp Type of failure: Runtime performance bug | Architecture: x86_64 Test Case: | (amd64) Blocking: | Difficulty: Unknown | Blocked By: | Related Tickets: #8638 --------------------------------------------+------------------------------ Comment (by Herbert Valerio Riedel <hvr@…>): In [changeset:"7bdcadda7e884edffb1427f0685493f3a2e5c5fa/integer-gmp"]: {{{ #!CommitTicketReference repository="integer-gmp" revision="7bdcadda7e884edffb1427f0685493f3a2e5c5fa" Allocate initial 1-limb mpz_t on the Stack and introduce MPZ# type We now allocate a 1-limb mpz_t on the stack instead of doing a more expensive heap-allocation (especially if the heap-allocated copy becomes garbage right away); this addresses #8647. In order to delay heap allocations of 1-limb `ByteArray#`s instead of the previous `(# Int#, ByteArray# #)` pair, a 3-tuple `(# Int#, ByteArray#, Word# #)` is returned now. This tuple is given the type-synonym `MPZ#`. This 3-tuple representation uses either the 1st and the 2nd element, or the 1st and the 3rd element to represent the limb(s) (NB: undefined `ByteArray#` elements must not be accessed as they don't point to a proper `ByteArray#`, see also `DUMMY_BYTE_ARR`); more specifically, the following encoding is used (where `⊥` means undefined/unused): - (# 0#, ⊥, 0## #) -> value = 0 - (# 1#, ⊥, w #) -> value = w - (# -1#, ⊥, w #) -> value = -w - (# s#, d, 0## #) -> value = J# s d The `mpzToInteger` helper takes care of converting `MPZ#` into an `Integer`, and allocating a 1-limb `ByteArray#` in case the value (`w`/`-w`) doesn't fit the `S# Int#` representation). The following nofib benchmarks benefit from this optimization: Program Size Allocs Runtime Elapsed TotalMem ------------------------------------------------------------------ bernouilli +0.2% -5.2% 0.12 0.12 +0.0% gamteb +0.2% -1.7% 0.03 0.03 +0.0% kahan +0.3% -13.2% 0.17 0.17 +0.0% mandel +0.2% -24.6% 0.04 0.04 +0.0% power +0.2% -2.6% -2.0% -2.0% -8.3% primetest +0.1% -17.3% 0.06 0.06 +0.0% rsa +0.2% -18.5% 0.02 0.02 +0.0% scs +0.1% -2.9% -0.1% -0.1% +0.0% sphere +0.3% -0.8% 0.03 0.03 +0.0% symalg +0.2% -3.1% 0.01 0.01 +0.0% ------------------------------------------------------------------ Min +0.1% -24.6% -4.6% -4.6% -8.3% Max +0.3% +0.0% +5.9% +5.9% +4.5% Geometric Mean +0.2% -1.0% +0.2% +0.2% -0.0% Signed-off-by: Herbert Valerio Riedel <hvr@gnu.org> }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8647#comment:13> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler