Jump to content
  • Advertisement
Sign in to follow this  
  • entries
    191
  • comments
    861
  • views
    117819

Buffers, oh my.

Sign in to follow this  
Mithrandir

162 views

I decided to play around with some different stream buffer concepts in .net, to see what kind of storage mechanism would be best for my high performance networking engine.


In the process, I came up with two paradigms:

NaiveBuffer
- Data always starts at index 0
- when the buffer is full, it autoresizes to twice its previous capacity
- removing data from the beginning of the buffer moves everything at the end downwards

CircularBuffer
- Data can start at any arbitrary index
- Resizes just like NaiveBuffer
- Oftentimes, data will cross the end of the array and overlap into the start of the array
- uses arraysegments to access the two parts of the array


So we have...


Naive Circular
Insertion of x items O(x) O(x)
Deletion of x items O(n) O(1)



where n is the count of the items in the buffer. Note that both insertion algorithms get bumped up to O(n) whenever they need to resize the array.


So my benchmarks:


Firstly, a comparison where every iteration adds X bytes, then removes Y bytes, where Y is less than X.

The winner should be obvious, but I never imagined by how much it would win.


CircularBuffer cbuffer = new CircularBuffer();
NaiveBuffer nbuffer = new NaiveBuffer();
byte[] b = new byte[1024];
System.Random r = new System.Random();
int seed = DateTime.Now.Millisecond;
int add;
int remove;

DateTime start;
DateTime end;

r = new System.Random( seed );
start = DateTime.Now;
for( int x = 0; x < 100000; x++ )
{
add = r.Next( b.Length - 1 );
remove = r.Next( add );
cbuffer.Add( b, add );
cbuffer.Remove( remove );
}
end = DateTime.Now;
TimeSpan ctime = end.Subtract( start );


r = new System.Random( seed );
start = DateTime.Now;
for( int x = 0; x < 100000; x++ )
{
add = r.Next( b.Length - 1 );
remove = r.Next( add );
nbuffer.Add( b, add );
nbuffer.Remove( remove );
}
end = DateTime.Now;
TimeSpan ntime = end.Subtract( start );





results:

circular buffer: 0.20 seconds
naive buffer: 17 minutes, 23.83 seconds

ouch.


Now, unfortunately for Mr. Circular buffer, real-life network traffic probably isn't going to work like that. A more realistic test is if we queue up multiple messages, and then remove them all when they are sent (rarely will they not all be sent):


CircularBuffer cbuffer = new CircularBuffer();
NaiveBuffer nbuffer = new NaiveBuffer();
byte[] b = new byte[1024];
System.Random r = new System.Random();
int seed = DateTime.Now.Millisecond;
DateTime start;
DateTime end;
int reps;


r = new System.Random( seed );
start = DateTime.Now;
for( int x = 0; x < 5000000; x++ )
{
reps = r.Next( 1, 16 );
for( int y = 0; y < reps; y++ )
{
cbuffer.Add( b, r.Next( 1, b.Length - 1 ) );
}
cbuffer.Remove( cbuffer.Count );
}
end = DateTime.Now;
TimeSpan ctime = end.Subtract( start );


r = new System.Random( seed );
start = DateTime.Now;
for( int x = 0; x < 5000000; x++ )
{
reps = r.Next( 1, 16 );
for( int y = 0; y < reps; y++ )
{
nbuffer.Add( b, r.Next( 1, b.Length - 1 ) );
}
nbuffer.Remove( nbuffer.Count );
}
end = DateTime.Now;
TimeSpan ntime = end.Subtract( start );





I increased the iterations to 5,000,000 from 100,000 to give more meaningful times.

circular: 20.48 seconds
naive: 14.26 seconds


Sorry circular, you're incredibly awesome in the worst case, but your overhead in typical circumstances says that NaiveBuffer is faster.






Regardless, I still think I'm going to use the circular buffer anyways. The overhead isn't really that great, and 5,000,000 iterations will probably take the server over 10 minutes to reach in the real world anyways, so I don't think it's a huge deal.
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!