Has there been historical work done to investigate small integer optimization?

[Richard Biener]

On Mon, 12 Feb 2024, Richard Biener wrote:

> On Mon, 12 Feb 2024, Torbj?rn Granlund wrote:
> 
> > marco.bodrato at tutanota.com writes:
> > 
> >   But implementing it with the current mpz type is "impossible".
> >   I mean, one should break the current interface.
> >   Currently, _mp_d is always a pointer AND it always point to a readable limb. Even if _mp_alloc is zero.
> > 
> > If we set alloc = 0 and size >= 2^30, then that means the the pointer
> > field is actually a numeric value, and perhaps the low 30 bits of the
> > size field is more bits for the numeric value.  :-)
> 
> Since both _mp_alloc is signed _mp_alloc < 0 could indicate an inline
> limb, you can then declare _mp_size irrelevant, fixed to one limb
> plus 2 * sizeof (int) * 8 - 1 bits.  Though that missing bit is
> likely going to be awkward (also the position of the sign-bit given
> endianesses).

Oh, and _mp_alloc < 0 could also simply mean the allocation is
"inline", aka

typedef struct
{
  int _mp_alloc;                /* Number of *limbs* allocated and pointed
                                   to by the _mp_d field.  */
  int _mp_size;                 /* abs(_mp_size) is the number of limbs 
the
                                   last field points to.  If _mp_size is
                                   negative this is a negative number.  */
  union {
     mp_limb_t *_mp_d;             /* Pointer to the limbs.  */
     mp_limb_t _mp_inline_limbs[]; /* Inline limbs if _mp_alloc < 0.  */
  };
} __mpz_struct;

you could then no longer pass such __mpz_struct by value though but
it would allow on-stack allocations of (small) temporary __mpz_struct
using alloca.

Richard.