From: marc@watson.ibm.com (Marc Auslander)
Newsgroups: comp.unix.aix
Subject: Re: Slowness of realloc() under AIX32
Date: 6 Apr 92 17:19:23 GMT
	<1992Apr3.182520.15960@awdprime.austin.ibm.com>
Distribution: usa
Organization: IBM T.J. Watson Research Center, Hawthorne, New York
Disclaimer: This posting represents the poster's views, not necessarily those of IBM

Chris Stephenson, who was the originator of malloc for AIX 3.2,
writes as follows:

  Indeed, when realloc is called repeatedly for small increments
  in size, the new malloc will perform badly (compared with the
  old one in AIX 3.1), for several reasons.

  1.   Internally, the old memory allocator rounds up the size
       requested to a power of 2. Therefore most calls to realloc
       which request a small increase in size can be satisfied in
       situ, without performing any real new allocation, and with-
       out copying the data.

       Internally, the new memory allocator rounds up the size re-
       quested to a multiple of 16 bytes. For typical applications,
       this uses less memory; but a call to realloc which requests
       an increase in size from (say) 600 bytes to 700 bytes can
       never be satisfied from the currently occupied internal
       block.

  2.   There are several competing traditions on the side effects
       of realloc. At least one version of the UNIX system V docu-
       mentation says that 'sequences of calls to free, malloc and
       realloc use the search strategy of the malloc subroutine to
       compact the storage'. The new memory allocator follows this
       tradition (except in the case of a call to realloc that re-
       quests a reduction in size; see below).  Sometimes this is
       what the caller wants; but it exacerbates the poor perform-
       ance in the particular case cited.

       Specifically, after a call to realloc in which new size
       >= old, the area of memory supplied will occupy the left-
       most block of adequate size, even if it *could* have been
       extended in place (without moving it).

  3.   The average performance is exacerbated still further because,
       in the new memory allocator, when realloc is called with new
       length >= old, it *always* copies the data from the old area
       to the new, even when the address does not change.

       I did this deliberately in order to make the performance
       reasonably repeatable. If copying was avoided in the special
       case, the performance would be better sometimes, but it might
       vary wildly, depending on the history of previous memory al-
       locations (including those made behind the scenes by library
       functions).  I think it is already hard enough to make mean-
       ingful performance measurements, and to predict how programs
       will bahave in practice, without having to chase down this
       kind of stuff.

  In the new memory allocator, realloc does *not* move the area (or
  copy the data) if new size < old.  In this case it simply removes
  the tail (and makes the space available).  If the caller wants to
  reduce the size *and* compact memory, he may call realloc twice,
  first with new size < old, and second with no change in size.

  Incidentally, I tend to frown on the practice of repeatedly calling
  realloc to obtain small increments in size. It is usually preferable
  to use a doubling strategy. This will perform much better; and if it
  eventually delivers too much, the caller can give back the unwanted
  tail when the precise requirement is known.
--


Marc Auslander       (IBM)<marc@marc.watson.ibm.com>      914 784-6699
                     (Internet)<marc@watson.ibm.com>