# Improving Queue Code

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

## 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 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 on other sites
Quote:
 Original post by AntheusSince 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 on other sites
Quote:
 Original post by kapilkapreYes 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 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 on other sites
Quote:
 Original post by AntheusThere'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 exitIs that short for "function exit"?

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

##### Share on other sites
Quote:
 Original post by ravyne2001I'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 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 on other sites
Quote:
 Original post by gsgA 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 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 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 on other sites
Quote:
 Original post by ravyne2001Its 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 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 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.

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.