Comment lister les répertoires plus rapidement?

Question

J'ai quelques situations où j'ai besoin de lister les fichiers de manière récursive, mais mes implémentations ont été lentes. J'ai une structure de répertoire avec 92784 fichiers. find répertorie les fichiers en moins de 0,5 seconde, mais mon implémentation Haskell est beaucoup plus lente.

Ma première implémentation a duré un peu plus de 9 secondes, la prochaine version un peu plus de 5 secondes et je suis actuellement à un peu moins de deux secondes.

listFilesR :: FilePath -> IO [FilePath] 
listFilesR path = let 
    isDODD "." = False 
    isDODD ".." = False 
    isDODD _ = True 

    in do 
     allfiles <- getDirectoryContents path 
    dirs <- forM allfiles $ \d -> 
     if isDODD d then 
     do let p = path </> d 
      isDir <- doesDirectoryExist p 
      if isDir then listFilesR p else return [d] 
     else return [] 
    return $ concat dirs 

Le test prend environ 100 Mo de mémoire (+ RTS -s), et le programme consacre environ 40% en GC.

Je pensais faire la liste dans une monade WriterT avec Sequence en tant que monoïde pour empêcher les concavités et la création de liste. Est-ce probable que cela aide? Que devrais-je faire d'autre?

Modifier: J'ai modifié la fonction pour utiliser readDirStream, et cela permet de réduire la mémoire. Il y a encore une certaine répartition, mais le taux de productivité est maintenant> 95% et il tourne en moins d'une seconde.

Ceci est la version actuelle:

list path = do 
    de <- openDirStream path 
    readDirStream de >>= go de 
    closeDirStream de 
    where 
    go d [] = return() 
    go d "." = readDirStream d >>= go d 
    go d ".." = readDirStream d >>= go d 
    go d x = let newpath = path </> x 
     in do 
      e <- doesDirectoryExist newpath 
      if e 
     then 
      list newpath >> readDirStream d >>= go d 
     else putStrLn newpath >> readDirStream d >>= go d 

Answer 1

Je pense que System.Directory.getDirectoryContents construit une liste complète et utilise donc beaucoup de mémoire. Que diriez-vous d'utiliser System.Posix.Directory? System.Posix.Directory.readDirStream renvoie une entrée une par une. En outre, FileManip library peut être utile bien que je ne l'ai jamais utilisé.

Answer 2

Un problème est qu'il doit construire la liste complète du contenu du répertoire, avant que le programme ne peut rien faire avec eux. Les E/S paresseuses sont généralement désapprouvées, mais l'utilisation d'interfaces non sécurisées réduit considérablement l'utilisation de la mémoire.

listFilesR :: FilePath -> IO [FilePath] 
listFilesR path = 
    let 
    isDODD "." = False 
    isDODD ".." = False 
    isDODD _ = True 
    in unsafeInterleaveIO $ do 
    allfiles <- getDirectoryContents path 
    dirs <- forM allfiles $ \d -> 
     if isDODD d then 
     do let p = path </> d 
      isDir <- doesDirectoryExist p 
      if isDir then listFilesR p else return [d] 
     else return [] 
    return $ concat dirs 

Answer 3

Le profilage de votre code montre que la plus grande partie du temps processeur est comprise entre getDirectoryContents, doesDirectoryExist et </>. Cela signifie que seule la modification de la structure des données ne sera pas très utile. Si vous voulez faire correspondre les performances de find, vous devez utiliser des fonctions de niveau inférieur pour accéder au système de fichiers, probablement celles que Tsuyoshi a signalées.

Answer 4

Serait-ce une option d'utiliser une sorte de système de cache combinée avec la lecture? Je pensais à un service d'indexation asynchrone/thread qui maintenait ce cache à jour en arrière-plan, peut-être que vous pourriez faire le cache comme une simple base de données SQL qui vous donnerait de bonnes performances lors des requêtes?

Pouvez-vous élaborer quelque chose sur votre «projet/idée» afin que nous puissions trouver quelque chose d'autre? Je n'irais pas moi-même pour un "index complet" car je construis principalement des services basés sur le Web et "resposnetime" est critique pour moi, d'autre part - si c'est une façon initiale de démarrer un nouveau serveur, je suis sûr les clients ne seraient pas dérangés d'attendre cette première fois. Je voudrais simplement stocker le résultat dans la base de données pour les recherches ultérieures.