Wie listet man Verzeichnisse schneller auf?

Question

Ich habe ein paar Situationen, in denen ich rekursiv Dateien auflisten muss, aber meine Implementierungen waren langsam. Ich habe eine Verzeichnisstruktur mit 92784 Dateien. find listet die Dateien in weniger als 0,5 Sekunden auf, aber meine Haskell-Implementierung ist viel langsamer.

Meine erste Implementierung dauerte etwas mehr als 9 Sekunden, die nächste Version etwas mehr als 5 Sekunden und ich bin momentan auf etwas weniger als zwei Sekunden.

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 

Der Test dauert etwa 100 Megabyte Speicher (+ RTS-S), und das Programm verbringt etwa 40% im GC.

Ich dachte daran, die Auflistung in einer WriterT-Monade mit Sequenz als Monoid zu machen, um die Erstellung von Konkatas und Listen zu verhindern. Ist das wahrscheinlich hilfreich? Was soll ich sonst machen?

Bearbeiten: Ich habe die Funktion bearbeitet, um readDirStream zu verwenden, und es hilft, den Speicher zu halten. Es gibt immer noch eine Zuteilung, aber die Produktivitätsrate liegt jetzt bei> 95% und sie läuft in weniger als einer Sekunde.

Dies ist die aktuelle Version:

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

Ich denke, dass System.Directory.getDirectoryContents eine ganze Liste konstruiert und verwendet daher viel Speicher. Wie wäre es mit System.Posix.Directory? System.Posix.Directory.readDirStream gibt einen Eintrag nacheinander zurück.

Auch FileManip library könnte nützlich sein, obwohl ich es nie benutzt habe.

Answer 2

Ein Problem ist, dass es die gesamte Liste der Verzeichnisinhalt zu konstruieren hat, bevor das Programm kann mit ihnen nichts tun. Lazy IO ist in der Regel verpönt, aber mit unsafeInterleaveIO hier Schnitt Speicherverbrauch erheblich.

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

Das Profiling Ihres Codes zeigt, dass die meiste CPU-Zeit in getDirectoryContents, doesDirectoryExist und </> geht. Dies bedeutet, dass nur die Änderung der Datenstruktur nicht sehr hilfreich ist. Wenn Sie die Leistung von find abgleichen möchten, sollten Sie Funktionen auf niedrigerer Ebene für den Zugriff auf das Dateisystem verwenden, wahrscheinlich diejenigen, auf die Tsuyoshi hingewiesen hat.

Answer 4

Wäre es eine Option, eine Art Cache-System in Kombination mit dem Lesen zu verwenden? Ich dachte an einen asynchronen Indizierungsdienst/Thread, der diesen Cache im Hintergrund auf dem neuesten Stand hielt, vielleicht könnten Sie den Cache als eine einfache SQL-DB machen, die Ihnen dann eine gute Leistung geben würde, wenn Sie dagegen Anfragen stellen würden?

Können Sie etwas zu Ihrem "Projekt/Idee" ausarbeiten, damit wir uns etwas anderes einfallen lassen können?

Ich würde mich nicht für einen "vollen Index" selbst gehen, da ich hauptsächlich webbasierte Dienste baue und "Respossetime" kritisiert, auf der anderen Seite - wenn es ein erster Weg ist, einen neuen Server zu starten, bin ich mir sicher die Kunden würden es nicht abwarten, das erste Mal zu warten. Ich würde das Ergebnis einfach in der Datenbank für spätere Nachschlagezwecke speichern.