Additional memory handler features.

[Fredrik Johansson]

On Mon, Jan 5, 2015 at 12:08 AM, Niels Möller <nisse at lysator.liu.se> wrote:
> Victor Shoup <shoup at cs.nyu.edu> writes:
>
>> But I see mention of itching and scratching: could somebody
>> describe what that is or provide a link? Sorry for my ignorance.
>> ....and sorry for the length of this post....
>
> The idea is that instead of having gmp allocate temporary storage, it
> should have a function to tell how much temporary storage is needed for
> each operation, and then let the application allocate that anyway it
> please, and pass it as an additional argument. So instead of
>
>   mpn_mul (rp, ap, an, bp, bn);
>
> one would do something like
>
>   mp_limb_t *scratch = xalloc (sizeof(mp_limb_t) * mpn_mul_itch (an, bn));
>   mpn_mul (rp, ap, bn, bp, bn, scratch);
>   free (scratch);
>
> For convenience, higher level functions could allow a NULL scratch
> argument, and allocate temporary storage using registered gmp allocation
> functions.
>
> All this applies to mpn functions only.
>
> There are several motivations for this type of interface:
>
> 1. For low-level mpn loops, this helps eliminate the frame pointer,
>    making one more register available. (Functions using alloca need a
>    frame pointer).
>
> 2. For higher-level functions, it may help reuse temporary storage,
>    reducing the total storage need of GMP.
>
> 3. It should make it possible for applications to allocate temporary
>    storage up front. E.g., when a cryptographic application initializes
>    a key, it may allocate up front all temporary storage needed for
>    operations using that key, so that later operations can never fail
>    for memory allocation reasons. Even static allocation may be possible
>    in some cases.
>
> Of course there are also some drawbacks. It makes life more complicated
> for applications, and the implementation of functions like mpn_mul_itch,
> which interact with pretty complex algorithm choice machinery, is going
> to be a bit complex too.

How would this work with functions that allocate a variable amount of
memory depending on the values of the inputs? Wouldn't you always have
to allocate for the worst case?

An example would be mpn_perfect_square_p, which "excludes 212/256
(82.8%) of the perfect square candidates in O(1) time".

Fredrik