Guide de Performance - MiniSheet

📋 Table des Matières

Introduction
Optimisations Actuelles
Goulots d'Étranglement
Métriques de Performance
Techniques de Profiling
Optimisations Recommandées
Bonnes Pratiques
Benchmarks
FAQ

Introduction

Ce guide explique les aspects de performance de MiniSheet, les optimisations actuelles, et comment améliorer les performances.

Objectifs de Performance

✅ Temps de réponse : Interface réactive (< 16ms par frame pour 60 FPS)
✅ Temps de calcul : Recalcul rapide même pour grandes feuilles
✅ Utilisation mémoire : Efficace grâce au stockage sparse
✅ Temps de chargement : Fichiers volumineux chargés rapidement

Optimisations Actuelles

1. Lazy Evaluation (Évaluation Paresseuse)

Implémentation :

Les valeurs des cellules sont calculées à la demande plutôt que pré-calculées.

fn eval_cell(&mut self, r: usize, c: usize, stack: &mut HashSet<(usize, usize)>) 
    -> Result<CellValue, CellValue> {
    // Vérifier le cache d'abord
    if let Some(v) = self.computed.get(&(r, c)).cloned() {
        return Ok(v);  // Retourner la valeur mise en cache
    }
    
    // Calculer seulement si pas dans le cache
    // ...
}

Avantages :

✅ Seules les cellules visibles sont calculées
✅ Pas de recalcul inutile
✅ Performance améliorée pour grandes feuilles

Impact :

Avant : Recalculer 10,000 cellules = ~100ms
Après : Calculer 100 cellules visibles = ~1ms

2. Cache des Valeurs Calculées

Implémentation :

Les valeurs calculées sont mises en cache dans computed: HashMap<(usize, usize), CellValue>.

struct Sheet {
    computed: HashMap<(usize, usize), CellValue>,  // Cache
    // ...
}

Stratégie d'Invalidation :

Le cache est invalidé de manière intelligente :

fn invalidate_cell(&mut self, r: usize, c: usize) {
    // Invalider la cellule modifiée
    self.computed.remove(&(r, c));
    
    // Invalider récursivement toutes les cellules dépendantes
    for dependent in self.get_dependents(r, c) {
        self.invalidate_cell(dependent.0, dependent.1);
    }
}

Avantages :

✅ Évite les recalculs inutiles
✅ Complexité O(1) pour la recherche dans le cache
✅ Invalidation ciblée (seulement les cellules affectées)

Impact :

Sans cache : Recalculer à chaque affichage = ~10ms par frame
Avec cache : Lecture depuis cache = ~0.01ms par frame

3. Sparse Storage (Stockage Sparse)

Implémentation :

Seules les cellules non vides sont stockées dans HashMap<(usize, usize), String>.

struct Sheet {
    raw: HashMap<(usize, usize), String>,  // Seulement cellules non vides
    // ...
}

Avantages :

✅ Mémoire efficace : pas de stockage pour cellules vides
✅ Pas de limite artificielle sur le nombre de cellules
✅ Recherche O(1) avec HashMap

Impact :

Stockage dense : 1,000,000 cellules × 8 bytes = 8 MB
Stockage sparse : 1,000 cellules remplies × 8 bytes = 8 KB

4. Détection de Cycles Efficace

Implémentation :

Utilisation de HashSet pour la détection de cycles en O(1).

fn eval_cell(&mut self, r: usize, c: usize, stack: &mut HashSet<(usize, usize)>) {
    // Détection O(1) avec HashSet
    if stack.contains(&(r, c)) {
        return Err(CellValue::Error("Circular reference".into()));
    }
    // ...
}

Avantages :

✅ Détection rapide (O(1) au lieu de O(n) avec Vec)
✅ Pas de parcours linéaire nécessaire

5. Recalcul Incrémental

Implémentation :

Le recalcul est déclenché seulement quand nécessaire :

fn set_raw(&mut self, r: usize, c: usize, value: String) {
    self.raw.insert((r, c), value);
    // Invalider seulement cette cellule et ses dépendances
    self.invalidate_cell(r, c);
}

Avantages :

✅ Pas de recalcul global inutile
✅ Seules les cellules affectées sont recalculées

Goulots d'Étranglement

1. Parsing des Formules

Problème :

Le parser récursif peut être lent pour des formules très complexes.

