KACHOW

Le moteur C# était devenu redoutablement rapide sur un cours isolé : moins de 3 secondes à profondeur 2, là où le solveur initial prenait des heures. L'étape suivante est donc de passer à l'échelle supérieure et traiter l'ensemble de l'année universitaire.

Calculer toute l'année, c'est un "marathon". on travaille sur 46 semaines de cours, 38 contenant des données réelles, soit 3 005 événements à évaluer à profondeur 3.

« plus de parallélisme »

Sur le papier, le problème est agréablement parallélisable : chaque semaine ou chaque cours peut être calculé indépendamment. Disposant de 32 threads et de 64 de ddr5, le calcul de dimensionnement initial a été de lancer 12 processus willowengine en mode serveur (le processus reste vivant en attendant une nouvelle tâche), avec 8 threads chacun. ça fait 96 threads de calcul, on peut tenir allez go

Le lancement du marathon a duré exactement 12 secondes :

[14:22:01] Pool démarré : 12 instances WillowEngine
[14:22:05] Semaine 2026-03-09 : 315 cours
[14:22:11] RAM utilisée : 18.4 Go
[14:22:05] Semaine 2026-010-09 : 311 cours
[14:22:11] RAM utilisée : 58.4 Go
[14:22:14] Hard freeze : le GC monopolise 100% du CPU

Bon en fait on tient pas, le disque swap et la ram vient de se faire manger par 12 processus qui devaient simplement déplacer des cours dans une semaine. il faut sortir les outils

autopsie

Premier élément mesuré : la volumétrie réelle. Le loader fusionne l'ensemble des fichiers ICS de l'université pour détecter les conflits croisés (9 groupes étudiants, 159 salles, 438 enseignants). Une semaine réelle (comme celle du 9 mars 2026) ne représente pas 80 cours isolés, mais 1 342 événements complets (??).

L'état bitboard d'une semaine pèse donc :
(9+159+438) * 5 + 1342 = 4 372 entiers 64 bits (ulong), soit 34Ko
34 Ko par état de semaine, ça va. le problème n'est pas là.

En fait c'était la file de travail de la décomposition de recherche à profondeur 3:

graph LR
        Root["Étape A : Génération<br><i>Parallel.ForEach</i>"] -->|84 394 WorkItems| Queue[("ConcurrentQueue<br><b>~6,2 Gio de snapshots</b>")]
        Queue -->|Consommation| Workers["Étape B : Workers<br><i>8 threads par moteur</i>"]

        style Root fill:#111,stroke:black,color:white
        style Queue fill:black,stroke:black,stroke-width:2px,color:#fff
        style Workers fill:white,stroke:black,color:black

1. La file est entièrement matérialisée avant d'être consommée: l'étape A générait tous les points d'entrée de la cascade dans une ConcurrentQueue<WorkItem> avant que les threads de l'étape B ne commencent.
2. Chaque WorkItem embarquait un snapshot complet de l'univers :

   // L'ancien WorkItem (classe sur le tas)
   class WorkItem {
       public ulong[] U;           // Tableau d'état
       public int[] Cd;            // Compteurs de conflits
       public bool[] Seen;         // Cours déjà déplacés
       public List<CompactMove> Stack;
   }

1. L'ArrayPool : pour éviter d'allouer, le moteur louait ces tableaux via ArrayPool<T>.Shared.RentAndCopy(). Mais ArrayPool arrondit la taille louée à la puissance de 2 supérieure :

• Rent(4372 ulongs) -> alloue 8 192 ulongs = 64 Ko (pas 34);
• Rent(1342 ints) -> 8 Ko;
• Rent(1342 bools) -> 2 Ko;
• Total par élément : ~75 Ko.

Sur un cours avec de nombreuses combinaisons de cascades, la file a atteint jusqu'à 84 394 WorkItems en vie ensemble, ça fait
84 394 * 75 = ~6.2Go RAM / processus

Avec nos 12 processus en parallèle on atteint ~74,4 Go. C'est ridiculement haut et on ne devrait pas avoir à supplier de nouvelles barettes à sk hynix pour calculer un edt

la réponse

Il me semble que recréer cet état de 75ko est atteignable et cohérent. Pourquoi les stocker dans une file d'attente quand on sait reconstruire cet état en quelques microsecondes ?

