Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

review buffer implementation

Posted on 2008-10-04
6
Medium Priority
?
1,013 Views
Last Modified: 2012-05-05
Please review the code i wrote, and suggest fixes.
Speed optimizations are also very much appreciated.

the code should buffer data, to have it processed a while after.
i simulated this in the main function, with simple(short) strings.

there is a circular single linked list from structures, describing each buffer item.
head is the current write position, tail is the current read position.

in the full implementation can be guaranteed:
the biggest possible item size will fit atleast 100 times in the buffer.
there need to be a maximum of 100 items cached.
it will always run on windows xp (no other platforms supported)

other comments:
cout and the process() function are only for testing purposes.

one pair of append() and removelast() would be executed about 20 times a second
this is why i chose to allocate all memory beforehand, to improve speed.
#include <iostream>
#include <windows.h>
using namespace std;
 
 
struct buf_info {
	buf_info *next;
	char *start;
	int len;
};
 
#define BUF_LEN		9		//this will be around 4096 in the non-test version
#define AVE_SIZE	3		//this will be around 49
#define NUM_STRUCT	3		//this will be around 84 (4096/49, rounded up)
 
char *cyclic_buf;			//dynamic, to not generate an application from 4 MB
buf_info *head = NULL;		//circular list, where head and tail walk trough
buf_info *tail = NULL;		//
 
 
void process( char *buf, int len )		//testfunc, this will be replaced by a real processing function
{
	for( int n = 0; n < len; n++ )
		cout << (char)*(buf+n);
	cout << endl;
}
 
bool removelast();
void append( char *test, int len )
{
	/*single linked list (circular) so cant look one back, thats why the 
	head needs to point to the item item before what we want to fill when entering this function*/
	if( !head->next->len )
	{
		head->next->len = len;
		head->next->start = head->start+head->len;
		head = head->next;
		if( ((int)head->start -(int)&cyclic_buf[0] + head->len > BUF_LEN) )		//dont want the message to split
			head->start = (char *)&cyclic_buf[0];
		memcpy( head->start, test, head->len );
	} else { //catched up with head
		removelast();
		append( test, len );
	}
}
 
bool removelast()
{
	if( tail->len )
	{
		process( tail->start, tail->len );
		tail->len = 0;
		tail = tail->next;
		if( head->next == tail )						//catched up with the head
			tail->start = (char *)&cyclic_buf[0];		//start at begin of buf
		return true;
	}
	return false;
}
 
 
void initBuf()
{
	buf_info *cur;		//for constructing the circular list
	cyclic_buf = (char*)malloc( BUF_LEN );
	head = new buf_info;
	cur = head;
	head->len = 0;
	for( int n = 0; n < NUM_STRUCT; n++ )
	{
		cur->next = new buf_info;
		cur = cur->next;
		cur->len = 0;
	}
	cur->next = head;
	head->start = (char *)&cyclic_buf[0];
	tail = head->next;
}
 
void freeBuf()
{
	buf_info *cur;
	free( cyclic_buf );
	tail = head->next;
	while( tail != head )
	{
		cur = tail->next;
		free( tail );
		tail = cur;
	}
	free( head );
}
 
 
int main()
{
	initBuf();		//setup all stuff (app startup)
 
	//fill the buffer
	append( "aaa", 3 );
	
	//normal operation, one write, one read 
	append( "bbbb", 4 );	//bigger item, cause this happens approx 1/20th
	removelast();
	
	append( "ccc", 3 );
	removelast();
	
	append( "ddd", 4 );
	removelast();
	
	append( "eee", 3 );
	removelast();
	
	while( removelast() );	//empty the buffer
	cin.get();				//dont close console :/
 
	freeBuf();		//free memory (app shutdown)
}

Open in new window

0
Comment
Question by:Mark_FreeSoftware
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
6 Comments
 
LVL 45

Accepted Solution

by:
sunnycoder earned 2000 total points
ID: 22643143
See comments inline. You should first sit down with a pen and paper and determine what exactly you want this program to do - goals, constraints, assumptions - everything.
#include <iostream>
#include <windows.h>
using namespace std;
 
 
struct buf_info {
        buf_info *next;
        char *start;
        int len;
};
 
#define BUF_LEN         9               //this will be around 4096 in the non-test version
#define AVE_SIZE        3               //this will be around 49
#define NUM_STRUCT      3               //this will be around 84 (4096/49, rounded up)
 
char *cyclic_buf;                       //dynamic, to not generate an application from 4 MB
buf_info *head = NULL;          //circular list, where head and tail walk trough
buf_info *tail = NULL;          //
 
 
void process( char *buf, int len )              //testfunc, this will be replaced by a real processing function
{
        for( int n = 0; n < len; n++ )
                cout << (char)*(buf+n);
        cout << endl;
}
 
bool removelast();
void append( char *test, int len )
{
        /*single linked list (circular) so cant look one back, thats why the 
        head needs to point to the item item before what we want to fill when entering this function*/
        if( !head->next->len )
        {
                head->next->len = len;
                head->next->start = head->start+head->len; //--->So all of the strings are in the same buffer and you use all the nodes to just keep track of offsets in this buffer??? This negates all benefits of a linked list ... what if I want to delete a node in between. This implementation severely limits your evolution. Also what stops you from eating your own tail in case you get a long message?
                head = head->next;
                if( ((int)head->start -(int)&cyclic_buf[0] + head->len > BUF_LEN) )             //dont want the message to split
                        head->start = (char *)&cyclic_buf[0];
                memcpy( head->start, test, head->len );
        } else { //catched up with head
                removelast();
                append( test, len );
        }
}
 
