Pointer-or-Int 63-bit representations for Integer

[Sylvain Henry]

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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20210308/74be22c2/attachment.html>