From: Hans-Bernhard Broeker <broeker AT physik DOT rwth-aachen DOT de>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: realloc causing fault
Date: 6 Dec 2000 12:56:59 GMT
Organization: Aachen University of Technology (RWTH)
Lines: 63
Message-ID: <90ld2r$72v$1@nets3.rz.RWTH-Aachen.DE>
References: <90j6oj$fjt$1 AT news5 DOT svr DOT pol DOT co DOT uk> <7458-Tue05Dec2000234242+0200-eliz AT is DOT elta DOT co DOT il> <000b01c05f60$3ce4ca60$f504883e AT gtdf>
NNTP-Posting-Host: acp3bf.physik.rwth-aachen.de
X-Trace: nets3.rz.RWTH-Aachen.DE 976107419 7263 137.226.32.75 (6 Dec 2000 12:56:59 GMT)
X-Complaints-To: abuse AT rwth-aachen DOT de
NNTP-Posting-Date: 6 Dec 2000 12:56:59 GMT
Originator: broeker@
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

Greg Holdridge <greg AT holdridge7 DOT freeserve DOT co DOT uk> wrote:
> ---- Original Message -----
> From: Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>
> To: Greg Holdridge <greg AT holdridge7 DOT freeserve DOT co DOT uk>
> Cc: <djgpp AT delorie DOT com>
> Sent: Tuesday, December 05, 2000 9:42 PM
> Subject: Re: realloc causing fault


>> Your calculations are mistaken.  You don't take into account the
>> overhead of each allocation (8 bytes per allocated buffer).  So in
>> fact you allocate much more than 150KB.  You also do it very

> even so, with 64MB plus virtual mem it should be ok.

Not necessarily. You still just don't see the problem your allocation
strategy is causing, it seems. You're calling realloc() to grow your
main buffer *extremely* often.  In the worst of all possible cases,
this could have to malloc() a fresh block, copy the old contents and
free() the old block _every_ time. I.e. if you use this strategy to allocate
N bytes in steps of n (your structure size), you may actually use

	SUM(i=1..N/n, i*n + m)
	= N/n * m + n * SUM(i=1..N/n, i)
	= N/n * m + n * (N/n+1)*(N/n)/2
	= N/n * m + (N^2/n + N)/2
	= N/n * (m + N/2 + n/2)

Here, 'm' is the overhead of each malloc() call (8 bytes or so in
DJGPP).  N/n is the number of realloc() calls. As you can see, this
grows quadratically with increasing final array size N. And it becomes
worse, the smaller your 'n', i.e. the step size of your realloc is.

And the fact that you keep allocating other, extremely small hunks of
1 or two bytes, mixed into the realloc() series, definitely doesn't
help, either.

As an example, let's take your 150K for N, and about 10 bytes for n. That
results in

	150000 / 10 * (8 + 150000/2 + 10/2)
	= 15000 * 75013
	= 1.1 * 10^9

That's a full GByte in the worst-case. Of course, the DJGPP libc will
not really hit that worst case. In the effect, 'n' will be much larger
than 10 (in the order of 4096, more likely). But even so, I think you
should be able to see your problem now.

> not one byte, one string.  

Plus one structure to hold it. And the string is only one or two bytes
long, in your example source.

> And besides, I need to allocate in array format
> because strings are accessed by code.  

Nobody's telling you not to do that. It's the pattern you grow the
array by that causes the problems, not the fact that you're using an
array.
-- 
Hans-Bernhard Broeker (broeker AT physik DOT rwth-aachen DOT de)
Even if all the snow were burnt, ashes would remain.