L'état de départ d'une branche de cascade est parfaitement déterministe, c'est l'état initial u0 (où seul le cours cible principal a été retiré, partagé et immuable), auquel on retire les 1 ou 2 cours en conflit rencontrés sur le chemin.

J'ai donc remplacé la classe WorkItem par une structure de données compacte passée par valeur :

// Le nouveau descripteur de chemin (~88 octets, pas d'alloc sur le tas)
readonly record struct WorkItemDesc(
    int RootIdx, int RootDay, int RootQ,
    int Retry1Idx, int Retry1Day, int Retry1Q,
    int Retry2Idx, int Retry2Day, int Retry2Q,
    int RemainingDepth,
    int RootPendingCount, double RootPendingLB,
    int Retry1PendingCount, double Retry1PendingLB,
    int Retry2PendingCount, double Retry2PendingLB
);

Chaque thread worker de l'étape B dispose désormais d'un seul buffer local réutilisable. Lorsqu'il extrait un descripteur de la file :
1. Il copie l'état de base u0 dans son buffer local via un simple memcpy (34 Kio / 1 à 2 µs);
2. Il applique le retrait des 1 ou 2 cours spécifiés dans le descripteur (RemoveFromOriginal);
3. Il lance sa recherche.

graph LR
        Root["Étape A : Génération"] -->|84 394 Descripteurs| Queue[("ConcurrentQueue<br><b>~7 Mio de descripteurs (88o)</b>")]
        Queue -->|Dépile & Reconstruit| Worker["Buffer ThreadStatic<br><i>34 Kio memcpy en 1µs</i>"]

        style Root fill:#111,stroke:black,color:white
        style Queue fill:white,stroke:black,color:black
        style Worker fill:black,stroke:black,stroke-width:2px,color:#fff

Résultat mesuré sur l'événement témoin :

Sur l'ensemble des 12 processus, le poste de dépense n°1 venait de passer de 74 Go à moins de 100 Mo.

éliminer les allocations dans le scoring

Une fois la file d'attente ramenée à une taille raisonnable, un nouveau a mis en évidence le second poste critique que sont les allocations dans la fonction d'évaluation ScoreDay.

ScoreDay calcule la pénalité d'une journée (trous dans l'emploi du temps, pause déjeuner, heure de fin tardive). Elle est appelée à chaque nœud de l'arbre et à chaque vérification de borne inférieure, parfois environ 1 million de fois sur un cours lourd.

Dans sa version initiale, elle allouait 3 listes dynamiques par appel (merged, lunchOverlaps, lunchMerged) pour fusionner les cours qui se touchent.

On essaie de réécrire ScoreDay en zéro-allocation :

• Utilisation de Span<(int,int)> sur la pile ;
• Parcours en une seule passe linéaire avec accumulateurs scalaires (occupied, mergedCount, dayEnd) ;
• Fusion des créneaux de déjeuner au vol directement pendant le flux.

En parallèle, j'ai corrigé l'ordonnancement dans HandleSolution : au lieu de lancer la validation complète de l'emploi du temps sur chaque feuille atteinte, on évalue d'abord le delta de score et la borne top-K. Si le résultat est de toute façon trop mauvais pour entrer dans le top 5, on ne perd pas de temps avec lui.

Mesure sur un événement lourd (168 434 appels de delta, à 1 worker déterministe) :

En ajoutant la lecture directe des scores d'origine précalculés (_origGroupDayScores) plutôt que de re-scorer l'état initial avant chaque delta, le temps de cette passe est descendu à 282 ms (-45 % cumulé).

on parse 3 000 fois la semaine??

Enfin je nous ai remis en question, moi et le serveur persistant. Il reste une aberration architecturale. A chaque cours évalué dans le marathon, python générait et sérialisait 2.9Mo de json pour décrire la semaine. willowengine désérialisait ce json, parsait 2700 dates et reconstruisait le graphe complet de 1.8 million de paires de conflits.
Sur 3 005 cours, c'était 8,5 Go de JSON sérialisés et parsés deux fois, bloquant le flux et consommant 76 % du temps initial de calcul ;;

Le moteur a gagné le mode semaine chargée:

stdin:  {"cmd":"load_week", "payload":{...1342 événements, contraintes...}}
stdout: LOADED:{"ok":true, "events":1342}

stdin:  {"cmd":"run_loaded", "targetUid":"ADE-102521", "depth":3, "maxResults":5}
stdout: RESULT:{"ok":true, "solutions":[...]}

