mmap () vs. Leseblöcke

184

Ich arbeite an einem Programm, das Dateien verarbeitet, die möglicherweise 100 GB oder mehr groß sein können. Die Dateien enthalten Sätze von Datensätzen variabler Länge. Ich habe eine erste Implementierung in Betrieb genommen und versuche nun, die Leistung zu verbessern, insbesondere um E / A effizienter zu gestalten, da die Eingabedatei viele Male gescannt wird.

Gibt es eine Faustregel für die Verwendung im mmap()Vergleich zum Lesen in Blöcken über die C ++ - fstreamBibliothek? Ich möchte große Blöcke von der Festplatte in einen Puffer lesen, vollständige Datensätze aus dem Puffer verarbeiten und dann mehr lesen.

Der mmap()Code könnte möglicherweise sehr unordentlich werden, da mmapd-Blöcke an Seitengrößengrenzen liegen müssen (nach meinem Verständnis) und Datensätze möglicherweise über Seitengrenzen hinweg mögen könnten. Mit fstreams kann ich einfach den Anfang eines Datensatzes suchen und erneut mit dem Lesen beginnen, da wir uns nicht darauf beschränken, Blöcke zu lesen, die an Grenzen der Seitengröße liegen.

Wie kann ich mich zwischen diesen beiden Optionen entscheiden, ohne zuerst eine vollständige Implementierung zu schreiben? Irgendwelche Faustregeln (zB mmap()ist 2x schneller) oder einfache Tests?

jbl
quelle
1
Dies ist eine interessante Lektüre: medium.com/@sasha_f/… In den Experimenten mmap()ist es 2-6 mal schneller als mit Syscalls, z read().
mplattner

Antworten:

208

Ich habe versucht, das letzte Wort zur mmap / read-Leistung unter Linux zu finden, und bin auf einen netten Beitrag ( Link ) auf der Linux-Kernel-Mailingliste gestoßen. Es ist aus dem Jahr 2000, daher wurden seitdem viele Verbesserungen an E / A und virtuellem Speicher im Kernel vorgenommen, aber es erklärt gut den Grund, warum mmapoder readmöglicherweise schneller oder langsamer.

  • Ein Aufruf von mmaphat mehr Overhead als read(genau wie epollmehr Overhead als poll, was mehr Overhead hat als read). Das Ändern von Zuordnungen virtueller Speicher ist auf einigen Prozessoren aus den gleichen Gründen ziemlich teuer, aus denen das Umschalten zwischen verschiedenen Prozessen teuer ist.
  • Das E / A-System kann den Festplatten-Cache bereits verwenden. Wenn Sie also eine Datei lesen, gelangen Sie in den Cache oder verpassen ihn, unabhängig davon, welche Methode Sie verwenden.

Jedoch,

  • Speicherzuordnungen sind für den Direktzugriff im Allgemeinen schneller, insbesondere wenn Ihre Zugriffsmuster spärlich und unvorhersehbar sind.
  • Speicherkarten können Sie halten aus dem Cache mit Seiten , bis Sie fertig sind. Dies bedeutet, dass die Seiten weiterhin zwischengespeichert werden, wenn Sie eine Datei über einen längeren Zeitraum häufig verwenden, sie schließen und erneut öffnen. Mit readwurde Ihre Datei möglicherweise vor langer Zeit aus dem Cache gelöscht. Dies gilt nicht, wenn Sie eine Datei verwenden und diese sofort verwerfen. (Wenn Sie versuchen, mlockSeiten nur zu speichern, um sie im Cache zu halten, versuchen Sie, den Festplatten-Cache zu überlisten, und diese Art von Dummheit trägt selten zur Systemleistung bei.)
  • Das direkte Lesen einer Datei ist sehr einfach und schnell.

Die Diskussion über mmap / read erinnert mich an zwei andere Performance-Diskussionen:

  • Einige Java-Programmierer waren schockiert, als sie feststellten, dass nicht blockierende E / A häufig langsamer sind als blockierende E / A. Dies ist absolut sinnvoll, wenn Sie wissen, dass für nicht blockierende E / A mehr Systemaufrufe erforderlich sind.

  • Einige andere Netzwerkprogrammierer waren schockiert, epollals pollsie erfuhren, dass dies oft langsamer ist als epoll. Dies ist durchaus sinnvoll, wenn Sie wissen, dass für die Verwaltung mehr Systemaufrufe erforderlich sind.

Fazit: Verwenden Sie Speicherzuordnungen, wenn Sie zufällig auf Daten zugreifen, diese lange aufbewahren oder wenn Sie wissen, dass Sie sie für andere Prozesse freigeben können ( MAP_SHAREDnicht sehr interessant, wenn keine tatsächliche Freigabe erfolgt). Lesen Sie Dateien normal, wenn Sie nacheinander auf Daten zugreifen, oder verwerfen Sie sie nach dem Lesen. Und wenn entweder Methode macht Ihr Programm weniger komplex, tun , dass . In vielen Fällen der realen Welt gibt es keinen sicheren Weg, um zu zeigen, dass einer schneller ist, ohne Ihre tatsächliche Anwendung und NICHT einen Benchmark zu testen.

(Es tut mir leid, dass ich diese Frage beantwortet habe, aber ich habe nach einer Antwort gesucht und diese Frage tauchte immer wieder ganz oben in den Google-Ergebnissen auf.)

