Dynamically resizing a buffer

[Richard Tobin]

Re: Dynamically resizing a buffer

In article <wfydnQ74ZZLZ3F HbnZ2dnUVZ8v2vn Z2d@bt.com>,
Richard Heathfield <rjh@see.sig.in validwrote:

>Once you know that the line has been read completely, you
>can "shrink" the allocation to be an exact fit, thus taking up no more
>memory than you actually need.

Possibly. realloc() may well be a no-op for size decreases.

-- Richard

--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Richard Heathfield]

Re: Dynamically resizing a buffer

Richard Tobin said:

In article <wfydnQ74ZZLZ3F HbnZ2dnUVZ8v2vn Z2d@bt.com>,
Richard Heathfield <rjh@see.sig.in validwrote:

>>Once you know that the line has been read completely, you
>>can "shrink" the allocation to be an exact fit, thus taking up no more
>>memory than you actually need.

>
Possibly. realloc() may well be a no-op for size decreases.

True enough, but then malloc() may well allocate in chunks of 16MB. You
can't fight a lousy implementation, except by ditching it in favour of
a better one.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Eric Sosman]

Re: Dynamically resizing a buffer

Richard Heathfield wrote On 08/22/07 10:05,:

Eric Sosman said:
>
<snip>
>
>

>>while ((tmp = realloc(buf->data, buf->size + inc)) == NULL) {
>>if ((inc /= 2) == 0)
>>exit(EXIT_FAI LURE);

>
>
Do you really think that's a good idea? We've had this whole discussion
recently, I know, but it bears reiterating nonetheless that it is not a
library function's job to decide whether to terminate a program.

If you'll review the discussion you mention, you'll
find that I was firmly on the "report, don't crash" side.

The purpose of my rewrite of the O.P.'s code was to
implement his choices less clumsily, not to confuse the
issue by inflicting my own choices on him. That's why
(for example) I didn't mention the alternative design
possibility of a linked list of smaller buffers instead
of one ever-growing array: it would only have distracted
attention from the main issue.

At one point I even had a /* your choice */ comment on
the exit() call, but decided it was too distracting and
removed it for fear it would provoke responses on side-
issues ... Damned if I do, damned if I don't, I guess.

--
Eric.Sosman@sun .com

[Richard Heathfield]

Re: Dynamically resizing a buffer

Eric Sosman said:

Richard Heathfield wrote On 08/22/07 10:05,:

>Eric Sosman said:
>>
><snip>
>>
>>

>>>while ((tmp = realloc(buf->data, buf->size + inc)) == NULL) {
>>>if ((inc /= 2) == 0)
>>>exit(EXIT_FA ILURE);

>>
>>
>Do you really think that's a good idea? We've had this whole
>discussion recently, I know, but it bears reiterating nonetheless
>that it is not a library function's job to decide whether to
>terminate a program.

>
If you'll review the discussion you mention, you'll
find that I was firmly on the "report, don't crash" side.
>
The purpose of my rewrite of the O.P.'s code was to
implement his choices less clumsily, not to confuse the
issue by inflicting my own choices on him.

Fair enough. I do the same myself sometimes (and get the same kind of
stick that I've just given you!).

<snip>

Damned if I do, damned if I don't, I guess.

I know. To make it up to you, we'll double your fee on this occasion.

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Flash Gordon]

Re: Dynamically resizing a buffer

cr88192 wrote, On 22/08/07 13:20:

"Philip Potter" <pgp@see.sig.in validwrote in message
news:fah5a6$qif $1@aioe.org...

>Hello clc,
>>
>I have a buffer in a program which I write to. The buffer has write-only,
>unsigned-char-at-a-time access, and the amount of space required isn't
>known a priori. Therefore I want the buffer to dynamically grow using
>realloc().
>>
>A comment by Richard Heathfield in a thread here suggested that a good
>algorithm for this is to use realloc() to double the size of the buffer,
>but if realloc() fails request smaller size increments until realloc()
>succeeds or until realloc() has failed to increase the buffer by even one
>byte.
>>

>
doubling is probably too steep IMO.
>
I usually use 50% each time ('size2=size+(s ize>>1);').
25% may also be sane ('size2=size+(s ize>>2);').

When you want to divide, divide. It is far easier for people to read and
shows your intention. It is over 15 years since I saw a compiler that
would not optimise division by a power of 2 to a shift.

33% may also be good.
>
33% is ugly though:
size2=size+(siz e>>2)+(size>>4) +(size>>6); //bulky
size2=size+size *33/100; //critical buffer size limit

Or more accurately and clearly
size2 = size + size/3;

Or, if you can put the result back in size
size += size/3;

but is a nice 4/3 ratio...

Nice is whatever gives a decent performance.
--
Flash Gordon

[CBFalconer]

Re: Dynamically resizing a buffer

Philip Potter wrote:

Richard wrote:
>

.... snip ...

>

>Clearly if you KNOW that the buffer is going to double/quadruple
>etc then malloc it to start with.

>
I've already stated that the final amount of space required isn't
known a priori. It could be thousands of bytes, it could be
millions. A linearly-growing buffer is not appropriate for this
situation, which is why I chose an exponentially-growing buffer.

And the choice of strategy depends on the usage. That is why my
ggets uses linear allocation (normal use is interactive input -
limited size) while my hashlib uses doubling (possibly millions of
entries).

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net>



--
Posted via a free Usenet account from http://www.teranews.com

[cr88192]

Re: Dynamically resizing a buffer


"Flash Gordon" <spam@flash-gordon.me.ukwro te in message
news:bo9up4xlfu .ln2@news.flash-gordon.me.uk...

cr88192 wrote, On 22/08/07 13:20:

>"Philip Potter" <pgp@see.sig.in validwrote in message
>news:fah5a6$qi f$1@aioe.org...

>>Hello clc,
>>>
>>I have a buffer in a program which I write to. The buffer has
>>write-only, unsigned-char-at-a-time access, and the amount of space
>>required isn't known a priori. Therefore I want the buffer to
>>dynamically grow using realloc().
>>>
>>A comment by Richard Heathfield in a thread here suggested that a good
>>algorithm for this is to use realloc() to double the size of the buffer,
>>but if realloc() fails request smaller size increments until realloc()
>>succeeds or until realloc() has failed to increase the buffer by even
>>one byte.
>>>

>>
>doubling is probably too steep IMO.
>>
>I usually use 50% each time ('size2=size+(s ize>>1);').
>25% may also be sane ('size2=size+(s ize>>2);').

>
When you want to divide, divide. It is far easier for people to read and
shows your intention. It is over 15 years since I saw a compiler that
would not optimise division by a power of 2 to a shift.
>

shifts are obvious enough...

>33% may also be good.
>>
>33% is ugly though:
>size2=size+(si ze>>2)+(size>>4 )+(size>>6); //bulky
>size2=size+siz e*33/100; //critical buffer size limit

>
Or more accurately and clearly
size2 = size + size/3;
>

odd that I missed such an obvious option...
makes me look stupid, oh well...

Or, if you can put the result back in size
size += size/3;
>

>but is a nice 4/3 ratio...

>
Nice is whatever gives a decent performance.

maybe, or whatever best follows a natural growth curve, or something...

--
Flash Gordon

[¬a\\/b]

Re: Dynamically resizing a buffer

On Wed, 22 Aug 2007 11:52:01 -0400, Eric Sosman wrote:

At one point I even had a /* your choice */ comment on
>the exit() call, but decided it was too distracting and
>removed it for fear it would provoke responses on side-
>issues ... Damned if I do, damned if I don't, I guess.

and if it would be, why have you to fear?

[jaysome]

Re: Dynamically resizing a buffer

On Wed, 22 Aug 2007 12:05:40 +0100, Philip Potter
<pgp@see.sig.in validwrote:

>Hello clc,
>
>I have a buffer in a program which I write to. The buffer has
>write-only, unsigned-char-at-a-time access, and the amount of space
>required isn't known a priori. Therefore I want the buffer to
>dynamically grow using realloc().
>
>A comment by Richard Heathfield in a thread here suggested that a good
>algorithm for this is to use realloc() to double the size of the buffer,
>but if realloc() fails request smaller size increments until realloc()
>succeeds or until realloc() has failed to increase the buffer by even
>one byte.
>
>The basic idea is below. The key function is MyBuffer_writeb yte(), which
>expects the incoming MyBuffer object to be in a consistent state.
>
>Are there any improvements I could make to this code? To me it feels
>clumsy, especially with the break in the 3-line while loop.
>
>struct mybuffer_t {
unsigned char *data;
size_t size; /* size of buffer allocated */
size_t index; /* index of first unwritten member of data */
>};
>
>typedef struct mybuffer_t MyBuffer;
>
>void MyBuffer_writeb yte(MyBuffer *buf, unsigned char byte) {
if(buf->size == buf->index) {
/* need to allocate more space */
size_t inc = buf->size;
unsigned char *tmp;
while(inc>0) {
tmp = realloc(buf->data, buf->size + inc);
if (tmp!=NULL) break; /* break to preserve the size of inc*/
inc/=2;
}
if(tmp==NULL) {
/* couldn't allocate any more space, print error and exit */
exit(EXIT_FAILU RE);

Nobody mentioned this so far, but I think it's worth mentioning.

Your immediate above comment is wrong. The exit() function does not
necessarily print an error. In this case, the exit() function
terminates the program and, according to the C standard, allowably
silently.

In fact, most implementations I've come across don't print anything
out as a result of calling the exit() function--the program simply
terminates silently, and the user is left waiving his or her hands in
the air.

And even if exit() did print out an error, what would you expect for
it to print out in this case? Surely it can't print out the following
(unless you expect C to have a crystal ball that intelligently reads
comments):

couldn't allocate any more space, print error and exit

If you want to print an error and then "exit()", you'll have to print
the error out on your own. Something like this would work:

if ( !tmp )
{
/* couldn't allocate any more space, print error and exit */
fprintf(stderr, "couldn't allocate any more space\n");
exit(EXIT_FAILU RE);
}

If you do something like the above, make sure you include <stdio.h>
for the prototype for fprintf() and <stdlib.hfor the prototype for
exit() and the definition of the macro EXIT_FAILURE.

One of the problems with outputting an error message to stderr (or
stdout) and then calling exit() is that your user may never see the
error message. There is nothing in the C standard that prevents an
operating system, or more appropriately, a run time environment, from
terminating your program when exit() is called without you having a
glimmer of a chance of viewing the message output to stderr (or
stdout).

When you decide to call the function exit(), you are basically, as a
programmer, throwing your hands up in the air (and most likely to have
the user emulate you) and claiming that "this condition should never
happen". After all, the exit() function simply terminates the program
as far as the user is concerned.

Given this, perhaps you should consider some alternatives to using or
not using exit(). Far better as an alternative, IMHO, is to use the
assert macro instead of the exit() function. As a compromise, use the
assert macro in conjunction with the exit() function. For example:

assert(tmp != NULL);
if ( !tmp )
{
exit(EXIT_FAILU RE);
}

If you use the assert macro, make sure you include <assert.h>.

As a developer, you should know to compile and test your code without
the NDEBUG macro defined. That way, the assert macro will fire off
before your program even gets to the exit() statement. Furthermore,
the assert macro will hopefully and most likely provide you with
valuable information that helps you to trace the root cause of your
problem, which is most likely, IMHO, a programming error. (If you're
really lucky, you'll be able to break into a debugger when the assert
macro fires off. Visual Studio 98 and later provide this feature,
BTW.)

Note that even with the added assert statement, you can get back to
your original functionality of calling only exit() and not assert'ing
simply by defining the macro NDEBUG; this is well defined by the C
standard.

On a somewhat related note, you should NEVER call the exit() function
from main(). Doing so expresses your lack of knowledge of Standard C,
which guarantees that a return statement in main() has the same effect
as calling exit() with an argument that is the same as the return
value. In other words, use only return statements in main()--never
call exit() from main().

And finally, the only acceptable return values from main, and the only
values you can pass into exit(), are 0, EXIT_SUCCESS and EXIT_FAILURE.
The latter two macros are defined in <stdlib.h>, so make sure to
include that header file if you use either one. Returning a value of 0
or calling exit(0) is equivalent to returning a value of EXIT_SUCCESS
or calling exit(EXIT_SUCCE SS), as far as the C standard is concerned.

One convention I've grown accustomed to is to return 0 from main() if
I never return a failure condition, e.g.:

int main(void)
{
return 0;
}

But I return EXIT_SUCCESS as a successful return value if I also
return a failure condition (which can only be EXIT_FAILURE and nothing
else) from main(), e.g.:

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
if ( argc < 2 )
{
printf("Error.\ n");
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}

The above could arguably be better written as (along with many other
variants):

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int status = EXIT_SUCCESS;
if ( argc < 2 )
{
printf("Error.\ n");
status = EXIT_FAILURE;
}
return status;
}

Best regards
--
jay

[Flash Gordon]

Re: Dynamically resizing a buffer

cr88192 wrote, On 23/08/07 00:03:

"Flash Gordon" <spam@flash-gordon.me.ukwro te in message
news:bo9up4xlfu .ln2@news.flash-gordon.me.uk...

>cr88192 wrote, On 22/08/07 13:20:

>>"Philip Potter" <pgp@see.sig.in validwrote in message
>>news:fah5a6$q if$1@aioe.org.. .
>>>Hello clc,
>>>>
>>>I have a buffer in a program which I write to. The buffer has
>>>write-only, unsigned-char-at-a-time access, and the amount of space
>>>required isn't known a priori. Therefore I want the buffer to
>>>dynamicall y grow using realloc().
>>>>
>>>A comment by Richard Heathfield in a thread here suggested that a good
>>>algorithm for this is to use realloc() to double the size of the buffer,
>>>but if realloc() fails request smaller size increments until realloc()
>>>succeeds or until realloc() has failed to increase the buffer by even
>>>one byte.
>>>>
>>doubling is probably too steep IMO.
>>>
>>I usually use 50% each time ('size2=size+(s ize>>1);').
>>25% may also be sane ('size2=size+(s ize>>2);').

>When you want to divide, divide. It is far easier for people to read and
>shows your intention. It is over 15 years since I saw a compiler that
>would not optimise division by a power of 2 to a shift.

>
shifts are obvious enough...

It is not as obvious. I can read shifts, but for something like the
above I then have to think to know what the scaling factor is, but with
division the scaling factor is actually stated. I also don't have to
worry about precedence because for arithmetic C just follows the rules I
was taught before I saw my first computer. I also don't have to worry
about whether it is a signed number (shifting a negative number is not
required to act as division). Is is also easier to change the factor
with division.

Finally, and most importantly, a division expresses the intent, shift
expresses a way of achieving that intent. It is always better to express
your intent where possible until you have *proved* you need to worry
about the details.

>>33% may also be good.
>>>
>>33% is ugly though:
>>size2=size+(s ize>>2)+(size>> 4)+(size>>6); //bulky
>>size2=size+si ze*33/100; //critical buffer size limit

>Or more accurately and clearly
>size2 = size + size/3;

>
odd that I missed such an obvious option...
makes me look stupid, oh well...

You missed it because you insist on looking for micro-optimisations
instead of trying to express your intent clearly. Oh wait, that is
another way of saying it makes you look stupid. This is because this
sort of micro-optimisation has been stupid for many years because the
compiler will do it for you so wasting your time trying to beet the
compiler is stupid.

>Or, if you can put the result back in size
>size += size/3;
>>

>>but is a nice 4/3 ratio...

>Nice is whatever gives a decent performance.

>
maybe, or whatever best follows a natural growth curve, or something...

I can't think of a good reason for wanting less than decent performance.
Of course, I consider all resources when thinking about performance, so
tell me what I've missed.
--
Flash Gordon

[Philip Potter]

Re: Dynamically resizing a buffer

jaysome wrote:

On Wed, 22 Aug 2007 12:05:40 +0100, Philip Potter
<pgp@see.sig.in validwrote:

> if(tmp==NULL) {
> /* couldn't allocate any more space, print error and exit */
> exit(EXIT_FAILU RE);

>
Nobody mentioned this so far, but I think it's worth mentioning.
>
Your immediate above comment is wrong. The exit() function does not
necessarily print an error. In this case, the exit() function
terminates the program and, according to the C standard, allowably
silently.
>
In fact, most implementations I've come across don't print anything
out as a result of calling the exit() function--the program simply
terminates silently, and the user is left waiving his or her hands in
the air.

<snip>

Yes, I know all this; the comment was to show the /intent/ of that
conditional in a code example which was studying something else -
namely, realloc()ing a buffer.

If you do something like the above, make sure you include <stdio.h>
for the prototype for fprintf() and <stdlib.hfor the prototype for
exit() and the definition of the macro EXIT_FAILURE.

Similarly, I didn't show headers because I was asking questions about
concepts rather than "Why doesn't this compile?".

One of the problems with outputting an error message to stderr (or
stdout) and then calling exit() is that your user may never see the
error message. There is nothing in the C standard that prevents an
operating system, or more appropriately, a run time environment, from
terminating your program when exit() is called without you having a
glimmer of a chance of viewing the message output to stderr (or
stdout).

True. But I'm not writing production code. If I were, I would likely be
within some sort of framework which provides better error reporting and
would wrap fprintf(stderr) or CreateErrorWind ow() in some sort of
errprint() function, as I have done here. I didn't quote errprint()
because it wasn't relevant. (In this case, it calls the nonstandard
function xil_printf() on the MicroBlaze soft processor, or
fprintf(stderr) in a UNIX environment.)

When you decide to call the function exit(), you are basically, as a
programmer, throwing your hands up in the air (and most likely to have
the user emulate you) and claiming that "this condition should never
happen". After all, the exit() function simply terminates the program
as far as the user is concerned.

Either that, or you're stating "if this condition does happen, this
program cannot reasonably continue". Which in this case is true. And
exit() is fine for my requirements, because this is not production code.
(Even if it was, I *still* think exit() on *alloc()-failure is the best
option for this particular application. The data generated in the buffer
is JPEG data, and a partly-generated JPEG bitstream just results in an
ugly mess and a disappointed user.)

Given this, perhaps you should consider some alternatives to using or
not using exit(). Far better as an alternative, IMHO, is to use the
assert macro instead of the exit() function. As a compromise, use the
assert macro in conjunction with the exit() function. For example:
>
assert(tmp != NULL);
if ( !tmp )
{
exit(EXIT_FAILU RE);
}
>
If you use the assert macro, make sure you include <assert.h>.

I already know about assert(), but I feel that assert() is for
conditions which the programmer believes can never happen, but which
during development all too often do. That way, it is theoretically
*safe* to turn off assert()s in production code with NDEBUG because
these conditions "can't happen".

Because we know that calls to *alloc() _can_ fail, we should not use
assert() to ensure they don't - far better to detect the error and
report it through the normal channels, even during development. This way
you have tested the error-reporting functionality, assuming the
out-of-memory error occurs during development.

As a developer, you should know to compile and test your code without
the NDEBUG macro defined. That way, the assert macro will fire off
before your program even gets to the exit() statement. Furthermore,
the assert macro will hopefully and most likely provide you with
valuable information that helps you to trace the root cause of your
problem, which is most likely, IMHO, a programming error. (If you're
really lucky, you'll be able to break into a debugger when the assert
macro fires off. Visual Studio 98 and later provide this feature,
BTW.)

That would be nice if I was programming for an environment which Visual
Studio and friends target.

<snip>

On a somewhat related note, you should NEVER call the exit() function
from main(). Doing so expresses your lack of knowledge of Standard C,
which guarantees that a return statement in main() has the same effect
as calling exit() with an argument that is the same as the return
value. In other words, use only return statements in main()--never
call exit() from main().

What? Why? This "NEVER" seems highly peculiar. Yes, exit() and return
are equivalent in main(). But you don't say why you should prefer
return. If it's because return is likely to be faster than exit(), this
laughable because exit() can only be called once, so the time saved is
completely insignificant.

If you like your error reporting to be idiomatic and consistent in
style, surely it's better to call exit() from main() just like you would
anywhere else?

In any case, I'd reserve the word "NEVER" for things like "NEVER free()
the same pointer twice" or "NEVER declare main() as returning void", not
stylistic points like this.

And finally, the only acceptable return values from main, and the only
values you can pass into exit(), are 0, EXIT_SUCCESS and EXIT_FAILURE.
The latter two macros are defined in <stdlib.h>, so make sure to
include that header file if you use either one. Returning a value of 0
or calling exit(0) is equivalent to returning a value of EXIT_SUCCESS
or calling exit(EXIT_SUCCE SS), as far as the C standard is concerned.

Yes, I know. That's why I wrote exit(EXIT_FAILU RE) and not exit(1).

<snip more>

Phil

--
Philip Potter pgp <atdoc.ic.ac. uk

[cr88192]

Re: Dynamically resizing a buffer


"Flash Gordon" <spam@flash-gordon.me.ukwro te in message
news:nurvp4xu0d .ln2@news.flash-gordon.me.uk...

cr88192 wrote, On 23/08/07 00:03:

>"Flash Gordon" <spam@flash-gordon.me.ukwro te in message
>news:bo9up4xlf u.ln2@news.flas h-gordon.me.uk...

>>cr88192 wrote, On 22/08/07 13:20:
>>>"Philip Potter" <pgp@see.sig.in validwrote in message
>>>news:fah5a6$ qif$1@aioe.org. ..
>>>>Hello clc,
>>>>>
>>>>I have a buffer in a program which I write to. The buffer has
>>>>write-only, unsigned-char-at-a-time access, and the amount of space
>>>>required isn't known a priori. Therefore I want the buffer to
>>>>dynamical ly grow using realloc().
>>>>>
>>>>A comment by Richard Heathfield in a thread here suggested that a good
>>>>algorithm for this is to use realloc() to double the size of the
>>>>buffer, but if realloc() fails request smaller size increments until
>>>>realloc() succeeds or until realloc() has failed to increase the
>>>>buffer by even one byte.
>>>>>
>>>doubling is probably too steep IMO.
>>>>
>>>I usually use 50% each time ('size2=size+(s ize>>1);').
>>>25% may also be sane ('size2=size+(s ize>>2);').
>>When you want to divide, divide. It is far easier for people to read and
>>shows your intention. It is over 15 years since I saw a compiler that
>>would not optimise division by a power of 2 to a shift.

>>
>shifts are obvious enough...

>
It is not as obvious. I can read shifts, but for something like the above
I then have to think to know what the scaling factor is, but with division
the scaling factor is actually stated. I also don't have to worry about
precedence because for arithmetic C just follows the rules I was taught
before I saw my first computer. I also don't have to worry about whether
it is a signed number (shifting a negative number is not required to act
as division). Is is also easier to change the factor with division.
>
Finally, and most importantly, a division expresses the intent, shift
expresses a way of achieving that intent. It is always better to express
your intent where possible until you have *proved* you need to worry about
the details.
>

after maybe a few years of experience, one has probably forgotten about the
issue anyways, the shift seems intuitive enough...

>>>33% may also be good.
>>>>
>>>33% is ugly though:
>>>size2=size+( size>>2)+(size> >4)+(size>>6) ; //bulky
>>>size2=size+s ize*33/100; //critical buffer size limit
>>Or more accurately and clearly
>>size2 = size + size/3;

>>
>odd that I missed such an obvious option...
>makes me look stupid, oh well...

>
You missed it because you insist on looking for micro-optimisations
instead of trying to express your intent clearly. Oh wait, that is another
way of saying it makes you look stupid. This is because this sort of
micro-optimisation has been stupid for many years because the compiler
will do it for you so wasting your time trying to beet the compiler is
stupid.
>

not optimizations. shifts are how one typically does these things...

it is much the same as why we call int variables i, j, and k I think, or
many other common practices. after enough years, and enough code, one
largely forgets any such reasoning, all rote response really...

actually, had I been thinking of compiler behavior much at all, I would have
realized that 'i/3' actually becomes a fixed point multiply by a reciprocal.
no such reasoning was used in this case.

this was a trivial and obvious mistake is all.

>>Or, if you can put the result back in size
>>size += size/3;
>>>
>>>but is a nice 4/3 ratio...
>>Nice is whatever gives a decent performance.

>>
>maybe, or whatever best follows a natural growth curve, or something...

>
I can't think of a good reason for wanting less than decent performance.
Of course, I consider all resources when thinking about performance, so
tell me what I've missed.

4/3 is a natural growth curve. something around this ratio should presumably
work good as a general mean case.

--
Flash Gordon

[Philip Potter]

Re: Dynamically resizing a buffer

cr88192 wrote:

4/3 is a natural growth curve. something around this ratio should presumably
work good as a general mean case.

What do you mean by this? What is a "natural growth curve"? And why is
4/3 more "natural" than, say, Euler's number or the golden ratio?

--
Philip Potter pgp <atdoc.ic.ac. uk

[Flash Gordon]

Re: Dynamically resizing a buffer

cr88192 wrote, On 23/08/07 11:12:

"Flash Gordon" <spam@flash-gordon.me.ukwro te in message
news:nurvp4xu0d .ln2@news.flash-gordon.me.uk...

>cr88192 wrote, On 23/08/07 00:03:

>>"Flash Gordon" <spam@flash-gordon.me.ukwro te in message
>>news:bo9up4xl fu.ln2@news.fla sh-gordon.me.uk...
>>>cr88192 wrote, On 22/08/07 13:20:
>>>>"Philip Potter" <pgp@see.sig.in validwrote in message
>>>>news:fah5a6 $qif$1@aioe.org ...
>>>>>Hello clc,
>>>>>>
>>>>>I have a buffer in a program which I write to. The buffer has
>>>>>write-only, unsigned-char-at-a-time access, and the amount of space
>>>>>required isn't known a priori. Therefore I want the buffer to
>>>>>dynamicall y grow using realloc().
>>>>>>
>>>>>A comment by Richard Heathfield in a thread here suggested that a good
>>>>>algorith m for this is to use realloc() to double the size of the
>>>>>buffer, but if realloc() fails request smaller size increments until
>>>>>realloc( ) succeeds or until realloc() has failed to increase the
>>>>>buffer by even one byte.
>>>>>>
>>>>doubling is probably too steep IMO.
>>>>>
>>>>I usually use 50% each time ('size2=size+(s ize>>1);').
>>>>25% may also be sane ('size2=size+(s ize>>2);').
>>>When you want to divide, divide. It is far easier for people to read and
>>>shows your intention. It is over 15 years since I saw a compiler that
>>>would not optimise division by a power of 2 to a shift.
>>shifts are obvious enough...

>It is not as obvious. I can read shifts, but for something like the above
>I then have to think to know what the scaling factor is, but with division
>the scaling factor is actually stated. I also don't have to worry about
>precedence because for arithmetic C just follows the rules I was taught
>before I saw my first computer. I also don't have to worry about whether
>it is a signed number (shifting a negative number is not required to act
>as division). Is is also easier to change the factor with division.
>>
>Finally, and most importantly, a division expresses the intent, shift
>expresses a way of achieving that intent. It is always better to express
>your intent where possible until you have *proved* you need to worry about
>the details.
>>

>
after maybe a few years of experience, one has probably forgotten about the
issue anyways, the shift seems intuitive enough...
>
>

>>>>33% may also be good.
>>>>>
>>>>33% is ugly though:
>>>>size2=size+ (size>>2)+(size >>4)+(size>>6 ); //bulky
>>>>size2=size+ size*33/100; //critical buffer size limit
>>>Or more accurately and clearly
>>>size2 = size + size/3;
>>odd that I missed such an obvious option...
>>makes me look stupid, oh well...

>You missed it because you insist on looking for micro-optimisations
>instead of trying to express your intent clearly. Oh wait, that is another
>way of saying it makes you look stupid. This is because this sort of
>micro-optimisation has been stupid for many years because the compiler
>will do it for you so wasting your time trying to beet the compiler is
>stupid.
>>

>
not optimizations. shifts are how one typically does these things...

Not if one is being sensible.

it is much the same as why we call int variables i, j, and k I think, or
many other common practices. after enough years, and enough code, one
largely forgets any such reasoning, all rote response really...

I have spent years programming in assembler where I would use shifts and
years spent programming in high level languages where I would not.

actually, had I been thinking of compiler behavior much at all, I would have
realized that 'i/3' actually becomes a fixed point multiply by a reciprocal.
no such reasoning was used in this case.
>
this was a trivial and obvious mistake is all.

A trivial mistake that does not get made if you code what you want to
express instead of trying to use tricks. That is part of the point.

Whatever the reason for you learning to use such tricks it is well past
time you learned not to use them excpet where it is proved that you need to.

>>>Or, if you can put the result back in size
>>>size += size/3;
>>>>
>>>>but is a nice 4/3 ratio...
>>>Nice is whatever gives a decent performance.
>>maybe, or whatever best follows a natural growth curve, or something...

>I can't think of a good reason for wanting less than decent performance.
>Of course, I consider all resources when thinking about performance, so
>tell me what I've missed.

>
4/3 is a natural growth curve. something around this ratio should presumably
work good as a general mean case.

Exponential is also a natural growth curve, if you don't believe me
check how populations grow in nature, for at least some it is
exponential until a crash.

The best growth curve depends on the situation. For some thing I know
that in the foreseeable future I need space for 10 foos and if it grows
beyond that it will be unlikely to be by much, so I start with 10 and
use a small linear growth (saves having to revisit the code unless
something very strange happens). For other things that would be
completely stupid.
--
Flash Gordon

[cr88192]

Re: Dynamically resizing a buffer


"Philip Potter" <pgp@see.sig.in validwrote in message
news:fajo5k$dpa $1@aioe.org...

cr88192 wrote:

>4/3 is a natural growth curve. something around this ratio should
>presumably work good as a general mean case.

>
What do you mean by this? What is a "natural growth curve"? And why is 4/3
more "natural" than, say, Euler's number or the golden ratio?
>

good mystery...
I don't know where this came from...


one would probably need to run simulations or something to determine this
(aka, 'what is the best growth curve').

well, in the past, I usually used 50%, or 3/2, probably good enough...

--
Philip Potter pgp <atdoc.ic.ac. uk