This is the mail archive of the
libc-help@sourceware.org
mailing list for the glibc project.
Suggestion: try_realloc
- From: nisse at lysator dot liu dot se (Niels Möller)
- To: libc-help at sourceware dot org
- Cc: Marco Bodrato <bodrato at mail dot dm dot unipi dot it>, Torbjorn Granlund <tg at gmplib dot org>
- Date: Mon, 25 Feb 2013 17:16:51 +0100
- Subject: Suggestion: try_realloc
In GNU GMP, there are many places where storage size for an object
(typically a array of unsigned long) is grown, but the old contents is
irrelevant and will be overwritten immediately.
Currently, the default allocation functions in GMP uses realloc, but
this is efficient only when realloc can succeed without copying. If it
can't, realloc resorts to malloc + copy + free, while it in this case
would be more efficient if GMP called free + malloc.
There are also other cases where the old contents is used, but copying
is inefficient, because the next operation done to the data can do the
copying for free if it gets access to both the old and the new area.
I would like to suggest (and maybe this is already under consideration?)
adding a try_reallloc function, which works exactly like realloc as long
as it can succeed without copying, and otherwise returns NULL.
Typical use in a gmp-like application:
struct mp_int
{
size_t size;
size_t alloc;
unsigned long *data;
};
void
mul (mp_int *r, const mp_int *a, const mp_int *b)
{
size_t rn = a->size + b->size;
unsigned long *rp;
if (r->alloc < rn)
{
unsigned long *rp = try_realloc (r->data, rn * sizeof(*rp));
if (!rp)
{
free (r->data);
rp = malloc (rn * sizeof(*rp));
if (!rp)
die ();
}
r->data = rp;
}
... Actual computation storing the product at r->data ...
}
void
add_in_place (mp_int *r, const mp_int *a)
{
mp_size_t rn = a->size + 1;
unsigned long *inp;
if (r->alloc < rn)
{
unsigned long *rp = try_realloc (r->data, rn * sizeof(*rp));
if (!rp)
{
rp = malloc (rn * sizeof(*rp));
if (!rp)
die ();
/* Keep track of old area */
inp = r->data;
}
else
inp = rp;
r->data = rp;
}
else
inp = rp;
... code reading at inp and a->data, storing at r->data ...
if (inp != r-->data)
free (inp);
}
While doing a web search for "try_realloc", I found
http://www.open-std.org/JTC1/SC22/wg14/www/docs/n1527.pdf. I'm not at all
familiar with the standardization process, so I don't know the status of
this draft.
Among other things, this draft specifies a try_realloc function, which
is *almost* what I would like. But if I understand it correctly it
requires try_realloc to return NULL whenever the block is moved, for any
reason.
But after a quick look at glibc's realloc, I noticed that in some cases
it will do realloc via remap, and then the block can get a new address
but *without* any copying taking place. In that case, I'd prefer
try_alloc to succeed.
Also reading the sources, I noticed the malloc_usable_size function. I
could use that to implement an approximation of try_realloc. But if I
write code to do that, it won't handle the mmap/mremap case, and maybe
there are additional cases, like merging wit the next chunk, that it
also won't handle. So adding the function to glibc seems preferable.
Essentially, I'd like try_realloc to succeed whenever it can succeed
with less work than free + malloc. With the current implementation, that
is when the current block can be grown in place, and when it can be
grown via remap.
What do you all think? There are other possible generalizations of
realloc, but this try_realloc function is the simplest one I can see
which supports the above use cases.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.