Hi Chris,
It has been considered in the past. There are some traces in the wiki:
https://gitlab.haskell.org/ghc/ghc/-/wikis/replacing-gmp-notes
>> The suggestion discussed by John Meacham
<http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010670.html>,
Lennart Augustsson
<http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010664.html>,
Simon Marlow
<http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010677.html>
and Bulat Ziganshin
<http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010687.html>
was to change the representation of Integer so the Int# does the work of
S# and J#: the Int# could be either a pointer to the Bignum library
array of limbs or, if the number of significant digits could fit into
say, 31 bits, to use the extra bit as an indicator of that fact and hold
the entire value in the Int#, thereby saving the memory from S# and J#.
It's not trivial because it requires a new runtime representation that
is dynamically boxed or not.
> An unboxed sum might be an improvement? e.g. (# Int# | ByteArray# #)
-- would this "kind of" approximate the approach described? I don't have
a good intuition of what the memory layout would be like.
After the unariser pass, the unboxed sum becomes an unboxed tuple: (#
Int# {-tag-}, Int#, ByteArray# #)
The two fields don't overlap because they don't have the same slot type.
In my early experiments before implementing ghc-bignum, performance got
worse in some cases with this encoding iirc. It may be worth checking
again if someone has time to do it :). Nowadays it should be easier as
we can define pattern synonyms with INLINE pragmas to replace Integer's
constructors.
Another issue we have with Integer/Natural is that we have to mark most
operations NOINLINE to support constant-folding. To be fair benchmarks
should take this into account.
Cheers,
Sylvain
On 08/03/2021 18:13, Chris Done wrote:
Hi all,
In OCaml's implementation, they use a well known 63-bit representation
of ints to distinguish whether a given machine word is either a
pointer or to be interpreted as an integer.
I was wondering whether anyone had considered the performance benefits
of doing this for the venerable Integer type in Haskell? I.e. if the
Int fits in 63-bits, just shift it and do regular arithmetic. If the
result ever exceeds 63-bits, allocate a GMP/integer-simple integer and
return a pointer to it. This way, for most applications--in my
experience--integers don't really ever exceed 64-bit, so you would
(possibly) pay a smaller cost than the pointer chasing involved in
bignum arithmetic. Assumption: it's cheaper to do more CPU
instructions than to allocate or wait for mainline memory.
This would need assistance from the GC to be able to recognize said
bit flag.
As I understand the current implementation of integer-gimp, they also
try to use an Int64 where possible using a constructor
(https://hackage.haskell.org/package/integer-gmp-1.0.3.0/docs/src/GHC.Integer.Type.html#Integer
<https://hackage.haskell.org/package/integer-gmp-1.0.3.0/docs/src/GHC.Integer.Type.html#Integer>),
but I believe that the compiled code will still pointer chase through
the constructor. Simple addition or subtraction, for example, is 24
times slower in Integer than in Int for 1000000 iterations:
https://github.com/haskell-perf/numbers#addition
<https://github.com/haskell-perf/numbers#addition>
An unboxed sum might be an improvement? e.g. (# Int# | ByteArray# #)
-- would this "kind of" approximate the approach described? I don't
have a good intuition of what the memory layout would be like.
Just pondering.
Cheers,
Chris
_______________________________________________
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
_______________________________________________
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
