Velocity Reviews > Re: Efficient use of realloc

# Re: Efficient use of realloc

Ben Bacarisse
Guest
Posts: n/a

 04-21-2011
http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Harter) writes:

> On Wed, 20 Apr 2011 21:22:38 +0200, Steve Keller <(E-Mail Removed)>
> wrote:

<snip>
>>To avoid numerous calls to realloc() I have often written code like
>>this:
>>
>> struct foo *p, *new, *a = NULL;
>> int count = 0, alloced = 0;
>> while (p = get_item()) {
>> if (count >= alloced) {
>> new = realloc(a, (alloced += 256) * sizeof(*a));
>> if (!new)
>> break;
>> a = new;
>> }
>> a[count++] = *p;
>> }
>>
>>But should one really do this or should one rely on the standard
>>library to handle things in an intelligent way, even without knowing
>>how many and how large the items will be?

>
> When you don't know how large an array might grow, the usual practice
> is to increase the size by some multiplicative factor. I usually use
> a factor of 1.5 but 2 is probably the most common choice. Thus
>
> new = realloc(a, (alloced *=2) * sizeof(*a)); /* Factor of 2 */
> new = realloc(a, (alloced += alloced/2) * sizeof(*a)); /* 1.5 */

Small point to watch out for: multiplicative schemes don't work when
alloced is zero to start with (as in this example). There are lots of
fixes, of course. I often just add a constant:

new = realloc(a, (alloced += alloced/2 + * sizeof(*a));

which gives a minimum starting size. Alternatively you can special-case
the first allocation or start with alloced not zero (which can affect the
logic of the loop since it is, effectively, a lie).

<snip>
--
Ben.

Keith Thompson
Guest
Posts: n/a

 04-21-2011
Ben Bacarisse <(E-Mail Removed)> writes:
> (E-Mail Removed) (Richard Harter) writes:

[...]
>> When you don't know how large an array might grow, the usual practice
>> is to increase the size by some multiplicative factor. I usually use
>> a factor of 1.5 but 2 is probably the most common choice. Thus
>>
>> new = realloc(a, (alloced *=2) * sizeof(*a)); /* Factor of 2 */
>> new = realloc(a, (alloced += alloced/2) * sizeof(*a)); /* 1.5 */

>
> Small point to watch out for: multiplicative schemes don't work when

[...]

And a factor of 1.5 doesn't work if alloced starts as 1, since 1/2 is 0.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson
Guest
Posts: n/a

 04-22-2011
pete <(E-Mail Removed)> writes:
> Keith Thompson wrote:
>> Ben Bacarisse <(E-Mail Removed)> writes:
>> > (E-Mail Removed) (Richard Harter) writes:

>> [...]
>> >> When you don't know how large an array might grow, the usual practice
>> >> is to increase the size by some multiplicative factor. I usually use
>> >> a factor of 1.5 but 2 is probably the most common choice. Thus
>> >>
>> >> new = realloc(a, (alloced *=2) * sizeof(*a)); /* Factor of 2 */
>> >> new = realloc(a, (alloced += alloced/2) * sizeof(*a)); /* 1.5 */
>> >
>> > Small point to watch out for: multiplicative schemes don't work when
>> > alloced is zero to start with (as in this example).

>> [...]
>>
>> And a factor of 1.5 doesn't work if alloced starts as 1,
>> since 1/2 is 0.

>
> (alloced += alloced + 1) works fine
> if alloced starts out as either 1 or 0.

Sure, it works, but it's likely to be horribly inefficient to grow an
allocated array by a single element at a time.

Growing by a factor of 1.5 or 2 is likely to be the best approach; you
just have to watch out for the edge cases.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson
Guest
Posts: n/a

 04-22-2011
(E-Mail Removed) (Richard Harter) writes:
> On Fri, 22 Apr 2011 09:12:17 -0700, Keith Thompson <(E-Mail Removed)>
> wrote:
>
>>pete <(E-Mail Removed)> writes:
>>> Keith Thompson wrote:
>>>> Ben Bacarisse <(E-Mail Removed)> writes:
>>>> > (E-Mail Removed) (Richard Harter) writes:
>>>> [...]
>>>> >> When you don't know how large an array might grow, the usual practice
>>>> >> is to increase the size by some multiplicative factor. I usually use
>>>> >> a factor of 1.5 but 2 is probably the most common choice. Thus
>>>> >>
>>>> >> new = realloc(a, (alloced *=2) * sizeof(*a)); /* Factor of 2 */
>>>> >> new = realloc(a, (alloced += alloced/2) * sizeof(*a)); /* 1.5 */
>>>> >
>>>> > Small point to watch out for: multiplicative schemes don't work when
>>>> > alloced is zero to start with (as in this example).
>>>> [...]
>>>>
>>>> And a factor of 1.5 doesn't work if alloced starts as 1,
>>>> since 1/2 is 0.
>>>
>>> (alloced += alloced + 1) works fine
>>> if alloced starts out as either 1 or 0.

>>
>>Sure, it works, but it's likely to be horribly inefficient to grow an
>>allocated array by a single element at a time.

>
> Are you misreading the line, or is there some obscure parsing gotcha
> that I'm missing?

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"