Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Dynamically resizing a buffer

Reply
Thread Tools

Dynamically resizing a buffer

 
 
Philip Potter
Guest
Posts: n/a
 
      08-22-2007
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_writebyte(), 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_writebyte(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_FAILURE);
}
buf->size += inc;
}
buf->data[buf->index++] = byte;
}

--
Philip Potter pgp <at> doc.ic.ac.uk
 
Reply With Quote
 
 
 
 
Richard
Guest
Posts: n/a
 
      08-22-2007
Philip Potter <(E-Mail Removed)> writes:

> 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.


Double the size of the buffer? Never IMO. Not if you "designed" the buffer
to be "about right" in the first place. Suppose it doesn't fail but does
exhaust memory? Well, bang goes your next malloc.

Keep it simple. Have a delta increase and use that. I would suggest
something like 10-20% of the initial size.

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

>
> The basic idea is below. The key function is MyBuffer_writebyte(),
> 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_writebyte(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_FAILURE);
> }
> buf->size += inc;
> }
> buf->data[buf->index++] = byte;
> }


--
 
Reply With Quote
 
 
 
 
Mark Bluemel
Guest
Posts: n/a
 
      08-22-2007
Philip Potter wrote:

>
> 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_writebyte(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_FAILURE);
> }


You never replace buf->data... It will continue to point to the original
space, which may have been freed ...

> buf->size += inc;
> }
> buf->data[buf->index++] = byte;
> }
>


I'd split out the resizing to a separate function, as it's a
generalizable technique.

You could combine the two forms of loop control (size of increment,
success/failure of allocation) in the while.

This (untested) is my rough hack :-

void MyBuffer_writebyte(MyBuffer *buf, unsigned char byte) {
if(buf->size == buf->index) {
if(!resizeBuffer(buf)){
exit(EXIT_FAILURE); /* or some better error handling */
}
}
buf->data[buf->index++] = byte;
}

/* returns new size */
int resizeBuffer(MyBuffer *buf) {
size_t inc = buf->size;
unsigned char *tmp = NULL;
while(inc>0 &&
(tmp = realloc(buf->data, buf->size + inc)) == NULL) {
inc/=2;
}
if(tmp!=NULL) {
buf->data = tmp;
buf->size += inc;
return buf->size;
} else {
return 0;
}

}
 
Reply With Quote
 
Philip Potter
Guest
Posts: n/a
 
      08-22-2007
Richard wrote:
> Philip Potter <(E-Mail Removed)> writes:
>
>> 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.

>
> Double the size of the buffer? Never IMO. Not if you "designed" the buffer
> to be "about right" in the first place. Suppose it doesn't fail but does
> exhaust memory? Well, bang goes your next malloc.
>
> Keep it simple. Have a delta increase and use that. I would suggest
> something like 10-20% of the initial size.
>
> 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.

Phil

--
Philip Potter pgp <at> doc.ic.ac.uk
 
Reply With Quote
 
Philip Potter
Guest
Posts: n/a
 
      08-22-2007
Mark Bluemel wrote:
> Philip Potter wrote:
>
> You never replace buf->data... It will continue to point to the original
> space, which may have been freed ...


Whoops! That bug was also in my project code...

>> buf->size += inc;
>> }
>> buf->data[buf->index++] = byte;
>> }
>>

>
> I'd split out the resizing to a separate function, as it's a
> generalizable technique.
>
> You could combine the two forms of loop control (size of increment,
> success/failure of allocation) in the while.


I think this is clumsy too, but less so

> This (untested) is my rough hack :-
>
> void MyBuffer_writebyte(MyBuffer *buf, unsigned char byte) {
> if(buf->size == buf->index) {
> if(!resizeBuffer(buf)){
> exit(EXIT_FAILURE); /* or some better error handling */
> }
> }
> buf->data[buf->index++] = byte;
> }
>
> /* returns new size */
> int resizeBuffer(MyBuffer *buf) {
> size_t inc = buf->size;
> unsigned char *tmp = NULL;
> while(inc>0 &&
> (tmp = realloc(buf->data, buf->size + inc)) == NULL) {
> inc/=2;
> }
> if(tmp!=NULL) {
> buf->data = tmp;
> buf->size += inc;
> return buf->size;
> } else {
> return 0;
> }
>
> }


