Newsgroups: comp.lang.c
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!barmar
From: barmar@think.com (Barry Margolin)
Subject: Re: Efficient dynamic storage question
Message-ID: <1991Apr20.230021.25248@Think.COM>
Sender: news@Think.COM
Organization: Thinking Machines Corporation, Cambridge MA, USA
References: <32121@usc>
Date: Sat, 20 Apr 91 23:00:21 GMT

In article <32121@usc> ajayshah@alhena.usc.edu (Ajay Shah) writes:
>  So the program profile is 
>realloc-malloc-realloc-malloc-realloc-malloc until all
>observations are read in.
>
>Question: is it much more efficient to realloc in groups of (say)
>100 observations at a time instead of calling realloc once for each
>observation?  Realloc might well have to copy a lot of elements in the
>process of doing this, right?  This could be expensive.

Yes, it's generally better to minimize the reallocs.  Consider an
implementation of malloc that allocates a new object right where the
previous object ended (perhaps with some header information interspersed).
The reallocs would have to copy because the previous malloc would prevent
the realloc from simply extended the array.

In some implementations, malloc rounds up the amount of memory you
requested (perhaps to a power of 2), in which case many of the reallocs
will be very cheap.  Also, if the size of the array gets larger than the
size of an observation record, the malloc may be able to use the space
vacated during the previous realloc, so every other realloc would be cheap.

Thus, at worst you would probably get about the same performance whether or
not you grow by larger chunks, but at best you may speed things up quite a
bit.  Furthermore, if these arrays are large, lots of reallocs can cause
quite a bit of paging, and paging is generally something you want to
minimize (a page fault is several orders of magnitude slower than any
individual instruction).

By the way, it's popular to grow things multiplicitavely, rather than
linearly.  For instance, rather than adding 100 to the size when
reallocing, you might want make the new size 1.5 or 2 times the old size.

--
Barry Margolin, Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar