I just noticed this in
https://gcc.gnu.org/gcc-5/changes.html
# A new set of built-in functions for arithmetics with overflow checking has been added: |__builtin_add_overflow|, |__builtin_sub_overflow| and |__builtin_mul_overflow| and for compatibility with clang also other variants. These builtins have two integral arguments (which don't need to have the same type), the arguments are extended to infinite precision signed type, |+|, |-| or |*| is performed on those, and the result is stored in an integer variable pointed to by the last argument. If the stored value is equal to the infinite precision result, the built-in functions return |false|, otherwise |true|. The type of the integer variable that will hold the result can be different from the types of the first two arguments. The following snippet demonstrates how this can be used in computing the size for the |calloc| function:
void * calloc (size_t x, size_t y) { size_t sz; if (__builtin_mul_overflow (x, y, &sz)) return NULL; void *ret = malloc (sz); if (ret) memset (res, 0, sz); return ret; }
On e.g. i?86 or x86-64 the above will result in a |mul| instruction followed by a jump on overflow.
Maybe we can exploit this to improve the speed of bignum arithmetic.
Brad
Afficher les réponses par date
What kind of speedup are we talking, like approx % on + - % * for bignum integers and bignum rationals, of size ~10^25/~10^25?
For bignum rationals I guess GCD calculation is what really the heaviest work; will this make GCD calculation faster too?
2015-01-18 2:49 GMT+05:30 Bradley Lucier lucier@math.purdue.edu:
I just noticed this in
https://gcc.gnu.org/gcc-5/changes.html
A new set of built-in functions for arithmetics with overflow checking has been added: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow and for compatibility with clang also other variants. These builtins have two integral arguments (which don't need to have the same type), the arguments are extended to infinite precision signed type, +, - or * is performed on those, and the result is stored in an integer variable pointed to by the last argument. If the stored value is equal to the infinite precision result, the built-in functions return false, otherwise true. The type of the integer variable that will hold the result can be different from the types of the first two arguments. The following snippet demonstrates how this can be used in computing the size for the calloc function:
void * calloc (size_t x, size_t y) { size_t sz; if (__builtin_mul_overflow (x, y, &sz)) return NULL; void *ret = malloc (sz); if (ret) memset (res, 0, sz); return ret; }
On e.g. i?86 or x86-64 the above will result in a mul instruction followed by a jump on overflow.
Maybe we can exploit this to improve the speed of bignum arithmetic.
Brad
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On 02/23/2015 01:10 PM, Mikael wrote:
What kind of speedup are we talking, like approx % on + - % * for bignum integers and bignum rationals, of size ~10^25/~10^25?
Well, it might double the speed of bignum addition/subtraction, but I'm not sure how much multiplication or division would benefit.
It might speed up safe fixnum operations, too, perhaps by a factor of two.
Brad
-
Bradley Lucier -
Mikael