zeitgemäßer Memory-Manager

Hier kann über allgemeine Themen diskutiert werden, die sonst in kein Forum passen.
Insbesondere über Szene, Games, Kultur, Weltgeschehen, Persönliches, Recht, Hard- und Software.
Antworten
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

zeitgemäßer Memory-Manager

Beitrag von Krishty »

Hi,


Kurz: Aramis und ich sind unzufrieden mit dem Speicher-Management der WinAPI. Insbesondere geht es darum, dass die Realisierung von Alignment zu eckig und das Konzept an sich zu schwerfällig ist. Wir würden gern eigene Speicher-Manager entwickeln (von ganz unten – also rohe Seiten vom OS anfordern und verwalten) und haben uns gedacht, dass in der Community sicher ein ausgereifteres Resultat entwickelt werden kann, als wenn jeder sein eigenes Süppchen kocht. Uns schwebt Plattformunabhängigkeit, Thread-Sicherheit, Alignment-Support und einfache Bedienbarkeit vor.

Die Frage ist nun: Besteht Interesse daran, einen solchen Memory-Manager zu benutzen oder gar zu pflegen?


Ausführlich: Unter Windows stehen einem mindestens vier Möglichkeiten zur Verfügung, Speicher zu allokieren. GlobalAlloc() und LocalAlloc() sind veraltet und nurnoch Wrapper für HeapAlloc(). Letzteres ist zeitgemäß und bietet die Benutzung eines Low-Fragmentation-Heaps an, unterstützt jedoch keine Ausrichtung. Das resultiert darin, dass man für ausgerichteten Speicher Alignment - 1 + sizeof(void *) zusätzliche Bytes allokieren und darin die Originaladresse unterbringen muss, also ein nicht unerheblicher Overhead sowohl an Platz als auch an Zeit und Komplexität. Dann bleiben noch die CRT-Funktionen à la malloc(), die sich in all ihren Varianten fast unmöglich kapseln lassen und intern wieder nur auf WinAPI-Funktionen zurückgreifen (natürlich auch mit entsprechendem Overhead). Zu guter Letzt kann man den Speicher auch direkt per VirtualAlloc() verwalten, muss dafür aber einen eigenen Allokator implementieren.

Uns schwebt ein Mehrschichtenmodell aus
• Plattformspezifischer Speicherallokation,
• Bereichs- und Thread-Verwaltung,
• Spezialisierungen für High-Performance- oder Low-Fragmentation-Heaps und
• sprachspezifischen Features (alloc()-Funktionen für C, new- und delete-Operatoren für C++, Allocator-Klassen für die C++-STL, usw)
vor. Wir sehen darin eine Menge Chancen, den Programmierkomfort und (unter dem Gesichtspunkt z.B. von zunehmender Parallelisierung, insbesondere aber durch Anpassbarkeit) die Leistungsfähigkeit zu erhöhen.

Wir sind leider keine Spezialisten auf dem Gebiet; d.h. dass Leute, die sich mit sowas gut auskennen, ganz besonders eingeladen sind, zu helfen (sogar, wenn sie nur lenkend in die Diskussion eingreifen wollen. Achja; es wird hier eine offene Entwicklungsdiskussion geben).


Gruß, Ky
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
glassbear
Establishment
Beiträge: 324
Registriert: 08.04.2003, 18:09
Alter Benutzername: Enrico_
Echter Name: Enrico
Wohnort: San Diego
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von glassbear »

Die google perftools haben einen performanten (gerade was multithreading angeht) Memory Manager. Ist Open source, aber wie es mit Windows aussieht, weiß ich nicht ...
Ein Hoch auf uns Männer... Auf die Frau, die uns HAT ( oder hat, und nicht weiß, dass sie uns hat ) ...auf die Idiotinnen ... besser gesagt VOLLPFOSTINNEN ... die uns hatten und uns verloren haben ... und auf die GLÜCKLICHEN, die das Vergnügen & Glück haben werden uns kennenzulernen!
Jörg
Establishment
Beiträge: 296
Registriert: 03.12.2005, 13:06
Wohnort: Trondheim
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von Jörg »

Von einem generischen Allokator, welcher die gleichen Interfaces wie das klassische malloc()/free() aus der C-Runtime bietet, wuerde ich die Finger lassen. Der Aufwand, die bestehenden Implementierungen um _Laengen_ zu schlagen, lohnt sich m.E. nicht. Der, dessen C-Runtime auch immer heute nicht ordentlich mit Multicore-Umgebungen klar kommt aber auf diesen zwangweise zu benutzen ist, wird sich schleunigst selber darum kuemmern, schon alleine der schlechten Presse wegen. D.h. messen/profilen und publizieren ist empfohlen ;) Meint Ihr, MS oder Sony wuerden sich 5% "for free" entgehen lassen, wenn sie einfach zu implementieren waeren?

