
<!DOCTYPE html><html><head><title></title><style type="text/css">p.MsoNormal,p.MsoNoSpacing{margin:0}</style></head><body><div>Hi all,<br></div><div><br></div><div>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.<br></div><div><br></div><div>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. <br></div><div><br></div><div>This would need assistance from the GC to be able to recognize said bit flag.<br></div><div><br></div><div>As I understand the current implementation of integer-gimp, they also try to use an Int64 where possible using a constructor (<a href="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</a>), 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:</div><div><br></div><div><a href="https://github.com/haskell-perf/numbers#addition">https://github.com/haskell-perf/numbers#addition</a></div><div><br></div><div>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.<br></div><div><br></div><div>Just pondering.</div><div><br></div><div>Cheers,<br></div><div><br></div><div>Chris</div></body></html>