GMP unboxed number representation

[Marcin 'Qrczak' Kowalczyk]

On Fri, May 04, 2001 at 11:08:59PM +0200, Hans Aberg wrote:

> GMP has a very interesting multi-precision floating number type as
> well, but it has the same problem as the integers: It does not use
> the native double's for small float, so it probably becomes slow.

I think that it's easier to check machine-size int for overflow
than to check double for overflow or loss of precision, so it's
impractical to use native double and keep predictable precision.

> >Indeed. ghc solves it by using gmp format only temporarily to perform
> >operations, and keeping numbers in its own structures.
> 
> Does that mean that you are getting extra memory allocations,

No. When mpz is constructed to perform an operation, _mp_d is set to
point to an already allocated memory on the ghc heap.

Ghc's heap address can generally move during GC. gmp is called from
blocks of C or assembler code which don't cause GC in the middle. Using
persistent mpz objects would require allocation of _mp_d on the C
heap which is slower, and a finalization hook for each Integer (which
would be an additional overhead given the way custom finalization
hooks are implemented).

> Perhaps GMP should provide small number arithmetic, with a fast
> way to determine if the answer fits in a small number representation.

Indeed. Ghc has those primops, used for Integer arithmetic, with
tricky implementations in the case the code is generated via C:

/* -----------------------------------------------------------------------------
 * Int operations with carry.
 * -------------------------------------------------------------------------- */

/* With some bit-twiddling, we can define int{Add,Sub}Czh portably in
 * C, and without needing any comparisons.  This may not be the
 * fastest way to do it - if you have better code, please send it! --SDM
 *
 * Return : r = a + b,  c = 0 if no overflow, 1 on overflow.
 *
 * We currently don't make use of the r value if c is != 0 (i.e. 
 * overflow), we just convert to big integers and try again.  This
 * could be improved by making r and c the correct values for
 * plugging into a new J#.  
 */
#define addIntCzh(r,c,a,b)			\
{ r = a + b;					\
  c = ((StgWord)(~(a^b) & (a^r)))		\
    >> (BITS_IN (I_) - 1);			\
}


#define subIntCzh(r,c,a,b)			\
{ r = a - b;					\
  c = ((StgWord)((a^b) & (a^r)))		\
    >> (BITS_IN (I_) - 1);			\
}

/* Multiply with overflow checking.
 *
 * This is slightly more tricky - the usual sign rules for add/subtract
 * don't apply.  
 *
 * On x86 hardware we use a hand-crafted assembly fragment to do the job.
 *
 * On other 32-bit machines we use gcc's 'long long' types, finding
 * overflow with some careful bit-twiddling.
 *
 * On 64-bit machines where gcc's 'long long' type is also 64-bits,
 * we use a crude approximation, testing whether either operand is
 * larger than 32-bits; if neither is, then we go ahead with the
 * multiplication.
 */

#if i386_TARGET_ARCH

#define mulIntCzh(r,c,a,b)				\
{							\
  __asm__("xorl %1,%1\n\t				\
	   imull %2,%3\n\t				\
	   jno 1f\n\t					\
	   movl $1,%1\n\t				\
	   1:" 						\
	: "=r" (r), "=&r" (c) : "r" (a), "0" (b));	\
}

#elif SIZEOF_VOID_P == 4

#ifdef WORDS_BIGENDIAN
#define C 0
#define R 1
#else
#define C 1
#define R 0
#endif

typedef union {
    StgInt64 l;
    StgInt32 i[2];
} long_long_u ;

#define mulIntCzh(r,c,a,b)			\
{						\
  long_long_u z;				\
  z.l = (StgInt64)a * (StgInt64)b;		\
  r = z.i[R];					\
  c = z.i[C];					\
  if (c == 0 || c == -1) {			\
    c = ((StgWord)((a^b) ^ r))			\
      >> (BITS_IN (I_) - 1);			\
  }						\
}
/* Careful: the carry calculation above is extremely delicate.  Make sure
 * you test it thoroughly after changing it.
 */

#else

#define HALF_INT  (1 << (BITS_IN (I_) / 2))

#define stg_abs(a) ((a) < 0 ? -(a) : (a))

#define mulIntCzh(r,c,a,b)			\
{						\
  if (stg_abs(a) >= HALF_INT			\
      stg_abs(b) >= HALF_INT) {			\
    c = 1;					\
  } else {					\
    r = a * b;					\
    c = 0;					\
  }						\
}
#endif

> So this, in the end, suggests that one perhaps should get a better GMP
> interface for perhaps both small and large number representations. But it
> should then be so that GHC could use that interface, rather than abusing
> its internals.

Yes, except that I'm not sure how much harder for ghc would be to
use a GMP's interface than to do it itself.

BTW, it could be nice to have a better way for writing large integer
literals. Ghc used to convert them from a decimal string, and now it
builds them from pieces by * and + in base 2^31-1 or 2^63-1. Both
approaches are a bit ugly. But probably large integer literals are
not that common for it to matter much.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK