Solved

review buffer implementation

Posted on 2008-10-04
6
1,001 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
  • 3
  • 3
6 Comments
 
LVL 45

Accepted Solution

by:
sunnycoder earned 500 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
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 
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

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Suggested Solutions

If your system is showing symptoms of browser hijacks or 'google search redirects' check out my other article (http://rdsrc.us/u3GP7A) first and run the tool TDSSKiller (http://rdsrc.us/GDBBs4) to get rid of the infection. Once done, and if the …
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
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.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

743 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

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now