Aligner les structures de données aux lignes de cache

Dans une application Rust multi-threadée traitant de grands ensembles de données, la conscience des lignes de cache est essentielle pour maximiser les performances. Les lignes de cache du CPU (généralement 64 octets sur les architectures x86_64 et ARM modernes) dictent la manière dont les données sont récupérées, et le faux partage - où les threads modifient des données adjacentes sur la même ligne de cache - peut dégrader considérablement le débit en raison des invalidations constantes du cache. J'alignerais les structures de données aux lignes de cache et utiliserais les fonctionnalités de Rust pour éliminer le faux partage, optimisant ainsi une charge de travail multi-threadée.

Conception de Structures Alignées sur le Cache

• Alignement : S'assurer que les données de chaque thread commencent sur une nouvelle ligne de cache en utilisant #[repr(align(64))].
• Remplissage : Ajouter des octets factices pour séparer les données locales aux threads, évitant le chevauchement.
• Séparation : Diviser les données partagées en segments par thread, accessibles indépendamment.

Exemple : Un compteur multi-threadé où chaque thread incrémente son propre total :

use std::sync::atomic::{AtomicU64, Ordering};
use std::thread;

// Naïf : Faux partage probable
struct Counters {
    counts: [AtomicU64; 4], // 4 threads, 8 octets chacun = 32 octets
}

impl Counters {
    fn new() -> Self {
        Counters {
            counts: [AtomicU64::new(0), AtomicU64::new(0), AtomicU64::new(0), AtomicU64::new(0)],
        }
    }
}

Problème : counts fait 32 octets, tenant dans une seule ligne de cache de 64 octets. Si le Thread 0 met à jour counts[0] et le Thread 1 met à jour counts[1], ils sollicitent excessivement la même ligne, sérialisant l'accès.

Version Restructurée Alignée sur le Cache

#[repr(align(64))] // Alignement sur ligne de cache de 64 octets
struct CacheAlignedCounter {
    count: AtomicU64,      // 8 octets
    _padding: [u8; 56],    // 56 octets de remplissage pour atteindre 64
}

struct Counters {
    counts: [CacheAlignedCounter; 4], // 4 threads, 64 octets chacun
}

impl Counters {
    fn new() -> Self {
        Counters {
            counts: [
                CacheAlignedCounter { count: AtomicU64::new(0), _padding: [0; 56] },
                CacheAlignedCounter { count: AtomicU64::new(0), _padding: [0; 56] },
                CacheAlignedCounter { count: AtomicU64::new(0), _padding: [0; 56] },
                CacheAlignedCounter { count: AtomicU64::new(0), _padding: [0; 56] },
            ],
        }
    }

    fn run(&self) {
        let mut handles = Vec::new();
        for i in 0..4 {
            let counter = &self.counts[i];
            handles.push(thread::spawn(move || {
                for _ in 0..1_000_000 {
                    counter.count.fetch_add(1, Ordering::Relaxed);
                }
            }));
        }
        for h in handles { h.join().unwrap(); }
    }
}

• Alignement : #[repr(align(64))] garantit que chaque CacheAlignedCounter commence sur une limite de 64 octets.
• Remplissage : _padding remplit la structure jusqu'à 64 octets, donc counts[1] est sur une nouvelle ligne de cache.
• Résultat : Chaque thread met à jour son propre count sans invalider les lignes de cache des autres.

Fonctionnalités et Techniques Rust

#[repr(align(N))]

Force l'alignement des structures à une puissance de 2 (ex. 64), les alignant avec les lignes de cache.

Remplissage Manuel

Des tableaux ou champs inutilisés (ex. [u8; 56]) garantissent que la taille correspond à la ligne de cache, évitant le chevauchement.

Données Par Thread

Utiliser thread_local! ou un tableau indexé par ID de thread pour une séparation complète :

thread_local! {
    static MY_COUNTER: AtomicU64 = AtomicU64::new(0);
}

Opérations Atomiques : fetch_add avec l'ordre Relaxed est sûr ici (pas de dépendance de données), minimisant la surcharge de synchronisation.

Prévention du Faux Partage

• Séparation : Chaque compteur est espacé de 64 octets, donc les écritures du Thread 0 sur counts[0] n'invalident pas counts[1].
• Vérification de Taille : std::mem::size_of::<CacheAlignedCounter>() retourne 64, confirmant l'alignement.
• Disposition : Éviter le compactage (ex. #[repr(packed)]) sauf besoin explicite - le remplissage est notre allié ici.

Vérification

Profilage avec perf

Exécuter perf stat -e cache-misses,L1-dcache-load-misses ./target/release/app sur les deux versions :

• Naïf : Nombre élevé de L1-dcache-load-misses (ex. 10M) dû au faux partage.
• Optimisé : Baisse significative (ex. 1M), car chaque ligne de cache de thread reste locale.

Benchmarking

use criterion::{black_box, Criterion};
fn bench(c: &mut Criterion) {
    let counters = Counters::new();
    c.bench_function("cache_aligned", |b| b.iter(|| black_box(counters.run())));
}

Attendre une accélération de 2-5x (ex. de 50ms à 10ms) sur un CPU 4 cœurs.

Disposition Mémoire

std::mem::align_of::<CacheAlignedCounter>() confirme l'alignement sur 64 octets.

Conclusion

J'alignerais les données avec #[repr(align(64))] et les remplirais jusqu'à 64 octets, comme dans cet exemple de compteur, garantissant que chaque thread opère sur sa propre ligne de cache. Le système de types et les attributs de Rust rendent cela précis et sûr, tandis que le profilage avec perf valide la réduction des défauts de cache. Cela élimine le faux partage, débloquant le vrai parallélisme dans un processeur d'ensembles de données multi-threadé.