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