3. [Schnelligkeit] Festplatte einlesen und nach Pattern suchen

[Schnelligkeit] Festplatte einlesen und nach Pattern suchen


  • @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