3. [Schnelligkeit] Festplatte einlesen und nach Pattern suchen

[Schnelligkeit] Festplatte einlesen und nach Pattern suchen

  • D

    SeppJ schrieb:

    Dann zielst du mit deinen Maßnahmen auch voll am Stand der Technik vorbei.

    Auf der Basis kann man auch argumentieren, dass C und C++ "voll am Stand der Technik" vorbeizielen, weil wir ja jetzt Java haben. Oder C#. Oder Swift oder Rust oder was auch immer.

    SeppJ schrieb:

    Bei 2 verwechselst du wohl Kontextwechsel mit Cache-Misses. Daran erkennt man den echten Experten.

    Und du verwechselst TLB-Misses mit Cache-Misses. TLBs kennen kein Prefetch. Und selbst im 2nd Level sind die begrenzt. Mal die Daten meiner CPU:

    [TLB] Instruction TLB: 2M/4M pages, fully associative, 8 entries
[TLB] Data TLB: 4 KByte pages, 4-way set associative, 64 entries
[TLB] Data TLB: 2 MByte or 4 MByte pages, 4-way set associative, 32 entries and a separate array with 1 GByte pages, 4-way set associative, 4 entries
[Prefetch] 64-Byte prefetching
[TLB] Instruction TLB: 4KByte pages, 8-way set associative, 64 entries
[STLB] Shared 2nd-Level TLB: 4 KByte/2MByte pages, 8-way associative, 1024 entries

    Cache-Größe kann ich noch nicht einlesen, daher verlasse ich mich mal auf die Information, dass dieser 6 MiB groß ist. Sagen wir mal, 4 MIB stehen dem Userspace zur Verfügung. Der Flaschenhals ist hier deutlich der TLB-Cache, der nur 1024 Einträge (2nd Level, also 4 MiB) erfassen kann (wenn du 4 KiB-Seiten verwendest - und wenn du Hugepages mit dem Dateisystem verwenden willst, ist das nervend auf Linux und nicht möglich auf Windows).

    "Wieso? 4 MiB TLB, 4 MiB Cache, reicht doch."

    Weil von den Übersetzungen ein Teil noch an den Kernel gehen. Wir haben also effektiv weniger Platz für Übersetzungen, als vom Cache getragen werden können. Außerdem ist das Holen einer Cache-Line nicht so tragisch wie das Holen einer Übersetzungsadresse, in der mehrmals auf den Speicher zugegriffen werden muss (weil es eben eine Tabelle ist).

    Falls das in irgendeiner Art und Weise falsch sein sollte, bei aller Liebe, korrigiere mich. Aber sag nicht einfach, das sei Voodoo. Unnötig? Ja. Den Aufwand nicht gerechtfertigt? Ja, wahrscheinlich, es sei denn, du verwendest den Code später noch etliche Male. Aber Voodoo? Glaube ich nicht.

    0
  • Mod

    Bitte richtig lesen, die Tipps zu 3+4 sind Voodoo. 2 ist einfach nur den Aufwand nicht wert. Optimier die Pipelines (sowohl Daten als auch Instructions), damit gewinnst du mit einfacheren Mitteln viel mehr.

    Warum 3+4 Voodoo sind:
    3: Und wie machst du sonst dynamische Speicheranforderungen? Entweder du brauchst sie, oder du verwendest sie besser nicht. Aber wenn du sie brauchst, dann glaubst du doch wohl nicht im Ernst, dass der Name der Handlerstruktur einen Unterschied macht?

    4: Was hat deine Lösung mit dem beschriebenen Problem zu tun? Weil der Voodoo-Priester mal gesehen hat, wie der weiße Mann eine Memory-mapped file benutzt hat, um etwas schneller zu machen, ist das nun das Zaubermittel für alle Performanceprobleme?

    0

  • @dachschaden
    Ich muss SeppJ Recht geben, dein Beitrag ist grösstenteils einfach nur Bullshit.
    Alleine wie du Kontextwechsel mit TLB-Misses vergleichst ist drollig^10. Oder dass du auf bem TLB-Cache rumreitest und den normalen Datencache dabei vollkommen ignorierst.

    Dein Beitrag zeigt wirklich dass du von gewissen Dingen keinen Plan hast. Und über Dinge zu schreiben von denen man keinen Plan hat, das ist ein Problem. Ein grosses Problem.

    0
  • D

    SeppJ schrieb:

    Bitte richtig lesen, die Tipps zu 3+4 sind Voodoo. 2 ist einfach nur den Aufwand nicht wert. Optimier die Pipelines (sowohl Daten als auch Instructions), damit gewinnst du mit einfacheren Mitteln viel mehr.

    Ich gehe hier von einer einfachen memmem -Suche aus. Standardmittel. Wenn man hier bereits optimieren will, ist was ganz anderes fundamental kaputt.

    SeppJ schrieb:

    3: Und wie machst du sonst dynamische Speicheranforderungen? Entweder du brauchst sie, oder du verwendest sie besser nicht. Aber wenn du sie brauchst, dann glaubst du doch wohl nicht im Ernst, dass der Name der Handlerstruktur einen Unterschied macht?

    Ich sehe so oft Leute, die dynamische Speicheranforderungen verwenden, und das wird gar nicht gebraucht. Beispiel aus dem Kopf: eine Zahl in einen String schreiben. Oder Daten von einem Socket byteweise lesen und in ein Array packen. Es geht nicht darum, keine dynamischen Speicheranforderungen zu verwenden, sondern sie nur dann zu verwenden, wenn es Sinn ergibt.

    Wenn man keine MMFs verwenden will, ist man zur Ermittelung der Buffergröße dazu gezwungen. Die Frage ist nicht: "Brauche ich dynamische Speicheranforderungen?", sondern "Warum kann/will ich keine MMFs verwenden?".

    SeppJ schrieb:

    4: Was hat deine Lösung mit dem beschriebenen Problem zu tun? Weil der Voodoo-Priester mal gesehen hat, wie der weiße Mann eine Memory-mapped file benutzt hat, um etwas schneller zu machen, ist das nun das Zaubermittel für alle Performanceprobleme?

    Ein Performanceproblem, welches hier am Deutlichsten zu sehen ist, ist die unnötige Kopie der Daten in den eigenen Buffer (C++-Streams halt). Jenes kann man eliminieren. Was dann übrig bleibt, ist die Sorge des OP, seine eigene Kopie könnte irgendwie die Performance beeinträchtigen, und die ist so gering, dass sie nun wirklich kaum zu rechtfertigen ist.

    hustbaer schrieb:

    @dachschaden
    Ich muss SeppJ Recht geben, dein Beitrag ist grösstenteils einfach nur Bullshit.

    Genau das hat SeppJ nicht geschrieben (habe ich anfangs aber auch nicht korrekt gelesen). Sondern nur, dass 2 den Aufwand nicht wert ist. Und das habe ich auch von Anfang an gesagt.

    hustbaer schrieb:

    Alleine wie du Kontextwechsel mit TLB-Misses vergleichst ist drollig^10

    Hm, habe mich jetzt nochmal ein bisschen informiert. Ein CW (Linux) kann 100 ns bis mehrere μs benötigen (jetzt nur der Overhead durch den Wechsel, nicht das Einladen der Daten), ein TLB-Miss auf einem Sandy-Bridge ~60 ns. Aber den CW hast du nur immer beim Einladen der Daten, den TLB-Miss hast du ständig (neue Seite wird angefangen, wirft alte Seite raus, Seite wird überprüft, neue Seite wird angefangen, wirft alte Seite raus ...). Bei konservativen 2 MiB (512 Seiten) haben wir also eine Verzögerung von 512 x 60 ns ~ 31 μs.

    Pauschal würde ich daher mal davon ausgehen, dass TLB-Misses stärker wehtun. Wenn du dem was hinzuzufügen hast - bin für alles offen. Aber dann komm bitte mit Argumenten. *

    hustbaer schrieb:

    Oder dass du auf bem TLB-Cache rumreitest und den normalen Datencache dabei vollkommen ignorierst.

    200 Cycles (~100 ns) wegen einer Line, während der Datencache größer ist als der TLB, vs. 31 μs ... ich weiß ja nicht, aber ich glaube, ich könnte den Datencache berechtigterweise ignoriert haben. Allein von der Logik her: mehrere Hauptspeicherzugriffe (TLB-Miss) vs. einen (Cache-Miss) ...

    EDIT: auch nicht vergessen: Der D-Cache kann prefetching. Die Daten muss man aber immer noch von Speicher laden. Dies kann tatsächlich langsamer sein als die CSs.

    EDIT 2: *Das gilt auch für SeppJ. A fool can despise what he cannot get.

    0
  • Mod

    dachschaden schrieb:

    hustbaer schrieb:

    @dachschaden
    Ich muss SeppJ Recht geben, dein Beitrag ist grösstenteils einfach nur Bullshit.

    Genau das hat SeppJ nicht geschrieben

    Ich war nur höflich. Ich habe das Gesamtpaket schon durchaus bewusst zu Anfang "Schmarrn" genannt.

    0
  • ?

    Ich habe jetzt die Wikipedia Seiten für TLB (Translation lookaside buffer) und den Cache geöffnet, verstehe die Beschreibungen jedoch nicht so recht.

    Kennt wer gute und einfache Referenzen, wo solches Architektur-Zeug (denk ich mal) genauer erleuchtet wird, damit ich der Diskussion besser folgen kann?

    Wäre ich echt dankbar dafür, wenn es da eine einfachere Erklärung dazu gäbe.

    Zum Thema mit dem Buffer: Ich lasse den Anwender meiner Klasse selbst entscheiden, wie groß der Buffer sein soll. Ich habs mit 1024 KiB getestet und funktioniert soweit ganz gut - auch das mit dem "Ende des Buffers mit sich schleifen", funktioniert ganz gut. Ich lese einfach X Bytes aus, teste sie und schiebe den Input Stream wieder um Pattern.size() Bytes zurück. Läuft jetzt echt schneller als vorhin, danke dafür.

    Ich erstelle übrigens ein einziges Mal einen Vektor mit der angegeben Buffergröße und überschreibe dann immer die Daten. Dabei hab ich eine bytes_available() -Funktion geschrieben, um zu testen, ob der Rest, den man noch einlesen muss kleiner ist, als der Buffer selbst, wenn das der Fall ist, wird der Vektor resize() et. Aber das ist glaub ich jetzt nicht so ein großes Performance-Leck, das kann nämlich nur ein einziges Mal im Programm vorkommen.

    Dann habe ich aber noch eine Frage: Wäre es nicht klüger std::istream::readsome() zu verwenden? Der gibt mir die Anzahl an Bytes zurück, die tatsächlich eingelesen wurden und könnte somit eine Funktion wie bytes_available() einsparen. Das mit bytes_available() funktioniert übrigens mit seekg() und tellg() . Oder tut das alles nicht zur Sache?

    0
  • D

    Pipette schrieb:

    Kennt wer gute und einfache Referenzen, wo solches Architektur-Zeug (denk ich mal) genauer erleuchtet wird, damit ich der Diskussion besser folgen kann?

    Ich hab' sogar 'nen Link verpflanzt ... aber wenn das Zeug für dich komplettes Neuland ist, dann lass es sein.

    Ja, ist lang. Ist auch kompliziert. Da sitzt du lange dran. Aber am Ende bist du schlauer als hustbaer. 🙂

    Pipette schrieb:

    Ich lese einfach X Bytes aus, teste sie und schiebe den Input Stream wieder um Pattern.size() Bytes zurück. Läuft jetzt echt schneller als vorhin, danke dafür.

    Du brauchst Pattern.size() - 1. Sonst hättest du das Muster ja gefunden. Aber wenn du es nicht findest, fehlt dir wenigstens ein Byte. Deswegen das -1.

    0

  • dachschaden schrieb:

    hustbaer schrieb:

    Alleine wie du Kontextwechsel mit TLB-Misses vergleichst ist drollig^10

    Hm, habe mich jetzt nochmal ein bisschen informiert. Ein CW (Linux) kann 100 ns bis mehrere μs benötigen (jetzt nur der Overhead durch den Wechsel, nicht das Einladen der Daten),

    Was interessiert es irgendwen wie lange der Context-Switch "alleine" dauert, wenn das nicht die Penalty ist die man im Programm dadurch real hat?
    Der Context-Switch haut viel stärker rein als bloss die Kosten des Switch alleine. Schliesslich fängt da dann an neuer Code zu laufen. Code der vermutlich irgendwas ganz anderes macht. Code der mit ziemlicher Sicherheit zu L1 Misses im I-Cache, D-Cache *und* TLB-Cache führt. Was erstmal selbst Zeit kostet, und dann weiters nochmal Zeit kostet wenn der ganze Ranz der dabei aus den Caches evicted wurde wieder reingelesen werden muss - was effektiv die Kosten dieser Cache-Misses verdoppelt.
    Und wenn der Context-Switch in einen anderen Prozess switched, dann wird's erst richtig böse. Dann werden nänmlich gleich alle TLB-Einträge ungültig die in den Usermode Adressraum zeigen. Und je nach CPU kann es nötig sein dabei den gesamten TLB für ungültig zu erklären.

    dachschaden schrieb:

    ein TLB-Miss auf einem Sandy-Bridge ~60 ns. Aber den CW hast du nur immer beim Einladen der Daten, den TLB-Miss hast du ständig (neue Seite wird angefangen, wirft alte Seite raus, Seite wird überprüft, neue Seite wird angefangen, wirft alte Seite raus ...).

    Ich verstehe nicht worauf du hinaus willst. Wieso sollte man den TLB Miss ständig haben?
    Du lässt die Daten vom OS 1x in den Puffer reinkopieren, da hast du u.U. den 1. TLB Miss (pro Page). Und dann prüfst/verarbeitest du die Daten im Puffer. Dort hast du - wieder nur u.U. - den 2. Miss (pro Page). 2x (pro Page) ist "ständig" oder wie?

    dachschaden schrieb:

    Pauschal würde ich daher mal davon ausgehen, dass TLB-Misses stärker wehtun. Wenn du dem was hinzuzufügen hast - bin für alles offen. Aber dann komm bitte mit Argumenten. *

    Aus deinem Beitrag ist ziemlich klar zu erkennen dass du selbst kaum bis gar keine Versuche zu dem Thema angestellt hast. Und jetzt willst du von mir "Argumente"? Eins hab ich dir oben gegeben: du kannst nicht einfach haufenweise Dinge ignorieren, dann sowas sagen wie "ich glaube X haut mehr rein als Y und wenn jmd. anderer Meinung ist dann will ich aber gute Argumenten hören". Speziell nicht bei einem Thema wo man sich so super-einfach verschätzen kann.
    Mach doch einfach ein paar Versuche zu dem Thema. Und dann berichte deine Resultate und die Interpretation dieser Resultate.

    dachschaden schrieb:

    hustbaer schrieb:

    Oder dass du auf bem TLB-Cache rumreitest und den normalen Datencache dabei vollkommen ignorierst.

    200 Cycles (~100 ns) wegen einer Line, während der Datencache größer ist als der TLB, vs. 31 μs ... ich weiß ja nicht, aber ich glaube, ich könnte den Datencache berechtigterweise ignoriert haben. Allein von der Logik her: mehrere Hauptspeicherzugriffe (TLB-Miss) vs. einen (Cache-Miss) ...

    Ach das ist schon anstrengend.
    Dir ist bekannt dass die meisten CPUs kein Prefetching über Pagegrenzen hinweg können, oder?
    D.h. du hast trotz Prefetching potentiell pro Page einen D-Cache Miss.
    Genau so wie du potentiell pro Page einen TLB-Cache Miss hast.
    Fällt dir was auf?
    Oder überleg' dir mal weiter wie gross der (shared!) L3 Cache von üblichen CPUs ist, und dann guck viele Einträge der (per CoreHW-Thread!) TLB-Cache fassen kann, und für wie viel Speicher das reicht (unter der Annahme dass jede Page zu 100% verwendet wird).
    Fällt dir vielleicht jetzt was auf?

    0
  • B

    Naja, bevor dachschaden mal wieder eine neue Speicherverwaltung baut, frage ich mal dumm.

    Welchen Pattern-Matching Algorithmus wird hier verwendet? Vielleicht lässt sich ja da noch was drehen.

    https://de.wikipedia.org/wiki/String-Matching-Algorithmus

    0
  • ?

    dachschaden schrieb:

    SeppJ schrieb:

    Dann zielst du mit deinen Maßnahmen auch voll am Stand der Technik vorbei.

    Auf der Basis kann man auch argumentieren, dass C und C++ "voll am Stand der Technik" vorbeizielen, weil wir ja jetzt Java haben. Oder C#. Oder Swift oder Rust oder was auch immer.

    völliger schwachsinn... wieso ist java neuer als c++ ?
    glaube sogar c++ hat den neueren standard. (bin mir gerade nicht ganz sicher...)

    was soll das also bedeuten? 🙄

    zu mal selbst wenn c++ "älter" wäre ist das nicht das selbe wie "voll am Stand der Technik vorbei".

    denn c++ hat durchaus seine berechtigung gegenüber java und ich z.B. brauche kein java, kann es(keine laufzeitumgebung) und will es auch nicht nutzen.

    also was soll deine aussage bedeuten macht für mich gar keine sinn...?

    außerdem dynamische speicherverwaltung hat nicht den vorteil das sie schneller oder sonst was ist (wie du ja schon gemerkt hast), sonder dafür das sicherer und fehlerunanfälliger entwickelt werden kann und du keine angst haben musst ein delete zuviel oder zuwenig oder ähnliches zu haben. 🙄

    dachschaden schrieb:

    Und wie machst du sonst dynamische Speicheranforderungen? Entweder du brauchst sie, oder du verwendest sie besser nicht. Aber wenn du sie brauchst, dann glaubst du doch wohl nicht im Ernst, dass der Name der Handlerstruktur einen Unterschied macht?

    na ja kommt sicher immer konkret auf das problem an.

    aber ich hab gelernt solage du keinen grund hast die stl-container nicht zu benutzen dann mach es und optimiert wird nachdem programmieren wenn das programm nicht schnell genug ist...

    ich möchte ja eine übersichtliche, wartbare und erweiterbare lösung haben, das was du beschreibst will eig niemand da es nicht wartbar geschweige denn nachvollziehbar ist
    (aber ok es läuft 1 millisekunde bzw mehr oder weniger schneller wow, hast schonmal was von wirtschaftlichkeit gehört? - nicht jedes programm muss das schnellste sein)

    aber wenn du ein kleines programm schreibst nimm die stl-container...
    warum nicht weil dein programm ansonsten 1millisekunde eher fertig ist ?

    du dafür aber fehleranfälliger programmierst und vorraussichtlich auch mehr zeit brauchst...

    lg

    0
  • D

    So, jetzt habe ich mal das Programm implementiert. Dem TE möchte ich die Lösung natürlich nicht direkt verraten, aber hier mal ein paar Kenndaten:

    - Gentoo Linux 4.6.0
    - In C geschrieben
    - kein Support für Windows (könnte ich einfügen, aber dann müsste ich Teile von Backend-Code einbinden, den ich gar nicht veröffentlichen will)
    - Daten werden wie beschrieben über mmap eingeladen und ausgeladen.
    - für das Speicher-Mapping wird PROT_READ | PROT_WRITE und MAP_PRIVATE | MAP_NORESERVE | MAP_32BIT verwendet (weil wir den reservierten Bereich unten im Speicher haben wollen)
    - für das File-Mapping wird PROT_READ und MAP_SHARED | MAP_NORESERVE verwendet, das Mapping wird direkt nach dem Speichermapping gesetzt.
    - die Tests fanden mit /dev/sds6 statt (Systempartition - ich wusste gar nicht, dass ich da Shakespeare druff hatte, aber egal).
    - um den Test nicht zu verfälschen (siehe unten) wurden nur die ersten 512 MiB der Partition eingelesen
    - die Daten befanden sich bereits im I/O-Cache (Arbeitsspeicher), es wurde hier also nicht das Einladen mitgemessen.
    - die CPU-Daten habe ich bereits gepostet.

    Ein paar Punkte am Rande:

    • mmap mappt nur dann Daten von der Festplatte, wenn der Kernel es muss - sprich, das eigentliche Laden wird nicht in den Calls gemacht, sondern während auf die Speicherbereiche ( memmem ) zugegriffen wird.
      - eine Iteration hat somit zwei CS (Kontextwechsel - mmap und munmap )

    Es wurde gemessen:

    mmap mit 256 Mebibyte Bufferlänge. Durchschnittliches Ergebnis: 722 Millionen Cycles, 4 CS
    mmap mit 64 Mebibyte Bufferlänge. Durchschnittliches Ergebnis: 730 Millionen Cycles, 16 CS
    mmap mit 4 Mebibyte Bufferlänge. Durchschnittliches Ergebnis: 705 Millionen Cycles, 256 CS
    mmap mit 2 Mebibyte Bufferlänge. Durchschnittliches Ergebnis: 700 Millionen Cycles, 512 CS
    mmap mit 1 Mebibyte Bufferlänge. Durchschnittliches Ergebnis: 700 Millionen Cycles, 1024 CS
    mmap mit 64 Kibibyte Bufferlänge. Durchschnittliches Ergebnis: 715 Millionen Cycles, 16384 CS

    Das Programm habe ich jetzt schnell zusammengeschrieben, und es sind auch vermutlich noch ein paar Bugs drin. Aber einen groben Überblick sollte es schon liefern: Kontextwechsel wiegen offenbar nicht so schwer wie die Verunreinigung des Caches bis zum (von mir prophezeiten) Threshold von 2 Mebibyte.

    Gerade habe ich keine Zeit mehr, daran weiterzuarbeiten. Aber die Tage werde ich es mir nochmal genauer anschauen.

    WASWEISSICHSCHON schrieb:

    völliger schwachsinn... wieso ist java neuer als c++ ?

    Mein Eindruck war immer, dass die Hauptkritik der Java-Leute an C++ war, dass dieses viel zu kompliziert, weswegen man dann was eigenes gebaut hat. Eine Ironie, dass die Komplexitätsberge, die Java inzwischen auftürmt, C++ in den Schatten stellt .

    WASWEISSICHSCHON schrieb:

    denn c++ hat durchaus seine berechtigung gegenüber java und ich z.B. brauche kein java, kann es(keine laufzeitumgebung) und will es auch nicht nutzen.

    Das war das Argument von SeppJ, dem ich nicht beipflichte. C hat auch seine Berechtigung, ob einige Leute meinen (ich schaue niemanden an hier), dass es voll am Stand der Technik vorbeigeht.

    WASWEISSICHSCHON schrieb:

    außerdem dynamische speicherverwaltung hat nicht den vorteil das sie schneller oder sonst was ist (wie du ja schon gemerkt hast), sonder dafür das sicherer und fehlerunanfälliger entwickelt werden kann und du keine angst haben musst ein delete zuviel oder zuwenig oder ähnliches zu haben. 🙄

    Schonmal einen Allokator programmiert? Oder zumindest mal in den Code von einem geblinzelt?

    Beides kann ich bejahen. Und mein Allokator hat keines der genannten Probleme, hat keine Userspace-Locks, und kann sogar, wenn Support dafür besteht, für kleinere Allokationen diese einfacher auf dem Stack anlegen (für gewöhnlich auf alles unter 4 KiB getrimmt). Er ist wohl auf Bulk-Allokationen ausgerichtet - 10-mal Resizing wird dich mit dem Ding mehr kosten als mit Standardmitteln (CW wegen), aber wenn du die vermeidest, ist das Ding rasend.

    EDIT: @Bitte ein Bit, das noch: verwende memmem , ich habe aber vor Jahren eine Boyer-Moore-Implementierung gebaut, die könnte ich, wenn ich Zeit habe, auch noch mal einbauen.

    0
  • ?

    Hallo,

    Ich hab das Programm jetzt auch fertig implementiert, sind sicherlich noch einige Dinge da, die man besser hätte machen können. Aber naja. Ich wills mit euch teilen. Würde mich freuen, wenn sich jemand den Code mal ansehen will und mir noch weitere Ratschläge gibt, wie man das Programm noch besser gestalten kann. Das Programm ist ein Kommandozeilenwerkzeug und ich habe es so gebaut, dass man wirklich alles selber einstellen kann. Die Namen der Optionen sind vielleicht nicht immer perfekt gewählt, aber das liegt an meinen mangelnden Englischkenntnissen. Ist auch wirklich kein großes Ding, sind rund 200 - 300 Zeilen. Und es klappt wunderbar! Ich habe mal testhalber nach dem Muster ' #include <iostream> ' gesucht und habe tatsächlich einen Haufen (eigentlich alles) gefunden.

    filter on github

    0

  • @dachschaden
    ZweiEin paar Dinge die mir dazu einfallen.

    1. Memory Mapping verursacht potentiell haufenweise Context-Switches, nicht bloss einen pro Map und einen pro Unmap Aufruf. Und zwar wenn man auf Daten zugreift bevor sie gelesen werden konnten. Wenn die Daten alle aus dem File-Cache/Block-Cache des OS kommen wird das vermutlich selten passieren. Je nachdem wo die Daten die da verarbeitet werden herkommen wird das im Realeinsatz allerdings sehrwohl passieren.

    2. Ein Kontextwechsel von "ich tu was" zu "ich tu nix" und ein zweiter wieder zurück zu "ich tu wieder was" tut lange nicht so sehr weh wie ein "echter" Kontextwechsel von "ich tu was" zu "ich tu was anderes". Soll heissen: Wäre interessant wie das ganze skaliert wenn du im Hintergrund Prozesse mit niedrigere Priorität laufen hast die die CPU komplett auslasten.
      (Dein Test ist natürlich aussagekräftig für Fälle wo das Programm die Maschine für sich alleine hat, aber das muss ja nicht das einzige Szenarion sein an dem man interessiert ist.)

    3. Davon abgesehen bezweifle ich dass mmap hier überhaupt das Mittel der Wahl ist - ich bin fast sicher dass man mit einer selbstgestrickten Producer-Consumer Queue noch ein paar Zyklen rausholen kann. Obwohl sich das dann vermutlich auch nur im "zahlt sich nicht aus" Bereich abspielen wird.

    4. PREFETCH?

    0
  • F

    hustbaer schrieb:

    1. Davon abgesehen bezweifle ich dass mmap hier überhaupt das Mittel der Wahl ist

    Ich denke auch dass Memory Mapping hauptsächlich bei Random Access glänzt.
    Das beschriebene Problem sieht mir doch ziemlich sequentiell aus, und auch das OS kommt nicht drumherum die Daten erstmal
    vom langsamen Datenträger einzulesen. Wenn man unnötige Kopien im Speicher sparen will, macht es evtl. mehr Sinn keine
    Funktionen mit internem Buffering zu verwenden, sondern die Daten direkt (unbuffered) in den Speicherbereich einzulesen wo sie weiterverarbeitet werden.
    Was die Buffergrösse angeht würde ich mir erstmal ein paar sinnvolle Größen überlegen (Blockgrösse auf Datenträger, Speicherseiten-Grösse, Default-Werte
    für Funktionen mit internem Buffering) und dann experimentell eine geeignete bestimmen. Erst wenn ich damit am Limit angelangt bin würde ich schauen ob
    sich mit irgendwelcher Thread- und Kontextswitch-Magie vielleicht noch etwas herausholen lässt - ich glaube allerdings dass diese potentiellen Effekte von
    den Datenträgerzugriffen derart dominiert werden (auch bei schneller SSD), dass sie kaum messbar sind.

    Finnegan

    0

  • Ja. Jain. Bei mmap und Random IO bin ich nicht unbedingt deiner Meinung. Aber das Thema hatten wir schon.

    Ansonten ... ja.
    Das grösste schlimmste Bottleneck hier ist wohl der Datenträger - es sei dann man hat ne superschnelle SSD-Karte die mehrere GB/s raushaut.
    Das zweitgrössteschlimmste Bottleneck ist dann die CPU. Aber nicht der TLB oder sonstwas, sondern einfach der Suchalgorithmus. Der Test von dachschaden kommt auf mehr als 1 Cycle/Byte, d.h. weniger als 4 GB/s auf nem 4GHz Chip. Und das ist weit entfernt von der Hauptspeicherbandbreite (üblicherweise >= 20 GB/s).

    Alles andere kommt danach.

    Das hat dachschaden aber auch nie bestritten. Er hat es bloss in einen Thread gepostet wo es wohl um alles andere als um die letzten 5% Performance geht.

    0
  • F

    hustbaer schrieb:

    Ja. Jain. Bei mmap und Random IO bin ich nicht unbedingt deiner Meinung. Aber das Thema hatten wir schon.

    Bei völlig zufälligen Zugriffen (wohl eher selten) würde ich da auch zurückrudern, sagen wir mal Random Access mit sequentiellen Abschnitten dazwischen.
    So was wie ein B-Baum auf Platte könnte davon gut profitieren (öfter Blöcke auf dem Pfad zum Blattknoten bereits im OS-Cache).
    Apropos SSD, im Labor nähern sich so einige Flashspeicher-Konstruktionen mit über 10GiB/s Durchsatz schon gefährlich an den Arbeitsspeicher an...
    wer weiss was uns da noch erwartet in ein paar Jahren 🙂

    0
  • D

    hustbaer schrieb:

    Und zwar wenn man auf Daten zugreift bevor sie gelesen werden konnten.

    Hm, gut, stimmt, da habe ich mich unklar ausgedrückt. Was ich meinte, waren die CS, die man direkt zu verantworten hat - oder besser, die, die man vermeiden kann.

    hustbaer schrieb:

    Wenn die Daten alle aus dem File-Cache/Block-Cache des OS kommen wird das vermutlich selten passieren.

    Das wiederum halte ich für ein Gerücht - zumindest was die Häufigkeit angeht.

    int main(void)
{
    const size_t max_pages = 40;

    int fd;
    uint8_t x;
    uint8_t*file;
    uint64_t rdtsc_before,rdtsc_after;
    size_t i;

    fd = open("/dev/sda6",O_RDONLY);
    if(fd == -1)
    {
        fprintf(stderr,"Kein gültiges Device, verschwinde\n");
        goto LABEL_NO_FD;
    }

    file = mmap(NULL,4096 * max_pages,PROT_READ,MAP_SHARED | MAP_NORESERVE,fd,0);
    if(file == MAP_FAILED)
        goto LABEL_NO_MAP;

    for(i = 0;i < max_pages;i++)
    {
        rdtsc_before = rdtsc();
        x = file[4096 * i];
        rdtsc_after = rdtsc();

        printf("%lu|%lu|\n",i,rdtsc_after - rdtsc_before);
    }

LABEL_NO_MAP:
    close(fd);
LABEL_NO_FD:
    return 0;
}

    Hier wird ein einzelnes Byte vom gemappten Device in x gespeichert. Habe sichergestellt, dass das Lesen nicht wegoptimiert wird. Den Teil der Platte hat der Kernel immer im I/O Cache, das kann man auch ganz leicht sicherstellen, indem man das Programm immer wieder aufruft.

    Die Ausgabe:

    0|9940|