Dietrich Epp
quelle
Denken Sie daran, dass es ein sehr verdächtiger Ansatz wäre, Ratschläge zu verwenden, die auf Hardware und Software aus den 2000er Jahren basieren, ohne sie heute zu testen. Auch wenn viele der Fakten zu mmapvs read()in diesem Thread wie in der Vergangenheit zutreffen, kann die Gesamtleistung nicht wirklich durch Addition der Vor- und Nachteile bestimmt werden, sondern nur durch Testen einer bestimmten Hardwarekonfiguration. Beispielsweise ist fraglich, ob "Ein Aufruf von mmap hat mehr Overhead als das Lesen" - yes mmapmuss der Prozessseitentabelle Zuordnungen hinzufügen, aber readalle gelesenen Bytes vom Kernel in den Benutzerbereich kopieren.
BeeOnRope
Das Ergebnis ist, dass auf meiner (modernen Intel, circa 2018) Hardware mmapder Overhead geringer ist als readbei Lesevorgängen mit einer Größe von mehr als einer Seite (4 KiB). Nun ist es sehr richtig, dass, wenn Sie sparsam und zufällig auf Daten zugreifen möchten, dies mmapwirklich sehr, sehr gut ist - aber das Gegenteil ist nicht unbedingt der Fall: mmapMöglicherweise ist es auch für den sequentiellen Zugriff das Beste.
BeeOnRope
1
@BeeOnRope: Sie sind vielleicht skeptisch gegenüber Ratschlägen, die auf Hardware und Software aus den 2000er Jahren basieren, aber ich bin noch skeptischer gegenüber Benchmarks, die keine Methodik und Daten liefern. Wenn Sie einen Fall mmaperstellen möchten , der schneller ist, würde ich erwarten, dass mindestens das gesamte Testgerät (Quellcode) mit den tabellarischen Ergebnissen und der Prozessormodellnummer angezeigt wird.
Dietrich Epp
@BeeOnRope: Denken Sie auch daran, dass Mikrobenchmarks beim Testen von Bits des Speichersystems wie diesem äußerst irreführend sein können, da ein TLB-Flush die Leistung des restlichen Programms negativ beeinflussen kann und diese Auswirkungen nicht auftreten, wenn Sie messen nur die mmap selbst.
Dietrich Epp
2
@DietrichEpp - ja, ich werde mich mit TLB-Effekten auskennen. Beachten Sie, dass mmapder TLB nur unter ungewöhnlichen Umständen (aber munmapmöglicherweise) geleert wird . Meine Tests umfassten sowohl Mikrobenchmarks (einschließlich munmap) als auch "in Anwendung", die in einem realen Anwendungsfall ausgeführt wurden. Natürlich ist meine Bewerbung nicht mit Ihrer Bewerbung identisch, daher sollten die Teilnehmer vor Ort testen. Es ist nicht einmal klar, dass mmapein Mikro-Benchmark dies bevorzugt: Er read()erhält auch einen großen Schub, da der benutzerseitige Zielpuffer im Allgemeinen in L1 bleibt, was in einer größeren Anwendung möglicherweise nicht der Fall ist. Also ja, "es ist kompliziert".
BeeOnRope
47

Die Hauptkosten für die Leistung werden Festplatten-E / A sein. "mmap ()" ist sicherlich schneller als istream, aber der Unterschied ist möglicherweise nicht erkennbar, da die Festplatten-E / A Ihre Laufzeiten dominieren.

Ich habe versucht, das Codefragment von Ben Collins (siehe oben / unten) auf seine Behauptung zu testen, dass "mmap () viel schneller ist" und keinen messbaren Unterschied festgestellt. Siehe meine Kommentare zu seiner Antwort.

Ich würde sicherlich nicht empfehlen, jeden Datensatz einzeln einzeln zuzuordnen, es sei denn, Ihre "Datensätze" sind riesig - das wäre schrecklich langsam, würde 2 Systemaufrufe für jeden Datensatz erfordern und möglicherweise die Seite aus dem Festplattenspeicher-Cache verlieren ... .

In Ihrem Fall denke ich, dass mmap (), istream und die Aufrufe open () / read () auf niedriger Ebene ungefähr gleich sind. Ich würde mmap () in folgenden Fällen empfehlen:

  1. Es gibt einen wahlfreien Zugriff (nicht sequentiell) innerhalb der Datei UND
  2. Das Ganze passt bequem in den Speicher ODER es gibt eine Referenzlokalität in der Datei, so dass bestimmte Seiten zugeordnet und andere Seiten zugeordnet werden können. Auf diese Weise nutzt das Betriebssystem den verfügbaren RAM optimal.
  3. ODER wenn mehrere Prozesse dieselbe Datei lesen / bearbeiten, ist mmap () fantastisch, da alle Prozesse dieselben physischen Seiten verwenden.

(Übrigens - ich liebe mmap () / MapViewOfFile ()).

