TESTER LES TESTS

Avec les précédents essais d'élagages plus ou moins agressifs, j'ai fini par me demander si aller deux fois plus vite voulait vraiment dire être deux fois plus efficace? Certes le résultat arrive plus rapidement, mais comment s'assurer de réellement tomber sur la meilleure solution, sans avoir à parcourir l'entièreté de l'arbre.
Dans une application classique, tester une fonction est binaire, le résultat est bon ou non. Mais sur un problème d'edt (NP-complet), il n'existe pas de réponse pré-calculée. On explore des millions de branches avec un bnb, et le moindre bug dans une condition d'élagage peut silencieusement dégrader la qualité du résultat sans jamais lever d'erreur.

réparer les tests

Le premier réflexe a été d'écrire des tests unitaires et de vérifier le déterminisme du moteur. Avec suffisamment de temps j'en suis venu à comprendre qu'un harnais de test qui ne sait pas échouer bruyamment ne prouve rien. Mes tests validaient le moteur quand j'essayais des méthodes d'élégage très agressives qui auraient du le rendre non exhaustif, j'ai donc décidé de passer de nouvelles journées à courir après les erreurs ridicules qui validaient du code pourtant faux :

• Le test compare des erreurs : mon test de déterminisme comparait les solutions produites avec 1 thread et 8 threads. On affichait fièrement 100% déterministe (6/6). En réalité, une faute de frappe (m.event_uid au lieu de m.event.uid) levait une exception interceptée par un try/catch. Le test comparait la chaîne de caractères de l'exception, alors strictement identique d'un run à l'autre.. hmhm... Le test était vert sans même faire tourner le solveur.
• Tri inversé : pour comparer deux listes de solutions sans tenir compte de l'ordre d'émission, mon comparateur triait les mouvements par ordre alphabétique. Finalement ça cachait juste le fait que le moteur émettait les mouvements dans le sens inverse de l'exploration, faisant remonter le pire cours comme premier choix.

J'en passe.

differential testing et baselines golden

Est donc apparue évidente la nécessité de s'appuyer sur des tests propres et solides, je me suis donc tourné vers le papier de William McKeeman, Differential Testing for Software (1998). L'idée est de capturer une référence complète (golden baseline) sur des semaines réelles, puis on rejoue chaque modification contre cet instantané.

graph TD
    Baseline[("Golden Baseline<br><i>(JSON)</i>")] --> Diff("<br>compare_golden.py<br><br>")
    Current["<br>Moteur à tester<br><br>"] --> Diff

    Diff -->|Étape 1| Valid["Contraintes Dures<br><i>(collisions/horaires/...)</i>"]
    Diff -->|Étape 2| Score["Delta de Score<br><i>(Scores identiques?)</i>"]
    Diff -->|Étape 3| Parity["Parité des Mouvements<br><i>(strict ou lenient)</i>"]

    style Baseline fill:black,stroke:black,color:white
    style Current fill:black,stroke:black,color:white
    style Diff fill:white,stroke:black,color:black
    style Valid fill:black,stroke:black,color:white
    style Score fill:black,stroke:black,color:white
    style Parity fill:black,stroke:black,stroke-width:2px,color:white

Le script compare_golden.py passe par deux modes de validation:

• Mode strict : comparaison entière, même ordre d'exploration, mêmes identifiants de salle, mêmes horaires exacts.
• Mode lenient : quand une modification change légitimement l'ordre de parcours des branches, plusieurs solutions peuvent avoir exactement le même score. On découpe les solutions en blocs de même score et on vérifie l'égalité par multiset :

# lenient
base_groups = _group_by_score(base_solutions, mode)
curr_groups = _group_by_score(curr_solutions, mode)

for (b_score, b_list), (c_score, c_list) in zip(base_groups, curr_groups):
    b_sigs = [_solution_signature(s) for s in b_list]
    c_sigs = [_solution_signature(s) for s in c_list]
    
    # une solution trouvée tue une solution de référence
    for sig in b_sigs:
        if sig in c_sigs:
            c_sigs.remove(sig)
        else:
            yield Divergence(uid, summary, "missing", f"solution manquante: {sig}")

tester les tests

Avant de faire confiance à un test vert, je casse donc volontairement le moteur pour vérifier qu'on me rend un rapport tout rouge. Si je désactive la contrainte de non-chevauchement des salles ou que j'ajoute un décalage artificiel de 5 points de pénalité, le harnais test golden smoke DOIT échouer en moins de 60 secondes en pointant l'événement exact qui diverge.

la suite

Cette nouvelle façon de stresser willowengine me permet donc de tenter des changements ou paramètres plus agressifs sans risquer de découvrir une erreur en production. Je pense maintenant à traiter ce que je me cache depuis des semaines et sortir les 3 500 lignes du serveur fastpi pour le découper proprement en services. Si le temps me le permet, j'irais aussi monitorer la consommation de RAM et m'occuper plus précisément de la parallélisation dans le moteur.

Ce n'est pas un travail visible du côté utilisateur, mais qui va permettre de réduire drastiquement l'inertie que prenaient les tests, et donc me permettre de me concentrer sur l'important en ce qui concerne le solveur:)

//pekmi