Seit die glibc auf einen DLMalloc-basierten Allokator umgestiegen ist, hat man bei allgemeinen Aufgaben eigentlich keinen Grund mehr, richtig zu meckern. Bzw. genau dort eine Stelle, an der man -zig Anwendungsprogrammierer noch gluecklicher machen kann, wenn man ein paar %te rausholt.

Die einzige Stelle, an der sich aus meiner Sicht Arbeit lohnt, sind den Problemen angepasste Allokatoren zu schreiben, z.B. Small-Block oder Object-Pooling. Da kann man wirklich noch was reissen, aber auch hier gilt, messen, messen, messen.
Mein letzte (beruflich bedingte) Implementierung eines Multicore-fähigen Small-Block-Allokators zeigte, dass er bei Verwendung von naivem (lock-basiertem) Zugriff nicht wirklich besser war als die blanke glibc-Standardimplementierung via malloc(). Lock-free sah die Sache freilich anders aus (zum Glueck)! Vielleicht reicht das dem einen oder anderen ja als Ansporn. Ich habe keinen Vergleich auf Windows gefahren, sondern dort einfach die auch unter Linux bessere Implementierung verwendet *shame on me*.

Neben der Fingerarbeit, dass zu "Templaten", ist eine grosse Huerde fuer "Unbedarfte" eine Lock-freie, das Speichermodel und Cache-Lines beachtende Implementierung zu bauen. Daher nur ein paar Stichpunkte:

* Cache-Lines
- Schlechte/Unpassende Platzierung von Variablen (Sharing generell) macht die Performance zunichte
- z.B. waere ein SB-Allokator, dessen Speicher durch verschiedene Threads benutzt wird, aber aus dem gleichen Pool kommt, sehr schlecht fuer die Performance, wenn jeweils eine halbe Cacheline fuer CPU und die andere Haelfte fuer CPU1 zugewiesen wird
- Variieren in der Groesse von Architektur zu Architektur
- sind zum Glueck compile-time constant fuer native Applikationen

* Speichermodel
- Unbedingt auf nicht-x86-Architekturen in Multicore-Varianten testen, die meisten bieten nur ein "Weak memory model", bei dem Schreib- und Lesezugriffe aus Sicht anderer Cores nicht in Programmreihenfolge erfolgen muessen
- fuer den "kleinen Mann" sollte eine alte PS3 (mit Linux drauf) die groebsten Schnitzer aufzeigen
- alles andere (ARM, IA64, Sparc, Alpha von Ebay?) bei jeder Gelegenheit testen, also immer einen USB-Stick mit einer aktuellen Implementierung dabeihaben, man weiss nie, wann man kurzfristig die Gelegenheit bekommt ;)
- Unis oder Rechenzentren haben oft Exoten stehen, ein paar Stunden pro Woche bekommt man vielleicht Zugriff

* Lock-Freies Programmieren
- Ist ohne Beachtung des vorigen Punktes nicht "sicher" moeglich
- Mit C++0x gibt's ja endlich die atomic<>-Primitiven
- Jede Publikation/Algoritmus genau pruefen
- Immer eine Lock-basierte Referenzimplementierung haben
- Ueber System und Compiler-Barrieren (Barriers) bzw. Acquire & Release - Semantiken informieren (gibts ja auch bei C++0x)
- jegliche Verwendung von gemeinsam genutzten Variablen minimieren
. die Trick-Kiste sollte hier voll ausgenutzt werden

* Achtung bei "Buchfuehrung/Statistiken"
- Eine Handvoll globale Variablen falsch verwendet ("Ach, da nehm ich schnell ein atomic_inc usw.") kann hier mehr Performance kosten als der Allokator am Ende bringt

Besser wird es auch noch, wenn man einen Allokator noch besser an ein Problem anpasst, z.B. fuer ein "Single-Producer-Multiple-Consumer"-Muster o.ae. Soetwas im Vorraus ohne ein existierendes Problem zu loesen, halte ich nicht fuer sinnvoll.

Basisimplementierung bei mir war in etwa (auch Bezug nehmend auf Alignment):
- hole 2^n 4KiB-Pages vom OS fuer einen Bereich, aus dem nur mit konstanter Blockgroesse bedient wird
- Am Anfang dieses gesamten Blockes ist der Speicher aller nötigen Verwaltungsinformationen
- Bilde eine einfach-verkettete Liste der freien Blöcke dahinter, unter Beachtung des Alignments
- Verwalte die Frei-Liste ohne Locks
- Bei Speicherfreigabe : Einfach die 2^n-Basisadresse ermitteln, dort sind die Verwaltungsinformationen zu finden
- per TLS jedem Thread einen eigenen Block zuweisen, von dem er moeglichst local alloziert

