Aller au contenu

Treemap : quand un vrai disque fait planter un algorithme récursif

Le scan complet d'un disque de 648 Go a fait planter mon visualiseur d'espace disque en C++ / Qt. Retour sur le passage du squarified treemap en version itérative.

Publié le 3 min de lectureProjet lié : Treemap

#C++#Qt#Algorithmique

Treemap est un visualiseur d’espace disque pour Windows, écrit en C++17 avec Qt 6 : on choisit un disque, le scan tourne en arrière-plan, puis chaque fichier et chaque dossier devient un rectangle dont l’aire est proportionnelle à sa taille, façon WinDirStat.

Le scan complet du disque système C:\ (648 Go) a fait planter le programme par stack overflow, sans message exploitable.

Le coupable : une frame de pile par élément

Le cœur du projet est l’algorithme squarified treemap (Bruls, Huizing, van Wijk). À chaque niveau, il regroupe les enfants d’un dossier en rangées, en cherchant à garder des rectangles aussi proches du carré que possible plutôt que des bandes fines illisibles.

La version classique de l’algorithme est récursive : chaque élément traité ajoute un appel à la pile. Sur un dossier à plusieurs centaines de milliers d’entrées, la pile déborde et le programme s’arrête net.

La solution : une boucle while

La version retenue parcourt les enfants avec une simple boucle. Les enfants sont triés du plus gros au plus petit, puis la liste est inversée pour pouvoir retirer le plus gros restant en O(1) avec pop_back. À chaque tour, on compare le pire ratio d’aspect de la rangée en cours avec et sans le nouvel élément : s’il s’améliore, l’élément rejoint la rangée ; sinon, la rangée est posée et une nouvelle commence.

while (!children.empty()) {
    FileNode* c = children.back(); // le plus gros qui reste

    double parentArea = bounds.width() * bounds.height();
    c->layoutArea = (totalRemainingWeight > 0)
                         ? (c->layoutWeight / totalRemainingWeight) * parentArea
                         : 0.0;

    // on regarde si ca ameliore ou empire le ratio d'ajouter cet
    // element a la rangee en cours
    std::vector<FileNode*> testRow = row;
    testRow.push_back(c);

    if (row.empty() || worstRatio(row, w) >= worstRatio(testRow, w)) {
        // ca ameliore (ou c'est le premier element), on l'ajoute a la rangee
        children.pop_back();
        row.push_back(c);
    } else {
        // ca empirerait, du coup on arrete la rangee ici et on la pose pour de vrai
        double rowWeight = 0;
        for (auto* r : row) rowWeight += r->layoutWeight;

        layoutRow(row, w, bounds);
        totalRemainingWeight -= rowWeight;
        w = std::min(bounds.width(), bounds.height());
        row.clear();
    }
}

Extrait de treemaplayout.cpp, lignes 163 à 190.

La mémoire utilisée par la pile reste plate quel que soit le nombre de fichiers d’un dossier. La descente dans les sous-dossiers, elle, reste un appel par niveau de profondeur, ce qui est borné par la profondeur de l’arborescence.

Les autres pièges d’un vrai disque

Un vrai disque réserve d’autres pièges, que le scanner gère explicitement :

  • Les jonctions et reparse points Windows, qui peuvent faire boucler un parcours à l’infini. Ils sont détectés via FILE_ATTRIBUTE_REPARSE_POINT, avec une limite de profondeur à 256 en filet de sécurité.
  • Les dossiers système inaccessibles ($Recycle.Bin, WinSxS…), exclus du scan, et les erreurs isolées entrée par entrée pour qu’un seul fichier problématique n’interrompe jamais tout le scan.
  • L’interface figée pendant le scan : le scan tourne dans un thread séparé avec QtConcurrent::run, et la progression revient sur le thread principal via QMetaObject::invokeMethod.

Ce que j’en retiens

Un algorithme correct sur le papier peut échouer sur des données réelles. Tester sur un vrai disque, avec ses centaines de milliers de fichiers et ses cas particuliers, a révélé une limite que des exemples simples ne montraient pas, et a orienté le choix d’une version itérative.

Le projet complet est décrit sur sa fiche, et le code est sur GitHub.

Toutes les notes