Re: GMP 6 the incomatible GMP?
Marc Glisse marc.gli...@inria.fr writes: Experimentally (for me, others can have wildly different use cases), what really helps for small nums isn't to save space, it is to not allocate at all, for instance storing a few limbs in the base type and only allocating when that's not enough (recycling storage can work even better, but is for very specific uses and may not make sense for a generic library). There are plans to add a bignum type to the C++ standard, and people are discussing whether it should be part of the specification that constructing small numbers (not even just 0) doesn't use dynamic allocation. Now the target users of this bignum type and GMP are not exactly the same (bignum would be used a lot by people who only need int but want to be safe), so it makes sense if the best solutions differ. I am sure this is often a god idea, perhaps it would be good also in GMP. My main reason for not originally doing it like that is code complexity. Having three operands (thing mpz_add) each with two possible representations, will give some alternative execution paths. Another problem is mpz_t size. It is currently 16 bytes on 64-bit machines (and 12 bytes on on 32-bit machines). Even if only one bit of these bytes are used for typing, we ain't getting much headroom from the remaining 127 and 95 bits, respectively. Making the structures larger is to costly. -- Torbjörn ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: GMP 6 the incomatible GMP?
Most people seem to prefer splitting the alloc data over a field in the structure and a field before mp_d[0], while I think that'd be slower as well as more complex than the floating-point coding I have in mind. My proposal will make allocations somewhat inaccurate, but I'll make sure it is never more that one percent of the allocation. I'll try my proposal at some point, to evaluate its effects. I might need to introduce a few more macros in the process, which should then make it easy to try various other alloc representeation styles. -- Torbjörn ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: GMP 6 the incomatible GMP?
On Tue, 8 Jan 2013, Niels Möller wrote: Marc Glisse marc.gli...@inria.fr writes: Then we might as well always put it in _mp_d[-1], no? IIRC that's what mpfr does. That will increase overhead (both allocation and processing, I think) for small bignums, which may be undesirable. But I don't really know how significant that is. I am not sure about processing. The allocated size is hidden behind the pointer, but you are already dereferencing that pointer anyway, and you are saving on the bit manipulations to separate size from alloc. It does indeed waste a bit of heap space (not sure that's significant), which can also increase the processing in malloc/free. Experimentally (for me, others can have wildly different use cases), what really helps for small nums isn't to save space, it is to not allocate at all, for instance storing a few limbs in the base type and only allocating when that's not enough (recycling storage can work even better, but is for very specific uses and may not make sense for a generic library). There are plans to add a bignum type to the C++ standard, and people are discussing whether it should be part of the specification that constructing small numbers (not even just 0) doesn't use dynamic allocation. Now the target users of this bignum type and GMP are not exactly the same (bignum would be used a lot by people who only need int but want to be safe), so it makes sense if the best solutions differ. -- Marc Glisse ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: GMP 6 the incomatible GMP?
Marc Glisse marc.gli...@inria.fr writes: Then we might as well always put it in _mp_d[-1], no? IIRC that's what mpfr does. I see some problems with that: * There is a serial memory dependency problem, making the allocation check at least one more cache latency away. I don't think OoO execution will be able to hide that, as this is used. * There is a slight type error mixing limbs and sizes. The ASL patch by Per Olofsson will require many limbs to represent a size. But this is a testing feature, which should not get in they way of an otherwise desirable change. -- Torbjörn ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: GMP 6 the incomatible GMP?
From: Torbjorn Granlund t...@gmplib.org Date: Tue, 08 Jan 2013 12:50:01 +0100 Marc Glisse marc.gli...@inria.fr writes: Then we might as well always put it in _mp_d[-1], no? IIRC that's what mpfr does. I see some problems with that: * There is a serial memory dependency problem, making the allocation check at least one more cache latency away. I don't think OoO execution will be able to hide that, as this is used. I don't know how amicable you are to an idea like this, but if user applications can only treat pointers to these objects as opaque then you can encode information in the lowest bits of the pointer. For example, you could encode in the lowest bit whether the _mp_d[-1] thing is being done or not. Then it's at worst a mis-predicted branch in the allocation check. ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: GMP 6 the incomatible GMP?
From: Marc Glisse marc.gli...@inria.fr Date: Wed, 9 Jan 2013 00:14:15 +0100 (CET) PS: thanks a lot for your sparc assembly work! No problem, it's actually fun, like solving sudoku puzzles, for me. ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: GMP 6 the incomatible GMP?
On Tue, 8 Jan 2013, Niels Möller wrote: Torbjorn Granlund t...@gmplib.org writes: The idea is to instead make a 64-bit bitfield of the _mp_size and _mp_alloc fields. One would give _mp_size about 48 bits, and _mp_alloc the remaining 16. The alloc field would lose granularity, but should code small sizes exactly. Hmm. I guess one could go down to only 8 bits or so for the alloc field, and for larger allocations, store the number of allocated limbs at the head of the limb array (in the case limb size is not artificially small, it could be just _mp_d[-1]). Then we might as well always put it in _mp_d[-1], no? IIRC that's what mpfr does. -- Marc Glisse ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
