Optimisation Cache Piles Files C : Performance x35 avec Tampon Circulaire

Piles et Files d'Attente : Optimisation du Cache et Performance en C

La pile d'appel est présente dans chaque programme, mais lors de l'implémentation de piles et de files d'attente personnalisées, le choix de la structure de données impacte de manière critique les performances. Les listes chaînées peuvent entraîner jusqu'à 37 fois plus de cycles en raison des défauts de cache et de la surcharge de malloc/free. Les tampons circulaires basés sur des tableaux offrent une utilisation mémoire prévisible et une accélération allant jusqu'à 35x.

Implémentation de Pile : Tableau vs Liste Chaînée

Les implémentations classiques de piles diffèrent dans leur comportement vis-à-vis du cache.

Pile basée sur un tableau (taille fixe, 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;
}

Pile basée sur une Liste Chaînée (dynamique, 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 opérations) :

| Implémentation | Cycles | Défauts de Cache |

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

| Tableau | 12K | 45 |

| Liste Chaînée | 450K | 2100 |

Raisons du Ralentissement des Listes Chaînées :

• Surcharge de malloc/free (~100 cycles par opération)
• Nœuds dispersés dans le tas (défauts de cache L1/L2)
• Poursuite de pointeurs (dépendance de données)

Recommandations de Sélection :

• Tableau : systèmes embarqués, applications temps réel
• Liste Chaînée : taille imprévisible + mémoire disponible

Tampon Circulaire : Fondation des Files d'Attente Efficaces

Une file d'attente naïve basée sur un tableau dysfonctionne en atteignant la fin du tampon :

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

Problème : front==rear ne peut pas distinguer une file vide d'une file pleine.

Le Tampon Circulaire résout le problème en utilisant l'arithmétique modulaire :

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 opérations) :

| Implémentation | Cycles | Défauts de Cache |

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

| Tampon Circulaire | 15M | 1234 |

| Liste Chaînée | 520M | 980K |

Une accélération de 35x grâce à la localité du cache.

Optimisation du Tampon Circulaire

L'opération % (10-40 cycles) est un goulot d'étranglement.

Optimisation 1 : Taille Puissance de Deux

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

q->tail = (q->tail + 1) & MASK;  // 1 cycle au lieu de 30

Résultat : accélération de 1.76x (15M → 8.5M cycles).

Optimisation 2 : Élimination de la Variable 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;
}

Compromis : maximum de MAX_SIZE-1 éléments.

Tampon Circulaire Sans Verrou (SPSC)

Pour les scénarios producteur unique/consommateur unique (interruptions, cœurs) :

typedef struct {
    volatile int data[MAX_SIZE];
    volatile int head;  // Consommateur uniquement
    volatile int tail;  // Producteur uniquement
} 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;
    }
}

Éléments Clés :

• volatile pour empêcher les optimisations du compilateur
• Barrières mémoire pour les modèles de mémoire faible (ARM, RISC-V)
• Aucune opération atomique requise

Version RISC-V :

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

File à Priorité : Tas Binaire

Tas Min (élément minimum à la racine) :

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

Complexité : O(log n), bonne localité du cache pour les petits n.

Points Clés à Retenir

• Les listes chaînées pour les piles/files causent un ralentissement de 30-40x dû aux défauts de cache
• Les tampons circulaires de taille 2^n gagnent 1.76x en vitesse grâce au ET bit à bit
• Les tampons SPSC sans verrou sont idéaux pour les interruptions et les RTOS
• Les tas binaires conservent les avantages des tableaux avec une complexité O(log n)
• Dans les systèmes embarqués, une taille fixe = déterminisme

— Editorial Team