Surely resizeBuffer() should return size_t?

--
Philip Potter pgp <at> doc.ic.ac.uk
 
Reply With Quote
 
Mark Bluemel
Guest
Posts: n/a
 
      08-22-2007
Philip Potter wrote:
> Mark Bluemel wrote:


>> I'd split out the resizing to a separate function, as it's a
>> generalizable technique.
> >
>> You could combine the two forms of loop control (size of increment,
>> success/failure of allocation) in the while.

>
> I think this is clumsy too, but less so


I'm inclined to agree. I'm still trying to think of a more elegant solution.

>
>> This (untested) is my rough hack :-

<snip>

>> /* returns new size */
>> int resizeBuffer(MyBuffer *buf) {

<snip>
> Surely resizeBuffer() should return size_t?


Indeed it should.
 
Reply With Quote
 
cr88192
Guest
Posts: n/a
 
      08-22-2007

"Philip Potter" <(E-Mail Removed)> wrote in message
news:fah5a6$qif$(E-Mail Removed)...
> 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+(size>>1);').
25% may also be sane ('size2=size+(size>>2);').
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

but is a nice 4/3 ratio...

<snip>


 
Reply With Quote
 
Mark Bluemel
Guest
Posts: n/a
 
      08-22-2007
Philip Potter wrote:

> 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_writebyte(), 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_writebyte(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_FAILURE);
> }
> buf->size += inc;
> }
> buf->data[buf->index++] = byte;
> }
>


Here's a simple alternative :-

void MyBuffer_writebyte(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) {
buf->data = tmp;
buf->size += inc;
inc = 0; /* force exit */
} else {
inc /= 2;
}
}
if(tmp==NULL) {
/* couldn't allocate any more space, print error and exit */
exit(EXIT_FAILURE);
}
}
buf->data[buf->index++] = byte;
}
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      08-22-2007
Richard <(E-Mail Removed)> writes:

> Philip Potter <(E-Mail Removed)> writes:
>
>> 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.

>
> Double the size of the buffer? Never IMO. Not if you "designed" the buffer
> to be "about right" in the first place. Suppose it doesn't fail but does
> exhaust memory? Well, bang goes your next malloc.
>
> Keep it simple. Have a delta increase and use that. I would suggest
> something like 10-20% of the initial size.


"of the initial size" means a linear growth pattern. An exponential
growth pattern gives better performance over a range of input
patterns. If memory is tight, then one can use a factor of the
current size that is < 2 but still > 1 to get O(log n) allocations
rather than O(n).

Initially, this is what I thought you meant (20% of the current size
is factor of 1.2) but I see now you wrote initial. Of course, there
are cases where one knows this to be a better strategy, but I think
they are rare.

To the OP:
Another strategy is to switch to linear growth (maybe even only adding
1!) when the doubling fails. The rationale is that we are now in a low
memory situation so it may be better (in order to proceed at all) to
allocate the minimum rather than that maximum. We also know that we
enter this pattern only once in the growth of any buffer, so the cost is
never that large (in big O terms).

--
Ben.
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      08-22-2007
Philip Potter wrote:
> [...]
>
> 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.
> [...]
> 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_FAILURE);
> }
> buf->size += inc;


The loop has two termination conditions -- realloc()
succeeds, or increment goes to zero -- so I don't see how
you can avoid two tests. But as written there's an after-
the-loop test to (re-)discover why the loop ended. That,
at least, is easy to get rid of:

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

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Resizing a div by resizing its borders Pil (Trustworthy from Experience) Javascript 9 04-21-2009 07:35 AM
Resizing a div by resizing its borders Proper Javascript 0 04-18-2009 08:02 PM
When using System.IO.FileStream, I write 8 bytes, then seek to the start of the file, does the 8 bytes get flushed on seek and the buffer become a readbuffer at that point instead of being a write buffer? DR ASP .Net 2 07-29-2008 09:50 AM
convert M bit buffer to N bit buffer runcyclexcski@yahoo.com C++ 2 03-26-2007 09:43 AM
How to know the buffer size and increase buffer size in c++ Raja C++ 12 06-21-2004 06:21 PM



Advertisments