This is the mail archive of the libc-help@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]