How large are arbitrarily large integers? (Was Re: Bitfield subtlety)

[Richard Biener]

On Thu, 29 Mar 2018, Torbjörn Granlund wrote:

> Richard Biener <rguenther at suse.de> writes:
> 
>   You can also steal low-order bits from the pointer depending on
>   alignment...  and depending on the host also some high-order bits.
> 
> I will resist those temptations.  :-)
> 
> (I have contemplates using the 2-3 low point bits for some other
> purposes, most likely to track used allocators.  But I don't think that
> will happen.)
> 
>   You can also simply off-load the allocation size to the allocated
>   area (like to *(size_t)(_mp_d - 8)).  In fact you are already breaking
>   the ABI in some sort by re-purposing fields given that the internals
>   of __mpz_struct is exposed.
> 
> Unfortunately, while that would be desirable, I have the feeling that it
> is not 100% portable.

I would be surprised if that wouldn't work everywhere - any reason
you have doubts?  To clarify, allocation would work like

 void *ptr = malloc (... + sizeof (size_t));
 ->_mp_d = (char *)ptr + sizeof (size_t);
 size_t *size = ptr;

if you think the pointer arithmetic on _mp_d is problematic you can
always go through uintptr_t ...

>   Not sure if you are already doing small-numbers optimization like
>   avoiding any allocation for size == 1 by re-purposing _mp_d as
>   the single allocated limb (where the size of _mp_d makes this possible).
> 
> We don't do that, no.
> 
>   2TiB is not unheard of - but my immediate followup question would be
>   why the storage needs to be in RAM?  Why can't mpz operate on offline
>   storage like large SSDs?
> 
> Too poor memory locality of the current large operand multiply.

Ah, ok.

Richard.

-- 
Richard Biener <rguenther at suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)