These are chat archives for symengine/symengine

4th
Nov 2015
Ralf Stephan
@rwst
Nov 04 2015 14:27
I just read in the Flint docs that fmpz_t is claimed to be more efficient than GMP's mpz_t in that it is faster for 1-limb numbers, that it only allocates limbs when needed, and other things. Has anyone compared?
Isuru Fernando
@isuruf
Nov 04 2015 15:56
@rwst, see symengine/symengine#477. @certik might have some numbers
Ondřej Čertík
@certik
Nov 04 2015 17:02
@rwst fmpz_t is either a (64bit) pointer to an allocated mpz_t or a (64bit) machine integer itself. Since a pointer has to be at least power of 2 aligned (typically it is aligned on 64bit or even up to 256bit boundary), so the highest bit is never used in the pointer (i.e. it must be 0), and so you use it to determine if the 64bits is a pointer or a machine integer. It's a nice trick. However, it has a double indirection if it is not a machine integer. piranha::integer is using an alternative approach, I think it's size is at least 128bit or more, and it is just a union. So the mpz_t type is directly in the memory, so it has only one indirection, but the price is that the piranha::integer type is larger than 64bit. Another difference is that fmpz_t is using a 64bit integer, while piranha::integer is using 128bit integer --- this choice has pros and cons: if your integers fit into 64bits, then 64bit is faster. If they fit into 128bit, then 128bit is a lot faster than mpz_t. If they are larger than 128bit, then it doesn't matter. @bluescarni did some benchmarking and concluded that for the applications that he needed, the 128bit version was faster overall. Either way, I think we can (or perhaps should) have more than just 1 type for integer, and the user would choose which one to use for the given application.
This is another motivation why I wanted to write our own class for GMP in #478, since if we keep it simple, we can then implement this small integer optimization quite easily.