Warum ist die Speicherzuweisung für Prozesse langsam und kann sie schneller sein?

Lesezeit: 9 Minuten

Benutzer-Avatar
hmm

Ich bin relativ vertraut mit der Funktionsweise des virtuellen Speichers. Der gesamte Prozessspeicher wird in Seiten unterteilt und jede Seite des virtuellen Speichers wird einer Seite im realen Speicher oder einer Seite in der Auslagerungsdatei zugeordnet, oder es kann eine neue Seite sein, was bedeutet, dass die physische Seite noch nicht zugewiesen ist. Das Betriebssystem ordnet neue Seiten bei Bedarf dem realen Speicher zu, nicht wenn eine Anwendung nach Speicher fragt malloc, aber nur, wenn eine Anwendung tatsächlich auf jede Seite aus dem zugewiesenen Speicher zugreift. Aber ich habe noch Fragen.

Ich habe dies bemerkt, als ich meine App mit Linux profilierte perf Werkzeug.

Geben Sie hier die Bildbeschreibung ein

Es sind etwa 20% der Zeit, die Kernelfunktionen in Anspruch genommen haben: clear_page_orig, __do_page_fault und get_page_from_free_list. Das ist viel mehr, als ich für diese Aufgabe erwartet hatte, und ich habe einige Nachforschungen angestellt.

Beginnen wir mit einem kleinen Beispiel:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#define SIZE 1 * 1024 * 1024

int main(int argc, char *argv[]) {
  int i;
  int sum = 0;
  int *p = (int *) malloc(SIZE);
  for (i = 0; i < 10000; i ++) {
    memset(p, 0, SIZE);
    sum += p[512];
  }
  free(p);
  printf("sum %d\n", sum);
  return 0;
}

Nehmen wir das mal an memset ist nur eine speichergebundene Verarbeitung. In diesem Fall weisen wir einmalig einen kleinen Teil des Speichers zu und verwenden ihn immer wieder. Ich werde dieses Programm wie folgt ausführen:

$ gcc -O1 ./mem.c && time ./a.out

-O1 erforderlich, weil clang mit -O2 eliminiert die Schleife vollständig und berechnet den Wert sofort.

Die Ergebnisse sind: Benutzer: 0,520 s, System: 0,008 s. Entsprechend perf99 % dieser Zeit ist in memset aus libc. In diesem Fall beträgt die Schreibleistung also etwa 20 Gigabyte/s, was mehr als die theoretische Leistung von 12,5 Gb/s für meinen Speicher ist. Sieht so aus, als ob dies am L3-CPU-Cache liegt.

Lassen Sie die Änderung testen und beginnen Sie, Speicher in der Schleife zuzuweisen (ich werde nicht dieselben Teile des Codes wiederholen):

#define SIZE 1 * 1024 * 1024
for (i = 0; i < 10000; i ++) {
  int *p = (int *) malloc(SIZE);
  memset(p, 0, SIZE);
  free(p);
}

Das Ergebnis ist genau das gleiche. Ich glaube das free gibt nicht wirklich Speicher für das Betriebssystem frei, sondern fügt ihn nur in eine freie Liste innerhalb des Prozesses ein. Und malloc Bei der nächsten Iteration erhalten Sie genau denselben Speicherblock. Deshalb gibt es keinen merklichen Unterschied.

Lassen Sie beginnen, SIZE von 1 Megabyte zu erhöhen. Die Ausführungszeit wird nach und nach wachsen und in der Nähe von 10 Megabyte gesättigt sein (es gibt für mich keinen Unterschied zwischen 10 und 20 Megabyte).

#define SIZE 10 * 1024 * 1024
for (i = 0; i < 1000; i ++) {
  int *p = (int *) malloc(SIZE);
  memset(p, 0, SIZE);
  free(p);
}

