About tiny tiny C code:
If I wanted to use a set amount of memory, like
unsigned char byteMem[2048]
in which to store and manipulate a number of byte queues; my standard C approach would be to create a set of structs the let me pool out chunks of memory from the space for the byte queues to work in.
I am not having luck finding references on how to keep the most possible usable space for my queues to use.
2 questions:
- What are some good books or other reading on memory efficient C code?
- Have I missed some easy optimizations in the following code?
The QueueSlot uses 8 bits for a queue identifier and 8 bits for storing a value. Is better memory efficiency just a matter of using more of memory for data storage?
Feel free to chop out most of this in replies:
I wrote some some C code that is straight forward enough
-------------------------------------------------------------------------- /* compactqueues.h
*/
//A place to store the queues typedef struct {
int dataLength; unsigned char* data;
} Store;
// A memory layout for a queue slot // A tag and a value // This approach is decidely in favor of very dynamic behavior sacrificing some // memory space for tagging. But any queue can easily grow to any size // permitted by the buffer limit. typedef struct {
unsigned char slotTag : 8; unsigned char slotValue : 8;
} QueueSlot;
//A queue in this approach needs to have //a distinct tag value //a headIndex for implicit queue ordering //and access to the buffer typedef struct {
unsigned char myTag : 4; int headIndex; Store *storeAccess;
} Queue;
//This is a convenience collection to pool access to the //management bits typedef struct { Queue *queuePool; unsigned char *queueMarkers; unsigned char poolSize; Store *storeKeeper; } QueueKeeper;
// An initialization function // To scrub the store buffer to 0's void initQueuePool();
Queue * create_queue();
void destroy_queue(Queue * q);
void enqueue_byte(Queue * q, unsigned char b);
unsigned char dequeue_byte(Queue * aQueue);
------------------------------------------------------------------------------------------- /* compactqueues.c
*/ #include "CompactQueue.h" #include //#include
//#define DEFAULT_STORE_SIZE 2048
//unsigned short externStoreSize = DEFAULT_STORE_SIZE;
//unsigned char TagGenerator = 0;
QueueKeeper* externQueueKeeper;
void on_out_of_memory() {
fprintf( stdout, "Out of memory! \n" );
while (1) { //dont return? well ok then
}
}
void on_illegal_operation() { fprintf( stdout, "Illegal operation! \n" );
while (1) { //dont return? well ok then
}
} void initQueuePool() {
if ( externQueueKeeper ) { //Scrub the marker slots to 0 for ( short i=0; i< externQueueKeeper->poolSize; ++i ) { externQueueKeeper->queueMarkers[i] = 0; }
//Scrub the data slots to 0 if ( externQueueKeeper->storeKeeper ) {
Store* localStoreAccess = externQueueKeeper->storeKeeper; unsigned char* store = localStoreAccess->data;
if (store) {
QueueSlot * asSlot = (QueueSlot*) store;
int slotCount = localStoreAccess->dataLength / sizeof(QueueSlot) ;
for ( int i=0;i< slotCount; ++i) {
asSlot->slotTag = 0; asSlot->slotValue = 0; //fprintf( stdout, "Clear QueueSlots - Slot - %i, Value - %i \n", asSlot->slotTag, asSlot->slotValue );
++asSlot; }
}
}
}
}
Queue* create_queue() {
if ( !externQueueKeeper ) return 0;
short indexToTake = -1;
for ( short i=0; i< externQueueKeeper->poolSize; ++i ) { if ( externQueueKeeper->queueMarkers[i] == 0 ) { indexToTake = i; //fprintf(stdout, "indexToTake - %i\n", indexToTake ); break; }
}
if ( indexToTake > -1 ) { externQueueKeeper->queueMarkers[indexToTake] = 1; externQueueKeeper->queuePool[indexToTake].myTag = indexToTake + 1; externQueueKeeper->queuePool[indexToTake].headIndex = 0; externQueueKeeper->queuePool[indexToTake].storeAccess = externQueueKeeper->storeKeeper; return &(externQueueKeeper->queuePool[indexToTake]); }
return 0; }
void destroy_queue(Queue * q) {
if ( q && q->storeAccess ) {
Store* localStoreAccess = q->storeAccess; unsigned char* store = localStoreAccess->data;
if (store) {
QueueSlot * asSlot = (QueueSlot*) store;
int slotCount = localStoreAccess->dataLength / sizeof(QueueSlot) ;
int headOffset = q->headIndex; int slotsFreed = 0; for ( int i=0 ;i < slotCount; ++i) {
QueueSlot* currentSlot = (asSlot + headOffset%slotCount);
if ( currentSlot->slotTag == q->myTag ) { currentSlot->slotTag = 0; currentSlot->slotValue = 0; ++slotsFreed; }
} //fprintf( stdout, "Destroying Queue - %i. %i slots left in use are now free.\n", q->myTag, slotsFreed );
//Reset Queue for reuse from the pool. externQueueKeeper->queueMarkers[q->myTag] = 0; q->headIndex = 0; q->myTag = 0; q->storeAccess = 0;
//now the queue for pool slot can be found for use again
}
} }
void enqueue_byte(Queue * q, unsigned char b) {
if ( q && q->storeAccess ) {
Store* localStoreAccess = q->storeAccess; unsigned char* store = localStoreAccess->data;
if (store) {
QueueSlot * asSlot = (QueueSlot*) store;
int slotCount = localStoreAccess->dataLength / sizeof(QueueSlot) ;
int headOffset = q->headIndex; int slotUsed = -1; for ( int i=0 ;i < slotCount; ++i) { int currentIndex = (i + headOffset%slotCount); QueueSlot* currentSlot = (asSlot + headOffset%slotCount);
if ( currentSlot->slotTag == 0 ) { slotUsed = currentIndex; currentSlot->slotTag = q->myTag;// this slot know belongs to the queue passed in currentSlot->slotValue = b;
//fprintf( stdout, "Slot %i belongs to queue- %i, with Value - %i \n", currentIndex, currentSlot->slotTag, currentSlot->slotValue ); break; }
++asSlot; }
if ( slotUsed == -1 ) { fprintf( stdout, "No Slot open. Enqueue failed \n" ); on_out_of_memory(); }
}
}
}
unsigned char dequeue_byte(Queue * q) {
unsigned char dequeueduchar = 0;
if ( q && q->storeAccess ) {
Store* localStoreAccess = q->storeAccess; unsigned char* store = localStoreAccess->data;
if ( store ) {
QueueSlot * asSlot = (QueueSlot*) store;
int slotCount = localStoreAccess->dataLength / sizeof(QueueSlot) ; int headOffset = q->headIndex;
unsigned char seeking = 1; //first seek the bit to dequeue, then try to update the headIndex
for ( int i=0;i< slotCount; ++i) { int currentIndex = (i + headOffset%slotCount); QueueSlot* currentSlot = (asSlot + headOffset%slotCount); //find the first slot with myTag as the slotTag value //use mod to do a complete loop around starting from the headIndex if ( seeking ) {
if ( currentSlot->slotTag == q->myTag ) { dequeueduchar = currentSlot->slotValue;
//free the slot for use currentSlot->slotValue = 0; currentSlot->slotTag = 0; q->headIndex = 0; //this will get updated to the true next headIndex if there really is a next one, if not then it should be 0 anyway //fprintf( stdout, "Free slot %i from Queue- %i, returning Value
- %i \n", currentIndex, currentSlot->slotTag, dequeueduchar ); seeking = 0; } } else {
if ( currentSlot->slotTag == q->myTag ) {
q->headIndex = currentIndex; //fprintf( stdout, "Updating headIndex of Queue- %i to slot - %i \n", q->myTag, currentIndex );
return dequeueduchar; } }
++asSlot; }
//if ( q->headIndex == 0 ) // fprintf( stdout, "Reseting headIndex of Queue- %i to slot 0 \n", q->myTag );
//if nothing to dequeue for given queue if ( seeking == 1 ) on_illegal_operation();
}
}
return dequeueduchar; }
------------------------------------------------------------------------------------------- /* main.c - Test it out
*/
#include #include "CompactQueue.h"
extern QueueKeeper* externQueueKeeper; //extern unsigned short externStoreSize;
int main (int argc, const char * argv[]) {
Store aStore; const int storeSize = 2048; //aStore.dataLength = externStoreSize; unsigned char storeData[storeSize]; aStore.dataLength = storeSize; aStore.data = storeData; const unsigned char poolSize = 64;
//setup the zooKeeper, I mean queueKeeper QueueKeeper aQueueKeeper;
Queue aQueuePool[poolSize]; unsigned char queueMarkers[poolSize]; aQueueKeeper.queuePool = aQueuePool; aQueueKeeper.queueMarkers = queueMarkers; aQueueKeeper.poolSize = poolSize; aQueueKeeper.storeKeeper = &aStore; externQueueKeeper = &aQueueKeeper; initQueuePool();
//Queues in action
Queue* q1 = create_queue(); Queue* q2 = create_queue();
enqueue_byte(q1, 0); enqueue_byte(q1, 1);
enqueue_byte(q2, 3); enqueue_byte(q1, 2); enqueue_byte(q2, 4);
printf("%d ", dequeue_byte(q1)); printf("%d\n", dequeue_byte(q1)); enqueue_byte(q1, 5); enqueue_byte(q2, 6);
printf("%d ", dequeue_byte(q1)); printf("%d\n", dequeue_byte(q1)); destroy_queue(q1); printf("%d ", dequeue_byte(q2)); printf("%d ", dequeue_byte(q2)); printf("%d\n", dequeue_byte(q2)); destroy_queue(q2);
return 0; }