Complexité :

Parsing : O(n) où n = longueur de la formule
Récursion : Peut être profonde pour expressions complexes

Exemple de formule lente :

=IF(A1>0, IF(A2>0, IF(A3>0, IF(A4>0, ...))))

Solutions :

Limiter la profondeur de récursion
Optimiser le parser (memoization)
Parser itératif au lieu de récursif

2. Recherche de Dépendances

Problème :

La recherche de dépendances parcourt toutes les cellules :

fn references_cell(&self, formula: &str, target_r: usize, target_c: usize) -> bool {
    // Parcourt toute la formule caractère par caractère
    // ...
}

Complexité :

O(n × m) où n = nombre de cellules, m = longueur moyenne des formules

Solutions :

Index des dépendances (graphe de dépendances)
Cache des dépendances
Parsing optimisé avec regex ou parser spécialisé

3. Rendu de la Grille

Problème :

Le rendu de toutes les cellules visibles peut être lent pour grandes feuilles.

Complexité :

O(visible_rows × visible_cols)

Solutions :

Virtualisation du rendu (seulement cellules visibles)
Caching du rendu
Rendu asynchrone

4. Sérialisation JSON

Problème :

La sérialisation JSON peut être lente pour très grandes feuilles.

Complexité :

O(n) où n = nombre de cellules

Solutions :

Format binaire pour la persistance
Sérialisation incrémentale
Compression

5. Invalidation Récursive

Problème :

L'invalidation récursive peut être coûteuse pour des chaînes de dépendances longues.

Complexité :

O(d) où d = profondeur de la chaîne de dépendances

Exemple :

A1 → B1 → C1 → D1 → E1 → F1 → ...

Solutions :

Limiter la profondeur
Invalidation itérative au lieu de récursive
Index des dépendances inverses

Métriques de Performance

Métriques Clés

1. Temps de Frame (Frame Time)

Objectif : < 16ms pour 60 FPS

Mesure :

use std::time::Instant;

fn update(&mut self, ctx: &egui::Context, frame: &mut eframe::Frame) {
    let start = Instant::now();
    
    // Rendu de l'UI
    // ...
    
    let duration = start.elapsed();
    if duration.as_millis() > 16 {
        eprintln!("Frame time: {:?} (> 16ms)", duration);
    }
}

2. Temps de Recalcul

Objectif : < 100ms pour 10,000 cellules

Mesure :

fn recalc_all(&mut self) {
    let start = Instant::now();
    self.computed.clear();
    
    // Recalculer toutes les cellules
    for (r, c) in self.raw.keys() {
        let _ = self.eval_cell(*r, *c, &mut HashSet::new());
    }
    
    let duration = start.elapsed();
    println!("Recalc time: {:?}", duration);
}

3. Utilisation Mémoire

Objectif : < 100 MB pour 100,000 cellules

Mesure :

use std::alloc::{GlobalAlloc, Layout, System};

fn measure_memory() {
    // Utiliser un profiler de mémoire
    // ou compter manuellement les allocations
}

4. Temps de Chargement

Objectif : < 1s pour fichiers de 10 MB

Mesure :

fn open(&mut self) {
    let start = Instant::now();
    
    // Charger le fichier
    // ...
    
    let duration = start.elapsed();
    println!("Load time: {:?}", duration);
}

Techniques de Profiling

1. Profiling avec `perf` (Linux)

Installation :

sudo apt-get install perf

Utilisation :

# Compiler en mode release
cargo build --release

# Profiler
perf record -g target/release/mini_sheet

# Analyser
perf report

Résultats :

Fonctions les plus coûteuses
Hotspots de performance
Arbre d'appels

2. Profiling avec `cargo-flamegraph`

Installation :

cargo install flamegraph

Utilisation :

# Générer un flamegraph
cargo flamegraph --bin mini_sheet

# Ouvrir flamegraph.svg dans un navigateur

Résultats :

Visualisation graphique des hotspots
Temps passé dans chaque fonction

3. Profiling avec `criterion`

Ajout à Cargo.toml :

[dev-dependencies]
criterion = "0.5"

[[bench]]
name = "eval_cell"
harness = false

Création de benches/eval_cell.rs :

use criterion::{black_box, criterion_group, criterion_main, Criterion};
use mini_sheet::*;