Tim Cooper
quelle
Guter Punkt zum wahlfreien Zugriff: Dies könnte eines der Dinge sein, die meine Wahrnehmung beeinflussen.
Ben Collins
1
Ich würde nicht sagen, dass die Datei bequem in den Speicher passen muss, nur in den Adressraum. Auf 64-Bit-Systemen sollte es also keinen Grund geben, keine großen Dateien zuzuordnen. Das Betriebssystem weiß, wie man damit umgeht. Es ist dieselbe Logik, die für das Auslagern verwendet wird, aber in diesem Fall ist kein zusätzlicher Auslagerungsspeicherplatz auf der Festplatte erforderlich.
MvG
@MvG: Verstehst du den Punkt über Disk I / O? Wenn die Datei in den Adressraum, aber nicht in den Speicher passt und Sie wahlfreien Zugriff haben, können Sie auf jeden Datensatzzugriff zugreifen, der ein Verschieben und Suchen des Plattenkopfs oder eine SSD-Seitenoperation erfordert, was eine Leistungskatastrophe darstellen würde.
Tim Cooper
3
Der Festplatten-E / A-Aspekt sollte unabhängig von der Zugriffsmethode sein. Wenn Sie wirklich zufälligen Zugriff auf Dateien haben, die größer als RAM sind, sind sowohl mmap als auch seek + read stark an die Festplatte gebunden. Andernfalls profitieren beide von den Caches. Ich sehe die Dateigröße im Vergleich zur Speichergröße nicht als starkes Argument in beide Richtungen. Die Dateigröße im Vergleich zum Adressraum ist dagegen ein sehr starkes Argument, insbesondere für einen wirklich wahlfreien Zugriff.
MvG
Meine ursprüngliche Antwort hatte und hat diesen Punkt: "Das Ganze passt bequem in den Speicher ODER es gibt eine Referenzlokalität in der Datei". Der zweite Punkt befasst sich also mit dem, was Sie sagen.
Tim Cooper
43

mmap ist viel schneller. Sie könnten einen einfachen Benchmark schreiben, um sich selbst zu beweisen:

char data[0x1000];
std::ifstream in("file.bin");

while (in)
{
  in.read(data, 0x1000);
  // do something with data
}

gegen:

const int file_size=something;
const int page_size=0x1000;
int off=0;
void *data;

int fd = open("filename.bin", O_RDONLY);

while (off < file_size)
{
  data = mmap(NULL, page_size, PROT_READ, 0, fd, off);
  // do stuff with data
  munmap(data, page_size);
  off += page_size;
}

Natürlich lasse ich Details aus (wie Sie beispielsweise feststellen können, wann Sie das Ende der Datei erreichen, falls Ihre Datei kein Vielfaches von page_sizeist), aber es sollte wirklich nicht viel komplizierter sein .

Wenn Sie können, können Sie versuchen, Ihre Daten in mehrere Dateien aufzuteilen, die mmap () - statt teilweise (viel einfacher) mmap () - bearbeitet werden können.

