«

I've a code in which I don't know how many elements an array may
contain, BUT I know the max. no. of values it may have. So I do this
malloc(MAXLEN), however I can use realloc(...) each time I add a new
element to this array.

Now my question is: will doing realloc everytime slow down the code very
much? My project is concerned about high performance.
Pushkar Pradhan

On Mon, 24 Nov 2003 22:06:19 -0600, Pushkar Pradhan wrote:

> I've a code in which I don't know how many elements an array may
> contain, BUT I know the max. no. of values it may have. So I do this
> malloc(MAXLEN), however I can use realloc(...) each time I add a new
> element to this array.
>
> Now my question is: will doing realloc everytime slow down the code very
> much?

Yes, but that's not a problem. Don't realloc for every element. Each time
you run out of elements, use realloc to double the size of the array.

"Sheldon Simms" <> wrote in message
news...
> On Mon, 24 Nov 2003 22:06:19 -0600, Pushkar Pradhan wrote:
>
> > I've a code in which I don't know how many elements an array may
> > contain, BUT I know the max. no. of values it may have. So I do this
> > malloc(MAXLEN), however I can use realloc(...) each time I add a new
> > element to this array.
> >
> > Now my question is: will doing realloc everytime slow down the code very
> > much?
>
> Yes, but that's not a problem. Don't realloc for every element. Each time
> you run out of elements, use realloc to double the size of the array.
>
< not on-topic, but maybe to the point>
But if all elements will have to be in memory soon or later,
why not malloc for all of them at the beginning (possibly
with realloc after initial assumption about size won't hold)?
While later on there may not be enough space to allocate
bigger continuous chunk, it can be on the beginning. If it is
not, why bother to start crunching? All later subsequent
allocations (for other stuff) could be smaller and "fit" into
possibly fragmented memory.
</ not on-topic, but maybe to the point>

On Mon, 24 Nov 2003 22:06:19 -0600, Pushkar Pradhan
<> wrote in comp.lang.c:

> I've a code in which I don't know how many elements an array may
> contain, BUT I know the max. no. of values it may have. So I do this
> malloc(MAXLEN), however I can use realloc(...) each time I add a new
> element to this array.
>
> Now my question is: will doing realloc everytime slow down the code very
> much? My project is concerned about high performance.
> Pushkar Pradhan

The C standard does not specify performance of anything. Much depends
on your particular compiler and operating system, which you can either
test or ask about in a group that supports your system.

There is a good chance that at least some reallocation calls will be
expensive in terms of time. Perhaps a better memory allocation
strategy would be in order.

If you really need to shrink the memory block, is it possible that you
can do it after all elements are added, instead of after each one?

If that is not possible, you could start out with an allocation for
some fraction of the maximum size, for example 25%. If you used that
up you could allocate another 25%, and another and another.

Other possibilities are to pick some likely size and always double it
or multiply it by 1.5 each time you need to grow the block.

You should investigate the typical needs of the program, if possible.
The maximum number of elements might be 1000, but perhaps most of the
time it will need 100 or less.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

In <> Pushkar Pradhan <> writes:

>I've a code in which I don't know how many elements an array may
>contain, BUT I know the max. no. of values it may have. So I do this
>malloc(MAXLEN), however I can use realloc(...) each time I add a new
>element to this array.
>
>Now my question is: will doing realloc everytime slow down the code very
>much? My project is concerned about high performance.

If you know the maximum number of elements, try to allocate memory for
all of them. When you know the exact number, call realloc to release
the unused memory. This way, the whole job takes one malloc and one
realloc call. This is important if performance is a concern, because
malloc and friends tend to be expensive in terms of CPU cycles.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email:

"Sheldon Simms" <> schrieb im Newsbeitrag
news...
> Yes, but that's not a problem. Don't realloc for every element. Each time
> you run out of elements, use realloc to double the size of the array.

That's actually very good strategy with which I made good experiences.

If he uses a structure type, he can write a set of functions to handle the
case universally, like

#include <stddef.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
typedef struct { void* buf; size_t elsz; size_t size; size_t used; }
dynamic_array_t;
typedef dynamic_array_t* dynamic_array_pointer_t;
dynamic_array_pointer_t create_dynamic_array( size_t elsz, size_t
initial ) {
dynamic_array_pointer_t da = (dynamic_array_pointer_t) malloc(
sizeof(dynamic_array_t) );
if ( da == 0 ) return 0;
da->buf = malloc( elsz * initial ); da->elsz = elsz; da->size =
initial; da->used = 0; return da;
}
void delete_dynamic_array( dynamic_array_pointer da ) { free( da.buf );
free( da ); }
void* address_dynamic_array_element_readonly( dynamic_array_pointer da,
size_t index ) {
if ( index >= da->used ) return 0;
{ char* p = (char*) da->buf; return p+( da->elsz * index ); }
}
void* address_dynamic_array_element_readwrite( dynamic_array_pointer da,
size_t index ) {
if ( index >= da->used ) {
if ( index >= da->size ) {
size_t newsz; void* newbf;
if ( index >= UINT_MAX / da->elsz ) return 0;
if ( da->size >= UINT_MAX / 2U ) newsz = UINT_MAX /
da->elsz; else newsz = da->size * 2U;
if ( index >= newsz ) newsz = index + 1U;
newbf = malloc( da->elsz * newsz ); if ( newbf == 0 ) return
0;
if ( da->used ) memcpy( newbf, da->buf, da->used *
da->elsz );
free( da->buf ); da->buf = newbf; da->size = newsz;
}
da->used = index + 1U;
}
{ char* p = (char*) da->buf; return p+( da->elsz * index ); }
}

Here, the functions create_dynamic_array() and delete_dynamic_array() handle
array creation / destruction, and address_dynamic_array_element_readonly()
and address_dynamic_array_element_readwrite() access the array for reading
and writing and return a pointer to an indexed array element. If during
write indexing, the index goes beyond the array size, it is automatically
resized to either twice the size, or a size including the indexed element.
This way, you can have arbitrary access to the array and can use it for many
kinds of purposes.

"Ekkehard Morgenstern" <> schrieb im
Newsbeitrag news:bq2gac$c9$...
> void delete_dynamic_array( dynamic_array_pointer da ) { free(
da.buf );
> free( da ); }

of course this should read " free( da->buf ) " not " free( da.buf ); ".

In <bq2gac$c9$> "Ekkehard Morgenstern" <> writes:

> void* address_dynamic_array_element_readonly( dynamic_array_pointer da,
> void* address_dynamic_array_element_readwrite( dynamic_array_pointer da,
1 2 3
12345678901234567890123456789012345

Not even C99 guarantees that many significant initial characters in
an external identifier. Apart from being brain dead from both a stylistic
and a practical point of view, such identifiers are not even portable.

6 Any identifiers that differ in a significant character are
different identifiers. If two identifiers differ only in
nonsignificant characters, the behavior is undefined.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email:

"Dan Pop" <> schrieb im Newsbeitrag
news:bq2lr3$mcl$...
> > void* address_dynamic_array_element_readwrite( dynamic_array_pointer
da,
> 1 2 3
> 12345678901234567890123456789012345
>
> Not even C99 guarantees that many significant initial characters in

Not true. The IEC 9899:1999 (C99) standard states that identifiers are
unlimited in length:

(6.4.2.1.2) "There is no specific limit on the maximum length of an
identifier."

Ekkehard Morgenstern <> wrote:

> "Dan Pop" <> schrieb im Newsbeitrag
> news:bq2lr3$mcl$...
>> > void* address_dynamic_array_element_readwrite( dynamic_array_pointer
> da,
>> 1 2 3
>> 12345678901234567890123456789012345
>>
>> Not even C99 guarantees that many significant initial characters in

> Not true. The IEC 9899:1999 (C99) standard states that identifiers are
> unlimited in length:

> (6.4.2.1.2) "There is no specific limit on the maximum length of an
> identifier."

No, but there is a limit on the /significant/ characters
in the identifier. The relevant text is:

5.2.4.1 Translation limits

[#1] The implementation shall be able to translate and
execute at least one program that contains at least one
instance of every one of the following limits:13)

...

-- 63 significant initial characters in an internal
identifier or a macro name (each universal character
name or extended source character is considered a
single character)

-- 31 significant initial characters in an external
identifier (each universal character name specifying a
short identifier of 0000FFFF or less is considered 6
characters, each universal character name specifying a
short identifier of 00010000 or more is considered 10
characters, and each extended source character is
considered the same number of characters as the
corresponding universal character name, if any)14)

Alex