fn bench_eval_cell(c: &mut Criterion) {
    let mut sheet = Sheet::default();
    sheet.set_raw(0, 0, "10".into());
    sheet.set_raw(0, 1, "20".into());
    sheet.set_raw(0, 2, "=A1+B1".into());
    
    c.bench_function("eval_cell", |b| {
        b.iter(|| {
            let _ = sheet.eval_cell(black_box(0), black_box(2), &mut HashSet::new());
        });
    });
}

criterion_group!(benches, bench_eval_cell);
criterion_main!(benches);

Exécution :

cargo bench

4. Profiling avec `println!` et Timing

Technique simple :

use std::time::Instant;

fn eval_cell(&mut self, r: usize, c: usize, stack: &mut HashSet<(usize, usize)>) 
    -> Result<CellValue, CellValue> {
    let start = Instant::now();
    
    // Code à profiler
    // ...
    
    let duration = start.elapsed();
    if duration.as_millis() > 10 {
        eprintln!("Slow eval_cell({}, {}): {:?}", r, c, duration);
    }
    
    Ok(value)
}

5. Profiling Mémoire avec `valgrind` (Linux)

Installation :

sudo apt-get install valgrind

Utilisation :

# Détecter les fuites mémoire
valgrind --leak-check=full target/debug/mini_sheet

# Profiler la mémoire
valgrind --tool=massif target/debug/mini_sheet
ms_print massif.out.*

Optimisations Recommandées

1. Index des Dépendances

Problème actuel :

La recherche de dépendances parcourt toutes les cellules à chaque fois.

Solution :

Maintenir un index des dépendances :

struct Sheet {
    // ...
    dependency_graph: HashMap<(usize, usize), Vec<(usize, usize)>>,  // cell → dependents
    reverse_dependency_graph: HashMap<(usize, usize), Vec<(usize, usize)>>,  // cell → dependencies
}

impl Sheet {
    fn build_dependency_graph(&mut self) {
        // Construire le graphe une fois
        // ...
    }
    
    fn get_dependents(&self, r: usize, c: usize) -> &[(usize, usize)] {
        // O(1) lookup au lieu de O(n) recherche
        self.dependency_graph.get(&(r, c)).unwrap_or(&[])
    }
}

Gain attendu : 10-100x plus rapide pour l'invalidation

2. Virtualisation du Rendu

Problème actuel :

Toutes les cellules visibles sont rendues à chaque frame.

Solution :

Rendre seulement les cellules dans le viewport :

fn render_grid_content(&self, visible_rect: Rect) {
    let start_row = self.row_from_y(visible_rect.min.y);
    let end_row = self.row_from_y(visible_rect.max.y);
    let start_col = self.col_from_x(visible_rect.min.x);
    let end_col = self.col_from_x(visible_rect.max.x);
    
    // Rendre uniquement les cellules visibles
    for r in start_row..=end_row {
        for c in start_col..=end_col {
            self.render_cell(r, c);
        }
    }
}

Gain attendu : 10-100x moins de cellules rendues

3. Parser Optimisé

Problème actuel :

Parser récursif peut être lent et profond.

Solution :

Parser itératif avec stack explicite :

struct FormulaParserIter {
    tokens: Vec<Token>,
    pos: usize,
}

impl FormulaParserIter {
    fn parse_expr(&mut self) -> Result<f64, CellValue> {
        // Parser itératif avec stack explicite
        // Évite la récursion profonde
    }
}

Gain attendu : 2-5x plus rapide, pas de stack overflow

4. Cache des Dépendances

Problème actuel :

Les dépendances sont recalculées à chaque invalidation.

Solution :

Cacher les dépendances :

struct Sheet {
    // ...
    dependency_cache: HashMap<(usize, usize), Vec<(usize, usize)>>,
}

impl Sheet {
    fn get_dependencies_cached(&mut self, r: usize, c: usize) -> Vec<(usize, usize)> {
        if let Some(deps) = self.dependency_cache.get(&(r, c)) {
            return deps.clone();
        }
        
        let deps = self.get_dependencies(r, c);
        self.dependency_cache.insert((r, c), deps.clone());
        deps
    }
}

Gain attendu : 5-10x plus rapide pour l'invalidation

5. Format Binaire pour Persistance

Problème actuel :

JSON est lent à parser pour très grandes feuilles.

Solution :