bool removelast()
{
        if( tail->len )
        {
                process( tail->start, tail->len );
                tail->len = 0;
                tail = tail->next;
                if( head->next == tail )                                                //catched up with the head
                        tail->start = (char *)&cyclic_buf[0];           //start at begin of buf
                return true;
        }
        return false;
}
 
 
void initBuf()
{
        buf_info *cur;          //for constructing the circular list
        cyclic_buf = (char*)malloc( BUF_LEN );  //-->>you are mining malloc and new - stick to one of them. If you continue using both of them, chances are some day you would free the memory allocated by new or delete the memory allocated by malloc - both dangerous
        head = new buf_info;
        cur = head;
        head->len = 0;
        for( int n = 0; n < NUM_STRUCT; n++ )
        {
                cur->next = new buf_info;
                cur = cur->next;
                cur->len = 0;
                //-->> cur->start has been left uninitialized - this would be a dangling pointer
        }
        cur->next = head;
        head->start = (char *)&cyclic_buf[0];
        tail = head->next;    //--->> Tail should be the last element in the list not next to head. Else you would keep deleting from list while there is plenty of space left - effectively using only 2 places. tail = head; head=head->next;
 
//-->> What is the benefit of dynamic allocation? You are creating a fixed size link at startup - you dont expand as required - you dont shrink as required - you might as well have simply declared a fixed size array. That way you would not have to spend memory on pointers and code would become much easier
}
 
void freeBuf()
{
        buf_info *cur;
        free( cyclic_buf );
        tail = head->next;
        while( tail != head )
        {
                cur = tail->next;
                free( tail );
                tail = cur;
        }
        free( head );
}
 
 
int main()
{
        initBuf();              //setup all stuff (app startup)
 
        //fill the buffer
        append( "aaa", 3 );
        
        //normal operation, one write, one read 
        append( "bbbb", 4 );    //bigger item, cause this happens approx 1/20th
        removelast();
        
        append( "ccc", 3 );
        removelast();
        
        append( "ddd", 4 );
        removelast();
        
        append( "eee", 3 );
        removelast();
        
        while( removelast() );  //empty the buffer
        cin.get();                              //dont close console :/
 
        freeBuf();              //free memory (app shutdown)
}

Open in new window

0
 
LVL 13

Author Comment

by:Mark_FreeSoftware
ID: 22644118
first of all, thank you for digging trough all code :)

So all of the strings are in the same buffer and you use all the nodes to just keep track of offsets in this buffer??? This negates all benefits of a linked list ... what if I want to delete a node in between. This implementation severely limits your evolution.
-since this is for buffering, i do not want to delete items inbetween

Also what stops you from eating your own tail in case you get a long message?
-the size of the buffer, i took the average packet, the average buffering time, and calculated the needed size of both the linked list and the big buffer to prevent this

you are mining malloc and new - stick to one of them. If you continue using both of them, chances are some day you would free the memory allocated by new or delete the memory allocated by malloc - both dangerous
-wow, didnt know this was dangerous, thanks!

cur->start has been left uninitialized - this would be a dangling pointer
-yes, but by design:
the head->start is set, and every next item is based on head->start+head->len

Tail should be the last element in the list not next to head. Else you would keep deleting from list while there is plenty of space left - effectively using only 2 places. tail = head; head=head->next;
-this is fixed when append is called mulptiple times, without removelast inbetween. (which would be the case in the final app)

What is the benefit of dynamic allocation?
You are creating a fixed size link at startup - you dont expand as required - you dont shrink as required - you might as well have simply declared a fixed size array. That way you would not have to spend memory on pointers and code would become much easieryes, code would be easier, but:
most of the buffered data is 49 bytes,
there are sometimes 50, 51 bytes, and once or twice 153 bytes
so buffers would need to be atleast 153 bytes, (probably more since size depends on information sent, this one can increase even more)
which would be an overhead of approximately 100 bytes for each frame
this compared to 4 bytes for a pointer, or 12 for the struct, is saving alot memory.

again, thank you for digging trough all code!
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22644208
Okay - but would it not save you more if you had a linked list that could grow dynamically ... something like

if (more input)
{
     allocate new node
     allocate memory for data and assign data
     append node to end of list
}
...
if ( node_already_used)
{
     delete memory allocated for data
     delete node from head of list
}

Whenever client is done with consuming a buffer node, it can signal the same and that node can be freed.
This gives you the flexibility of expanding and shrinking your buffer as required.

Current price of RAM is few cents per MB ... The price of this implementation is maintainability and flexibility. It will be hard to evolve this kind of buffer management. Unless you are developing for an embedded system, I would recommend revisiting the design.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 13

Author Comment

by:Mark_FreeSoftware
ID: 22644235
this would indeed be the preferred and more maintainable solution,
but speed _is_ an issue

the code needs to be as fast as possible, and i think that allocate and delete adds some unneeded overhead.


i will run some speedtests later today to see what the added overhead is
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22644281
Your implementation looks good for speed - apart from startup there are no mallocs and free - which incur big run time costs. Most expensive operations you are doing is memcpy but since your buffers are small and memcpy is usually optimized for writing double words - you should not see much problems there.

Final word of caution - do test for all boundary cases. Such implementations typically falter when all buffers are full/all+1 items were available/all-1 were available/Inserting first element/deleting last element/inserting when full/deleting when empty.  I am still having difficulty wrapping my head around this code for dry running boundary cases - but thats probably just because I am not used to such implementations :)

Good Luck!
0
 
LVL 13

Author Closing Comment

by:Mark_FreeSoftware
ID: 31503096
thank you for taking the time,
sadly i can't give out more points,
i would like to cause iI know how hard it is to understand other peoples code ;)
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
When you start your Windows 10 PC and got an "Operating system not found" error or just saw  "Auto repair for startup" or a blinking cursor with black screen. A loop for Auto repair will start but fix nothing.  You will be panic as there are no back…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

636 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question