Zásobníky a fronty v C: optimalizace cache a výkonu

Zásobníky a fronty: optimalizace pro cache a výkon v jazyce C

Zásobník volání je přítomen v každém programu, ale při implementaci uživatelských zásobníků a front volba datové struktury kriticky ovlivňuje výkon. Spojové seznamy způsobují až 37krát více cyklů kvůli chybám v cache a režii malloc/free. Kruhové fronty založené na polích zajišťují předvídatelné využití paměti a zrychlení až 35krát.

Implementace zásobníku: pole vs spojový seznam

Klasické výukové implementace zásobníků se liší chováním cache.

Zásobník na poli (pevná velikost, 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;
}

Zásobník na spojovém seznamu (dynamický, 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;
}

Benchmarky (1000 operací):

| Implementace | Cykly | Chyby v cache |

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

| Pole | 12K | 45 |

| Seznam | 450K | 2100 |

Příčiny zpomalení spojového seznamu:

• Režie malloc/free (~100 taktů na operaci)
• Rozptýlení uzlů po haldě (chyby L1/L2 cache)
• Následování ukazatelů (závislost na datech)

Doporučení pro výběr:

• Pole: vestavěné systémy, systémy reálného času
• Seznam: nepředvídatelná velikost + nadbytek paměti

Kruhová fronta: základ efektivních front

Naivní fronta na poli selhává při dosažení konce bufferu:

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

Problém: front==rear nerozlišuje prázdnou a plnou frontu.

Kruhová fronta řeší problém pomocí modulární aritmetiky:

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;
}

Benchmarky (1M operací):

| Implementace | Cykly | Chyby v cache |

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

| Kruhová | 15M | 1234 |

| Seznam | 520M | 980K |

Zrychlení 35krát díky lokalitě cache.

Optimalizace kruhové fronty

Operace % (10-40 taktů) — úzké hrdlo.

Optimalizace 1: mocnina dvou

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

q->tail = (q->tail + 1) & MASK;  // 1 takt místo 30

Výsledek: zrychlení 1.76krát (15M → 8.5M taktů).

Optimalizace 2: bez count

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;
}

Kompromis: maximálně MAX_SIZE-1 prvků.

Bezbloková kruhová fronta (SPSC)

Pro jediného producenta/konzumenta (přerušení, jádra):

typedef struct {
    volatile int data[MAX_SIZE];
    volatile int head;  // Pouze konzument
    volatile int tail;  // Pouze producent
} 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;
    }
}

Klíčové prvky:

• volatile proti optimalizacím kompilátoru
• Bariéry paměti pro slabé modely (ARM, RISC-V)
• Absence atomických operací

RISC-V verze:

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

Prioritní fronta: binární halda

Min-halda (minimální prvek v kořeni):

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;
        // prohození
        int temp = h->data[i];
        h->data[i] = h->data[parent];
        h->data[parent] = temp;
        i = parent;
    }
}

Složitost: O(log n), dobrá lokalita cache pro malá n.

Co je důležité

• Spojové seznamy pro zásobníky/fronty způsobují 30-40x zpomalení kvůli chybám cache
• Kruhová fronta s velikostí 2^n se zrychlí 1.76x díky bitovému AND
• Bezbloková SPSC fronta je ideální pro přerušení a RTOS
• Binární haldy zachovávají výhody polí při O(log n)
• Ve vestavěných systémech pevná velikost = determinismus

— Editorial Team