Come faccio ad attraversare rapidamente un file system mentre estrae / estrapolo vari dati e fornisco il feedback degli utenti?

Hai un problema legato all'I / O. Ciò significa che dovrai adattare il calcolo per far corrispondere l'I / O. Probabilmente hai a che fare con i dischi rigidi fisici, il che significa che le ricerche sono dominanti. Pertanto, "rapidamente" si traduce in "numero minimo di ricerche".

Possiamo quindi elencare i seguenti principi: 1. Scansione di intere directory (ampiezza prima). Non essere tentato di inserire sottodirectory prima di aver scansionato la directory genitore; tornare indietro richiede un'altra ricerca. 2. Salvare tutti i dati che è possibile ottenere da una directory. Dover tornare richiede un'altra ricerca.

Ora alcuni filesystem (ad es. NTFS) salvano il contenuto di piccoli file all'interno delle voci della directory. Su tali sistemi, è necessario eseguire l'hash di tali contenuti immediatamente dopo aver effettuato la scansione della directory. Altrimenti, non importa quando lo fai. Potrebbe essere opportuno eseguire prima la scansione delle sottodirectory in modo da poter segnalare il numero di file trovati e ritardare la lettura di file di grandi dimensioni.

Quando vuoi veramente spingere prestazioni elevate, l'I / O asincrono è la soluzione giusta. Questo non sarà necessario sui normali PC, anche un SSD non è così veloce, ma i file server di fascia alta possono sovraccaricare un singolo thread. In tali sistemi, una soluzione come Boost ASIO può scalare. Basta lanciare richieste di lettura a Boost ASIO, e restituirà i risultati un po 'di tempo dopo come entrano. Probabilmente su altri thread, se necessario. Ciò fornisce all'O / S sottostante una maggiore flessibilità per gestire le richieste di lettura.

'Se Mohammed non verrà sulla montagna, la montagna deve venire a Mohammed.'

Non puoi sempre farlo velocemente. A volte devi renderlo veloce.

Velocità della barra di avanzamento falsa. L'utente vuole sapere che sta succedendo qualcosa, l'utente vuole un feedback veloce. Ci sono alcuni studi che mostrano come rendere progressbar più fluido e veloce, ma non ricordo i documenti.

C'è uno studio su come far apparire la barra di progressione più veloce . Alcuni altri link a ulteriori ricerche su come far apparire la barra di avanzamento dei processi essere più veloce .

Non legato a una lingua specifica? Erm. La maggior parte di ciò che viene in mente è di evitare il più possibile il confronto dei file (con un corrispondente aumento di dati che si mantiene in memoria) anziché tentare di ottimizzare gli attraversamenti.

1. Mantieni una struttura dati / mappa che utilizza i conteggi di byte come chiavi e un elenco di identificatori di file come payload. Ogni volta che aggiungi un file alla struttura dei dati, se entra in un elenco e ha "vicini" della stessa dimensione del file, sai che potrebbe essere necessario confrontarlo più profondamente con i vicini.
2. Non hash interi file a meno che tu non ne abbia davvero bisogno. Invece, considera l'hashing sequenziale "blocchi" del file. Due file identici richiedono l'hash di entrambi nella loro interezza, ma due file che differiscono molto presto richiederanno meno lavoro. Se è possibile, memorizza questi chunk-hash in memoria per rendere più veloci i controlli futuri.
3. Non esagerare con i thread, tieni semplicemente separati i file I / O dall'interfaccia utente o dal thread principale. Prendi in considerazione l'utilizzo di un framework (in Java, che potrebbe essere Executor ) in modo che, se è necessario ottimizzare il numero di thread che si stanno svolgendo, è possibile.
4. Per un programma della GUI, prendere in considerazione l'idea di dire agli utenti che i controlli di duplicazione sui file hanno uno stato "in sospeso". Ciò significa che mostri immediatamente all'utente tutti i tranne controlli di duplicazione, e semplicemente riempi quelli nel tempo a disposizione.

