Re: Additional memory handler features.
Marc Glisse marc.gli...@inria.fr writes:
Er, people have been using the custom allocators for (possibly
imperfect) recovery on allocation failure for years. PPL's configure
script complains if gmp was compiled without -fexceptions for that
reason. Apparently SWI-Prolog uses longjmp
(http://stackoverflow.com/a/14245611/1918193).
Ok, good to hear about some examples. We ought to investigate these
before deciding what to do to improve error recovery hooks.
Although itch/scratch may force a compromise between overestimating
the space required or spending too long estimating it, which I hope
won't penalize small numbers too much.
I think a typical itch function will look like
mp_size_t
foo_itch (mp_size_t n)
{
if (LIKELY (BELOW_THRESHOLD (n, FOO_THRESHOLD)))
return n; /* Or possibly zero or some other constant */
else
... something possibly more complicated, perhaps
a full synthetic computation ...
}
So it's a function call (I think we usually want to avoid macros here),
but for small operands it's just the function call overhead and a
well-predicted branch.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: Additional memory handler features.
On Sun, 4 Jan 2015, Victor Shoup wrote: 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 general idea is to push all operations that may fail or otherwise require customization to user code. There would be a function mpn_mul_itch that would tell you how much temporary (scratch) space mpn_mul may need, and mpn_mul would take as argument a pointer to a buffer of at least this size. Allocation is the user's responsibility. There should already be a few functions or macros with itch in their name. [FULL DISCLOSURE: my own, somewhat narrow and selfish goal is to see GMP's mpn-level routines throw exceptions, rather than abort, with no interface changes. This is what would work best for my own NTL library] mpn functions have few reasons to abort. Except for allocation failure, as long as you checked the operands before passing them to GMP... [And yet another issue: my understanding is that some OS's actually have rather weird ways of dealing with out-of-memory errors: malloc always succeeds and returns a non-null pointer, but indirecting through that pointer may abort the program. In such a setting, all of this memory-related error handling stuff is pointless] Yes. Memory overcommit can often be disabled or mitigated in various ways, but it does complicate things (get a better OS ;-) -- Marc Glisse ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: Additional memory handler features.
Victor Shoup sh...@cs.nyu.edu writes: First, it seems to me that Marc's example of custom allocators can perhaps best be viewed as a work-around of GMP's lack of proper error handling. So one should be careful not to conflate error handling with memory management. Maybe. Nevertheless, I'll focus on the handling of allocation failures below. So let's ignore custom memory allocators for a minute, and just think about error handling. There are just a few viable approaches: 1) abort with error message (current approach) 2) return codes (the traditional C approach) 3) C++ exceptions 4) longjump My take is that (1) is a reasonable default behaviour. (2) is probably a too big interface change (even if one realizes that applications using default allocators, which abort on failure, doesn't need to check the return values). As for (3) and (4), I'd prefer to not have gmp make this choice. But defer to the custom allocation functions (and any other exception function pointer for other types of errors) if it wants to abort, or longjmp, or raise some type of exception. I think we should also keep in mind other types of exceptions than those provided by C++, e.g., guile exceptions or objc exceptions. I'd strongly prefer if we can define an interface for error handling and clean up temporary storage which works fine if gmp is compiled as plain C, and is language agnostic, e.g., based on memory pools. But if that turns out to be too difficult, I guess it's not too unreasonable to have proper cleanup on C++ exceptions require that gmp is compiled with a C++ compiler. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: Additional memory handler features.
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. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: Additional memory handler features.
On 5 Jan 2015, at 10:08 am, Niels Möller ni...@lysator.liu.se wrote: 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. Another downside is the additional overhead in the case of very small operands. david ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: Additional memory handler features.
On 2015-01-04 11:41:02 -0500, Victor Shoup wrote: So let's ignore custom memory allocators for a minute, and just think about error handling. There are just a few viable approaches: 1) abort with error message (current approach) 2) return codes (the traditional C approach) 3) C++ exceptions 4) longjump Approach (2) would require changes to the current interface. For functions that currently return void, one could just make them return int, and so this would be a fairly minor change. But there are presumably some functions that already return a non-void value, and so this would not work for such functions. Another issue is that clients would now have to constantly check these return codes -- failure to do so is even worse than approach (1). An alternate approach to (2) would be to have objects (mpz_t, mpq_t, mpf_t...) that can contain error values. For the usual arithmetic operations, the clients would not really need to do any check since error values would propagate. This would be a bit like NaN for floating-point values (except that the error would not come from the values of the arguments, but from limitations of the environment). Of course, the clients would need to be careful with operations that cannot propagate the error (comparisons, some conversions...). -- Vincent Lefèvre vinc...@vinc17.net - Web: https://www.vinc17.net/ 100% accessible validated (X)HTML - Blog: https://www.vinc17.net/blog/ Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon) ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: Additional memory handler features.
I completely agree with Niel's assessment of Victor's options (1) - (4) for handling errors. Recall the following from Torbjörn's original post: There are real scenarios where one would want different sets of allocation functions. E.g., many libraries use GMP. Some of them have their own error reporting mechanisms, and memory handles. But then the user might use GMP directly, or she might from the same program use several libraries which use GMP. The current GMP memory allocation mechanism is not suitable here. Correct. Single global pointer -- bothersome to share in a multi-library context, impossible to share in a multi-library + multi-threaded context. [Torbjörn] I am not too fond of these global pointers. It would be better design to refer the memory handling and error handling functions from each GMP user variable, akin to object oriented languages' vtables. Except that this would make these small structures 3 times larger. ... That would cost a lot in cache load for applications which e.g. use arrays of GMP numbers. I use large (potentially huge) arrays of GMP numbers, and would suffer greatly from such a design choice. This is why I entered the discussion. This is a poor resource utilization trade-off -- i.e., making these objects 3 times larger for functionality that is executed very rarely (if at all) in normal operation. It is still a poor trade-off at 25% overhead, and perhaps even at 4 bits if the main functionality suffers too much. [Niels] I think we should also keep in mind other types of exceptions than those provided by C++, e.g., guile exceptions or objc exceptions. I'd strongly prefer if we can define an interface for error handling and clean up temporary storage which works fine if gmp is compiled as plain C, and is language agnostic, e.g., based on memory pools. But if that turns out to be too difficult, I guess it's not too unreasonable to have proper cleanup on C++ exceptions require that gmp is compiled with a C++ compiler. I agree completely. While I do not mind compiling GMP as C++ code, I vigorously reject the recent suggestion of migrating GMP toward a C++ only code base. There is too much C code out there that uses GMP, mine included. Although it is relatively simple for C++ to call a C library, the reverse is indescribably ugly, difficult and non-portable. [Niels] I'd strongly prefer if we can define an interface for error handling and clean up temporary storage which works fine if gmp is compiled as plain C, and is language agnostic... Consider my dynamically scoped exception handler example -- upon further reflection, I realize that it is possible to implement this completely outside of GMP using only a single static function pointer that GMP invokes to report exceptions. This would even work in a multi-threaded context. [The handler record resides in the application's stack frame, and the signal raising/propagation loop resides in the application's handler function invoked via pointer from GMP.] The reason you would want to build it all into GMP is to address Torbjörn's several libraries requirement. If this is built into GMP, then every well-behaved library that uses GMP will choose to receive exceptions using dynamically-scoped handlers, and the handler of last resort can/should be set by the top-level application. This works well even in contexts that are both multi-library and multi-threaded. If you don't build it into GMP, there would be no standard for libraries and applications to adhere to and each library would still fight over the global function pointer -- and it wouldn't work at all if you add multiple threads to the mix. The cost of this mechanism (both in space and time) yields an efficient utilization of resources, especially for a mechanism that is almost never used under normal conditions. One piece missing from my example code: a GMP longjmp cleanup function that takes a prospective jmp_buf * as an argument. It would perform cleanup / popping of both the stack temporaries, and pop any intervening handler records (while possibly delivering unwind-protect exceptions) from the dynamic chain. Applications could call this before doing longjmp(). It would take care of the platform-dependent problem of choosing how far to traverse/pop each chain (TMP_ALLOC and exception). Details of what to pass to the handler (and how) are an independent issue. A proposal, based on Unix/Linux signal handler interface: - An integer code indicating the type of exception (#define's in gmp.h). - A pointer to the struct gmp_exception_handler_record whose handler is being invoked (NULL when invoking the static pointer handler). The user can embed her gmp_exception_handler_record inside of a larger structure in the stack frame. The handler can know this and use it to gain access to arbitrary local state -- even cleanup when handling unwind-protect exceptions. - A void * pointer to info provided by the
Re: Additional memory handler features.
On 2015-01-04 23:17:16 +, David Harvey wrote: On 5 Jan 2015, at 10:08 am, Niels Möller ni...@lysator.liu.se wrote: 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. Another downside is the additional overhead in the case of very small operands. It depends on how this is implemented. For very small arguments, the memory could be taken from the stack and the pointer to the scratch area could be ignored. Ideally the whole code could be inlined in such a case, reducing even more the overhead. -- Vincent Lefèvre vinc...@vinc17.net - Web: https://www.vinc17.net/ 100% accessible validated (X)HTML - Blog: https://www.vinc17.net/blog/ Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon) ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