Vor ein paar Monaten hatte ich eine halbherzige Implementierung einer mmap () - Ed-Stream-Klasse für Boost-Fenster für boost_iostreams, aber niemand kümmerte sich darum und ich beschäftigte mich mit anderen Dingen. Leider habe ich vor einigen Wochen ein Archiv alter unvollendeter Projekte gelöscht, und das war eines der Opfer :-(

Update : Ich sollte auch den Vorbehalt hinzufügen, dass dieser Benchmark in Windows ganz anders aussehen würde, da Microsoft einen raffinierten Datei-Cache implementiert hat, der das meiste tut, was Sie mit mmap überhaupt tun würden. Das heißt, für Dateien, auf die häufig zugegriffen wird, können Sie einfach std :: ifstream.read () ausführen, und es wäre so schnell wie mmap, da der Dateicache bereits eine Speicherzuordnung für Sie durchgeführt hätte und transparent ist.

Letztes Update : Schauen Sie, Leute: In vielen verschiedenen Plattformkombinationen von Betriebssystem- und Standardbibliotheken sowie Festplatten und Speicherhierarchien kann ich nicht mit Sicherheit sagen, dass der Systemaufruf mmap, der als Black Box angesehen wird, immer immer wesentlich schneller sein wird als read. Das war nicht genau meine Absicht, auch wenn meine Worte so ausgelegt werden könnten. Letztendlich war mein Punkt, dass speicherabgebildete E / A im Allgemeinen schneller sind als bytebasierte E / A. das ist immer noch wahr . Wenn Sie experimentell feststellen, dass es keinen Unterschied zwischen den beiden gibt, ist die einzige Erklärung, die mir vernünftig erscheint, dass Ihre Plattform die Speicherzuordnung unter der Decke auf eine Weise implementiert, die für die Leistung von Aufrufen von vorteilhaft istread. Die einzige Möglichkeit, absolut sicher zu sein, dass Sie speicherabgebildete E / A auf tragbare Weise verwenden, ist die Verwendung mmap. Wenn Sie sich nicht für Portabilität interessieren und sich auf die besonderen Merkmale Ihrer Zielplattformen verlassen können, ist die Verwendung readmöglicherweise geeignet, ohne die Leistung messbar zu beeinträchtigen.

Bearbeiten, um die Antwortliste zu bereinigen: @jbl:

Die Schiebefenster-mmap klingt interessant. Können Sie etwas mehr dazu sagen?

Sicher - Ich habe eine C ++ - Bibliothek für Git geschrieben (ein libgit ++, wenn Sie so wollen) und bin auf ein ähnliches Problem gestoßen: Ich musste in der Lage sein, große (sehr große) Dateien zu öffnen und keine Leistung zu haben, um ein totaler Hund zu sein (wie es wäre mit std::fstream).

Boost::Iostreamshat bereits eine mapped_file-Quelle, aber das Problem war, dass mmapganze Dateien gepingt wurden, was Sie auf 2 ^ (Wortgröße) beschränkt. Auf 32-Bit-Computern sind 4 GB nicht groß genug. Es ist nicht unangemessen zu erwarten, dass .packDateien in Git viel größer werden, daher musste ich die Datei in Blöcken lesen, ohne auf reguläre Datei-E / A zurückgreifen zu müssen. Unter dem Deckmantel von habe Boost::Iostreamsich eine Quelle implementiert, die mehr oder weniger eine andere Sicht auf die Interaktion zwischen std::streambufund ist std::istream. Sie können auch einen ähnlichen Ansatz ausprobieren, indem Sie einfach std::filebufin a erben mapped_filebufund in ähnlicher Weise std::fstreamin a mapped_fstream. Es ist die Interaktion zwischen den beiden, die schwer zu finden ist. Boost::Iostreams hat einen Teil der Arbeit für Sie erledigt und bietet auch Haken für Filter und Ketten, daher dachte ich, es wäre nützlicher, es auf diese Weise zu implementieren.

Ben Collins
quelle
3
RE: mmaped-Dateicache unter Windows. Genau: Wenn die Dateipufferung aktiviert ist, ordnet der Kernelspeicher die Datei, die Sie intern lesen, zu, liest in diesen Puffer und kopiert sie zurück in Ihren Prozess. Es ist, als ob Sie den Speicher selbst zugeordnet hätten, außer mit einem zusätzlichen Kopierschritt.
Chris Smith
6
Ich bin nicht bereit, einer akzeptierten Antwort zu widersprechen, aber ich glaube, diese Antwort ist falsch. Ich folgte Ihrem Vorschlag und versuchte Ihren Code auf einem 64-Bit-Linux-Computer, und mmap () war nicht schneller als die STL-Implementierung. Theoretisch würde ich auch nicht erwarten, dass 'mmap ()' schneller (oder langsamer) ist.
Tim Cooper
3
@ Tim Cooper: Möglicherweise finden Sie diesen Thread ( markmail.org/message/… ) von Interesse. Beachten Sie die beiden Dinge: mmap ist unter Linux nicht richtig optimiert, und man muss auch madvise in seinem Test verwenden, um die besten Ergebnisse zu erzielen.
Ben Collins
9
Lieber Ben, ich habe diesen Link gelesen. Wenn 'mmap ()' unter Linux nicht schneller ist und MapViewOfFile () unter Windows nicht schneller ist, können Sie dann behaupten, dass "mmap viel schneller ist"? Aus theoretischen Gründen glaube ich, dass mmap () für sequentielle Lesevorgänge nicht schneller ist - haben Sie eine gegenteilige Erklärung?
Tim Cooper
11
Ben, warum sollte man sich die Mühe machen, mmap()eine Seite nach der anderen zu archivieren? Wenn a size_tgroß genug ist, um die Größe der Datei zu speichern (sehr wahrscheinlich auf 64-Bit-Systemen), dann nur mmap()die gesamte Datei in einem Aufruf.
Steve Emmerson
39

Hier gibt es bereits viele gute Antworten, die viele der wichtigsten Punkte abdecken. Daher möchte ich nur einige Punkte hinzufügen, die ich nicht direkt oben angesprochen habe. Das heißt, diese Antwort sollte nicht als umfassend für die Vor- und Nachteile angesehen werden, sondern als Ergänzung zu anderen Antworten hier.

mmap scheint magisch

Wenn Sie den Fall, in dem die Datei bereits vollständig zwischengespeichert ist 1 als Basis 2 haben , mmapals magisch erscheinen :

  1. mmap Es ist nur ein Systemaufruf erforderlich, um (möglicherweise) die gesamte Datei zuzuordnen. Danach sind keine weiteren Systemaufrufe erforderlich.
  2. mmap erfordert keine Kopie der Dateidaten vom Kernel in den User-Space.
  3. mmapErmöglicht den Zugriff auf die Datei "als Speicher", einschließlich der Verarbeitung mit allen erweiterten Tricks, die Sie gegen den Speicher ausführen können, z. B. automatische Vektorisierung des Compilers, SIMD- Intrinsics, Prefetching, optimierte In-Memory-Parsing-Routinen, OpenMP usw.

Für den Fall, dass sich die Datei bereits im Cache befindet, scheint es unmöglich zu sein: Sie greifen einfach direkt auf den Kernel-Seiten-Cache als Speicher zu und es kann nicht schneller werden.

Nun, das kann es.

mmap ist eigentlich keine Magie, weil ...

mmap arbeitet immer noch pro Seite

Ein primärer versteckter Preis von mmapvs read(2)(was eigentlich der vergleichbare Systemaufruf auf Betriebssystemebene zum Lesen von Blöcken ist ) besteht darin, dass mmapSie für jede 4K-Seite im Benutzerbereich "etwas Arbeit" erledigen müssen, auch wenn sie möglicherweise von der Seitenfehlermechanismus.

Zum Beispiel muss eine typische Implementierung, die nur mmapdie gesamte Datei enthält, einen Fehler verursachen, sodass 100 GB / 4K = 25 Millionen Fehler zum Lesen einer 100-GB-Datei vorliegen. Nun, dies werden kleinere Fehler sein , aber 25 Milliarden Seitenfehler werden immer noch nicht superschnell sein. Die Kosten für einen kleinen Fehler liegen wahrscheinlich im besten Fall bei 100 Nanos.

mmap hängt stark von der TLB-Leistung ab

Jetzt können Sie an übergeben MAP_POPULATE, mmapum anzuweisen, dass alle Seitentabellen eingerichtet werden sollen, bevor Sie zurückkehren, damit beim Zugriff keine Seitenfehler auftreten. Dies hat das kleine Problem, dass es auch die gesamte Datei in den Arbeitsspeicher liest, was explodieren wird, wenn Sie versuchen, eine 100-GB-Datei zuzuordnen - aber lassen Sie uns dies vorerst ignorieren 3 . Der Kernel muss pro Seite arbeiten , um diese Seitentabellen einzurichten (wird als Kernelzeit angezeigt). Dies ist ein erheblicher Kostenfaktor für den mmapAnsatz und proportional zur Dateigröße (dh er wird mit zunehmender Dateigröße nicht weniger wichtig) 4 .

Selbst im Benutzerbereich ist der Zugriff auf eine solche Zuordnung nicht gerade kostenlos (im Vergleich zu großen Speicherpuffern, die nicht aus einer dateibasierten Zuordnung stammen mmap). Selbst wenn die Seitentabellen eingerichtet sind, wird jeder Zugriff auf eine neue Seite ausgeführt. konzeptionell entsteht ein TLB-Fehler. Da das mmapErstellen einer Datei die Verwendung des Seitencaches und seiner 4K-Seiten bedeutet, fallen für eine 100-GB-Datei erneut 25 Millionen Mal Kosten an.

Nun hängen die tatsächlichen Kosten dieser TLB-Fehler stark von mindestens den folgenden Aspekten Ihrer Hardware ab: (a) wie viele 4K-TLB-Enties Sie haben und wie der Rest des Übersetzungs-Caching funktioniert (b) wie gut Hardware-Prefetch funktioniert mit dem TLB - kann zB Prefetch einen Seitenlauf auslösen? (c) wie schnell und wie parallel die Page-Walking-Hardware ist. Auf modernen High-End-x86-Intel-Prozessoren ist die Page-Walk-Hardware im Allgemeinen sehr stark: Es gibt mindestens zwei parallele Page-Walker, ein Page-Walk kann gleichzeitig mit der fortgesetzten Ausführung erfolgen, und Hardware-Prefetching kann einen Page-Walk auslösen. Daher ist die Auswirkung des TLB auf eine Streaming- Leselast relativ gering - und eine solche Last wird unabhängig von der Seitengröße häufig ähnlich ausgeführt. Andere Hardware ist jedoch normalerweise viel schlechter!

read () vermeidet diese Fallstricke

Der read()Syscall, der im Allgemeinen den "Block Read" -Aufrufen zugrunde liegt, die z. B. in C, C ++ und anderen Sprachen angeboten werden, hat einen Hauptnachteil, den jeder kennt:

  • Jeder read()Aufruf von N Bytes muss N Bytes vom Kernel in den Benutzerbereich kopieren.

Auf der anderen Seite werden die meisten der oben genannten Kosten vermieden - Sie müssen nicht 25 Millionen 4K-Seiten in den Benutzerbereich abbilden. Normalerweise können Sie malloceinen einzelnen Puffer, einen kleinen Puffer im Benutzerbereich, verwenden und diesen wiederholt für alle Ihre readAnrufe wiederverwenden . Auf der Kernelseite gibt es fast kein Problem mit 4K-Seiten oder TLB-Fehlern, da der gesamte RAM normalerweise linear mit einigen sehr großen Seiten (z. B. 1 GB Seiten auf x86) zugeordnet wird, sodass die zugrunde liegenden Seiten im Seitencache abgedeckt sind sehr effizient im Kernelraum.

Grundsätzlich haben Sie also den folgenden Vergleich, um festzustellen, welche für einen einzelnen Lesevorgang einer großen Datei schneller ist:

Ist die zusätzliche Arbeit pro Seite, die durch den mmapAnsatz impliziert wird, teurer als die Arbeit pro Byte beim Kopieren von Dateiinhalten vom Kernel in den Benutzerbereich, die durch die Verwendung impliziert wird read()?

Auf vielen Systemen sind sie tatsächlich ungefähr ausgeglichen. Beachten Sie, dass jeder mit völlig unterschiedlichen Attributen der Hardware und des Betriebssystemstapels skaliert.

Insbesondere wird der mmapAnsatz relativ schneller, wenn:

  • Das Betriebssystem verfügt über eine schnelle Behandlung kleinerer Fehler und insbesondere über Bulk-Optimierungen kleiner Fehler wie Fehlerumgehung.
  • Das Betriebssystem verfügt über eine gute MAP_POPULATEImplementierung, mit der große Karten effizient verarbeitet werden können, wenn beispielsweise die zugrunde liegenden Seiten im physischen Speicher zusammenhängend sind.
  • Die Hardware bietet eine starke Leistung bei der Seitenübersetzung, z. B. große TLBs, schnelle TLBs der zweiten Ebene, schnelle und parallele Page-Walker, eine gute Prefetch-Interaktion mit der Übersetzung usw.

... während der read()Ansatz relativ schneller wird, wenn:

  • Der read()Syscall hat eine gute Kopierleistung. ZB gute copy_to_userLeistung auf der Kernelseite.
  • Der Kernel verfügt über eine effiziente (im Verhältnis zum Benutzerland) Möglichkeit, Speicher zuzuordnen, z. B. indem nur wenige große Seiten mit Hardwareunterstützung verwendet werden.
  • Der Kernel verfügt über schnelle Systemaufrufe und eine Möglichkeit, Kernel-TLB-Einträge über Systemaufrufe hinweg zu speichern.

Die Hardware - Faktoren , die oben variieren wild über verschiedene Plattformen hinweg, sogar innerhalb der gleichen Familie (zB innerhalb x86 Generationen und vor allem Marktsegmente) und auf jeden Fall über Architekturen (zB ARM vs x86 vs PPC).

Auch die OS-Faktoren ändern sich ständig, wobei verschiedene Verbesserungen auf beiden Seiten bei dem einen oder anderen Ansatz zu einem starken Anstieg der Relativgeschwindigkeit führen. Eine aktuelle Liste enthält:

  • Hinzufügen der oben beschriebenen Fehlerbehebung, die den mmapFall ohne wirklich hilft MAP_POPULATE.
  • Hinzufügen von Fast-Path- copy_to_userMethoden arch/x86/lib/copy_user_64.S, z. B. REP MOVQwenn es schnell ist, was dem read()Fall wirklich hilft .

Update nach Spectre und Meltdown

Die Abschwächung der Schwachstellen Spectre und Meltdown erhöhte die Kosten eines Systemaufrufs erheblich. Auf den Systemen, die ich gemessen habe, gingen die Kosten für einen Systemaufruf "nichts tun" (der eine Schätzung des reinen Overheads des Systemaufrufs darstellt, abgesehen von der tatsächlichen Arbeit, die durch den Aufruf ausgeführt wurde) von ungefähr 100 ns auf einen typischen Wert modernes Linux-System bis ca. 700 ns. Abhängig von Ihrem System kann der speziell für Meltdown festgelegte Seitentabellen-Isolations- Fix neben den direkten Systemaufrufkosten zusätzliche Downstream-Effekte haben, da TLB-Einträge neu geladen werden müssen.

All dies ist ein relativer Nachteil für read()basierte Methoden im Vergleich zu mmapbasierten Methoden, da read()Methoden für jede Datenmenge mit "Puffergröße" einen Systemaufruf ausführen müssen. Sie können die Puffergröße nicht willkürlich erhöhen, um diese Kosten zu amortisieren, da die Verwendung großer Puffer normalerweise schlechter abschneidet, da Sie die L1-Größe überschreiten und daher ständig unter Cache-Fehlern leiden.

Auf der anderen Seite können Sie mit mmapeine große Speicherregion mit MAP_POPULATEund nur effizientem Zugriff auf Kosten eines einzigen Systemaufrufs abbilden.


1 Dies schließt mehr oder weniger auch den Fall ein, in dem die Datei zunächst nicht vollständig zwischengespeichert war, das Vorauslesen des Betriebssystems jedoch gut genug ist, um es so erscheinen zu lassen (dh die Seite wird normalerweise zu dem Zeitpunkt zwischengespeichert, zu dem Sie sich befinden will es). Dies ist jedoch ein subtiles Problem, da die Art und Weise, wie das Vorauslesen funktioniert, zwischen mmapund readAnrufen häufig sehr unterschiedlich ist und durch "Beratung" -Anrufe weiter angepasst werden kann, wie in 2 beschrieben .

2 ... denn wenn die Datei nicht zwischengespeichert wird, wird Ihr Verhalten vollständig von E / A-Bedenken dominiert, einschließlich der Sympathie Ihres Zugriffsmusters für die zugrunde liegende Hardware - und Sie sollten sich alle Mühe geben, um sicherzustellen, dass ein solcher Zugriff so sympathisch ist wie möglich, z. B. durch Verwendung von madviseoder fadviseAufrufe (und welche Änderungen auf Anwendungsebene Sie vornehmen können, um die Zugriffsmuster zu verbessern).

3 Sie können dies umgehen, indem Sie beispielsweise mmapFenster kleinerer Größe, z. B. 100 MB , nacheinander eingeben.

4 Tatsächlich stellt sich heraus, dass der MAP_POPULATEAnsatz (mindestens eine Kombination aus Hardware und Betriebssystem) nur geringfügig schneller ist als die Nichtverwendung , wahrscheinlich weil der Kernel eine Fehlerbehebung verwendet. Daher wird die tatsächliche Anzahl kleinerer Fehler um den Faktor 16 reduziert oder so.

BeeOnRope
quelle
4
Vielen Dank, dass Sie eine differenziertere Antwort auf dieses komplexe Problem gegeben haben. Den meisten Menschen scheint es offensichtlich, dass mmap schneller ist, obwohl dies in der Realität oft nicht der Fall ist. In meinen Experimenten stellte sich heraus, dass der zufällige Zugriff auf eine große 100-GB-Datenbank mit einem In-Memory-Index mit pread () schneller war, obwohl ich für jeden der Millionen Zugriffe einen Puffer mallocierte. Und es scheint, als hätten viele Leute in der Branche dasselbe beobachtet .
Caetano Sauer
5
Ja, das hängt sehr vom Szenario ab. Wenn Ihre Lesevorgänge klein genug sind und Sie im Laufe der Zeit dazu neigen, wiederholt dieselben Bytes zu lesen, mmaphat dies einen unüberwindlichen Vorteil, da der feste Kernelaufruf-Overhead vermieden wird. Auf der anderen Seite mmaperhöht sich auch der TLB-Druck und wird tatsächlich langsamer für die "Aufwärm" -Phase, in der Bytes im aktuellen Prozess zum ersten Mal gelesen werden (obwohl sie sich noch auf der Seitenseite befinden), da dies möglicherweise der Fall ist mehr Arbeit als readzum Beispiel, um benachbarte Seiten "zu umgehen" ... und für die gleichen Anwendungen ist "Aufwärmen" alles, was zählt! @ CaetanoSauer
BeeOnRope
Ich denke, wo Sie sagen "... aber 25 Milliarden Seitenfehler werden immer noch nicht superschnell sein ..." sollte lauten: "... aber 25 Millionen Seitenfehler werden immer noch nicht superschnell sein ..." . Ich bin nicht 100% positiv, deshalb bearbeite ich nicht direkt.
Ton van den Heuvel
7

Es tut mir leid, dass Ben Collins seinen MMAP-Quellcode für Schiebefenster verloren hat. Das wäre schön in Boost zu haben.

Ja, das Zuordnen der Datei ist viel schneller. Sie verwenden im Wesentlichen das virtuelle Speichersubsystem des Betriebssystems, um Speicher der Festplatte zuzuordnen und umgekehrt. Stellen Sie sich das so vor: Wenn die Entwickler des Betriebssystemkerns es schneller machen könnten, würden sie es tun. Denn dadurch wird fast alles schneller: Datenbanken, Startzeiten, Ladezeiten von Programmen usw.

Der Schiebefenster-Ansatz ist wirklich nicht so schwierig, da mehrere zusammenhängende Seiten gleichzeitig zugeordnet werden können. Die Größe des Datensatzes spielt also keine Rolle, solange der größte eines einzelnen Datensatzes in den Speicher passt. Das Wichtigste ist die Verwaltung der Buchhaltung.

Wenn ein Datensatz nicht an einer getpagesize () - Grenze beginnt, muss Ihre Zuordnung auf der vorherigen Seite beginnen. Die Länge des zugeordneten Bereichs erstreckt sich vom ersten Byte des Datensatzes (bei Bedarf auf das nächste Vielfache von getpagesize () abgerundet) bis zum letzten Byte des Datensatzes (auf das nächste Vielfache von getpagesize () aufgerundet). Wenn Sie mit der Verarbeitung eines Datensatzes fertig sind, können Sie die Zuordnung aufheben () und mit dem nächsten fortfahren.

Dies alles funktioniert auch unter Windows mit CreateFileMapping () und MapViewOfFile () (und GetSystemInfo (), um SYSTEM_INFO.dwAllocationGranularity --- nicht SYSTEM_INFO.dwPageSize) zu erhalten.

mlbrock
quelle
Ich habe nur gegoogelt und diesen kleinen Ausschnitt über dwAllocationGranularity gefunden - ich habe dwPageSize verwendet und alles war kaputt. Vielen Dank!
Wickedchicken
4

mmap sollte schneller sein, aber ich weiß nicht wie viel. Es hängt sehr stark von Ihrem Code ab. Wenn Sie mmap verwenden, ist es am besten, die gesamte Datei auf einmal zuzuordnen, was Ihnen das Leben erheblich erleichtert. Ein mögliches Problem besteht darin, dass Sie eine 64-Bit-Architektur benötigen, wenn Ihre Datei größer als 4 GB ist (oder in der Praxis das Limit niedriger ist, häufig 2 GB). Wenn Sie also eine 32-Umgebung verwenden, möchten Sie sie wahrscheinlich nicht verwenden.

Allerdings gibt es möglicherweise einen besseren Weg, um die Leistung zu verbessern. Sie sagten, dass die Eingabedatei viele Male gescannt wird. Wenn Sie sie in einem Durchgang auslesen und dann fertig sind, könnte dies möglicherweise viel schneller sein.

Leon Timmermans
quelle
3

Vielleicht sollten Sie die Dateien vorverarbeiten, damit sich jeder Datensatz in einer separaten Datei befindet (oder zumindest, dass jede Datei eine mmap-fähige Größe hat).

Können Sie auch alle Verarbeitungsschritte für jeden Datensatz ausführen, bevor Sie mit dem nächsten fortfahren? Vielleicht würde das einen Teil des E / A-Overheads vermeiden?

Douglas Leeder
quelle
3

Ich bin damit einverstanden, dass mmap'd file I / O schneller sein wird, aber sollte das Zählerbeispiel nicht etwas optimiert werden, während Sie den Code vergleichen ?

Ben Collins schrieb:

char data[0x1000];
std::ifstream in("file.bin");

while (in)
{
    in.read(data, 0x1000);
    // do something with data 
}

Ich würde vorschlagen, auch zu versuchen:

char data[0x1000];
std::ifstream iifle( "file.bin");
std::istream  in( ifile.rdbuf() );

while( in )
{
    in.read( data, 0x1000);
    // do something with data
}

Darüber hinaus können Sie auch versuchen, die Puffergröße auf die Größe einer Seite des virtuellen Speichers zu bringen, falls 0x1000 nicht die Größe einer Seite des virtuellen Speichers auf Ihrem Computer ist ... IMHO mmap'd file I / O noch gewinnt, aber das sollte die Dinge näher bringen.

paxos1977
quelle
2

Meiner Meinung nach entlastet die Verwendung von mmap () den Entwickler "nur" davon, seinen eigenen Caching-Code schreiben zu müssen. In einem einfachen Fall "Datei einmal genau durchlesen" wird dies nicht schwierig sein (obwohl, wie mlbrock hervorhebt, Sie die Speicherkopie immer noch im Prozessspeicher speichern), aber wenn Sie in der Datei oder hin und her gehen Ich glaube, die Kernel-Entwickler haben das Caching wahrscheinlich besser implementiert als ich ...

Mike
quelle
1
Höchstwahrscheinlich können Sie Ihre anwendungsspezifischen Daten besser zwischenspeichern als der Kernel, der sehr blind mit Seitenblöcken arbeitet (z. B. verwendet er nur ein einfaches Pseudo-LRU-Schema, um zu entscheiden, welche Seiten entfernt werden sollen ) - während Sie möglicherweise viel über die richtige Caching-Granularität wissen und auch eine gute Vorstellung von zukünftigen Zugriffsmustern haben. Der eigentliche Vorteil des mmapCaching besteht darin, dass Sie den vorhandenen Seitencache, der bereits vorhanden sein wird, einfach wiederverwenden , sodass Sie diesen Speicher kostenlos erhalten und er auch prozessübergreifend gemeinsam nutzen kann.
BeeOnRope
2

Ich erinnere mich, wie ich vor Jahren eine riesige Datei mit einer Baumstruktur in den Speicher abgebildet habe. Ich war erstaunt über die Geschwindigkeit im Vergleich zur normalen De-Serialisierung, die viel Arbeit im Speicher erfordert, wie das Zuweisen von Baumknoten und das Setzen von Zeigern. Tatsächlich habe ich einen einzelnen Aufruf von mmap (oder seinem Gegenstück unter Windows) mit vielen (VIELEN) Aufrufen von Operator-Neu- und Konstruktoraufrufen verglichen. Für solche Aufgaben ist mmap im Vergleich zur De-Serialisierung unschlagbar. Natürlich sollte man sich dafür die Boosts des verschiebbaren Zeigers ansehen.


quelle
Das klingt eher nach einem Rezept für eine Katastrophe. Was machen Sie, wenn sich das Objektlayout ändert? Wenn Sie virtuelle Funktionen haben, sind wahrscheinlich alle vftbl-Zeiger falsch. Wie steuern Sie, wo die Datei zugeordnet ist? Sie können ihm eine Adresse geben, aber es ist nur ein Hinweis und der Kernel kann eine andere Basisadresse wählen.
Jens
Dies funktioniert perfekt, wenn Sie ein stabiles und klar definiertes Baumlayout haben. Anschließend können Sie alles in Ihre relevanten Strukturen umwandeln und den internen Dateizeigern folgen, indem Sie jedes Mal einen Versatz von "mmap start address" hinzufügen. Dies ist sehr ähnlich zu Dateisystemen mit Inodes und Verzeichnisbäumen
Mike76
1

Dies klingt nach einem guten Anwendungsfall für Multithreading ... Ich würde denken, Sie könnten ziemlich einfach einen Thread so einrichten, dass er Daten liest, während die anderen ihn verarbeiten. Dies kann eine Möglichkeit sein, die wahrgenommene Leistung dramatisch zu steigern. Nur ein Gedanke.

Pat Notz
quelle
Ja. Ich habe darüber nachgedacht und werde es wahrscheinlich in einer späteren Version ausprobieren. Der einzige Vorbehalt, den ich habe, ist, dass die Verarbeitung viel kürzer als die E / A-Latenz ist, sodass es möglicherweise keinen großen Nutzen gibt.
jbl
1

Ich denke, das Beste an mmap ist das Potenzial für asynchrones Lesen mit:

    addr1 = NULL;
    while( size_left > 0 ) {
        r = min(MMAP_SIZE, size_left);
        addr2 = mmap(NULL, r,
            PROT_READ, MAP_FLAGS,
            0, pos);
        if (addr1 != NULL)
        {
            /* process mmap from prev cycle */
            feed_data(ctx, addr1, MMAP_SIZE);
            munmap(addr1, MMAP_SIZE);
        }
        addr1 = addr2;
        size_left -= r;
        pos += r;
    }
    feed_data(ctx, addr1, r);
    munmap(addr1, r);

Das Problem ist, dass ich nicht die richtigen MAP_FLAGS finden kann, um einen Hinweis zu geben, dass dieser Speicher so schnell wie möglich aus der Datei synchronisiert werden sollte. Ich hoffe, dass MAP_POPULATE den richtigen Hinweis für mmap gibt (dh es wird nicht versucht, alle Inhalte vor der Rückkehr vom Aufruf zu laden, sondern dies wird asynchron mit feed_data durchgeführt). Zumindest liefert es mit diesem Flag bessere Ergebnisse, selbst wenn das Handbuch angibt, dass es seit 2.6.23 nichts ohne MAP_PRIVATE macht.

nur
quelle
1
Sie möchten posix_madvisemit derWILLNEED Flagge faule Hinweise vorab ausfüllen.
ShadowRanger
@ ShadowRanger, klingt vernünftig. Obwohl ich die Manpage aktualisieren würde, um klar zu posix_madvisesagen, dass es sich um einen asynchronen Aufruf handelt. Es wäre auch schön, mlockauf diejenigen zu verweisen , die warten möchten, bis der gesamte Speicherbereich ohne Seitenfehler verfügbar ist.
Nur