Pouvoir indexer un arbre de répertoire et de fichiers, c’est important pour la collecte de résultats, l’agrégation de données, la génération automatique de rapport ou de scripts … autant de processus qui sont importants dans mon domaine. Les codes d’indexation dans le module dir étaient assez anciens, très génériques et ne s’appuyaient que peu sur  les fonctions système du langage, conformément à une politique de compatibilité. Mais ils étaient assez lents aussi, c’est donc quelque chose que j’ai fait évoluer avec un nouveau module index et la création d’un écosystème buildez.sys qui inclue quelques briques pouvant travailler ensemble.

1. Formats d’index

N’ayant jamais renié une orientation data centric, je démarre cette note par les données, j’utilise 3 formats : une liste python basique, un format simple et un format dirmatrix, pour résumer :

Format liste : chaque élément correspond à une entrée [dir+file].

['C:\Python3\envs\prod\Lib\site-packages\buildez\',  'C:\Python3\envs\prod\Lib\site-packages\buildez\__init__.py', ...]

Format simple : chaque ligne correspond à [dir, ] ou [dir, file]. Il s’agit d’une matrice de type string, à deux colonnes. La première identifie le répertoire jusqu’à la racine, et la seconde est vide si l’item est un répertoire, sinon elle contient le nom du fichier.

[['C:\Python3\envs\prod\Lib\site-packages\buildez\', ''],  ['C:\Python3\envs\prod\Lib\site-packages\buildez\', '__init__.py'], ...]

Format dirmatrix : chaque ligne correspond à [type, dir, dir|file, rname, ext]. Ce format correspond  à une matrice de type string à 5 colonnes. La première contient un identifiant de type : 'd' (répertoire), 'f' (fichier), 'l' lien et '' (type inconnu). La seconde contient le répertoire si l’élément est un fichier. Dans le cas d’un répertoire elle contient tout le chemin depuis la racine sauf cet item. La troisième contient l’item proprement dit (nom complet) qu’il s’agisse d’un fichier ou d’un répertoire. Les deux suivantes incluent le nom de l’item sans extension, et l’extension (si l’item est un fichier).

[['d', 'C:\Python3\envs\prod\Lib\site-packages\', 'buildez', '', ''],  ['f', 'C:\Python3\envs\prod\Lib\site-packages\buildez\', '__init__.py', '__init__', 'py'], ... ]

Chaque format a des avantages et des inconvénients. J’utilise principalement dirmatrix, car il correspond à une systématisation, basée sur les listes d’items que l’on peut avoir quand on fait un dir|ls dans un répertoire. Il est plus lourd, mais beaucoup rapide à exploiter que list ou simple, car toutes les informations dont nous pouvons avoir besoin sont déjà dans la liste. Recalculer des informations prends du temps sur des arbres profonds, il y a toujours un choix d’optimisation à faire entre le calcul initial dans la collecte et le recalcul dans l’exploitation. Dans le cas du module index, l’effort à porté sur l’optimisation de la collecte, puis sur les filtres pour limiter l’index ou faire des recherches dans cet index.

2. Comptage et typage d’items

Sur les index au format simple et dirmatrix, j’utilise une fonction index_simple_counter (de index.py) qui permet de calculer le nombre d’items aux formats 'd|f|l| ' et de les sommer pour avoir le nombre total d’items (qui correspond en principe à la longueur de l’index). Ce type de fonction est très utile pour vérifier le contenu d’un index, son utilisation est simple :

def index_simple_counter(index, format, verb):

Ou verb est le niveau de verbosité (0 pour silencieux), index est une liste au format défini par l’argument format (simple ou dirmatrix). Cette fonction est plutôt réservée à de la validation, elle n’est pas optimisée et peut être assez longue si on doit retrouver le type des items quand l’index est au format simple, car on utilise des fonctions telles que os.path.isfile(item), os.path.isdir(item), ospath.islink(item). Mais elle est très rapide au format dirmatrix, car il n’y a qu’à compter. Cette fonction n’utilise pas des arguments nommés pour des raisons de simplification et par ce qu’elle est souvent associée à un mécanisme de thread qui implémente une barre de progression. Elle renvoie une liste de 5 compteurs, par exemple (ligne en rouge) :

! test_dir: C:\Python3\envs\prod\Lib\site-packages\buildez ! Working using format='simple' index_tree_files found 2006 items +++ Counting . [files, dirs, links, unkn, total] [1805, 201, 0, 0, 2006]

3. Fonctions d’interconversion

Le module index_tools.py (buildez.sys) inclue 7 fonctions d’interconversion entre ces 3 formats, leurs noms sont self explicatifs :

index_list2simple(index, blank='', verb=0) index_list2dirmatrix(index, blank='', verb=0) index_dirmatrix2list(index, blank='', verb=0) index_dirmatrix2simple(index, blank='', verb=0) index_simple2list(index, blank='', verb=0) index_simple2dirmatrix(index, blank='', verb=0) index_converter(src, src_format, dst_format, blank='', verb=0)

En général j’utilise index_converter qui est une interface aux 6 autres, src est l’index à convertir et au format src_format, dst_format est le format destination, blank est utilisé pour spécifier un caractère ou une chaine pour les éléments nuls, dans certains processus on utilisera '-' plutôt qu’une chaine vide, la fonction renvoie un nouvel index (non destructive).

4. Indexation basée sur os.walk

Une fois que nous avons défini quelques utilitaires nous pouvons indexer, avec 4 fonctions (récursives et non récursives) qui remplacent les anciennes :

Fonction	Description
index_files(d, format='simple', blank='', verb=0)	Produit un index (au format simple ou dirmatrix) à partir du répertoire d et qui liste tous les éléments de d : répertoires, fichiers, liens, sans type connu (non récursif).
index_tree_files(d, format='simple', blank='', verb=0)	Version récursive de index_files sans contrôle sur la profondeur d’indexation (tout l’arbre est parcouru).
index_dirs(d, format='simple', blank='', verb=0)	Produit un index (au format simple ou dirmatrix) à partir du répertoire d qui ne liste que des répertoires de d (non récursif).
index_tree_dirs(d, format='simple', blank='', verb=0)	Version récursive de index_dirs sans contrôle sur la profondeur d’indexation (tout l’arbre est parcouru).

Pour l’input, les fonctions cleanpath (module oslocal.py) et file_cleanpath (module file.py) sont disponibles, elles permettent de nettoyer en profondeur la valeur de d, sans s’occuper de l’OS. Donc d’utiliser le caractère séparateur / que l’on soit sous Linux ou Windows, ce qui est un vrai confort au quotidien. Les fonctions non récursives utilisent os.listdir et les fonction récursives implémentent un  walker basé os.walk qui permettent d’avoir directement les types des items. Dans ce contexte, pour optimiser il faut absolument éviter les appels Python de type os.path.is .. ou l’utilisation de Path et de os.path.join (pour concaténer les éléments d’un chemin d’accès). Si nous partons d’une définition saine de d (les 4 fonctions incluent également des vérifications) il n’y a pas de problèmes dans le déroulé du walker et on peut optimiser.

5. Performances

Si on utilise le répertoire C:\Python3\envs\prod\Lib\site-packages\ nous avons à peu près 30000 items (avec de petites variations en fonction de chaque poste). Sur un PC de travail bi-Xeon, avec une fréquence tranquille (moins de 2 Ghz), 16/32 Go RAM,  équipé d’un SSD mi-gamme, Windows10 ou 11 (x64), nous avons ce niveau de performances:

Fonction	Format	Méthode time.time	[files, dirs, links, unkn, total]
index_tree_files	simple dirmatrix	0.7 – 0.9 s 0.9 – 1 s	[27995, 2876, 0, 0, 30871]
index_tree_dirs	simple dirmatrix	0.7 – 0.8 s 1 – 1.3 s	[0, 2876, 0, 0, 2876]
index_files	simple dirmatrix	~ 0 s 0.2 – 0.3 s	[48, 237, 0, 0, 285]
index_dirs	simple dirmatrix	0.04 – 0.05 s 0.04 – 0.05 s	[0, 237, 0, 0, 237]

Les fonctions index_dirs et index_tree_dirs sont plus lentes que leurs contreparties car il y a un test pour déterminer si l’item est un répertoire et s’il doit être inclus dans l’index. Le format simple est plus rapide à construire que le format dirmatrix, mais ce dernier sera plus performant coté exploitation.

6. Comparaison avec les anciennes routines

Les anciennes fonctions (antérieures à 2014) sont regroupées dans le module deprec_dirmatrix.py, elles ne fonctionnent qu’au format dirmatrix. La fonction deprec_dir_dirmatrix_old indexe les répertoires et fichiers, elle utilise un algorithme qui est basé sur la génération et le traitement d’une queue au fur et à mesure de la progression. Cette approche qui marche sur tous les systèmes (pour peu qu’on aie une fonction capable de lister le contenu d’un répertoire) semble être (5x) moins efficace que le walker sur les arbres profonds et ramifiés. L’écart s’annule sur les petits arbres. Les performances s’équilibrent aussi quand on utilise deprec_dir_dirmatrix_dirs qui n’indexe que les répertoires, car elle ne mets en queue que les répertoires, alors que le walker mets les pieds partout. Les autres fonctions, non récursives (deprec_dir_dirmatrix et deprec_dir_dirmatrix_dirs) ont des performances similaires, travaillant sur un seul niveau de l’arbre il n’est pas possible de percevoir des différences (et nouvelles/anciennes fonctions utilisent le même appel à os.listdir de toutes manières).

Fonction	Format / Récursive	Méthode time.time	[files, dirs, links, unkn, total]
deprec_dir_dirmatrix	dirmatrix / oui	0.8 – 1.1 s	[27995, 2876, 0, 0, 30871]
deprec_dir_dirmatrix_old	dirmatrix / oui	5.2 – 5.6 s	[27995, 2876, 0, 0, 30871]
deprec_dir_dirmatrix_dirs	dirmatrix / oui	1.1 s	[0, 2876, 0, 0, 2876]
deprec_dir_dirmatrix	dirmatrix / non	~0 s	[48, 237, 0, 0, 285]
deprec_dir_dirmatrix_dirs	dirmatrix / non	0.09 s	[0, 237, 0, 0, 237]

La fonction deprec_dir_dirmatrix (maintenue pour des raisons de compatibilité) est juste une interface, elle appelle index_tree_files ou index_files selon qu’elle est récursive ou non, elle a donc globalement les mêmes performances.

7. Conclusion

L’idée était de passer sous la barre de la seconde pour indexer complètement (dir + file) un répertoire du type /site-packages/ avec des PC courants. L’objectif étant de ne pas trop perdre de temps dans l’indexation, car pour cette nouvelle itération de codes, j’ai pris l’option de découpler la génération des index (étape lente) vs. le filtrage ou la recherche dans les index (étapes rapides). L’index de ce point de vue n’est plus qu’une structure de données pivot, qui est exploitée par l’écosystème buildez.sys.

Je n’ai pas encore intégré des alternatives comme os.scandir, réputé plus rapide pour la génération d’index, il n’y a pas grand chose à faire c’est aussi un itérateur avec une exploitation différente des items (objets os.DirEntry) qui ont l’avantage d’être typés au fur et à mesure de l’exploration de l’arbre. Donc il n’est pas impossible que la fonction index_tree_files devienne à son tour obsolète.