Format binaire personnalisé :

// Format binaire simple
struct BinaryFormat {
    magic: [u8; 4],  // "MSHT"
    version: u32,
    rows: u32,
    cols: u32,
    cells: Vec<CellEntry>,
}

struct CellEntry {
    row: u32,
    col: u32,
    value_len: u32,
    value: Vec<u8>,
}

Gain attendu : 5-10x plus rapide pour charger/sauvegarder

6. Parallélisation du Recalcul

Problème actuel :

Recalcul séquentiel sur un seul thread.

Solution :

Paralléliser avec rayon :

use rayon::prelude::*;

fn recalc_all_parallel(&mut self) {
    let cells: Vec<(usize, usize)> = self.raw.keys().cloned().collect();
    
    cells.par_iter().for_each(|(r, c)| {
        // Recalculer en parallèle
        // ...
    });
}

Gain attendu : N× plus rapide (N = nombre de cœurs)

7. Compression du Cache

Problème actuel :

Le cache peut devenir très volumineux.

Solution :

Compresser les valeurs dans le cache :

enum CachedValue {
    Empty,
    Number(f64),
    Text(Arc<String>),  // Partage de mémoire
    Error(Arc<String>),
}

Gain attendu : 2-5x moins de mémoire

Bonnes Pratiques

1. Éviter les Allocations Inutiles

❌ Mauvais :

fn get_cell(&self, r: usize, c: usize) -> String {
    format!("{}", self.eval_cell(r, c))  // Allocation à chaque appel
}

✅ Bon :

fn get_cell(&self, r: usize, c: usize) -> Cow<str> {
    match self.eval_cell(r, c) {
        CellValue::Text(s) => Cow::Borrowed(&s),
        CellValue::Number(n) => Cow::Owned(format!("{}", n)),
        // ...
    }
}

2. Réutiliser les Structures

❌ Mauvais :

fn eval_cell(&mut self, r: usize, c: usize) {
    let mut stack = HashSet::new();  // Nouvelle allocation à chaque appel
    // ...
}

✅ Bon :

fn eval_cell(&mut self, r: usize, c: usize, stack: &mut HashSet<(usize, usize)>) {
    // Réutiliser le HashSet passé en paramètre
    stack.clear();
    // ...
}

3. Utiliser des Références

❌ Mauvais :

fn process_cell(value: CellValue) {  // Clone
    // ...
}

✅ Bon :

fn process_cell(value: &CellValue) {  // Référence
    // ...
}

4. Éviter les Clones Inutiles

❌ Mauvais :

let value = self.computed.get(&(r, c)).cloned().unwrap();  // Clone même si pas nécessaire

✅ Bon :

if let Some(value) = self.computed.get(&(r, c)) {
    // Utiliser la référence
}

5. Pré-allouer les Collections

❌ Mauvais :

let mut cells = Vec::new();  // Réallocation à chaque push
for r in 0..1000 {
    cells.push((r, 0));
}

✅ Bon :

let mut cells = Vec::with_capacity(1000);  // Pré-allocation
for r in 0..1000 {
    cells.push((r, 0));
}

Benchmarks

Benchmark 1 : Évaluation de Cellule

Test : Évaluer une cellule simple

Résultats attendus :

Cellule vide : < 0.001ms
Cellule nombre : < 0.001ms
Cellule formule simple : < 0.01ms
Cellule formule complexe : < 0.1ms

Benchmark 2 : Recalcul Global

Test : Recalculer toutes les cellules

Résultats attendus :

100 cellules : < 1ms
1,000 cellules : < 10ms
10,000 cellules : < 100ms
100,000 cellules : < 1s

Benchmark 3 : Chargement de Fichier

Test : Charger un fichier JSON

Résultats attendus :

1 MB : < 100ms
10 MB : < 1s
100 MB : < 10s

Benchmark 4 : Rendu de la Grille

Test : Rendre la grille visible

Résultats attendus :

10×10 cellules : < 1ms
50×20 cellules : < 5ms
100×50 cellules : < 16ms (pour 60 FPS)

FAQ

Q: Pourquoi le recalcul est-il lent ?

R: Plusieurs raisons possibles :

Beaucoup de cellules à recalculer
Formules complexes
Chaînes de dépendances longues
Pas de cache efficace

Solutions :