stdin:  {"cmd":"unload_week"}

• Le modèle hebdomadaire (WeekModel) est construit une seule fois par semaine et reste immuable en mémoire ;
• Chaque appel run_loaded n'envoie que 50 octets de paramètres ;
• Le temps moyen par calcul s'est effondré à ~35 ms ;
• L'empreinte mémoire totale de l'ensemble des 12 serveurs stabilisés est tombée à ~2 Go.

le delta incrémental

Tout ne peut pas toujours marcher, il y a des idées séduisantes en théorie qui se révèlent catastrophiques en pratique. Javascript, electron, les imprimantes réseau et le delta incrémental par exemple.

Au lieu de recalculer le score des journées affectées lors de chaque test de borne inférieure, pourquoi ne pas maintenir le score de façon incrémentale dans l'arbre de recherche ? Chaque nœud passerait d'un calcul proportionnel à la taille de la pile à un coût O(1). J'ai tenté un brouillon et implémenté, armé d'un harnais de validation stricte (WILLOW_ENGINE_DELTA_CROSSCHECK) vérifiant à chaque nœud que le delta incrémental était rigoureusement égal au recalcul complet. Le résultat était parfaitement exact, zéro divergence sur l'ensemble de la suite de tests.

Puis voilà les résultats du benchmark (tester les tests) sur 100 cours de TD, semaine du 9 mars 2026 :

Pourquoi un tel échec? La forme de l'arbre de recherche. Dans les emplois du temps universitaires, l'arbre est très large (des dizaines de créneaux et de salles testés à chaque niveau) mais plutot peu profond (les cascades font rarement plus de 1 à 3 cours déplacés).

Le delta incrémental forçait à payer le coût de mise à jour des structures de suivi à chaque branchement exploré (push et pop), alors que le recalcul complet from scratch sur les 2 ou 3 jours touchés par la pile était déjà dérisoire.

Bon voilà, on fait bien de mesurer systématiquement. Même avec une bonne idée et une implémentation au résultat correct, si le chronomètre dit non, il faut jetter. je m'en remettrai.

réglage des threads

Pourquoi 12 processus × 8 workers (96 threads) ne donnait-il pas les performances espérées sur nos 32 threads matériels? En traçant la durée exacte de chaque cours dans une semaine, voilà :

pie title "....               Répartition du temps sur 20 cours
    "19 cours ordinaires (~1 ms)" : 32
    "1 cours lourd (TP Dév. Durable)" : 153

Sur 20 cours consécutifs :

19 cours sont résolus en ~1 ms (très peu de conflits) ;

1 seul cours lourd monopolise 153 ms sur les 185 ms totales (83 % du temps).

C'est le problème des stragglers décrit dans les travaux de Blumofe et Leiserson sur le Work Stealing, 1999 (papier ici, rien compris):

1. Si on lance 24 processus à 1 seul worker (24×1 = 24 threads), le débit s'effondre (1,02 s sur 315 cours) car les cours légers se terminent instantanément et 23 coeurs dorment pendant que le cours lourd patoge.
2. Si on lance 12 processus à 8 workers (12×8 = 96 threads), les 96 threads se battent pour 32 threads matériels, détruisent la localité des caches L2/L3.
3. Le compromis idéal mesuré : 12 processus × 4 workers (48 threads).

Comparaison sur le marathon réel (315 cours) :

Le passage en 12×4 augmente le débit global de +22 % tout en divisant par deux le nombre de threads et la charge mémoire.

résultats

En attaquant méthodiquement chaque couche du système :

la suite

Le moteur est désormais solide et super rapide, il peut traiter une année complète d'emplois du temps en quelques minutes, en depth 3, sans faire cligner des yeux la RAM d'un téléphone, et avec le sourire.

Voilà! Je pense que niveau perf, on est BONS :)
Résoudre vite, maintenant on sait faire. Mais pour rappel, le calcul s'effectue sur un seul cours, il reste très localisé. Le gain en est restreint, ce n'est qu'une réparation. Je pense à ajouter un script léger (DFS/bnb) pour cummuler ces réparations quand elles vont ensemble, pour additionner les gains. J'aimerais aussi prendre le temps de refaire tout ce moteur c# en c++ pour me faire la main.

Une incroyable update qui marque probablement la fin des posts de performance sur willowengine! ⋆˚✿˖°

//pekmi