1|36|
2|24|
3|32|
4|24|
5|24|
6|28|
7|28|
8|24|
9|28|
10|28|
11|28|
12|24|
13|24|
14|24|
15|28|
16|2808|
17|7256|
18|24|
19|24|
20|24|
21|24|
22|24|
23|24|
24|24|
25|24|
26|24|
27|28|
28|28|
29|24|
30|24|
31|24|
32|24|
33|3320|
34|24|
35|28|
36|24|
37|24|
38|24|
39|24|

    Beim ersten Zugriff gibt es einen Page Fault, der wird vom Kernel abgefangen (CS), dann werden die Daten eingemappt. Beim zweiten Zugriff gibt es keinen Wechsel mehr, die Daten sind bereits drin.
    Lustig fand ich an der Stelle die Heuristik des Kernel - ich habe immer gedacht, der Kernel lädt immer nur die Seite ein, auf die zugegriffen wird, aber die Anzahl an Seiten, die der Kernel einmappt, scheint zu variieren.

    hustbaer schrieb:

    Wäre interessant wie das ganze skaliert wenn du im Hintergrund Prozesse mit niedrigere Priorität laufen hast die die CPU komplett auslasten.

    Kann ich testen. Wobei ich im Hintergrund einen Emulator, einen Browser und den VLC laufen hatte. Wird aber wahrscheinlich nicht ausgereicht haben, um in dieser Hinsicht aussagekräft zu sein.

    hustbaer schrieb:

    Davon abgesehen bezweifle ich dass mmap hier überhaupt das Mittel der Wahl ist - ich bin fast sicher dass man mit einer selbstgestrickten Producer-Consumer Queue noch ein paar Zyklen rausholen kann.

    Werden wir sehen. Ich will erst mal schauen, ob read nicht schneller ist. Aber wie gesagt, erst in den nächsten Tagen.

    hustbaer schrieb:

    1. PREFETCH?

    1. Meine Erfahrungen mit manuellem Prefetch waren bisher ... mäßig, aber:
    2. Das ist dann eine Sache des Algorithmus (sprich memmem ). welches keine intelligente Mustersuche implementiert. Mein Beispiel war jetzt vor allem darauf ausgelegt, zu zeigen, dass die Buffergroße, so wie ich gesagt hatte - nicht einfach nur groß sein sollte, sondern dass es da auch andere Faktoren gibt.

    Ich konnte auch einfach einen Zugriff auf jeden Seitenanfang durchführen und dann wiederholen, das lässt sich erstmal wesentlich einfacher optimieren als die Mustersuche, und wir würden trotzdem sehen, was am Ende schneller ist. Oder siehst du was, was dem widerspräche?

    0

  • dachschaden schrieb:

    Ich konnte auch einfach einen Zugriff auf jeden Seitenanfang durchführen und dann wiederholen, das lässt sich erstmal wesentlich einfacher optimieren als die Mustersuche, und wir würden trotzdem sehen, was am Ende schneller ist. Oder siehst du was, was dem widerspräche?

    Wenn du ganz gezielt nur die Auswirkung des TLB messen willst vermutlich nicht. Was du dadurch allerdings machst, ist die Auswirkung des Datencache aus der Messung grösstenteils zu entfernen.

    Aber du könntest z.B. ne XOR Prüfsumme rechnen. Das lässt sich auch halbwegs einfach optimieren.

    dachschaden schrieb:

    Lustig fand ich an der Stelle die Heuristik des Kernel - ich habe immer gedacht, der Kernel lädt immer nur die Seite ein, auf die zugegriffen wird, aber die Anzahl an Seiten, die der Kernel einmappt, scheint zu variieren.

    Wenn der Kernel immer nur die eine Seite laden würde, dann wäre Memory-Mapping vermutlich die langsamste Art IO zu machen. Vergleichbar eben wie wenn man unbuffered 4K IOs der Reihe nach an den Datenträger schickt - mit einem syscall pro IO.

    0
Anmelden zum Antworten