Und am Ende: Habt Ihr Euch ueberlegt, womit Ihr praxis-relevant benchmarken wollt? Bietet nicht auch IntelTBB entsprechende Allokatoren an?

Ich freue mich schon auf einen langen, erkenntnisreichen Thread im ZFX! Auch wenn es oft Grund zum Jammern geben wird, lassen wir es hier, damit es beim Thema nicht verloren geht ;)
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von Schrompf »

Theoretisch finde ich eine neue Speicherverwaltung eine tolle Sache. Vor allem, wenn das Ding für den Anfang sich einfach transparent in den Hintergrund packt und all meine new's gleich davon profitieren. Aber beim Wort "Profit" kommen meine Zweifel: denkt ihr ernsthaft, dass ihr bzw. wir hier als semiprofessionelle Stümper die gängige Heap-Implementation von Windows oder Linux schlagen? Ich zweifle... ich zweifle.

Ich persönlich würde einen Per-Thread-Heap begrüßen. Wenn eine lockfreie Implementation das gleiche Tempo erreicht - auch prima. Low Fragmentation dagegen finde ich unkritisch - wenn man wirklich nennenswert Vorteile gegenüber dem bestehenden Systen erreichen will, wäre das wohl der einfachste Ansatzpunkt. Und bei der Verbreitung von 64bit-Systemen wäre das wohl auch das einfachste Ziel.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
kimmi
Moderator
Beiträge: 1405
Registriert: 26.02.2009, 09:42
Echter Name: Kim Kulling
Wohnort: Luebeck
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von kimmi »

Habt ihr mal den Low-Fragmentattion-Heap von Windows getestet, wie der sich gegenüber der Best-Fit-Variante verhält, die per default für den Heap aktiviert ist? Dazu unterstützt die WIndows-API Cachezeilen, die euch vielleicht das Leben leichter machen können.

Ansonsten sehe ich für einen eigenen Memory-Manager noch andere Anforderungen, die sicherlich vielen helfen würden:
  • Tracing für Allocs, um Memoryleaks und vor allem versteckte Memory-Leaks leichter finden zu können.
  • Object-Pooling ( wie ja schon vorher angemerkt ).
  • Small-Memory-Allocator-Unterstützung.
  • Gegebenenfalls Stack-Allocator oder Frame-Allocator anbieten, um sich besser auf Probleme einstellen zu können.
  • Sich nicht in Optmierungen des Compilers verfangen. Gerade bei portablen Code ist das wichtig!
  • vereinfachtes Profiling.
Gruß Kimmi
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: zeitgemäßer Memory-Manager

Beitrag von Lord Delvin »

Im ersten Augenblick fand ich die Idee irgendwie gut. Aber wenn man 10 minuten drüber nachdenkt, dann ist das einzige, was mir einfällt, dass das Speichermodell bezüglich threads und objekten etwas unvorteilhaft ist, das was ich gerne hätte wäre allerdings langsamer als das, was zZ implementiert ist, also für euch vermutlich nicht von Interesse. Schaut euch vielleicht mal VisualVM Heap dumps an, da sieht man vielleicht ein bisschen was ich meine, geht aber in die Richtung von dem was kimmi will.

Ihr solltet aber auf jeden Fall drauf achten, dass ihr Objekte in einem Thread allokieren und in einem anderen freigeben könnt.

Gruß
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Jörg
Establishment
Beiträge: 296
Registriert: 03.12.2005, 13:06
Wohnort: Trondheim
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von Jörg »

Schrompf hat geschrieben:Ich persönlich würde einen Per-Thread-Heap begrüßen. Wenn eine lockfreie Implementation das gleiche Tempo erreicht - auch prima.
Beides muss sich nicht ausschliessen :) Man sollte soweit wie moeglich thread-lokal bleiben (schon aus Gruenden der Skalierbarkeit, LF ist da kein Allheilmittel), aber es dennoch moeglich machen, bei Bedarf auch Speicher freigeben zu koennen, welcher von einem anderen Thread mal alloziiert wurde.
Benutzeravatar
Aramis
Moderator
Beiträge: 1458
Registriert: 25.02.2009, 19:50
Echter Name: Alexander Gessler
Wohnort: 2016
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von Aramis »

