Does realloc actually shrink buffers in common implementations?

Question

In common implementations such as Linux/Glibc, Windows/MSVC and BSD/Mac OS X, will

void *p = malloc(N + M);  // assume this doesn't fail
p = realloc(p, N);        // nor this

for N, M > 0, actually shrink the buffer returned by malloc in the realloc call, in the sense that up to M bytes may return to the free list? And more importantly, is there a chance that it reallocates the buffer?

I want to know because I just implemented dynamic arrays on top of numpy.ndarray, and I'm doing a resize, which calls realloc, to get the final size right. I may be able to skip the final resize as an optimization (at the expense of permanent overallocation) and I want to know if that's even worth trying.

Answer 1

I can say about Linux/glibc. In the source code it contains comments like this:

if n is for fewer bytes than already held by p, the newly unused
space is lopped off and freed if possible.

if you look at code of glibc, it contains lines like this:

remainder_size = newsize - nb;

if (remainder_size < MINSIZE) { /* not enough extra to split off */
  set_head_size(newp, newsize | (av != &main_arena ? NON_MAIN_ARENA : 0));
  set_inuse_bit_at_offset(newp, newsize);
}
else { /* split remainder */
  remainder = chunk_at_offset(newp, nb);
  set_head_size(newp, nb | (av != &main_arena ? NON_MAIN_ARENA : 0));
  set_head(remainder, remainder_size | PREV_INUSE |
       (av != &main_arena ? NON_MAIN_ARENA : 0));
  /* Mark remainder as inuse so free() won't complain */
  set_inuse_bit_at_offset(remainder, remainder_size);
 #ifdef ATOMIC_FASTBINS
  _int_free(av, remainder, 1);
 #else
  _int_free(av, remainder);
 #endif
}

nb - number of bytes you want, newsize here, should be called oldsize. So it tries to free the excess if possible.

About Mac OSX. More precisely about magazine_malloc, current implementation of malloc from Apple. See http://cocoawithlove.com/2010/05/look-at-how-malloc-works-on-mac.html for details.

realloc calls the zone realloc method, its current implementation as I see is szone_realloc. For different allocation sizes exists different code, but the algorithm is always the same:

if (new_good_size <= (old_size >> 1)) {
            /*
             * Serious shrinkage (more than half). free() the excess.
             */
            return tiny_try_shrink_in_place(szone, ptr, old_size, new_good_size);
} else if (new_good_size <= old_size) {
            /* 
             * new_good_size smaller than old_size but not by much (less than half).
             * Avoid thrashing at the expense of some wasted storage.
             */
             return ptr;
}

So as you can see, its implementation checks that new_size <= old_size / 2, and if so frees memory, and if not it does nothing.

Answer 2

Whether or not its worth it depends on how long the object is going to be around and how important it is to the application to reduce its memory footprint. There's no one right generic answer.

Generic memory allocators typically assume that the caller knows the previous size of the block and would only be called realloc if they actually knew they wanted to shrink the block. The last one I looked at was willing to shrink the block if the block was already over 128 bytes and the reallocation would free at least 1KB or at least a number of bytes equal to 1/4 of the block's current allocation size. It was tuned for high-volume server applications where objects typically don't stay around very long and where a special 'right size' operation was offered for objects known to be around for very long periods of time.