Stacks & Queues: Cache Optimization for Performance in C

Stacks and Queues: Cache Optimization and Performance in C

The call stack is present in every program, but when implementing custom stacks and queues, the choice of data structure critically impacts performance. Linked lists can cause up to 37 times more cycles due to cache misses and malloc/free overhead. Ring buffers based on arrays provide predictable memory usage and up to 35x speedup.

Stack Implementation: Array vs. Linked List

Classic textbook stack implementations differ in cache behavior.

Array-based Stack (fixed size, O(1)):

#define MAX_SIZE 1000

typedef struct {
    int data[MAX_SIZE];
    int top;
} stack_t;

void push(stack_t *s, int value) {
    if (s->top < MAX_SIZE) {
        s->data[s->top++] = value;
    }
}

int pop(stack_t *s) {
    if (s->top > 0) {
        return s->data[--s->top];
    }
    return -1;
}

Linked List-based Stack (dynamic, O(1)):

typedef struct node {
    int value;
    struct node *next;
} node_t;

typedef struct {
    node_t *top;
} stack_t;

void push(stack_t *s, int value) {
    node_t *node = malloc(sizeof(node_t));
    node->value = value;
    node->next = s->top;
    s->top = node;
}

int pop(stack_t *s) {
    if (s->top) {
        node_t *node = s->top;
        int value = node->value;
        s->top = node->next;
        free(node);
        return value;
    }
    return -1;
}

Benchmarks (1000 operations):

| Implementation | Cycles | Cache Misses |

|----------------|--------|--------------|

| Array | 12K | 45 |

| Linked List | 450K | 2100 |

Reasons for Linked List Slowdown:

• Overhead of malloc/free (~100 cycles per operation)
• Nodes scattered across the heap (L1/L2 cache misses)
• Pointer chasing (data dependency)

Selection Recommendations:

• Array: embedded systems, real-time applications
• Linked List: unpredictable size + memory to spare

Ring Buffer: The Foundation of Efficient Queues

A naive array-based queue breaks when reaching the buffer's end:

void enqueue(queue_t *q, int value) {
    if (q->rear < MAX_SIZE) {
        q->data[q->rear++] = value;
    }
}

Problem: front==rear cannot distinguish between an empty and a full queue.

Ring Buffer solves the problem using modular arithmetic:

typedef struct {
    int data[MAX_SIZE];
    int head;
    int tail;
    int count;
} ring_buffer_t;

void enqueue(ring_buffer_t *q, int value) {
    if (q->count < MAX_SIZE) {
        q->data[q->tail] = value;
        q->tail = (q->tail + 1) % MAX_SIZE;
        q->count++;
    }
}

int dequeue(ring_buffer_t *q) {
    if (q->count > 0) {
        int value = q->data[q->head];
        q->head = (q->head + 1) % MAX_SIZE;
        q->count--;
        return value;
    }
    return -1;
}

Benchmarks (1M operations):

| Implementation | Cycles | Cache Misses |

|----------------|----------|--------------|

| Ring Buffer | 15M | 1234 |

| Linked List | 520M | 980K |

A 35x speedup due to cache locality.

Optimizing the Ring Buffer

The % operation (10-40 cycles) is a bottleneck.

Optimization 1: Power of Two Size

#define MAX_SIZE 1024
#define MASK (MAX_SIZE - 1)

q->tail = (q->tail + 1) & MASK;  // 1 cycle instead of 30

Result: 1.76x speedup (15M → 8.5M cycles).

Optimization 2: Eliminating the Count Variable

int is_empty(ring_buffer_t *q) {
    return q->head == q->tail;
}

int is_full(ring_buffer_t *q) {
    return ((q->tail + 1) & MASK) == q->head;
}

Trade-off: maximum of MAX_SIZE-1 elements.

Lock-Free Ring Buffer (SPSC)

For single producer/single consumer scenarios (interrupts, cores):

typedef struct {
    volatile int data[MAX_SIZE];
    volatile int head;  // Consumer only
    volatile int tail;  // Producer only
} spsc_ring_buffer_t;

void enqueue(spsc_ring_buffer_t *q, int value) {
    int next_tail = (q->tail + 1) & MASK;
    if (next_tail != q->head) {
        q->data[q->tail] = value;
        __sync_synchronize();
        q->tail = next_tail;
    }
}

Key Elements:

• volatile to prevent compiler optimizations
• Memory barriers for weak memory models (ARM, RISC-V)
• No atomic operations required

RISC-V Version:

asm volatile("fence w, w" ::: "memory");

Priority Queue: Binary Heap

Min-Heap (minimum element at the root):

typedef struct {
    int data[MAX_SIZE];
    int size;
} heap_t;

void heap_push(heap_t *h, int value) {
    int i = h->size++;
    h->data[i] = value;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (h->data[i] <= h->data[parent]) break;
        // swap
        int temp = h->data[i];
        h->data[i] = h->data[parent];
        h->data[parent] = temp;
        i = parent;
    }
}

Complexity: O(log n), good cache locality for small n.

Key Takeaways

• Linked lists for stacks/queues cause 30-40x slowdown due to cache misses
• Ring buffers with size 2^n gain 1.76x speedup using bitwise AND
• Lock-free SPSC buffers are ideal for interrupts and RTOS
• Binary heaps retain array advantages with O(log n) complexity
• In embedded systems, fixed size = determinism

— Editorial Team