Aber beim Wort "Profit" kommen meine Zweifel: denkt ihr ernsthaft, dass ihr bzw. wir hier als semiprofessionelle Stümper die gängige Heap-Implementation von Windows oder Linux schlagen? Ich zweifle... ich zweifle.
Vielleicht zweifelst du zu Recht, vielleicht auch nicht :-)

U.a. ist die MSVC-Heapimplementierung voll von Sicherheitsfeatures. Groesstenteils haben die wohl keinen gewaltigen Einfluss, ich denke sie verringern alle zusammen die Gesamtperformance dann aber doch.

Wenn wir das Thema Sicherheit rauslassen, sparen wir uns eine Menge Arbeit. Viel wichtiger ist IMHO leichtes Debugging, wobei auch da die Messlatte von den Default-Implementierungen recht hoch gesetzt wird …

Wichtigster Designaspekt ist ein schluessiges Lock (oder non-Lock, je nach Sichtweise :-))-Konzept. Wenn wir die ganze Geschichte schoen (wie von Krishty im Startposting ausgefuehrt) in voneinander getrennte Ebenen gliedern, gewinnen wir Flexibilitaet und hoffentlich eine gute Basis auf der sich schnell verschiedene Varianten austesten lassen.

Benchmark und Testsuite muessten ebenfalls designt werden.

… soweit der aktuelle Stand des Brainstormings. Dass das eine Menge Arbeit wird (wuerde), ist klar. Aber wenn sich 3 oder 4 aktiv Mitmachende faenden, waere es vermutlich machbar.
Alexander Kornrumpf
Moderator
Beiträge: 2106
Registriert: 25.02.2009, 13:37

Re: zeitgemäßer Memory-Manager

Beitrag von Alexander Kornrumpf »

Ich finde immer interessant was ihr euch so überlegt, und für die Community werden bestimmt allein die Zwischenberichte ein Gewinn sein, auch wenn es "nichts wird". Allerdings frage ich mich ernsthaft wo ihr die Zeit dafür hernehmt :).
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: zeitgemäßer Memory-Manager

Beitrag von Chromanoid »

Da ich mich hüte systemnah zu arbeiten, würde mir ein memory manager nicht viel nutzen :D. Nichts desto trotz hört es sich interessant an...
Bei Java, Flash, C# und Co. hat man mit sowas ja eigentlich nicht zu tun. Bei Java und C# gibt es vielleicht noch Anwendungsfälle, aber die halte ich für sehr selten. Wenn euch einfach nur langweilig ist und ihr nützliche Middleware entwickeln wollt und euch nichts anderes einfällt kann ich mir gerne was ausdenken :D. ZFX Wissensbibliotheken für Algorithmen der prozeduralen Generierung, Shaderfunktionen oder sowas fände ich nützlicher ^^...
Benutzeravatar
Aramis
Moderator
Beiträge: 1458
Registriert: 25.02.2009, 19:50
Echter Name: Alexander Gessler
Wohnort: 2016
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von Aramis »

Allerdings frage ich mich ernsthaft wo ihr die Zeit dafür hernehmt
Das frage ich mich grade auch … hab noch genug anderes in der Queue, aber man kann ja mal planen :-)
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von Krishty »

Nun, langfristig gesehen brauche ich einen eigenen Manager … und ich wollte so früh wie möglich anfangen, mich darauf einzuschießen. Da ich das Gefühl hatte, nicht der Einzige zu sein, wäre das eine tolle Möglichkeit gewesen, mal nicht immer nur im Elfenbeinturm das Rad neu zu erfinden …

… wenn aber das nationale Klima auf Zeitverschwendung und Feature-Inflation steht, baue ich mir innerhalb von zwei Stunden eine Minimalimplementierung (im Moment habe ich weder genug Allokationen, noch ausreichend Speicherverbrauch, als dass die Speicherverwaltung irgendwelchen messbaren Einfluss auf die Performance meiner Programme hätte), benutze die und verfeinere sie über die nächsten Monate, während meine Ansprüche an sie wachsen. Ich persönlich habe da eigentlich nichts zu verlieren und würde Code und Erfahrung auch später noch mit euch teilen; ob die Qualität dann überzeugen würde, ist eine andere Frage.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Chromanoid
Moderator
Beiträge: 4254
Registriert: 16.10.2002, 19:39
Echter Name: Christian Kulenkampff
Wohnort: Lüneburg

Re: zeitgemäßer Memory-Manager

Beitrag von Chromanoid »

