Pointer-or-Int 63-bit representations for Integer
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...), 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 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
For what it's worth, Ocaml uses the fact that pointers are word-aligned (hence even numbers) to let the gc distinguish between unboxed values and pointers: 63-bit integers are made odd by representing n as (2n+1). But GHC also makes use of the word-alignment of pointers: it is used for pointer tagging [ https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/haskell-execution/... ]. The tag is, for a closure that has been forced, a representation of its constructor (only the 7 first constructors can be so tagged, if I understand correctly). This is an optimisation for pattern matching: you don't have to run the closure's entry code every time you pattern-match. The bottom-line is that it can't be true, in GHC, that odd values are unboxed and even values are pointers, since odd pointers already exist. Not sure whether the optimisation can be recovered. Best, Arnaud
On Mon, Mar 8, 2021, at 5:41 PM, Spiwack, Arnaud wrote:
For what it's worth, Ocaml uses the fact that pointers are word-aligned (hence even numbers) to let the gc distinguish between unboxed values and pointers: 63-bit integers are made odd by representing n as (2n+1).
But GHC also makes use of the word-alignment of pointers: it is used for pointer tagging [ https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/rts/haskell-execution/... ]. The tag is, for a closure that has been forced, a representation of its constructor (only the 7 first constructors can be so tagged, if I understand correctly). This is an optimisation for pattern matching: you don't have to run the closure's entry code every time you pattern-match.
The bottom-line is that it can't be true, in GHC, that odd values are unboxed and even values are pointers, since odd pointers already exist. Not sure whether the optimisation can be recovered.
Best, Arnaud
I see, thanks for the pointer (tee hee!). Seems like that real-estate is already used up in the runtime's representation. I replied to the thread just now a mildly interesting result with unboxed sums prior to reading this. Seems like a potentially fun avenue for someone with more time. Cheers, Chris
Hi all, I did a trivial test, in case anybody's interested, in the unboxed sum idea approach, only considering the Int# branch. https://gist.github.com/chrisdone/6aef640a49fc30b45ad210eac287dce9 It seems to be on par with Int, which is pretty cool because I wasn't sure what to expect. Assuming I didn't make a horrible mistake. `B = 272.2 μs` `Int = 270.9 μs ` `Integer = 7.860 ms ` Cheers, Chris
The suggestion discussed by John Meacham http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010670.ht..., Lennart Augustsson http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010664.ht..., Simon Marlow http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010677.ht... and Bulat Ziganshin http://www.haskell.org/pipermail/glasgow-haskell-users/2006-August/010687.ht... 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
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 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... https://hackage.haskell.org/package/integer-gmp-1.0.3.0/docs/src/GHC.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
participants (4)
-
chris done -
Chris Done
-
Spiwack, Arnaud -
Sylvain Henry