Forse non capisco cosa stai cercando di fare con i dati ma ... Non è un problema di riduzione della mappa? Per ogni cartella, utilizzare la funzione mappa per estrarre i dati necessari (dato che è possibile distribuire il numero di directory a qualsiasi numero di thread / processi che possono eseguire la funzione di mappatura, possono essere eseguiti tutti "in parallelo" e report in, ottieni una serie di indicazioni sullo stato di avanzamento, quindi riduci il set di dati per fornire le informazioni specifiche che desideri fornire all'utente.

Inoltre, capisci dove sei in attesa di questo problema? Se si esegue questa funzione per un intero file system, potresti non essere in grado di leggere tutte le informazioni sulla directory / file dalla cache, quindi potresti essere limitato alle ore di ricerca del disco rigido per creare il tuo elenco. Se si finisce per aspettare l'unità, potrebbe non avere senso ottimizzare l'utilizzo della CPU / dello schermo.

Come regola generale

Probabilmente i thread rallenteranno l'applicazione se entrambi stanno eseguendo l'accesso simultaneo di IO alla stessa interfaccia fisica (rete o disco).

Strategie

Mappa / Riduci può essere applicato per le statistiche e altre cose che si adattano a quel modello e può essere aggiornato in modo incrementale man mano che i file vengono elaborati.

Avere un sistema basato sugli eventi consentirà un feedback in tempo reale all'utente, ma non permetterà loro di conoscere la percentuale completa dell'intero processo, solo dell'evento corrente. inotify è un buon punto di partenza se sei su Linux, altre piattaforme OS hanno API native equivalenti per fare la stessa cosa.

Memorizzare nella cache l'elenco dei file , ottenere i totali per i progressi su lavori di grandi dimensioni sarà probabilmente una buona cosa, anche se si aggiunge al tempo complessivo, l'utente saprà quanto a lungo prendere un pausa mentre il lavoro funziona.

Una soluzione ibrida di memorizzazione nella cache di alcune cose e la creazione di eventi da elaborare in una mappa riducono le modalità saranno la migliore via di mezzo che ci si può aspettare, quindi rispondendo agli eventi che accadono in tempo reale utilizzando alcune piattaforme specifiche il meccanismo di notifica sarà la soluzione migliore.

Ricorda IO è limitato dalla fisica, il threading aumenterà la contesa per le risorse fisiche già stressate.

Dalla semplice scansione della tua domanda, posso solo dare alcuni consigli molto generali.

Il multithreading aiuterà sicuramente le prestazioni, a seconda della quantità di elaborazione che stai facendo. Prova a separare i componenti I / O dai componenti di elaborazione nella progettazione del software, quindi puoi scrivere la prima versione in modo sincrono, quindi tornare indietro e modificare il software per eseguire queste operazioni in parallelo.

In secondo luogo, so che usare la ricorsione per attraversare un file system è allettante. Vedrai un miglioramento delle prestazioni se utilizzi i loop anziché la ricorsione, sebbene il livello di miglioramento dipenda dalla dimensione del tuo input.

Quello che potresti considerare è che un thread gestisce l'I / O e passa i risultati a un altro thread per l'elaborazione. In questo modo la tua CPU non è in attesa di I / O lenti con il disco.

Inoltre, se questo sistema avrà un'interfaccia utente, sicuramente vorrai, come minimo, collocare l'interfaccia utente in un thread di esecuzione separato. Ciò sicuramente aumenterà le prestazioni, in particolare considerando l'operazione potenzialmente lunga e ad alta intensità di risorse che verrà eseguita in background con tutto l'I / O e l'elaborazione dei metadati del file.

Vorrei utilizzare un thread per scorrere continuamente le directory sul file system e leggere i metadati in una struttura di dati che è thread-safe. Quindi avrei un altro thread che elabora i dati ed estrae qualsiasi informazione da esso che si desidera fornire all'utente e memorizza tali informazioni in un'altra struttura dati sicura di thread. Infine, l'interfaccia utente dovrebbe essere sul proprio thread di esecuzione e aggiornarsi ogni volta che vengono modificati i dati nella struttura dati sicura del secondo thread.

Solo una nota a margine, .NET Framework ha una classe "FileSystemWatcher" che gestirà efficacemente tutto tranne l'interfaccia utente. Se non vuoi utilizzare .NET, potresti almeno prendere in considerazione la lettura della documentazione di quella classe per darti un vantaggio. Dai un'occhiata a Mono per .NET se sei interessato alla piattaforma multipiattaforma.

Ho scritto una libreria per fare qualcosa di simile, ma è adatta solo per i filesystem che hanno molte teste di unità (come lustro o panf). Raccogliamo informazioni su centinaia di milioni di file (circa 20 PB di dati) su base regolare. Dai un'occhiata a il documento che abbiamo scritto e la libreria per distribuire il carico di lavoro e strumenti per analizzare i dati .

Se hai un filesystem più piccolo, CEA ha scritto un programma chiamato Robinhood per fare qualcosa di simile.