hash of mpz_t and mpq_t

[Hans Åberg]

> On 17 Jun 2021, at 17:21, Marco Bodrato <bodrato at mail.dm.unipi.it> wrote:
> 
> Il 2021-06-17 10:32 Hans Åberg ha scritto:
>>> On 16 Jun 2021, at 22:54, Marco Bodrato <bodrato at mail.dm.unipi.it> wrote:
> 
>>> namespace std {
>>> template<> struct hash<gmp::integer> {
>>>   size_t operator()(gmp::integer const& x) const {
>>>     std::size_t h = std::hash<mp_size_t>()(x.value_->_mp_size);
>>>     for (mp_size_t i = 0; i < mpz_size(x.value_); ++i)
>>>       h ^= std::hash<mp_limb_t>()(mpz_getlimbn(x.value_, i));
>>>     return h;
>>>   }
>>> };
>>> } // namespace std
> 
>> But one still has to call _mp_size, underneath the API.
> 
> You are right, one should use mpz_sgn(X) < 0 ? -mpz_size(X) : mpz_size(X) , instead.
> 
> It might seem too complex, …

Conditions can be expensive on piped CPUs.

> but a modern gcc is able to understand what we mean and compile the right thing.
> 
> $ cat foo.c
> #include "gmp.h"
> 
> size_t foo (mpz_t z)
> {
>  return mpz_sgn(z) < 0 ? -mpz_size(z) : mpz_size(z);
> }
> $ gcc-9 -fverbose-asm -O2 foo.c -S -o foo.S
> $ grep -v "# -" foo.S
> 	.file	"foo.c"
> # GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
> # options passed:  -imultiarch x86_64-linux-gnu foo.c -mtune=generic
> # options enabled:  -fPIC -fPIE -faggressive-loop-optimizations
> 
> 	.text
> 	.p2align 4
> 	.globl	foo
> 	.type	foo, @function
> foo:
> .LFB20:
> 	.cfi_startproc
> 	endbr64
> # foo.c:5:   return mpz_sgn(z) < 0 ? -mpz_size(z) : mpz_size(z);
> 	movslq	4(%rdi), %rax	# z_4(D)->_mp_size, z_4(D)->_mp_size
> # foo.c:6: }
> 	ret
> 	.cfi_endproc
> .LFE20:
> 	.size	foo, .-foo
> 	.section	.note.GNU-stack,"", at progbits
> 	.section	.note.gnu.property,"a"
> 	.align 8
> 	.long	 1f - 0f
> 	.long	 4f - 1f
> 	.long	 5
> 0:
> 	.string	 "GNU"
> 1:
> 	.align 8
> 	.long	 0xc0000002
> 	.long	 3f - 2f
> 2:
> 	.long	 0x3
> 3:
> 	.align 8
> 4:
> 
> As you can see form the lines
> 
> # foo.c:5:   return mpz_sgn(z) < 0 ? -mpz_size(z) : mpz_size(z);
> 	movslq	4(%rdi), %rax	# z_4(D)->_mp_size, z_4(D)->_mp_size
> 
> the seemingly complex expression was compiled as a simple access to the relevant field of the structure.

Even though modern compilers are pretty aggressive in optimizations, it would be better to having rely on that.