3 ms·

I am just curiosu why gcc's __int128 is that faster than GMP.

by chenzhekl 11y ago

api 11y ago
A few inline instructions vs a library call.
tacos 11y ago
GMP is arbitrary precision. __int128 on a 64 bit processor is optimized for one size.
- jmgao 11y ago
  It's actually even better than that. They're only using __int128 to hold the result of a 64 by 64 bit multiplication, and x86_64's mul instruction will give you this for free. gcc is smart enough to generate code that is literally just a single mul.
fdej 11y ago
Because GMP is designed for arbitrary size integers, and for safety. Given two mpz_t operands to multiply, it needs, in some order, to: * Dereference pointers * Extract the signs of both input operands * Extract the sizes (number of limbs) of both input operands * Check whether the output variable has enough space for the result, and otherwise, reallocate it * Check whether the output operand is the same object in memory as either input, and in that case allocate temporary scratch space and make a copy of the data (since the multiplication algorithm doesn't allow aliasing) * Decide which multiplication algorithm to use (different algorithms are optimal for different sizes) * Call the chosen multiplication algorithm * In the multiplication algorithm, loop over the variable numbers of limbs * Actually perform the arithmetic operations in the multiplication * Normalize the resulting size by checking whether the top limb of the output is nonzero * Write the sign and size of the result to the output variable In addition, mpz_t variables need to malloc and free every time they are created and destroyed. This is not so much a concern in practice, because optimizing programmers will reuse variables as much as possible. (However, some language wrappers don't reuse GMP variables, and are unnecessarily slow as a result.) You can use GMP's internal functions if you want faster arithmetic and either know that overflow cannot occur or want to do overflow checking manually. For example, if z, x and y are pairs of 64-bit integers, not aliased with each other, then mpn_mullo_basecase(&z, &x, &y, 2) does a 128-bit multiplication (mod 2^128). Depending on the platform, using mpn_mul_basecase to compute the full product with some scratch space might be faster. This kind of code should generally be faster than calling the general and safe function mpz_mul, though it will still have a few cycles of overhead for the function call and looping. For integers up to a few hundred bits, inlined fixed-size code is always going to be faster.

I am just curiosu why gcc's __int128 is that faster than GMP.

api 11y ago

A few inline instructions vs a library call.

tacos 11y ago

GMP is arbitrary precision. __int128 on a 64 bit processor is optimized for one size.

jmgao 11y ago
It's actually even better than that. They're only using __int128 to hold the result of a 64 by 64 bit multiplication, and x86_64's mul instruction will give you this for free. gcc is smart enough to generate code that is literally just a single mul.

fdej 11y ago

Because GMP is designed for arbitrary size integers, and for safety. Given two mpz_t operands to multiply, it needs, in some order, to: * Dereference pointers * Extract the signs of both input operands * Extract the sizes (number of limbs) of both input operands * Check whether the output variable has enough space for the result, and otherwise, reallocate it * Check whether the output operand is the same object in memory as either input, and in that case allocate temporary scratch space and make a copy of the data (since the multiplication algorithm doesn't allow aliasing) * Decide which multiplication algorithm to use (different algorithms are optimal for different sizes) * Call the chosen multiplication algorithm * In the multiplication algorithm, loop over the variable numbers of limbs * Actually perform the arithmetic operations in the multiplication * Normalize the resulting size by checking whether the top limb of the output is nonzero * Write the sign and size of the result to the output variable In addition, mpz_t variables need to malloc and free every time they are created and destroyed. This is not so much a concern in practice, because optimizing programmers will reuse variables as much as possible. (However, some language wrappers don't reuse GMP variables, and are unnecessarily slow as a result.) You can use GMP's internal functions if you want faster arithmetic and either know that overflow cannot occur or want to do overflow checking manually. For example, if z, x and y are pairs of 64-bit integers, not aliased with each other, then mpn_mullo_basecase(&z, &x, &y, 2) does a 128-bit multiplication (mod 2^128). Depending on the platform, using mpn_mul_basecase to compute the full product with some scratch space might be faster. This kind of code should generally be faster than calling the general and safe function mpz_mul, though it will still have a few cycles of overhead for the function call and looping. For integers up to a few hundred bits, inlined fixed-size code is always going to be faster.