Algoritmo veloce multipiattaforma per leggere/scrivere file in C++

Question

Voglio porre una domanda apparentemente semplice che non riesco a trovare la risposta da nessuna parte. Esiste un algoritmo FAST per l'input e/o l'output di file che può essere compilato con tutti i compilatori C++ conformi agli standard e funziona per tutti i sistemi operativi senza il bisogno di librerie esterne?

1. Ho scoperto che il modo più veloce è quello di utilizzare i file di memoria mappata, ma non lo farò perché vogliamo che lo stesso pezzo di codice che lavora su tutte le piattaforme
2. non possiamo usare le API come Win32 API causa che lo renderà specifico della piattaforma
3. non voglio usare c, voglio che l'algoritmo sia solo codice C++ puro con stl se fattibile, non un po 'brutto con intermixato asm hack/trucco
4. quadri o esterno le librerie che non appartengono a standart C++ non devono essere utilizzate come wxWidgets, Qt, MFC ecc.
5. Il grande empasis di tutta questa domanda è che l'algoritmo è come VELOCE possibile, qualcosa sulla falsariga della velocità di farlo con i file di memoria mappata, ancora più veloce sarebbe fantastico ma so che non è possibile

Hai mai visto qualcosa di così folle essere stato studiato da qualcun altro eccetto me? È possibile un simile algoritmo?

Grazie per eventuali raccomandazioni

Answer 1

Con le seguenti restrizioni:

possono essere compilati con tutti conformi compilatori C++ standard e funziona per tutti i sistemi operativi senza la necessità di librerie esterne?

Hai praticamente da soli limitato ai file di libreria funzioni standard IO. Forse funzioni POSIX (a seconda del sottoinsieme di "tutti i compilatori C++ conformi agli standard" che stai considerando).

Se non sono abbastanza veloci per te, dovrai iniziare a ridurre alcune restrizioni.

Answer 2

Questo non ha nulla a che fare con un "algoritmo".

Quando si tratta di scrivere dati in un file, sei in balia del sistema operativo - i file mappati in memoria sono "veloci" perché stai solo scrivendo in memoria e il sistema operativo lo sincronizza nuovamente il suo tempo. Se il sistema operativo non lo supporta, sei sfortunato in questo senso, a meno che tu non voglia implementare il tuo livello di mappatura della memoria.

Per inciso, POSIX ha mmap, quindi se vi sta limitando a sistemi POSIX-compliant, che stai bene.

Answer 3

Alcuni punti:

• Questo non ha nulla a che fare con gli algoritmi.
• La ricerca di tutti i sistemi operativi non è un obiettivo molto produttivo (ed è impossibile
• il tuo codice non funziona su una piattaforma particolare finché non lo hai testato). Invece, mi concentrerei su alcuni set di sistemi operativi che sono fattibili - diciamo POSIX + Win32.
• In tal caso, è possibile eseguire il mapping della memoria, ad esempio implementando mmap() per Windows (in cima a MapViewOfFile(), ecc.) Se il codice sorgente di git ha un'implementazione mmap per Windows se si necessita di ispirazione)
• Se non è possibile utilizzare la mappatura della memoria, si consiglia di utilizzare la normale API del file C anziché i flussi di file di C++ se le prestazioni sono un grosso problema. Anche se i flussi di C++ hanno il potenziale di prestazioni più elevate per alcune operazioni, in pratica è un po 'più lento.
• Ma, per ottenere buone prestazioni, spesso può essere "abbastanza buono" solo per essere sicuro di trattare i dati in modo sano. Leggere i dati in sequenza, non rileggere, ecc. Perfetto è il nemico del bene;)

Answer 4

Gli altri poster sono corretti in quanto le prestazioni sono sempre in disaccordo con la genericità (multipiattaforma).

Tuttavia, in generale, otterrete i risultati migliori "tamponando" il vostro input - usando fread() per leggere in blocchi di dati relativamente grandi e elaborarli.

So che è una risposta piuttosto semplice e generica, ma è più specifica che si può ottenere senza essere più specifici della piattaforma, o conoscere di più sullo specifico input che si sta elaborando.

Answer 5

La lettura sequenziale in blocchi che sono multipli (o potenze di 2) della dimensione del blocco del file system può essere d'aiuto. Quindi seleziona i tuoi dati una volta che il blocco è in memoria. C'è un white paper da qualche parte dove hanno testato le prestazioni per varie dimensioni dei blocchi. Vorrei poterlo trovare di nuovo.

Si potrebbe anche provare ad avere un thread dedicato per la lettura dei blocchi dal file e un altro che esegue le manipolazioni dei dati in memoria (con le sincronizzazioni corrette, ovviamente). Questo ti consente di utilizzare la CPU per elaborare i dati mentre blocchi le tue chiamate di lettura dei file.

In ogni caso, se provi a provare queste idee, faccelo sapere se noti una differenza. I risultati effettivi dei test di benchmark sarebbero interessanti.

Answer 6

Fast IO si riduce generalmente riduce a due cose:

1. Ridurre al minimo i dati copiando
2. Minimizzare contesto kernel/user switching

La maggior parte tutte le tecniche IO tentativo di affrontare uno o l'altro. Il codice cross-platform più veloce per IO che io conosca è il sistema Perl IO. Suggerirei di dare un'occhiata a the source. Gli hacker Perl hanno trascorso decenni a ottenere il loro IO il più velocemente possibile su quante più piattaforme possibili.

Answer 7

Per mettere un altro punto di vista sulla "misericordia del sistema operativo", la maggior parte del sovraccarico nella copia dei file si trova con il sistema operativo. Un file frammentato richiederà più tempo per essere letto rispetto a un file deframmentato. Non ci sono funzioni C++ generiche o standard per il rilevamento di file frammentati.

Il metodo più veloce in C++:

std::ifstream in_file; 
std::ofstream out_file; 

out_file << in_file.rdbuf(); 

è possibile trovare ulteriori dettagli dalla ricerca sul Web con le parole chiave "copia di file rdbuf". Il suddetto frammento lascia la copia al sistema operativo, ma è portatile su tutte le piattaforme. Leggendo i flussi di i/o in C++, è possibile impostare la dimensione del buffer di lettura o utilizzare il proprio buffer.

La copia di file più veloce richiede funzionalità specifiche della piattaforma, come i trasferimenti DMA. L'utilizzo di thread e buffer multipli potrebbe velocizzarlo; ma C++ non ha supporto per i thread (esiste uno standard defacto, POSIX, che supporta i thread). Un thread verrebbe letto nei buffer mentre un altro thread scrive dai buffer.