Also ich denke auch außerhalb von ZFX gibt es sicherlich Anwender, die einen guten memory manager gebrauchen könnten. Vielleicht kannst du ja mal bei den OpenSource C++ Engines vorbeischauen und mal evaluieren, wie die das so machen. Sobald der memory manager wirklich signifikante vorteile bietet würde sowas sicherlich Anklang finden. Bei solchen Windows orientierten Projekten ist halt imo oft die Frage ob sich Entwickler, die ihre Engine mit C++ entwickeln, überhaupt auf fremde pakete einlassen. Denn gerade im C++-Windows-Spiele-Sektor vermute ich viele Radneuerfinder... ;)
Bei den Linux-Entwicklern sieht es da IMO ganz anders aus...
odenter
Establishment
Beiträge: 207
Registriert: 26.02.2009, 11:58

Re: zeitgemäßer Memory-Manager

Beitrag von odenter »

Das ein spezialisierter MemoryManager schneller ist, als der vom OS sollte ja klar sein.
Die einzige Frage ist nur ob man etwas spezielles so umbauen kann das es generell, einfach und schnell zu benutzen ist, oder ob man dann nicht doch wieder bei dem landet was es im OS sowieso gibt, einem Kompromis zwischen Performance und genereller Nutzbarkeit.
Benutzeravatar
kimmi
Moderator
Beiträge: 1405
Registriert: 26.02.2009, 09:42
Echter Name: Kim Kulling
Wohnort: Luebeck
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von kimmi »

Es gibt gerade für Engine ja spezielle Anwendungsfälle wie zum Beispiel das Vermeiden von Allocs in einem Renderpass. PLant ihr, für so etwas spezielle Allokatoren anzubieten oder wollt ihr wirklich nur einen Ersatz für Allokatoren wie zum Beispiel heapAlloc schreiben.
Übrigens: Ogre hat einen eigenen Memorymanager, Nebula3 benutzt auch spezielle betriebssystem-spezifische Allokatoren in einem eigenen Memorymanager. Die ZFXCE benutzt zur Zeit unter Windows den Debug-Runtime-Allokator der Windows-API.

Gruß Kimmi
Benutzeravatar
dv
Beiträge: 51
Registriert: 15.09.2002, 17:46
Benutzertext: Ugauga.
Alter Benutzername: dv
Wohnort: Südamerikanischer Dschungel
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von dv »

Ich will wissen, was für einen Sinn ein Speichermanager heutzutage ergibt. Reden wir hier von Konsolenentwicklung? Nein, vom PC, wie es scheint (und bei Konsolen kann man generische Lösungen getrost vergessen). Wo ist da was noch zu holen? Wozu diese Arbeit?

Und:
Krishty hat geschrieben: ob die Qualität dann überzeugen würde, ist eine andere Frage.
Welche Qualität? Wen überzeugen?
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von Krishty »

Chromanoid hat geschrieben:Vielleicht kannst du ja mal bei den OpenSource C++ Engines vorbeischauen und mal evaluieren, wie die das so machen.
kimmi hat geschrieben:Ogre hat einen eigenen Memorymanager, Nebula3 benutzt auch spezielle betriebssystem-spezifische Allokatoren in einem eigenen Memorymanager.
In Nebula habe ich noch nicht reingeschaut; Ogre sieht interessant aus (mit Thread-Sicherheit und allem) … da lässt sich garantiert draus lernen.
kimmi hat geschrieben:Die ZFXCE benutzt zur Zeit unter Windows den Debug-Runtime-Allokator der Windows-API.
Ähm … ich kann mich ja irren, aber ich sehe da überall nur calloc() – also nicht doch eher den C-Runtime-Allocator?
dv hat geschrieben:Wo ist da was noch zu holen? Wozu diese Arbeit?
Überall. Von der Anwendungsseite, die sich dank Alignment-Support viel Mühe sparen kann, über die Allocator-Implemenentierung, die sich auf den Footprint der Anwendung optimieren lässt, bis zur blanken Seitenverwaltung, die gegenüber der des OS weitaus schlanker ausfällt (was aber auch zum Fluch werden könnte).
dv hat geschrieben:Welche Qualität? Wen überzeugen?
Die Qualität eines rein von mir für mich entwickelten Managers, der nur auf meine Bedürfnisse zugeschnitten und optimiert ist. Jeden, der einen eigenen MM braucht, auf diesen Thread stößt und sich fragt, was draus geworden ist.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
kimmi
Moderator
Beiträge: 1405
Registriert: 26.02.2009, 09:42
Echter Name: Kim Kulling
Wohnort: Luebeck
Kontaktdaten:

Re: zeitgemäßer Memory-Manager

Beitrag von kimmi »

Ops, stimmt ja. Wir haben zwar einen MemoryManager, aber haben den nicht scharf geschaltet :o).

Gruß Kimmi
Antworten