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

[Stefan Koch]

On Mon, Feb 12, 2024 at 7:01 AM Richard Biener <rguenther at suse.de> wrote:
>
> 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.

This was mostly my idea.  I thought that if _mp_alloc was small enough (in
most cases 1), then  instead of _mp_d being the pointer to the first lib it
was just the first limb.

This could be relatively easy to implement.  (That is assuming that the _mp_d
is not part of the public interface.)  In that case the x._mp_d could be
replaced with a macro _mpz_mp_d(x).  Where

#define _mpz_mp_d(x) ((x)._mp_alloc == 1) ? x._mp_inline_limbs : x._mp_d)

Stefan