On Mon, Jan 5, 2015 at 12:08 AM, Niels Möller <ni...@lysator.liu.se> wrote: > Victor Shoup <sh...@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 _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