Die Zeit zeigt: Benutzer: 1,184 s, System: 0,004 s. perf meldet immer noch, dass 99 % der Zeit in ist memset, aber der Durchsatz beträgt etwa 8,3 Gb/s. An diesem Punkt verstehe ich, was los ist, mehr oder weniger.

Wenn wir die Speicherblockgröße weiter erhöhen, wird die Ausführungszeit irgendwann (bei mir auf 35 MB) dramatisch ansteigen: Benutzer: 0,724 s, System: 3,300 s.

#define SIZE 40 * 1024 * 1024
for (i = 0; i < 250; i ++) {
  int *p = (int *) malloc(SIZE);
  memset(p, 0, SIZE);
  free(p);
}

Entsprechend perf, memset verbraucht nur 18% der Zeit.

Geben Sie hier die Bildbeschreibung ein

Offensichtlich wird Speicher vom Betriebssystem zugewiesen und bei jedem Schritt freigegeben. Wie ich bereits erwähnt habe, sollte das Betriebssystem jede zugewiesene Seite vor der Verwendung löschen. Also 27,3 % von clear_page_orig sieht nicht außergewöhnlich aus: es sind nur 4 s * 0,273 ≈ 1,1 s für clear mem – dasselbe, was wir im dritten Beispiel erhalten. memset dauerte 17,9%, was zu ≈ 700 ms führt, was aufgrund des Speichers bereits im L3-Cache danach normal ist clear_page_orig (erstes und zweites Beispiel).

Was ich nicht verstehe — warum der letzte Fall 2 mal langsamer ist als nur memset für Speicher + memset für L3-Cache? Kann ich damit etwas anfangen?

Die Ergebnisse sind (mit kleinen Unterschieden) auf nativem Mac OS, Ubuntu unter Vmware und Amazon c4.large-Instanz reproduzierbar.

Außerdem denke ich, dass es auf zwei Ebenen Raum für Optimierung gibt:

  • auf OS-Ebene. Wenn das Betriebssystem weiß, dass es eine Seite an dieselbe Anwendung zurückgibt, zu der es zuvor gehörte, kann es sie nicht löschen.
  • auf CPU-Ebene. Wenn die CPU weiß, dass die Seite früher frei war, kann sie die Seite im Speicher nicht löschen. Es kann es einfach im Cache löschen und erst nach einiger Verarbeitung im Cache in den Speicher verschieben.

  • Sie haben keine konkrete Frage, aber ich sehe in Ihrem Profil nichts Ungewöhnliches oder Unerwartetes. Alles, was Sie tun, ist das Generieren von Seitenfehlern mit memset.

    – Benutzer3344003

    10. Oktober 2016 um 15:25 Uhr

  • Ich habe die konkrete Frage. “Warum der letzte Fall 2-mal langsamer ist als die Zeit für (Memset für Speicher + Memset für L3-Cache)” . Ich glaube, dass alle anderen Manipulationen mit Seiten nicht so teuer sein sollten.

    – hmm

    10. Oktober 2016 um 18:54 Uhr

Benutzer-Avatar
Joe Damato

Was hier passiert, ist ein bisschen kompliziert, da es ein paar verschiedene Systeme betrifft, aber es ist definitiv so nicht bezogen auf die Kontextwechselkosten; Ihr Programm macht nur sehr wenige Systemaufrufe (überprüfen Sie dies mit spur).