Utiliser le recalcul incrémental
Optimiser les formules
Limiter la profondeur des dépendances

Q: Pourquoi l'interface lag ?

R: Causes possibles :

Trop de cellules rendues
Recalcul pendant le rendu
Allocations fréquentes

Solutions :

Virtualiser le rendu
Recalculer en arrière-plan
Réduire les allocations

Q: Comment améliorer les performances de chargement ?

Utiliser un format binaire au lieu de JSON
Compresser les fichiers
Charger de manière incrémentale
Utiliser des threads pour le parsing

Q: Le cache prend trop de mémoire ?

Limiter la taille du cache (LRU)
Compresser les valeurs
Nettoyer le cache périodiquement
Utiliser des références partagées (Arc)

Q: Comment profiler l'application ?

Utiliser cargo flamegraph pour les hotspots
Utiliser perf (Linux) pour le profiling système
Ajouter des timings manuels avec Instant::now()
Utiliser criterion pour les benchmarks

Résumé

Optimisations Actuelles

✅ Lazy evaluation
✅ Cache des valeurs
✅ Sparse storage
✅ Détection de cycles efficace
✅ Recalcul incrémental

Goulots d'Étranglement

⚠️ Parsing des formules
⚠️ Recherche de dépendances
⚠️ Rendu de la grille
⚠️ Sérialisation JSON
⚠️ Invalidation récursive

Optimisations Recommandées

Index des dépendances : 10-100x plus rapide
Virtualisation du rendu : 10-100x moins de cellules
Parser optimisé : 2-5x plus rapide
Cache des dépendances : 5-10x plus rapide
Format binaire : 5-10x plus rapide
Parallélisation : N× plus rapide (N = cœurs)
Compression du cache : 2-5x moins de mémoire

Bonnes Pratiques

✅ Éviter les allocations inutiles
✅ Réutiliser les structures
✅ Utiliser des références
✅ Éviter les clones inutiles
✅ Pré-allouer les collections

Dernière mise à jour : 2026-01-20

Version : 0.1.0

FilesExpand file tree

PERFORMANCE.md

Latest commit

History

PERFORMANCE.md

File metadata and controls

Guide de Performance - MiniSheet

📋 Table des Matières

Introduction

Objectifs de Performance

Optimisations Actuelles

1. Lazy Evaluation (Évaluation Paresseuse)

2. Cache des Valeurs Calculées

3. Sparse Storage (Stockage Sparse)

4. Détection de Cycles Efficace

5. Recalcul Incrémental

Goulots d'Étranglement

1. Parsing des Formules

2. Recherche de Dépendances

3. Rendu de la Grille

4. Sérialisation JSON

5. Invalidation Récursive

Métriques de Performance

Métriques Clés

1. Temps de Frame (Frame Time)

2. Temps de Recalcul

3. Utilisation Mémoire

4. Temps de Chargement

Techniques de Profiling

1. Profiling avec perf (Linux)

2. Profiling avec cargo-flamegraph

3. Profiling avec criterion

4. Profiling avec println! et Timing

5. Profiling Mémoire avec valgrind (Linux)

Optimisations Recommandées

1. Index des Dépendances

2. Virtualisation du Rendu

3. Parser Optimisé

4. Cache des Dépendances

5. Format Binaire pour Persistance

6. Parallélisation du Recalcul

7. Compression du Cache

Bonnes Pratiques

1. Éviter les Allocations Inutiles

2. Réutiliser les Structures

3. Utiliser des Références

4. Éviter les Clones Inutiles

5. Pré-allouer les Collections

Benchmarks

Benchmark 1 : Évaluation de Cellule

Benchmark 2 : Recalcul Global

Benchmark 3 : Chargement de Fichier

Benchmark 4 : Rendu de la Grille

FAQ

Q: Pourquoi le recalcul est-il lent ?

Q: Pourquoi l'interface lag ?

Q: Comment améliorer les performances de chargement ?

Q: Le cache prend trop de mémoire ?

Q: Comment profiler l'application ?

Résumé

Optimisations Actuelles

Goulots d'Étranglement

Optimisations Recommandées

Bonnes Pratiques

1. Profiling avec `perf` (Linux)

2. Profiling avec `cargo-flamegraph`

3. Profiling avec `criterion`

4. Profiling avec `println!` et Timing

5. Profiling Mémoire avec `valgrind` (Linux)