4. Allokator auf Windows programmieren - Denkanstöße und Korrekturen

Allokator auf Windows programmieren - Denkanstöße und Korrekturen

  • D

    Ich schreibe gerade einen (auf Windows und Linux funktionierenden) Alloktor für größere/zahlreiche Objekte. Die Idee dahinter ist, dass man oft nur ein Array von Objekten benötigt, welches nach der Benutzung einfach gelöscht, oder noch besser, wiederverwertet werden kann. Bei entsprechender Implementierung kann man so auch auf (Userspace)-Locks verzichten.

    Wir reden hier im Bereich von Mebibytes bis Gebibytes. Hugepages/large pages werden bereits unterstützt (unter Linux bis 1 GiB, bei Windows 2 MiB). Unter Linux verwende ich mmap , mremap und munmap , unter Windows VirtualAlloc und VirtualFree .

    Mein Problem im Speziellen ist, dass Windows keine Möglichkeit zu besitzen scheint, bereits gemappte Speicherbereiche zu erweitern. Soweit ich die Lage beurteilen kann, bleiben mir damit zwei Möglichkeiten, neuen Speicher zu reservieren:

    1. Neuen Speicherbereich mit neuer Größe anfordern, alte Daten reinkopieren, alten Speicherbereich freigeben.

    2. Für jedes Mapping-Objekt, das ich habe, eine Mapping-Tabelle anlegen, in der dann alle Mappings drinstehen. Halt das, was Linux macht, aber für Windows im Userspace.

    3. hat seine ganz eigenen Probleme - z.B. dass es gar nicht gut skaliert. Da Windows derzeit nur 2 MIB-Pages unterstützt, haben wir bei 512 MiB, die um 128 MiB erweitert werden sollen (Wachstum wird über das Objekt exportiert und kann jederzeit geändert werden), 256 Page-Mappings, zu denen 64 weitere dazukommen. Nicht nur, dass wir dann 512 MiB Daten kopieren müssen, vernichtet uns das auch die CPU- und die dTLB-Caches. Der Vorteil ist natürlich, dass es leicht zu implementieren ist. Sagen wir, dass wir ein hochgezüchtetes memcpy verwenden, welches nur darauf ausgelegt ist, 2-MiB-Pages auszutauchen (mit AVX-Detektierung und ausgerolltem Code und weiß der Geier), dann haben wir immer noch 256 Aufrufe dieser Funktion. Das ist Blöde. Außerdem haben wir so einen zusätzlichen Kopiervorgang, wenn der Programmier der Struktur gesagt hat, dass die Daten schon an Ort und Stelle beleiben müssen, weil Zeiger darauf referenzieren. Indizes wären eine Lösung, aber nicht überall. Und wenn am Ende an der Adresse nicht genug Speicher vorhanden ist, dann müssen wir den alten Block wiederherstellen, also wieder kopieren.

    Ich habe mich daher für 2) entschieden, obwohl das ebenfalls Probleme mit sich bringt. Zum Beispiel haben wir unter Windows das Problem, dass die Auflösung, mit der virtueller Speicher reserviert wird, mindestens 64 KiB betragen, d.h. dass wir, wenn wir die Daten im Block, ohne Speicherlöcher, haben wollen, immer mindestens 64 KiB anfordern müssen (das Problem haben wir bei 2 MiB-Pages nicht, weil wir da bereits deutlich über 64 KiB sind). Speicherbereiche komplett zu reduzieren ist ebenfalls nicht mehr möglich (da wir mit Zero-Copy arbeiten), es sei denn, wir können Mappings komplett entfernen (wenn die neue Länge also 4.7 Mapping-Einträge entfernen lassen würde - Mapping, nicht Pages - können wir maximal 4 Einträge wieder loswerden. Und da jeder Mapping-Eintrag variabel lang sein kann, müssen wir dafür wieder jeden Mapping-Eintrag durchgehen, bestimmen, ob wir jetzt das Maß erreicht haben, und dann die durchlaufenen Mappings minus 1 wieder freigeben).

    Für den Fall, dass uns der Programmierer erlaubt hat, den Speicherbereich zu verschieben, wenn wir nicht genug Speicher haben, habe ich mir gedacht, dass, wenn wir schon ein neues Mapping erstellen müssen, wir das dann direkt als ein Mapping behandeln können, selbst wenn in der vorherigen Tabelle n Mappings drin waren. Das hat den Vorteil, dass wir dann später das Mapping komplett loswerden können (die alten Mappings müssen wir eh loswerden, aber wenn wir diese nicht zusammenfassen, wenn der Inhalt umgezogen wird, dann müssen wir später, wenn das Mapping nicht mehr gebraucht wird, wieder n Mapping-Einträge freigeben - wir würden hier also Overhead sparen). Auf der anderen Seite bedeutet das allerdings, dass das Mapping, einmal zusammengefasst, nicht mehr ohne Kopie reduziert werden, sondern nur noch entfernt werden kann.

    Dadurch, dass jedes Mapping separat wäre, können sich auch die Erstellungspptionen jedes Mapping-Eintrages ändern. Dass wir zu Anfang also 10 64-KiB-Chunks (nicht Pages, aber wir müssen ja den virtuellen Speicher komplett ausnutzen, sonst lässt Windows da Löcher) reservieren, gefolgt von 5 2-MiB-Pages, wieder gefolgt von 32 64-KiB-Chunks - unter Linux wäre das nicht möglich, unter Windows aber schon.

    Meine Fragen wären jetzt:

    1. Habe ich bezüglich der Implementieren der Mapping-Tabelle irgendetwas übersehen, oder fällt jemandem etwas ein, was ich noch beachten müsste/könnte?
    2. Habe ich eventuell eine nützliche Funktion von Windows übersehen, die es mir erlaubt, eine ähnliche Funktionalität wie mremap zu verwenden?

    Für die, die sich wundern: es handelt sich um eine plattform-übergreifende API, die unter Linux und Windows laufen, einfach in bestehende Programme integrierbar sein und die Möglichkeiten, die Hardware und Betriebssystem anbieten, so gut wie möglich ausnutzen muss.

    EDIT: Ich sollte dazuschreiben: die Gründe, warum ich das nicht einfach realloc machen lassen will, sind folgende:

    1. ich habe bereits eine Speicherstruktur, die ohne großen Overhead Objekte der Reihe nach anlegen kann und dafür sogar eine Array-Abstraktion anbietet.
    2. realloc unterstützt - zumindest nachprüftbarereweise auf Linux, auf Windows weiß ich es nicht (weil ich da /sys-Dateien nicht catten kann) keine Hugepages, sondern arbeitet halt mit der Default-Pagesize.

    EDIT2: realloc kann Hugepages schon über madvise aktivieren. Aber das muss dann ständig gewechselt werden (es gibt Anwendungsfälle, wo man explizit keine Hugepages haben will, z.B. in der Mapping-Tabellenverwaltung auf WIndows), und zudem wird es auf Windows (wo wir das Problem ja haben) nicht unterstützt.

    EDIT3: Ich könnte auch HeapAlloc und HeapReAlloc nehmen, aber da haben die Microsoft-Programmierer wohl auch auf halber Strecke aufgegeben:

    MSDN schrieb:

    HeapReAlloc is guaranteed to preserve the content of the memory being reallocated, even if the new memory is allocated at a different location. The process of preserving the memory content involves a memory copy operation that is potentially very time-consuming.

    Tolle Wurst.

    0
  • B

    Meinst Du einen Ersatz für std::allocator<T>? Wenn das so ist, dann kommst Du nicht umhin, dass der Speicher beim Vergrößern eines Containers wie std::vector doppelt allokiert ist.
    Wenn nicht, dann kannst Du ja eigene Container schreiben. Und wenn Du z.B. sowas analoges wie std::vector hast, dann kannst Du nachdem Du den neuen Speicher für ein Vergrößertes Array allokiert hast während des Umkopierens (am saubersten über Placement-new) dann Abschnittsweise im alten Speicherblock den Speicher dann decommitten. Die physischen Pages werden dann gleich vom Windows recycelt, da der Speicher für die neuen Pages erst beim ersten Zugriff auf eine Page physisch allokiert werden (beim VirtualAlloc mit MEM_COMMIT wird nur Speicher vom Pagefile subtrahiert, damit der Speicher beim ersten Zugriff im Extremfall durch Paging befriedigt werden kann, und wenn kein Pagefile aktiv ist, dann wird der Speicher gleich beim VirtualAlloc physisch allokiert - deswegen sollte man für Overcommit-Geschichten immer das Pagefile anhaben, selbst wenn tatsächlich nicht gepaget wird); bei large Pages könnte das aber anders sein, da bin ich mir nicht sicher.
    Und es ist nicht kritisch wenn Du mehr Speicher committest als der Container groß ist. Da die Pages erst beim ersten Zugriff physisch zugeordnet werden kann kann man mehr Speicher allokieren als man zunächst braucht - das nennt man Overcommit (und funktioniert auch unter Linux analog).

    Das mit den TLBs ist übrigens nicht so kitisch wenn Du linear auf den Speicher zugreifst; da kannst Du selbst mit 4kB-Pages arbeiten. Wenn Du Random-Access auf den Speicher zugreifst is sieht das anders aus.
    Allerdings musst Du um unter Windows Speicher mit large Pages allokieren zu können dem Process-Token das Recht dazu hinzufügen.Außerdem ist Speicher mit large Pages unter Windows ein bisschen bäh, weil er nicht gepaget werden kann. Außerdem ist das Hinzufügen dieses Rechts zum Process-Token meines Wissens daran gebunden, dass man Administrator oder Power-User ist.

    Da das Umkopieren von solch großen Datenstrukturen kaum über Cache-Hits geht ist der erste Zugriff auf einen 64-Byte-Block (Cachezeilen-Größe) sehr teuer. In Relation dazu ist der Zugriff auf die geladene Cachezeile sehr günstig. Da das in der Relation so extrem ist, ist es fast egal ob Du den Speicher Byte-weise oder per AVX umkopieren würdest wenn der Speicherblock so groß ist. Während Du die restlichen Bytes des Speichers umkopierst holt der Prefetcher schon die nächste Cachezeile beim RAM ab.

    0
  • D

    Bonita.M schrieb:

    Meinst Du einen Ersatz für std::allocator<T>?

    Wir reden hier von C.

    Bonita.M schrieb:

    Wenn das so ist, dann kommst Du nicht umhin, dass der Speicher beim Vergrößern eines Containers wie std::vector doppelt allokiert ist.

    Ordentliche Kernel (Linux z.B.) bekommen das hin, indem, wenn der virtuelle Adressraum an der Stelle zu klein wird, die Pages einfach umgemappt werden (siehe auch hier - dort werden die Nutzerdaten nicht ein einziges Mal kopiert, was geändert wird, sind die Speichermappings).

    Windows kann das im Kernel aber scheinbar nicht, deswegen erstelle ich mir meine eigene Liste für jedes Mal, wenn ich das Mapping "vergrößere" (ich also neuen Speicher vom Kernel anfordere).

    Bonita.M schrieb:

    Wenn nicht, dann kannst Du ja eigene Container schreiben.

    Jaah ... ich habe bereits geschrieben, dass ich einen Array-Basistypen habe, von dem man relativ einfach ableiten kann? Funktionieren tut das unter Linux herrlich (alloziert 2MiB und 1GiB-Pages einfach so, Zero Copy). Das Problem ist die Speicherverwaltung unter Windows, und dass ich um Grunde dabei bin, meine eigene Page Table pro Memory Mapping im Userspace anzulegen.

    Übrigens, nicht falsch verstehen - Speicherallokation und Array-Logik sind ordentlich voneinander abgekapselt. Dem Array ist es komplett egal, wie der Speicher aussieht, Hauptsache, der Allokator sagt an, dass für X Elemente jetzt Speicherbereich vorhanden ist. Das Einzige, was das Array den Allokator NOCH fragt, ist, wo sich die Elemente befinden - und das ist ein einfacher Zeiger, also nix weltbewegendes.

    Bonita.M schrieb:

    Und wenn Du z.B. sowas analoges wie std::vector hast, dann kannst Du nachdem Du den neuen Speicher für ein Vergrößertes Array allokiert hast während des Umkopierens (am saubersten über Placement-new) dann Abschnittsweise im alten Speicherblock den Speicher dann decommitten.

    Um das Umkopieren geht es hier doch?

    Ich alloziere in einem 64 Bit Prozess (heißt: JEDE MENGE virtuellen Speicher) mir 4 MiB. Am Anfang eines riesigen Blocks, der MEM_FREE deklariert ist. Jetzt merke ich, hm, mit 4 MiB komm ich nicht aus, ich brauch mehr Speicher.

    Unter Linux kann ich mremap aufrufen, wahlweise mit MREMAP_MAYMOVE , damit ich dem Kernel sagen kann, dass er ruhig das Mapping verschieben dürfte (wenn denn nicht genug virtueller Speicher vorhanden wäre - und das ist ja bei Wachstum nach oben und am Beginn des genannten RIESIGEN freien Adressblocks ja eh nicht gegeben). mremap kopiert mir den Speicher nicht ein einziges Mal, sondern legt ihn nur um - wie die Rente.

    Unter Windows kann ich nur 50% davon erreichen, es sei denn, ich hacke mir einen Kernel-Treiber zurecht. Ich habe einfach keinen direkten Zugriff auf meine Page Entries, die kann ich vom Userspace nicht so einfach verschieben (wüsst' jedenfalls nicht, wie). Wenn ich also keinen virtuellen Speicher mehr habe, dann MUSS ich umkopieren. ABER: in den oben genannten Beispiel habe ich ja noch MASSIG virtuellen Speicher. Anstatt also umkopieren, lasse ich den Kernel lieber noch mal 4 MIB am Ende meines bestehenden Mappings einfügen, muss nix kopieren, sondern nur Buch darüber führen, wo das neue Mapping liegt (damit ich's später kopieren/zusammenfassen/freigeben kann), und habe nicht eine einzige Kopie angelegt.

    Bonita.M schrieb:

    Die physischen Pages werden dann gleich vom Windows recycelt, da der Speicher für die neuen Pages erst beim ersten Zugriff auf eine Page physisch allokiert werden (beim VirtualAlloc mit MEM_COMMIT wird nur Speicher vom Pagefile subtrahiert, damit der Speicher beim ersten Zugriff im Extremfall durch Paging befriedigt werden kann, und wenn kein Pagefile aktiv ist, dann wird der Speicher gleich beim VirtualAlloc physisch allokiert - deswegen sollte man für Overcommit-Geschichten immer das Pagefile anhaben, selbst wenn tatsächlich nicht gepaget wird);

    Jaah, und ...? Darum geht's doch gar nicht. Wobei ich mir hier nicht sicher bin - das Verhalten, was du beschreibst, ist auf jeden Fall so bei Linux implementiert. Bei Windows bin ich mir (bei Default Page Sizes) nicht sicher.

    Bonita.M schrieb:

    bei large Pages könnte das aber anders sein, da bin ich mir nicht sicher.

    Korrekt - bei anderen Page Sizes verhalten sich Windows und Linux (!) beide so, dass sie die Daten im Speicher halten wollen, und halt nicht auf die Festplatte swappen/pagen. Begründung: Das würde dann Probleme mit I/O verursachen - also kurz: es gibt keine Probleme, sie haben's einfach nur nicht implementiert.

    Bonita.M schrieb:

    Und es ist nicht kritisch wenn Du mehr Speicher committest als der Container groß ist.

    Gerade bei Hugepages ist das Quatsch. Weil der Kernel die Pages immer im Speicher halten will. Stell dir mal vor, ich reserviere 16 1-GiB Hugepages - "weil können wir ja mal gebrauchen". Abgesehen davon, dass Windows eh Probleme mit der ordentlichen Allokation von Hugepages hat - Linux supportet ein Interface, mit dem man über die Boot Line die Anzahl an Pages einer bestimmten Größe angeben kann - weil sofort danach der Speicher fragmentiert, und für so große Pages brauchst du große Blöcke freien Speichers. Andere Programme, die dann ebenfalls Hugepages brauchen, kriegen diese nicht.

    Du siehst, es hat seine Gründe, warum wir das Ganze abstrahieren wollen. 🙂

    Und wenn ich dann neuen Speicher anfordern muss, dann soll nicht wild rumkopiert werden, wenn das komplett unnötig ist. Das lohnt sich (zumindest meinem Verständnis nach) auch schon, wenn wir nur mit 4 KiB arbeiten würden, weil wir den neuen Speicher eh reservieren und irgendwann freigeben müssen - mit meiner Methode sparen wir uns das unnötige Kopieren in jeden Fall.

    Bonita.M schrieb:

    Das mit den TLBs ist übrigens nicht so kitisch wenn Du linear auf den Speicher zugreifst; da kannst Du selbst mit 4kB-Pages arbeiten. Wenn Du Random-Access auf den Speicher zugreifst is sieht das anders aus.

    WIE mit dem Speicher gearbeitet wird, weiß ich im Besten Fall noch gar nicht. 🙂 Deswegen achten wir darauf, lieber von Anfang an die Variablen zu minimieren.

    Bonita.M schrieb:

    Allerdings musst Du um unter Windows Speicher mit large Pages allokieren zu können dem Process-Token das Recht dazu hinzufügen.

    Siehe obigen Post. Manuell habe ich das bereits alles getestet, es geht jetzt um die weitere Logik.

    Bonita.M schrieb:

    Da das Umkopieren von solch großen Datenstrukturen kaum über Cache-Hits geht ist der erste Zugriff auf einen 64-Byte-Block (Cachezeilen-Größe) sehr teuer. In Relation dazu ist der Zugriff auf die geladene Cachezeile sehr günstig.

    Sach an. Mir ging es ja auch nicht um die Reduzierung von Cache-Misses, sondern von TLB-Misses.

    Wobei ich sagen muss, dass meine Implementierung über SSE/AVX gegenüber der glibc-Implementierung rund 16.000 Cycles langsamer ist, gegenüber der Windows-Version aber 1.600 Cycles schneller (beides Durchschnittswerte mehrerer tausend Durchläufe). Da ich das Kopieren aber eh nur für Windows brauche, verbuche ich diesen Aspekt bereits als Erfolg.

    0
  • B

    dachschaden schrieb:

    Wir reden hier von C.

    Igitt, wie kann man heute noch plain C programmieren, das ist doch ein Wartbarkeits und Produktivitäts-Hemmnis.
    Außerdem ist das ein C++-Forum, da sollte man annehmen, dass sich die Fragen um C++ drehen.

    Windows kann das im Kernel aber scheinbar nicht, deswegen erstelle ich mir meine eigene Liste für jedes Mal, wenn ich das Mapping "vergrößere" (ich also neuen Speicher vom Kernel anfordere).

    Ne, das kann Windows definitiv nicht.

    Gerade bei Hugepages ist das Quatsch.

    Ich dachte dabei an normale 4kB Pages. Bei hauptsächlich linearen Speicherzugriffen sind die Kosten für das TLB-Laden nicht hoch.

    Sach an. Mir ging es ja auch nicht um die Reduzierung von Cache-Misses, sondern von TLB-Misses.

    Meine Aussage bezog sich ja auch nicht darauf, sondern auf die Effizienz des Umkopierens mit verschiedenen Methoden.

    Hier http://stackoverflow.com/questions/11621606/faster-way-to-move-memory-page-than-mremap findet sich übrigens ein Beitrag von jemanden der meint, dass mremap langsamer ist als Umkopieren. Ist drei Jahre alt.

    0
  • D

    Bonita.M schrieb:

    Igitt, wie kann man heute noch plain C programmieren, das ist doch ein Wartbarkeits und Produktivitäts-Hemmnis.
    Außerdem ist das ein C++-Forum, da sollte man annehmen, dass sich die Fragen um C++ drehen.

    Nicht sicher, ob Troll oder einfach nur unwissend ...

    Das hier ist die WinAPI-Ecke. Nicht mehr, nicht weniger. Von mehr als dem auszugehen ist komplett unnötig. Und C kann man auch wunderbar objektorientiert programmieren. Vor allem dann, wenn man Templates und Virtualisierung einfach nicht benötigt (und glaube mir: wir benötigen sie nicht).

    Bonita.M schrieb:

    Ne, das kann Windows definitiv nicht.

    Eben. Deswegen die Frage, ob in meinem Ansatz ein Fehler liegt, oder etwas, was man besser machen könnte.

    Bonita.M schrieb:

    Ich dachte dabei an normale 4kB Pages. Bei hauptsächlich linearen Speicherzugriffen sind die Kosten für das TLB-Laden nicht hoch.

    Und mein "Quatsch" bezog sich auf die Aussage, dass es nichts ausmacht, wenn ich mehr commite, als ich brauche. Dem ist leider nicht der Fall bei Hugepages.

    Bonita.M schrieb:

    Meine Aussage bezog sich ja auch nicht darauf, sondern auf die Effizienz des Umkopierens mit verschiedenen Methoden.

    Ja, aber die habe ich eh, wenn ich kopiere. 🙂 Speicher stallt im Verhältnis heutzutage noch schlimmer als vor 20 Jahren. Das einzige, was man da tun kann, ist Prefetching, und versuchen, die CPU nicht noch mit schlimmerem Unsinn zu befüllen.

    Aber gegen TLB-Misses, gegen DIE kann ich was tun.

    Bonita.M schrieb:

    Hier http://stackoverflow.com/questions/11621606/faster-way-to-move-memory-page-than-mremap findet sich übrigens ein Beitrag von jemanden der meint, dass mremap langsamer ist als Umkopieren. Ist drei Jahre alt.

    Kenn ich. Aber da misst er auch das Ummappen ohne Resizing. Ich hingegen will Resizing ohne Kopierung.

    EDIT: Außerdem würde Kopierung erfordern, wieder Pages vom gleichen Typ anzufordern. Kurz, eh schon begrenzten Speicher noch weiter zu begrenzen. Das kann leicht schiefgehen. Wenn der virtuelle Speicher ausläuft, gut, dann geht's halt nicht anders. Aber wenn er das das nicht tut, dann geht's halt auch anders.

    0
  • V

    dachschaden schrieb:

    Das hier ist die WinAPI-Ecke. Nicht mehr, nicht weniger. Von mehr als dem auszugehen ist komplett unnötig. Und C kann man auch wunderbar objektorientiert programmieren. Vor allem dann, wenn man Templates und Virtualisierung einfach nicht benötigt (und glaube mir: wir benötigen sie nicht).

    Jupp, aber RAII ist auch hier supi praktisch: Türlich ziehen wir hier nur Sprachmittel, die Nullkosten oder weniger gegenüber C haben. C ist halt an sich lahm, weil der Compiler weniger weiß.

    Die sind aber völlig egal gegenüber den Betrachtungen, wie Multigigabytespeicher in Mikrosekunden umgemappt werden kann.

    Ich höre meistens spätestens auf, wenn ich sicher bin, daß mein Framework weniger als 1Promille der Zeit frisst, die der Anwendungscode frisst, zum Beispiel wenn ich 160T zur Verfügung stelle und die nur linear durchzulaufen 150min Zeit brauchen, dann muss ich nicht mehr als 10s zum ummappen brauchen.
    Übrigens war's eh nur eine sparse matrix, 10G hätte gereicht. Also bei mir immer.

    0
  • D

    volkard schrieb:

    Jupp, aber RAII ist auch hier supi praktisch: Türlich ziehen wir hier nur Sprachmittel, die Nullkosten oder weniger gegenüber C haben. C ist halt an sich lahm, weil der Compiler weniger weiß.

    Brauch ich nicht. Habe ich mal in ein paar Testprogrammen verwendet, als ich mir C++ angeschaut habe, und danach nie wieder. Irgendwie verursacht es mir Magenschmerzen, wenn man nachgucken muss, was genau für ein Typ hinter einem Objekt steht. Das ist ähnlich elegant wie eine Funktion, die die TID holen muss, um zu prüfen, welcher Thread sie gerade aufruft - nämlich gar nicht.

    Und normalerweise sind Compiler auch intelligenter als die Programmierer, die mit ihnen arbeiten. Außer in den Fällen, wo's dann plötzlich 16K Cycles Unterschied pro Call macht.

    volkard schrieb:

    Die sind aber völlig egal gegenüber den Betrachtungen, wie Multigigabytespeicher in Mikrosekunden umgemappt werden kann.

    Aber nur im besten Fall. Der auf 64 Bit-Systemen fast immer eintritt.

    Aber seien wir mal pessimistisch und sagen, irgendwann muss der Rotz auch auf x86-Prozessoren laufen. Da wird der Worst Case definitiv häufiger zuschlagen - und dennoch wollen wir auch da TLB-Misses verhindern.

    0

  • dachschaden schrieb:

    volkard schrieb:

    ... RAII ...

    Brauch ich nicht. Habe ich mal in ein paar Testprogrammen verwendet, als ich mir C++ angeschaut habe, und danach nie wieder. Irgendwie verursacht es mir Magenschmerzen, wenn man nachgucken muss, was genau für ein Typ hinter einem Objekt steht. Das ist ähnlich elegant wie eine Funktion, die die TID holen muss, um zu prüfen, welcher Thread sie gerade aufruft - nämlich gar nicht.

    Bin mir angesichts dieser Aussage gerade nicht sicher ob du weisst was RAII ist/bedeutet. Weil sauberer C Code diesbezüglich ("nachgucken was genau für ein Typ hinter einem Objekt steht") nicht viel anders ist als sauberer C++ Code. Nur dass man in C halt immer und immer wieder Code wiederholen muss -- und in C++ halt nicht.

    0
  • D

    hustbaer schrieb:

    Bin mir angesichts dieser Aussage gerade nicht sicher ob du weisst was RAII ist/bedeutet. Weil sauberer C Code diesbezüglich ("nachgucken was genau für ein Typ hinter einem Objekt steht") nicht viel anders ist als sauberer C++ Code.

    Sauberer C-Code muss im Zweifelsfall gar nichts dynamisch nachschauen. Das Array-Interface habe ich implementiert mit der Größe eines der Elemente, die gespeichert werden soll, mit der das Array dann rechnet, und dieser Wert steht bereits zur Kompilierzeit fest. Da habe ich - meinem Verständnis nach anders als bei RTTI - dann keine andere Metadaten und brauche sie auch gar nicht.

    In C nennt man die Art von Abstrahierung, die C++ da macht, übrigens Type-Punning, und ist UB. 🙂 Selbst, wenn man sich sicher ist, dass das ABI das gleiche ist.

    hustbaer schrieb:

    Nur dass man in C halt immer und immer wieder Code wiederholen muss -- und in C++ halt nicht.

    Bin mir angesichts dieser Aussage gerade nicht sicher, ob du weißt, wie man ordentlich in C programmiert. Weil du, wenn du ordentlich deine Strukturen pflegst und deine Funktionen in Module packst, nur selten Instanzen hat, in denen Code sich immer und immer wieder wiederholen muss.

    Und je generalisierter das Interface, desto besser.

    Was sich ändern kann, sind die Implementierungen. Weil (zumindest mein Eindruck) eher die C- und Assembler-Leute sich mit Unterschieden zwischen verschiedenen CPU-Architekturen auseinandersetzen und dann gegebenenfalls die Implementierung ändert. memcpy der glibc ist das beste Beispiel dafür - Atom bringt Prefetch, dafür muss die Richtung, in der kopiert wird, aber geändert werden, also wird das halt geändert für den Atom.

    Jetzt simmer aber heftig vom Thema abgekommen. 🙂

    0
  • J

    dachschaden schrieb:

    ... RTTI ...

    RAII ist doch nicht das Selbe wie RTTI...

    Einen C vs C++-Krieg brauchst du hier gar nicht runterzubrechen, das ist sowas von 1999.

    0
  • D

    Jodocus schrieb:

    RAII ist doch nicht das Selbe wie RTTI...

    Ugh, da hab' ich mich verlesen. Ja, stimmt. RAII != RTTI. Ich bin blöd.

    0
  • V

    dachschaden schrieb:

    volkard schrieb:

    Jupp, aber RAII ist auch hier supi praktisch: Türlich ziehen wir hier nur Sprachmittel, die Nullkosten oder weniger gegenüber C haben. C ist halt an sich lahm, weil der Compiler weniger weiß.

    Brauch ich nicht. Habe ich mal in ein paar Testprogrammen verwendet, als ich mir C++ angeschaut habe, und danach nie wieder. Irgendwie verursacht es mir Magenschmerzen, wenn man nachgucken muss, was genau für ein Typ hinter einem Objekt steht.

    (kleine RTTI/RAII-Verwechslung)
    Da sind wir einer Meinung. Ich verwende in C++ auch nie RTTI. RTTI ist nur ein Notnagel, falls man eine total verbuggte und fehlgeplante Fremdlib benutzen muss.
    RAII ist kostenlos im Vergleich zu C oder im Zusammenhang mit Exceptions sogar schneller als C. Das wollen wir schon nehmen. Es ist auch angenehm zu benutzen und vermeidet viele Fehler.

    0

  • dachschaden schrieb:

    Wobei ich sagen muss, dass meine Implementierung über SSE/AVX gegenüber der glibc-Implementierung rund 16.000 Cycles langsamer ist, gegenüber der Windows-Version aber 1.600 Cycles schneller (beides Durchschnittswerte mehrerer tausend Durchläufe). Da ich das Kopieren aber eh nur für Windows brauche, verbuche ich diesen Aspekt bereits als Erfolg.

    Hast du bei Windows/MSVC gegen memcpy verglichen oder gegen memmove ?
    Ich frag' nur weil memmove bei mir (deutlich) schneller ist (ca. ~9 GB/s vs. ~6.1 bei memcpy ).
    (Oder gegen eine WinAPI-Funktion?)

    dachschaden schrieb:

    Ugh, da hab' ich mich verlesen. Ja, stimmt. RAII != RTTI.

    OK. Jetzt verstehe ich was du geschrieben hast 💡 Kam mir halt komisch vor, aber bin nicht auf die Idee gekommen dass du RTTI meinen könntest.

    0
  • D

    volkard schrieb:

    RAII ist kostenlos im Vergleich zu C oder im Zusammenhang mit Exceptions sogar schneller als C. Das wollen wir schon nehmen. Es ist auch angenehm zu benutzen und vermeidet viele Fehler.

    Sehe ich nicht so. Gerade bei dem Topic - dem Halten der Mappings, die mir der Kernel zurückgibt - muss ich diese ja irgendwo speichern. Dafür hole ich mir einmal unbürokratisch 64 KiB Speicher. Aber das muss ich ja nur dann machen, wenn ich das Mapping auch wirklich haben will. Jetzt gibt es aber Codepfade innerhalb von Funktionen, wo ein Mapping gar nicht gebraucht wird. Sprich, ich habe das Objekt auf dem Stack, muss es aber in einem Codepfad gar nicht verwenden. Ich will den Code aber dennoch in einer Funktion halten, sonst schreibe ich eventuell anderen Code wieder und wieder.

    Wenn die Funktion bei RAII aufgerufen wird, habe ich bei C++ direkt zwei Kernel-Calls sitzen, selbst, wenn ich das Objekt gar nicht brauche (allozieren + freigeben). Ja, kannst du sagen, dann pack die Tabelleninitialisierung doch in eine eigene Funktion deiner Klasse/Stuktur. Dafür brauche ich aber nicht RAII - das kann ich auch über eine <Strukturname>_init -Funktion regeln (und <Strukturname>_free für's freigeben). Nur in diesen Funktionen muss ich mich dann um Ressourcenmanagement kümmern.

    Das sind alles so Automatismen, die gut gemeint sind, aber dann häufig doch nur im Weg liegen. Ja, Programmierer vergessen die manchmal. Aber deswegen jetzt die Programme langsamer werden zu lassen ist auch blöd.

    hustbaer schrieb:

    Hast du bei Windows/MSVC gegen memcpy verglichen oder gegen memmove ?

    Zuerst gegen memcpy , jetzt auch mal gegen memmove . MSVC's memmove und mein memcpy brauchen beide so ungefähr 380K Cycles zum Kopieren von 2 MiB.

    Habe außerdem gemerkt: prefetching hilft, aber nur, wenn man den Schreibzugriff cached, und dann am Besten 2 oder 3 Iterationen vorher laden. Sonst wird's mit den Stalls echt lächerlich.
    Nichttemporär (zu schreiben) ist übrigens so ziemlich das langsamste im Universum, hat den Durchsatz verdoppelt, das nicht zu verwenden.

    hustbaer schrieb:

    Ich frag' nur weil memmove bei mir (deutlich) schneller ist (ca. ~9 GB/s vs. ~6.1 bei memcpy ).
    (Oder gegen eine WinAPI-Funktion?)

    CopyMemory ist auf meiner Hardware nochmal durchschnittlich 0.5K Cycles schneller als meine Implementierung. Hat mich erstaunt, weil ich vor gar nicht langer Zeit gelesen habe, dass auf Windows memcpy intern CopyMemory aufrufen würde.

    Ich glaub' inzwischen, der Speicher hat sowas wie eine Tageslaune, und gibt mir mal schnelleren, mal weniger schnellen Zugriff. Oder die Ausführungen fielen manchmal unglücklich mit dem DRAM-Refresh zusammen.
    Der Grund, warum dein memmove so viel schneller ist, könnte mit dem Prefetching zusammenhängen - soweit ich weiß sind CPUs da höllisch eigen. Hm ... vielleicht sollte ich mal schauen, ob das ebenfalls Ausschlag auf den Durchsatz hat. EDIT: "sind CPUs mit der Kopierrichtung höllisch eigen", wollte ich schreiben.

    EDIT2: Nein, die Kopierrichtung zu ändern bringt nichts.

    0

  • Achja, nur kleiner Tip: Vergleich auch mal gegen rep movsb .
    Ist bei mir gleich schnell wir memmove (also auch 9 GB/s).

    0
  • D

    hustbaer schrieb:

    Achja, nur kleiner Tip: Vergleich auch mal gegen rep movsb .
    Ist bei mir gleich schnell wir memmove (also auch 9 GB/s).

    Mit rep movsb komme ich beinahe auf glibc's Durchsatz - ist zwar immer noch ein wenig langsamer, aber da werde ich von mir aus nichts mehr dran machen. Vielleicht noch mal Prefetching, mehr aber nicht.

    Für Windows musste ich mir erst anschauen, wie ich MASM-Support da reingepfriemelt bekomme (MS hat für die 64-Bit-Version Inline-Assembly rausgekommen). Habe dennoch diesen Code hier ans Laufen bekommen:

    _text SEGMENT

.code

memcpy_page_4KiB PROC
	push RDI
	push RSI

	cld

	;Windows verwendet für x64 folgende Convention:
	;1. Parameter in RCX
	;2. Parameter in RDX
	mov RDI,RCX
	mov RSI,RDX
	mov RCX,1000h
	rep movsb

	pop RSI
	pop RDI

	ret

memcpy_page_4KiB ENDP

END

    Ich bin mir sicher, dass man das noch optimieren könnte - aber ich war noch nie der große Assembly-Held.

    Jedenfalls benötige ich damit nur noch 310K Cycles anstelle von 370-380K Cycles. Kann man das mit Memory-Stalls erklären, oder benötigt das Ausführen der AVX-Instuktionen so lange, dass ich damit kaum mithalten kann?

    Ich hätte auch erwartet, dass es zumindest einen messbaren Unterschied zwischen

    mov RCX,1000h
	rep movsb

    und:

    mov RCX,200h
	rep movsq

    gibt, aber die halten sich eigentlich die Waage.

    0

  • MASM muss man im Projekt einfach nur aktivieren:
    http://stackoverflow.com/questions/20078021/how-to-enable-assembly-language-support-in-visual-studio-2013

    Wenn du danach .asm Files im Projekt anlegst sollten die automatisch mit MASM verknüpft werden. (Wenn du davor .asm Files anlegst musst du es nachträglich mit Hand machen, also in den File-Properties als Build-Tool MASM einstellen.)

    Was die verwunderliche Geschwindigkeit von rep movsb angeht: soweit ich weiss hat Intel das speziell optimiert. Quasi nen fast perfektes memcpy in Microcode. Möglicherweise haben manche CPUs sogar ne spezielle "Copy-Engine"?

    Auf jeden Fall ist rep movsb vermutlich der Befehl der bei weitem am häufigsten in exakt der Form zum kopieren von Speicherblöcken verwendet wird (also auch häufiger als kompliziertere Schleifen). Daher zahlt es sich aus rep movsb so schnell wie möglich zu machen. Und daher halte ich es auch für halbwegs "zukunftssicher".

    Allerdings gibt es auch Nachteile, auf einigen CPUs ist es wohl deutlich langsamer. Weiss leider nimmer welche es waren, aber wenn du maximale Geschwindigkeit auf allen möglichen CPUs willst/brauchst, dann solltest du ausgiebig testen.

    ps: Misst du mit Workloads die in den Cache passen, oder mit grossen? Ich hab meine Tests mit 1 GiB grossen Blöcken (mit 4K Alignment) gemacht, weil ich die "RAM-to-RAM" Copy-Speed messen wollte. Aber sollte klar sein, 9 GB/s für Cache-to-Cache wären schon sehr mickrig.

    0
  • B

    dachschaden schrieb:

    Für Windows musste ich mir erst anschauen, wie ich MASM-Support da reingepfriemelt bekomme (MS hat für die 64-Bit-Version Inline-Assembly rausgekommen). Habe dennoch diesen Code hier ans Laufen bekommen:

    Für fast alle x86-Instruktionen die man nicht indirekt durch Standard-C(++) ausdrücken kann gibt es Intrinsics, so auch für MOVSB:
    https://msdn.microsoft.com/de-de/library/hhta9830.aspx
    Da man eben für fast alles was sonst nur in Assembler ging Intrinsics hat, ist Assembler fast nie nötig.

    0
  • D

    hustbaer schrieb:

    MASM muss man im Projekt einfach nur aktivieren:
    http://stackoverflow.com/questions/20078021/how-to-enable-assembly-language-support-in-visual-studio-2013

    Nein, eben nicht. Die Datei war noch vom Build ausgeschlossen (frag' mich nicht, warum, gesetzt habe ich es nicht - die ASM-Datei war ja komplett neu).

    hustbaer schrieb:

    Auf jeden Fall ist rep movsb vermutlich der Befehl der bei weitem am häufigsten in exakt der Form zum kopieren von Speicherblöcken verwendet wird (also auch häufiger als kompliziertere Schleifen). Daher zahlt es sich aus rep movsb so schnell wie möglich zu machen. Und daher halte ich es auch für halbwegs "zukunftssicher".

    Allerdings gibt es auch Nachteile, auf einigen CPUs ist es wohl deutlich langsamer. Weiss leider nimmer welche es waren, aber wenn du maximale Geschwindigkeit auf allen möglichen CPUs willst/brauchst, dann solltest du ausgiebig testen.

    Hm. Notfalls kann man immer noch auf den Prozessor prüfen (CPUID-Interface habe ich hier).

    hustbaer schrieb:

    ps: Misst du mit Workloads die in den Cache passen, oder mit grossen? Ich hab meine Tests mit 1 GiB grossen Blöcken (mit 4K Alignment) gemacht, weil ich die "RAM-to-RAM" Copy-Speed messen wollte. Aber sollte klar sein, 9 GB/s für Cache-to-Cache wären schon sehr mickrig.

    Workloads, die in den Cache passen.

    Ich habe allerdings auch mal versuchsweise das Kopieren von einem GiB gemessen, 560M Cycles. Allerdings werde ich da auch ein paar TLB-Misses gehabt haben, einfach, weil ich gerade nicht mit 1-GiB-Pages gebootet habe (Bei 1-GiB werden die Pages schon beim Booten reserviert, und man kann sie danach nicht mehr freigeben, deswegen sind die standardmässig aktiviert - den Platz möcht ich noch für andere Sachen haben). Wenn ich dann mit 1024 2-MiB-Pages arbeite (1 GiB-Source, 1 GiB-Destination), habe ich ungefähr einen Durchsatz von 6 GiB/s. Auf Linux jetzt.

    @Bonita.M: damit bin ich nochmal um 10K-20K Cycles schneller. Vielen Dank!

    0

  • @Bonita.M
    Sehr cool. Danke auch von mir, kannte ich noch nicht.

    0

  • @dachschaden
    Du solltest auf jeden Fall immer alle Varianten mit der selben Programmausführung ausführen und vergleichen, und immer mehrere Versuche machen. Und mit den selben Pufferadressen. Und dann den schnellsten raussuchen. Und so lange versuchen bis z.B. 100 Ausführungen zu keiner Verbesserung mehr geführt haben. Damit bekommt man zumindest halbwegs reproduzierbare Resultate die kaum noch von Sonnenflecken beeinflusst werden.

    Ca so.

    #include <intrin.h>
#include <windows.h>
#include <immintrin.h>

// candidates

typedef void __stdcall RtlCopyMemoryType(void*, const void*, size_t Length);

RtlCopyMemoryType* MyRtlCopyMemory;
RtlCopyMemoryType* MyRtlMoveMemory;

void char_copy(unsigned char const* s, unsigned char* d, size_t n)
{
	while (n--)
		*d++ = *s++;
}

void int_copy(unsigned char const* s, unsigned char* d, size_t n)
{
	size_t n4 = n / 4;
	int const* s4 = reinterpret_cast<int const*>(s); // strict aliasing, yes, I know
	int* d4 = reinterpret_cast<int*>(d);

	s += n4 * 4;
	d += n4 * 4;
	n = n % 4;

	while (n4--)
		*d4++ = *s4++;

	while (n--)
		*d++ = *s++;
}

void avx_copy(unsigned char const* s, unsigned char* d, size_t n)
{
	size_t n128 = n / 128;
	__m256i const* s32 = reinterpret_cast<__m256i const*>(s); // strict aliasing, yes, I know
	__m256i* d32 = reinterpret_cast<__m256i*>(d);

	s += n128 * 128;
	d += n128 * 128;
	n = n % 128;

	while (n128--)
	{
		auto r1 = _mm256_loadu_si256(s32);
		auto r2 = _mm256_loadu_si256(s32 + 1);
		auto r3 = _mm256_loadu_si256(s32 + 2);
		auto r4 = _mm256_loadu_si256(s32 + 3);
		_mm256_storeu_si256(d32, r1);
		_mm256_storeu_si256(d32 + 1, r2);
		_mm256_storeu_si256(d32 + 2, r3);
		_mm256_storeu_si256(d32 + 3, r4);
		s32 += 4;
		d32 += 4;
	}

	while (n--)
		*d++ = *s++;
}

extern "C" void repmovsb(unsigned char const* s, unsigned char* d, size_t n); // implemented in the .asm file

// timing

#include <chrono>
#include <iostream>
#include <cassert>

using namespace std;
using namespace std::chrono;

extern "C" __declspec(dllexport) volatile void* g_dummy1 = 0;
extern "C" __declspec(dllexport) volatile void* g_dummy2 = 0;
extern "C" __declspec(dllexport) volatile int g_dummy3 = 0;

nanoseconds baseline = nanoseconds(0);

unsigned char* buffer0;
unsigned char* buffer1;
//size_t const buffer_size = 1024 * 1024 * 1024;
//size_t const repeat = 1;
//size_t const buffer_size = 2048 * 1024;
//size_t const repeat = 10;
//size_t const buffer_size = 64 * 1024;
//size_t const repeat = 100;
size_t const buffer_size = 4 * 1024;
size_t const repeat = 1000;

void optimization_barrier()
{
	_ReadWriteBarrier();
	g_dummy1 = buffer0;
	g_dummy2 = buffer1;
	g_dummy3++;
}

template <class F>
nanoseconds measure_once(F fun)
{
	auto const t0 = high_resolution_clock::now();

	for (size_t i = 0; i < repeat; i++)
	{
		optimization_barrier();
		fun();
		optimization_barrier();
	}

	auto const t1 = high_resolution_clock::now();
	return duration_cast<nanoseconds>(t1 - t0);
}

template <class F>
nanoseconds measure(F fun)
{
	nanoseconds best_duration;

	for (size_t i = 0; i < 100; i++)
	{
		nanoseconds duration = measure_once(fun);
		if (duration < best_duration || i == 0)
		{
			best_duration = duration;
			i = 0;
		}
	}

	return best_duration;
}

template <class F>
void measure(char const* name, F fun)
{
	nanoseconds best_duration = measure(fun) - baseline;

	auto gbps = 1.0 * buffer_size * repeat / best_duration.count();
	cout << name << ": " << best_duration.count() << " ns (" << gbps << " GB/s)\n";
}

unsigned char* aligned_alloc(size_t size)
{
	auto buf = new unsigned char[size + 4096];
	uintptr_t offset = reinterpret_cast<uintptr_t>(buf) % 4096;
	buf += 4096 - offset;
	offset = reinterpret_cast<uintptr_t>(buf) % 4096;
	assert(offset == 0);
	return buf;
}

int main(int argc, char *argv[])
{
	auto ntdll = ::LoadLibraryW(L"ntdll.dll");
	MyRtlCopyMemory = reinterpret_cast<RtlCopyMemoryType*>(GetProcAddress(ntdll, "RtlCopyMemory"));
	MyRtlMoveMemory = reinterpret_cast<RtlCopyMemoryType*>(GetProcAddress(ntdll, "RtlMoveMemory"));

	buffer0 = aligned_alloc(buffer_size);
	buffer1 = aligned_alloc(buffer_size);

	baseline = measure([]() {});
	cout << "baseline: " << baseline.count() << " ns\n";

	measure("nothing", []() { });
	measure("memcpy", []() { memcpy(buffer0, buffer1, buffer_size); });
	measure("memmove", []() { memmove(buffer0, buffer1, buffer_size); });
	measure("char_copy", []() { char_copy(buffer0, buffer1, buffer_size); });
	measure("int_copy", []() { int_copy(buffer0, buffer1, buffer_size); });
	measure("avx_copy", []() { avx_copy(buffer0, buffer1, buffer_size); });
	measure("repmovsb", []() { repmovsb(buffer0, buffer1, buffer_size); });
	measure("__movsb", []() { __movsb(buffer0, buffer1, buffer_size); });
	measure("RtlCopyMemory", []() { MyRtlCopyMemory(buffer0, buffer1, buffer_size); });
	measure("RtlMoveMemory", []() { MyRtlMoveMemory(buffer0, buffer1, buffer_size); });

	return 0;
}

    Damit bekomme ich (Haswell Xeon E3-1245 v3 @ 3.4 GHz)

    // 1 GiB (x1)
memcpy: 173110767 ns (6.20263 GB/s)
memmove: 120273184 ns (8.92752 GB/s)
char_copy: 374367046 ns (2.86815 GB/s)
int_copy: 179932513 ns (5.96747 GB/s)
avx_copy: 173484789 ns (6.18926 GB/s)       <----------- ???
repmovsb: 121840513 ns (8.81268 GB/s)
__movsb: 121446265 ns (8.84129 GB/s)
RtlCopyMemory: 111961087 ns (9.59031 GB/s)  <----------- ???
RtlMoveMemory: 111988860 ns (9.58793 GB/s)  <----------- ???

// 2 MiB (x10)
memcpy: 1159800 ns (18.082 GB/s)
memmove: 943356 ns (22.2308 GB/s)
char_copy: 6663866 ns (3.14705 GB/s)
int_copy: 1953426 ns (10.7358 GB/s)
avx_copy: 1156177 ns (18.1387 GB/s)         <----------- ???
repmovsb: 943054 ns (22.2379 GB/s)
__movsb: 930677 ns (22.5336 GB/s)
RtlCopyMemory: 1125687 ns (18.63 GB/s)
RtlMoveMemory: 1130216 ns (18.5553 GB/s)

// 64 KiB (x100)
memcpy: 219161 ns (29.9031 GB/s)
memmove: 213425 ns (30.7068 GB/s)
char_copy: 2021047 ns (3.24268 GB/s)
int_copy: 535525 ns (12.2377 GB/s)
avx_copy: 217652 ns (30.1105 GB/s)
repmovsb: 215840 ns (30.3632 GB/s)
__movsb: 215538 ns (30.4058 GB/s)
RtlCopyMemory: 218859 ns (29.9444 GB/s)
RtlMoveMemory: 219161 ns (29.9031 GB/s)

// 4 KiB (x1000)
memcpy: 66412 ns (61.6756 GB/s)
memmove: 42866 ns (95.5536 GB/s)
char_copy: 1154064 ns (3.5492 GB/s)
int_copy: 324515 ns (12.6219 GB/s)
avx_copy: 31999 ns (128.004 GB/s)           <----------- ???
repmovsb: 42564 ns (96.2316 GB/s)
__movsb: 40753 ns (100.508 GB/s)
RtlCopyMemory: 69733 ns (58.7383 GB/s)
RtlMoveMemory: 69431 ns (58.9938 GB/s)

    Also durchaus eigenartige Resultate 🙂

    ps:
    Falls du die Seite noch nicht kennst, SEHR COOLE Übersicht über die ganzen Intel Intrinsics:
    https://software.intel.com/sites/landingpage/IntrinsicsGuide/#

    pps: Beim avx_copy fehlen vermutlich noch irgendwelche Fences.

    0
Anmelden zum Antworten