Zuerst ist es wichtig, einige grundlegende Prinzipien über den Weg zu verstehen malloc Implementierungen funktionieren im Allgemeinen:

  1. Die meisten malloc Implementierungen erhalten durch Aufrufen eine Menge Speicher vom Betriebssystem sbrk oder mmap während der Initialisierung. Die erhaltene Speichermenge kann in einigen angepasst werden malloc Implementierungen. Sobald der Speicher erhalten ist, wird er typischerweise in verschiedene Größenklassen geschnitten und in einer Datenstruktur angeordnet, so dass, wenn ein Programm Speicher anfordert, z. malloc(123)das malloc Die Implementierung kann schnell ein Stück Speicher finden, das diesen Anforderungen entspricht.
  2. Wenn du anrufst freeSpeicher wird an eine freie Liste zurückgegeben und kann bei nachfolgenden Aufrufen von wiederverwendet werden malloc. Etwas malloc Implementierungen ermöglichen es Ihnen, genau abzustimmen, wie dies funktioniert.
  3. Wenn Sie große Speicherblöcke zuweisen, werden die meisten malloc Implementierungen übergeben einfach Aufrufe für große Speichermengen direkt an die mmap Systemaufruf, der jeweils “Seiten” Speicher zuweist. Bei den meisten Systemen beträgt 1 Speicherseite 4096 Byte.
  4. In diesem Zusammenhang versuchen die meisten Betriebssysteme, Speicherseiten zu löschen, bevor sie an Prozesse weitergegeben werden, die Speicher über angefordert haben mmap oder sbrk. Aus diesem Grund sehen Sie Anrufe an clear_page_orig in der perf-Ausgabe. Diese Funktion versucht, Nullen in Speicherseiten zu schreiben.

Nun überschneiden sich diese Prinzipien mit einer anderen Idee, die viele Namen hat, aber allgemein als “Bedarfs-Paging” bezeichnet wird. Was “Demand Paging” bedeutet, ist, wenn ein Benutzerprogramm einen Teil des Speichers vom Betriebssystem anfordert (z. B. durch Aufrufen von mmap), wird der Speicher im virtuellen Adressraum des Prozesses zugewiesen, aber es gibt noch keinen physischen RAM, der diesen Speicher unterstützt.

Hier ist ein Überblick über den Demand-Paging-Prozess:

  1. Ein Programm namens mmap 500 MB RAM zuweisen.
  2. Der Kernel bildet einen Adressbereich im Adressraum des Prozesses für die angeforderten 500 MB RAM ab. Es bildet “wenige” (vom Betriebssystem abhängige) Seiten (normalerweise jeweils 4096 Byte) des physischen RAM ab, um diese virtuellen Adressen zu sichern.
  3. Das Benutzerprogramm beginnt mit dem Zugriff auf den Speicher, indem es darauf schreibt.
  4. Schließlich greift das Benutzerprogramm auf eine Adresse zu, die gültig ist, aber von keinem physischen RAM unterstützt wird.
  5. Dies erzeugt einen Seitenfehler auf der CPU.
  6. Der Kernel reagiert auf den Seitenfehler, indem er sieht, dass der Prozess auf eine gültige Adresse zugreift, aber auf eine Adresse ohne physischen RAM, der sie unterstützt.
  7. Der Kernel findet dann RAM, um es dieser Region zuzuweisen. Dies kann langsam sein, wenn Speicher für andere Prozesse zuerst auf die Festplatte geschrieben werden muss (“ausgelagert”).

Der wahrscheinlichste Grund, warum Sie im letzten Fall eine Leistungsminderung sehen, ist folgender:

  1. Ihrem Kernel ist die nullgestellte Speicherseite ausgegangen, die verteilt werden kann, um Ihre Anforderung von 40 MB zu erfüllen, daher nullt er den Speicher immer wieder, wie Ihre perf-Ausgabe zeigt.
  2. Sie erzeugen Seitenfehler, wenn Sie auf Speicher zugreifen, der noch nicht zugeordnet ist. Da Sie auf 40 MB statt auf 10 MB zugreifen, erzeugen Sie mehr Seitenfehler, da mehr Speicherseiten zugeordnet werden müssen.
  3. Wie eine andere Antwort darauf hinwies, memset ist O(n), was bedeutet, je mehr Speicher Sie zum Schreiben benötigen, desto länger dauert es.
  4. Weniger wahrscheinlich, da 40 MB heutzutage nicht viel RAM sind, aber überprüfen Sie die Menge an freiem Speicher auf Ihrem System, um sicherzustellen, dass Sie genug RAM haben.

