Jump to content
  • Advertisement
Sign in to follow this  
Purple-Haze

Improving Queue Code

This topic is 3905 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, A couple of weeks back I was given a coding test to write a manager for byte queues and optimize it for mem/cpu. An excerpt from the problem statement: -- On average while your system is running, there will be a dozen or so queues with an average of 100 or so bytes in each queue. Your functions may be asked to create a larger number of queues with fewer bytes in each. Your functions may be asked to create a smaller number of queues with more bytes in each. There may be spikes in the number of queues allocated, or in the size of an individual queue. -- Edit: I could't use any form of dynamic allocation. and max size for storage of queue data is MAX_DATA_SIZE. -- In the time given, I came up with what I thought would be a decent manager. I'd appreciate any input / criticism on improving the code. (In case you were wondering, I've already submitted the test ! ) This header file was provided and I had to implement the "interface"
#define MAX_QUEUES    64
#define MAX_DATA_SIZE 2048

namespace QueueManager
{
  // Queue handles are a single byte.  Do not change the typedef!
  typedef unsigned char QueueHandle;

  // Performs any necessary initialization of the QueueManager.
  void initializeQueueManager();

  // Creates a FIFO byte queue, returns the handle for the created
  // queue.
  QueueHandle createQueue();

  // Destroy the queue specified by queueHandle.
  void destroyQueue (QueueHandle queueHandle);

  // Adds a new byte to the queue specified by queueHandle.
  void enQueue (QueueHandle queueHandle, unsigned char value);

  // Pops the next byte off the queue specified by queueHandle.
  unsigned char deQueue (QueueHandle queueHandle);

  // If you are unable to satisfy a request due to lack of memory your 
  // code should call this provided failure function (which will not return):
  void onOutOfMemory();

  // If the caller makes any illegal request your code should call this 
  // provided failure function (which will not return):
  void onIllegalOperation(const char* fmt = 0, ... );
    // eg:
    //   int errorCode;
    //   ...
    //   onIllegalOperation("Error in createQueue: %d", errorCode);
}


#include "QueueManager.h"

namespace QueueManager
{
	const int CHUNK_SIZE = 8;				// in Bytes 
	const int NUM_BITS_CHUNK_DATA_COUNT = 4;  // number of bits needed to hold numbers from 0...CHUNK_SIZE
	const int NUM_CHUNKS = MAX_DATA_SIZE / CHUNK_SIZE;
	const int NUM_BITS_CHUNK_COUNT = 8;		// number of bits needed to hold numbers from 0...NUM_CHUNKS

	//Holds the the collective queue-contents
	unsigned char Data[MAX_DATA_SIZE];

	// Queue management data structures	
	struct CHUNKS
	{
		unsigned	next	: NUM_BITS_CHUNK_COUNT;    // next linked chunk
		unsigned	isFree	: 1;			 			 // is chunk free

	}Chunks[NUM_CHUNKS];

	struct QUEUES
	{
		// first and last chunk of the queue and the indices into those chunks
		unsigned startChunk 	: NUM_BITS_CHUNK_COUNT;
		unsigned s_idx			: NUM_BITS_CHUNK_DATA_COUNT;

		unsigned endChunk		: NUM_BITS_CHUNK_COUNT;
		unsigned e_idx			: NUM_BITS_CHUNK_DATA_COUNT;

		unsigned isActive		: 1;  // is queue free to be used by createqueue

	}Queues[MAX_QUEUES];


	// To check the amount of memory used in bytes for queue management data structures (without padding);
	const int MEM_USED =	( (NUM_CHUNKS * (NUM_BITS_CHUNK_COUNT + 1)) / 8 ) +
							( (MAX_QUEUES * (NUM_BITS_CHUNK_COUNT * 2 + NUM_BITS_CHUNK_DATA_COUNT * 2 + 1)) / 8 );

	// Performs any necessary initialization of the QueueManager.
	void initializeQueueManager()
	{
		int i;
		//Initialzie the Chunks, Queues datastructures
		for ( i=0; i < NUM_CHUNKS; i++ )
		{
			Chunks.isFree = 0x1;
			Chunks.next = 0x0;
		}

		for ( i=0; i < MAX_QUEUES; i++ )
		{
			Queues.isActive = 0x0;
		}
	}

	// Creates a FIFO byte queue, returns the handle for the created
	// queue.
	QueueHandle createQueue()
	{
		for ( int i=0; i < MAX_QUEUES; i++ )
		{
			// Look for an inactive (free) queue
			if ( int ( Queues.isActive ) == 0x0 ) 
			{
				for ( int j=0; j < NUM_CHUNKS; j++ )
				{
					// Look for the first free chunk to allocate
					if ( int( Chunks[j].isFree ) == 0x1 )
					{
						Queues.startChunk = j;
						Queues.isActive = 0x1;
						Queues.endChunk = j;
						Queues.s_idx = 0x0;
						Queues.e_idx = 0x0;
						
						Chunks[j].isFree = 0x0;

						return ( i );  //The handle is simply the index into the Queues array
					}
				}			
				onOutOfMemory();  // f'n exit
			}
		}
		onIllegalOperation("Unable to create Queue. MAX_QUEUES limit reached"); // exit;
		return 0; // to avoid noreturn warning;
	}

	// Destroy the queue specified by queueHandle.
	void destroyQueue (QueueHandle queueHandle)
	{
		int i,j,k;

		// Check if queueHandle is valid;
		if ( !( queueHandle < MAX_QUEUES && queueHandle >= 0 ) )
		{
			onIllegalOperation("Invalid Handle : %d",(int)queueHandle);
		}
		
		i = (int)(queueHandle);
		Queues.isActive = 0x0;		

		// If queue is madeup of only 1 chunk;
		if ( int(Queues.startChunk) == int(Queues.endChunk) )
		{
			Chunks[ int(Queues.startChunk) ].isFree = 0x1;
			return;
		}


		// Free all the chunks allocated by the queue;
		j = Queues.startChunk;
		k = Queues.endChunk;

		Chunks.isFree = 0x1;
		Chunks[k].isFree = 0x1;

		while ( j != k )
		{
			Chunks[j].isFree = 0x1;
			j = Chunks[j].next;
		}
	}

	// Adds a new byte to the queue specified by queueHandle.
	void enQueue (QueueHandle queueHandle, unsigned char value)
	{
		int i,j,k;

		// Check if queueHandle is valid;
		if ( !( queueHandle < MAX_QUEUES && queueHandle >= 0 ) )
		{
			onIllegalOperation("Invalid Handle : %d",(int)queueHandle);
		}

		i = int( queueHandle );
		j = int( Queues.endChunk );
		k = int( Queues.e_idx );

		Data[ ( j * CHUNK_SIZE ) + k ] = value;
		
		// check if we have reached the chunk end;
		if ( (k+1) < CHUNK_SIZE )
		{
			Queues.e_idx = Queues.e_idx + 0x1;
		}
		else
		{
			for ( int n=0; n < NUM_CHUNKS; n++ )
			{
				// Allocate a fresh chunk for the next value to be enqued; 
				if ( int(Chunks[n].isFree) == 0x1 ) 
				{
					Chunks[n].isFree = 0x0;
					
					Chunks[j].next = n;
					Queues.endChunk = n;
					Queues.e_idx = 0x0;
					
					return;
				}
			}
			onOutOfMemory();
		}

	}

	// Pops the next byte off the queue specified by queueHandle.
	unsigned char deQueue (QueueHandle queueHandle)
	{
		int i,j,k;
		unsigned char val;

		// Check if queueHandle is valid;
		if ( !( queueHandle < MAX_QUEUES && queueHandle >= 0 ) )
		{
			onIllegalOperation("Invalid Handle : %d",(int)queueHandle);
		}

		i = int( queueHandle );
		j = int( Queues.startChunk );
		k = int( Queues.s_idx );

		// Check if Queue is empty;
		if	( (int(Queues.startChunk) == int(Queues.endChunk)) &&
					(int(Queues.s_idx) == int(Queues.e_idx))
				)
		{
			onIllegalOperation("Queue is empty");
		}

		val = Data[ j * CHUNK_SIZE + k];
		
		// check if we have reached the chunk end;
		if ( (k+1) < CHUNK_SIZE )
		{
			Queues.s_idx = Queues.s_idx + 0x1;
		}
		else
		{
			// update the start chunk to the next linked chunk

			Queues.startChunk = Chunks[j].next;
			Queues.s_idx = 0x0;

			// free current chunk
			Chunks[j].isFree = 0x1;
		}

		return val;
	}
};



Not sure why the tabs are off.. [Edited by - kapilkapre on February 12, 2008 8:10:56 PM]

Share this post


Link to post
Share on other sites
Advertisement
Since this is a job test, it's more of an impression than a true/false type of thing. The only way to not pass is to not meet the specification, or provide non-functioning code.

But there is no "correct" way, especially not with specifications given. If anything, this may later serve as basis for an interview, where you may need to justify your choices, or propose alternatives.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Since this is a job test, it's more of an impression than a true/false type of thing. The only way to not pass is to not meet the specification, or provide non-functioning code.

But there is no "correct" way, especially not with specifications given. If anything, this may later serve as basis for an interview, where you may need to justify your choices, or propose alternatives.


Yes I know that. The point of the thread was so that I could improve the code further and maybe learn some new optimization tricks.

Share this post


Link to post
Share on other sites
Quote:
Original post by kapilkapre

Yes I know that. The point of the thread was so that I could improve the code further and maybe learn some new optimization tricks.


There's nothing to optimize due to lack of characteristic usage and profiling data. First requirement for optimization is observing where bottle-necks are, and this is something that's lacking here.

One thing though:
 // f'n exit


Is that short for "function exit"?

Share this post


Link to post
Share on other sites
I've completed this same quiz in the last 2-3 months, taking an approach similar to yours, although the header given is slightly different. I wonder if it was for the same company, although its probably for the best to *not* answer that question in public since it may unjustly influence future applicant's code.

At any rate, I'm at work now and about to head home. I'll post to compare some notes when I have my code in front of me.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus

There's nothing to optimize due to lack of characteristic usage and profiling data. First requirement for optimization is observing where bottle-necks are, and this is something that's lacking here.

I agree, but it might still be possible to squeeze some extra memory out. Maybe a new funky way of organizing the Queues. I just wanted to sorta put it out there and see what people think.


Quote:

One thing though:
 // f'n exit


Is that short for "function exit"?

ah.. yes :D the wording should have been changed..

Share this post


Link to post
Share on other sites
Quote:
Original post by ravyne2001
I've completed this same quiz in the last 2-3 months, taking an approach similar to yours, although the header given is slightly different. I wonder if it was for the same company, although its probably for the best to *not* answer that question in public since it may unjustly influence future applicant's code.

At any rate, I'm at work now and about to head home. I'll post to compare some notes when I have my code in front of me.

Hmm, Thats a valid point but the question is very generic. (Queue Management). I was going to post another question; something more specific but decided against it for that reason. Besides, how do you explain code which you didn't write...

Share this post


Link to post
Share on other sites
A few things. enQueue/deQueue don't check that their argument is a handle to an active queue, only that it doesn't exceed array bounds. That means user code could delete a queue then silently continue using it, which should really result in a call to onIllegalOperation.

About the only thing I can see regarding performance is to change how you find free resources. Instead of searching through the whole array every time, you could maintain a lowest numbered free spot variable. This is still worst case O(n), but average time would be better. You could get fancy and dream up some scheme for approximating a free list without using dynamic allocation, if you like - although it's hard to justify any real complexity.

Share this post


Link to post
Share on other sites
Quote:
Original post by gsg
A few things. enQueue/deQueue don't check that their argument is a handle to an active queue, only that it doesn't exceed array bounds. That means user code could delete a queue then silently continue using it, which should really result in a call to onIllegalOperation.

Ahh.. crap. ! shoulda gone over the code once more ..
Quote:

About the only thing I can see regarding performance is to change how you find free resources. Instead of searching through the whole array every time, you could maintain a lowest numbered free spot variable. This is still worst case O(n), but average time would be better. You could get fancy and dream up some scheme for approximating a free list without using dynamic allocation, if you like - although it's hard to justify any real complexity.

That sounds like a good idea. I wasn't sure of what the priority (mem or cpu , or both!) should be. They gave me a MAX_DATA_SIZE of 2048 bytes so I assumed mem to be really scarce.

Share this post


Link to post
Share on other sites
That and the restriction on dynamic allocation suggests an embedded system, so you probably wouldn't have a whole lot of any resource to throw around if this were a real world problem. Maybe have a think about how you'd design a resource allocator to best balance size, performance, and maintainability.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!