3. [Schnelligkeit] Festplatte einlesen und nach Pattern suchen

[Schnelligkeit] Festplatte einlesen und nach Pattern suchen

  • 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