Wenn Ihre Anwendung extrem leistungsempfindlich ist, können Sie stattdessen anrufen mmap direkt und:

  1. passieren die MAP_POPULATE -Flag, das bewirkt, dass alle Seitenfehler im Voraus auftreten und den gesamten physischen Speicher abbilden – dann zahlen Sie nicht die Kosten für Seitenfehler beim Zugriff.
  2. passieren die MAP_UNINITIALIZED -Flag, das versucht, das Nullen von Speicherseiten zu vermeiden, bevor sie an Ihren Prozess verteilt werden. Beachten Sie, dass die Verwendung dieses Flags ein Sicherheitsproblem darstellt und nicht verwendet werden sollte, es sei denn, Sie verstehen die Auswirkungen der Verwendung dieser Option vollständig. Es ist möglich, dass der Prozess Speicherseiten ausgibt, die von anderen unabhängigen Prozessen zum Speichern vertraulicher Informationen verwendet wurden. Beachten Sie auch, dass Ihr Kernel kompiliert sein muss, um diese Option zuzulassen. Bei den meisten Kernels (wie dem AWS-Linux-Kernel) ist diese Option standardmäßig nicht aktiviert. Das sollten Sie mit ziemlicher Sicherheit nicht Verwenden Sie diese Option.

Ich möchte Sie warnen, dass dieses Optimierungsniveau fast immer ein Fehler ist; Die meisten Anwendungen haben viel weniger hängende Früchte für die Optimierung, die keine Optimierung der Seitenfehlerkosten beinhaltet. In einer realen Anwendung würde ich empfehlen:

  1. Vermeidung der Verwendung von memset auf großen Speicherblöcken, es sei denn, es ist wirklich notwendig. Meistens ist es nicht erforderlich, den Speicher vor der Wiederverwendung durch denselben Prozess auf Null zu setzen.
  2. Vermeiden, immer wieder dieselben Speicherblöcke zuzuweisen und freizugeben; Vielleicht können Sie einfach einen großen Block im Voraus zuweisen und ihn später nach Bedarf wiederverwenden.
  3. Verwendung der MAP_POPULATE Flag oben, wenn die Kosten der Seitenfehler beim Zugriff wirklich schädlich für die Leistung sind (unwahrscheinlich).

Bitte hinterlassen Sie Kommentare, wenn Sie Fragen haben, und ich werde diesen Beitrag gerne bearbeiten und bei Bedarf ein wenig erweitern.

Benutzer-Avatar
Charly Martin

Ich bin mir nicht sicher, aber ich bin bereit zu wetten, dass die Kosten für den Kontextwechsel vom Benutzermodus zum Kernel und wieder zurück alles andere dominieren. memset nimmt auch viel Zeit in Anspruch – denken Sie daran, dass es O (n) sein wird.

Aktualisieren

Ich glaube, dass Free nicht wirklich Speicher für das Betriebssystem freigibt, sondern ihn nur in eine freie Liste innerhalb des Prozesses einfügt. Und malloc erhält bei der nächsten Iteration genau denselben Speicherblock. Deshalb gibt es keinen merklichen Unterschied.

Das ist im Prinzip richtig. Der Klassiker malloc die Implementierung weist Speicher auf einer einfach verknüpften Liste zu; free setzt einfach ein Flag, das besagt, dass die Zuordnung nicht mehr verwendet wird. Wie die Zeit vergeht, malloc neu zuweist, wenn er zum ersten Mal einen freien Block findet, der groß genug ist. Das funktioniert gut genug, kann aber zu einer Fragmentierung führen.

Es gibt jetzt eine Reihe eleganterer Implementierungen, siehe diesen Wikipedia-Artikel.

1373760cookie-checkWarum ist die Speicherzuweisung für Prozesse langsam und kann sie schneller sein?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy