Additional memory handler features.

[David M. Warme]

 > But I'm not ocnvinced this level of granularity makes sense. Which
 > problem does it solve?

Limb arrays have the potential to receive special treatment by the
memory manager.  One critical property of limb arrays is that they
never contain any pointers to other data, and therefore never need
to be accessed by the "mark" phase of a garbage collector.

Another property that can already be exploited, for example, is
space reduction.  The malloc()/free() model requires that the size of
the block being free'd/realloc'd must be inferred solely from the
address of the block.  This usually means that the size of the block
must be stored just before the block returned for use by the
application, causing additional memory space overhead.

This is not necessary for limb arrays because the size of the array is
always explicitly available (via some field in the mpz_t or mpf_t
object).  Good design on the part of the GMP development team
has resulted in the existing GMP custom memory management
function pointers that always explicitly pass the current size, so that
this implicit address-to-size mapping (and its corresponding overhead)
is unnecessary.  Memory managers can already take advantage of the
fact that they don't have to "remember" the size of each block resulting
in space savings, and reap additional improvements in locality and
cache utilization (over what a pure "malloc/free/realloc"
implementation of these would achieve).

For limb arrays "in the wild" (i.e., those that are NOT allocated as
temporaries for use inside of various GMP functions), a memory
manager could also make use of the fact that there is one-and-only-
one permanent reference to each limb array -- namely by the mpz_t
or mpf_t object that "owns" the limb array.  There is a one-to-one
relationship between these.  This property can be exploited by
certain memory management techniques.  For example, the limb
array can be moved to a new address, and only a single reference
need be updated (so long as GMP is not actively using that mpz_t
or mpf_t object).

This may not be the case, however, for temporary limb arrays
that are allocated internally by GMP, used transiently for computational
purposes, and then freed before the corresponding GMP function
returns.  Thus it might be important for the memory manager to be
aware that it is dealing with an internal GMP stack temporary,
rather than a limb array that has a one-to-one relationship with the
mpz_t or mpf_t object that "owns" it.

The other reason concerns memory lifetime.  The stack temporaries
tend to have LIFO behavior with respect to allocation and freeing.
This is another attribute that a memory manager could exploit -- if
indeed it had any way of knowing that the request was for a stack
temporary, rather than for a longer-lived (or less predictably-lived)
object.

One of the difficulties with GMP is that the limb arrays associated
with mpz_t (and therefore mpq_t) objects *never* decrease in
size, unless the user explicitly calls mpz_realloc2().  There is a very
common phenomenon called "intermediate expression swell" in
which the size of intermediate results grow to be very large, even
though the final answer may be very small and very sparse.  This
very common behavior, coupled with GMP's "monotonically
increasing size" behavior means that an application can have some
very large limb arrays lurking about that contain some very small
values (even zero).

One fairly simple thing that a memory manager can do to recover
some additional memory (without increasing the virtual space) is to
simply scan all of the existing mpz_t/mpq_t objects and "right size"
all of their limb arrays to contain their current values, without excess
space.  Once again, the one-to-one relationship allows these limb
arrays to be copied to new locations with only a single reference to
update -- but only if it can be confident of the one-to-one relationship.

In summary, there are several different types of memory that get
requested via the GMP custom memory management function pointers.
These different types of memory yield very different patterns of
lifetime, locality and access behavior.  These attributes can be
meaningfully exploited by memory managers -- but only if the type
is clearly communicated in the request.

There are limits to how much of this could be handled outside of GMP.
For example, the very fact that one of the three function-pointers has
been invoked can be a completely reliable indication that the request
is emanating from somewhere "inside" of GMP -- but it would still not
be clear whether it concerned a limb array, some other kind of object, or
whether the request was for a stack temporary, or for the initialization,
clearing, or re-sizing of a longer-lived output parameter.  Only the
particular GMP call site presently "knows" this information.  It is
valuable, exploitable information.  It is also easily ignored by the
uninterested.

With very few exceptions (e.g., I/O functions), GMP consumes only
two resources: CPU time and memory.  It should not be surprising to
receive requests for more detail about either of these resources.
There are power/energy folks out there who may soon be knocking
on your door regarding energy estimates.  :^>

Torbjörn's additional concerns (e.g., library-to-library interactions)
are "system-level" issues.  The concerns I raise here are likewise
"system-level" issues.  They concern the interaction of GMP with the
entire ecosystem of software bound together with it.  As GMP gets
used within ever more complicated environments, GMP may have to
evolve in order to retain its "plays well with others" status. C++ is
just one of many other environments that may currently be
straining this status.  Garbage collection, multiple threads, signal
safety, cleanup in the presence of setjmp/longjmp, and other issues
are also looming.

Taking the long view of it all is likely to be a good idea.

David




On 12/20/2014 02:56 PM, Niels Möller wrote:
> "David M. Warme" <David at Warme.net> writes:
>
>> Proposal: add a new, final int/enum argument to the signature of
>> each of the memory functions, and have the int/enum value that
>> GMP passes indicate the type of memory being manipulated.
> I'm not sure if gmp currently ever stores any pointers in dynamically
> allocate memory, but if it does, it makes some sense for gc integration
> to tell the allocator function about that.
>
>> Some useful attributes to encode in the bits that are passed:
>>
>>      - limb array versus other.
>>
>>      - internal GMP stack temporary versus other.
> But I'm not ocnvinced this level of granularity makes sense. Which
> problem does it solve?
>
> Regards,
> /Niels
>