The fastest way to expand a byte array?

[fingerprint211b]

Hello
I'm writing a general purpose server in C , and I'm using a blocking function for receiving, so I read data byte-by-byte.
Anyway, you can see that I need to append these bytes (chars) to an array, so I can later read them/parse them/whatever I need.
A few logical answers (with even more questions following them) come to mind :

I can implement this as a linked list, but would it be wasteful on memory? Will it be fast, as it needs to be?
I can realloc() it, to add new bytes. That looks rather slow (unless I realloc() +10 bytes at a time)

All in all, it seems to me that realloc() is the way to go, after all, it is just malloc()+free() with some pointer swapping, which I would have to use in a linked list anyway. But, my server is a threaded beast, and (besides the main thread) I will have a thread dealing with every connection that my server accepts.

So, my question is :
Is there a faster way to do this?
Do you recommend using linked lists, in order to make my program more flexible (for instance, be able to receive more that 1 byte at a time)?
Should I simply use realloc() ?

[AJ]

Hi,

I wonder if something like Ring Buffer Streaming may be useful? Of course, you still have the decision of how big to make your ring buffer in the first place...

You mention realloc being a kind of malloc()+free(). Just one point here about optimisation - before using malloc/free and a memory copy, perhaps your realloc could check if the next heap area above the original pointer is free first, and if so, just expand the original heap area.

HTH,
Adam

[JamesM]

Hi,

I would NEVER recommend using linked lists as a buffer. Each linked list object must take up at least 4 bytes (assuming a 32-bit OS) for the pointer, and your datum size is only 1 byte, so each linked list item uses 400% more space than you need!

If you need to add and remove from the buffer asynchronously (probably), use a circular queue. That will do whatever you need, and with just one pointer increment/decrement per add/remove, it'll be a hell of a lot faster than any linked list...

James

EDIT: You win this round AJ, but I'll be back!... *mutters under breath*

[fingerprint211b]

Thanks for the ring buffer link.
But, the situation is a bit more...complicated.
In fact, server does nothing on it's own (just listens and assigns threads to deal with clients) : Every thread has it's own Lua interpreter, and loads a Lua script, which tells it what to do. If I wanted to turn it into an web server, my Lua script would need to receive text line-by-line, and it's up to server to know what a line is. It must find the '\n', and send everything before it to the Lua script. That is not a problem, but if I use a ring buffer I must give a limit to the lenght of the line. If I make it too small, the (oldest) data gets overwritten. If I make it too big, I waste memory (imagine 1000 threads, each having an eg. 512 byte buffer). The answer has to be dynamic, but I agree that linked lists are not the way to go. I could use singly-linked lists (3 bytes per 'object') but it's still a waste...

[JamesM]

Hi,

With a ring buffer you can do a dynamic expand - if you detect that the buffer is full, realloc() the buffer to a larger size, and copy the existing data across. Problem solved.

Cheers,

James

[fingerprint211b]

Agreed
Thank you JamesM, AJ