Sign in to follow this  

Improving Queue Code

This topic is 3590 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[i].isFree = 0x1;
			Chunks[i].next = 0x0;
		}

		for ( i=0; i < MAX_QUEUES; i++ )
		{
			Queues[i].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[i].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[i].startChunk = j;
						Queues[i].isActive = 0x1;
						Queues[i].endChunk = j;
						Queues[i].s_idx = 0x0;
						Queues[i].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[i].isActive = 0x0;		

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


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

		Chunks[i].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[i].endChunk );
		k = int( Queues[i].e_idx );

		Data[ ( j * CHUNK_SIZE ) + k ] = value;
		
		// check if we have reached the chunk end;
		if ( (k+1) < CHUNK_SIZE )
		{
			Queues[i].e_idx = Queues[i].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[i].endChunk = n;
					Queues[i].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[i].startChunk );
		k = int( Queues[i].s_idx );

		// Check if Queue is empty;
		if	( (int(Queues[i].startChunk) == int(Queues[i].endChunk)) &&
					(int(Queues[i].s_idx) == int(Queues[i].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[i].s_idx = Queues[i].s_idx + 0x1;
		}
		else
		{
			// update the start chunk to the next linked chunk

			Queues[i].startChunk = Chunks[j].next;
			Queues[i].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
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
Its gotten late, so I'll have to reply with a more in-depth answer tomorrow, I may actually PM you, due to my concern for polluting the applicant pool.

However, one quick note I'll make is that I read the question specification differently than you. I read the question specification as indicating that you had *exactly* 2048 bytes in which to store *everything* -- book-keeping included. Perhaps you assumed otherwise, perhaps you were told otherwise, but this makes your implementation very different than mine.

Your implementation uses 384 extra bytes to keep the books. In contrast, mine uses only 256 bytes for book-keeping, and its embedded within the 2048 byte data area. On the other hand, it could be me that was mistaken, and perhaps how I read the specification was not in line with what they intended [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by ravyne2001
Its gotten late, so I'll have to reply with a more in-depth answer tomorrow, I may actually PM you, due to my concern for polluting the applicant pool.

However, one quick note I'll make is that I read the question specification differently than you. I read the question specification as indicating that you had *exactly* 2048 bytes in which to store *everything* -- book-keeping included. Perhaps you assumed otherwise, perhaps you were told otherwise, but this makes your implementation very different than mine.

Your implementation uses 384 extra bytes to keep the books. In contrast, mine uses only 256 bytes for book-keeping, and its embedded within the 2048 byte data area. On the other hand, it could be me that was mistaken, and perhaps how I read the specification was not in line with what they intended [grin]

Hmm, They told me that - " The maximum size allowed for storage of the queued data is MAX_DATA_SIZE."

w.r.t the extra bytes, thats kinda flexible depending on what constants you define. I think I can get it down to ~240 (don't remember the exact number) but it affects the performance too so I kinda chose a sweet spot.



Share this post


Link to post
Share on other sites
Here's a few things I spotted. Nothing really major though.

The MEM_USED calculation is a little optimistic - unless you actually bit pack the arrays manually it'll use more memory than that. I'd go with sizeof(Data) + sizeof(Chunks) + sizeof(Queues).

For size optimization your CHUNKS structure is somewhat inefficient - it's a bitfield with a total of 9 bits used. Most compilers would expand that to at least 16 bits, and maybe 32. If it's 32 then that array is 1024 bytes.

The simplest improvement is to just double the chunk size so you only need 8 bits per chunk, and half the number of chunks. You can then use an array of unsigned chars which gives a total of 128 bytes.

Big optimization: To save on the big loop searching for an unused chunk what I'd have done is created one extra hidden queue at the start which contains all free chunks. You then simply move chunks on and off the front of the free queue to allocate and deallocate chunks. You could even drop the free chunk bit if you did that, and therefore leave the chunk size at 8. That saves more memory than the extra QUEUE structure takes.

Minor optimization: As a QueueHandle is unsigned testing it for >=0 is completely pointless - unsigned values are never negative! Of course most compilers will optimize the pointless test away so it's a minor issue.

There's also quite a few 'magic' constants used in the code, which all seem to be written in hex. I'd probably have used decimal for most of them, and maybe defined 'used' and 'unused' constants up front. That's just a style thing though.

Share this post


Link to post
Share on other sites
So far, I'll agree with the sentiments that have been stated already. In particular, the use of a free-list is the most important win since it eliminates that nasty linear search and the need for an "is-active" marker. Technically, a stack makes a better free-list in theory due to cache-coherence, but since you've already got the Queues in place, they cost you nothing to implement.

Stylistically, there is a disturbing lack of helper functions -- granted, I don't see a ton of code duplication, but breaking out small bits of functionality into functions makes the code easier to read and understand, which is what you want when someone is analyzing your code and making a judgment about you. For the same reason, you should use better variable names in some instances -- i, j and k, for example, are generally only acceptable as loop indexers but you've used them to hold whether a given block is active and where the start and end blocks are in some instances. Similarly, many of the comments are redundant because they only state what is about to be done. This would have become more apparent had you made good use of helper functions. The same applies to your function heading comments -- they don't contain any more information than the function signature, so they are redundant. They add nothing to my understanding of the code. They should indicate the following: What the function does (you have this, essentially), how it goes about it (briefly), what the parameters are expected to contain, what the function returns, what assumptions are made, what restrictions are enforced, what errors are trapped, and what happens when a restriction fails to be met or an error occurs. These things add value to my understanding; just restating the function signature in prose does not.


Given your location, the likelihood of it being the same company is high, but the problem statement has changed significantly if so. I was never given a header, instead the interface was specified and the header was up to me to implement. Another important difference is that your specification uses QueueHandles, while the spec I worked from specified that Queues were given as pointers, which certainly influenced certain design decisions I made. Reading through it once again on their website, the problem statement I worked from clearly indicates that *all* storage other than local variables must come from the 2K data buffer:

Quote:
Your code is not allowed to call malloc() or other heap management routines. Instead, all storage (other than local variables in your functions) must be within a provided array.


The specification I was given is still intact, as I remember it, on the company's website. So either they've changed the problem specification since then and not updated their jobs page, or it is indeed a different company.


Since we've worked from different specs, and the remainder of my optimizations and neat tricks are basically dependent on the interface I was given, I won't post any of it here since its not directly applicable. However, if you're really interested feel free to PM me and I'll supply an in-depth explanation of my approach and some excerpts of code.

Share this post


Link to post
Share on other sites

This topic is 3590 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.

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

Sign in to follow this