CQueue

$Revision: 23 $

Description

This class a simple, thread-safe but high-performance queue. It allows one thread to add to the queue while another thread can get from the queue without blocking. Normally, getting something from a queue blocks anyone from adding to that queue. This is a performance bottleneck. CQueue was designed for speed.

CQueue automatically grows the queue when needed. It is a first-in, first-out queue. In other words, the order in which things were added to the queue is the order in which they will be retrieved from the queue.

Constructors

CQueue( DWORD initial_queue_size = 1024 ): Constructs the object. You can specify an initial size for the queue. The larger the queue the fewer the growth periods (which can be expensive).

Methods

BOOL Add( DWORD new_item ) BOOL Add( void * item ): This is how you add something to the queue. The queue will automatically grow to accomodate new items.
void Dump( CDumpContext& dump_context ) const: Present only in debug builds. Dumps interesting information about CQueue to the dump_context provided.
void Empty( void ): Empties the queue. There will be no entries in the queue when you call this method.
BOOL Get( DWORD& item ) BOOL Get( void * & item ): This is how you get something from the queue. It will return TRUE if a value was successfully retrieved from the queue. It will return FALSE when there is nothing in the queue to pull.
DWORD GetLength( void ) const: Returns the number of items in the queue. Warning! This method will prevent anything from being added or gotten from the queue. It must prevent queue operations for the time it takes to compute the number of elements in the queue. In other words, calling this method is a performance hit.
DWORD GetMaximumLength( void ) const: Returns the maximum size of the current queue. This is not the maximum number of things the queue can hold. It is the maximum number of items the queue can hold before it enters a growth period. Currently, when the queue fills, its size doubles.

Performance

It is boring to use CQueue on a single-CPU machine. The chances of entering a deadlock are pretty much nil. However, CQueue really shines on multiple-CPU boxes. To test this, I created a simple toy program that creates two threads. One constantly adds to the test queue while the other thread constantly gets from the test queue. Using a single locking mechanism on a two-CPU machine, I was able to get this performance from the queue code in a 30 second test:

Number of Adds	1,517,100 (50,570 operations per second)
Number of Gets	1,200,136 (40,004 operations per second)
Number of Items Left In Queue	316,974
Queue Grew To Maximum Size	524,288
Average CPU Usage	58%

Using the double-locking technique, I got these numbers:

Number of Adds	11,675,987 (389,199 operations per second)
Number of Gets	11,675,537 (389,184 operations per second)
Number of Items Left In Queue	462
Maximum Size	1024
Average CPU Usage	100%

As you can see, the double-locking mechanism is the best. CQueue

Example

void test_CQueue( void )
{
   WFCTRACEINIT( TEXT( "test_CQueue()" ) );

   CQueue queue( 4 );

   queue.Add( 1 );
   queue.Add( 2 );
   queue.Add( 3 );

   WFCTRACE( TEXT( "Next addition should cause growth" ) );

   queue.Add( 4 );
   queue.Add( 5 );

   DWORD item = 0;

   while( queue.Get( item ) != FALSE )
   {
      WFCTRACEVAL( TEXT( "Got ", item ) );
   }

   queue.Add( 6 );
   queue.Add( 7 );
   queue.Add( 8 );

   queue.Get( item );

   queue.Add( 9 );
   queue.Add( 10 );

   while( queue.Get( item ) != FALSE )
   {
      WFCTRACEVAL( TEXT( "Got ", item ) );
   }
}

Copyright, 2000, Samuel R. Blackburn
$Workfile: CQueue.cpp $
$Modtime: 1/17/00 9:10a $