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