Thema: Optimale Baumstrukturen fuer malloc/free

[rizor]

Nabend zusammen,

ich arbeite gerade an einem neuen kmalloc, da ich bei meinem derzeitigen Kernel festgestellt habe, dass der Kernel dabei sehr viel zeit vertreiben muss.

Nun wollte ich einen balancierenden Baum verwenden allerdings habe ich dabei das Problem, dass ich bei identischen Knoten nicht fuer einen sortierten Baum garantieren kann, wodurch mir ja die ganzen Vorteile verloren gehen.
Dann hatte ich die Idee, dass die freien Speicherbereiche mit identischer Groesse in einem einzigen Knoten abgelegt werden.

Wie habt ihr das Problem geloest?
Ausserdem ueberlege ich mir die ganze Zeit, welche Baeume am besten fuer die Speicherverwaltung am besten sind.
Habe leider nichts aufschlussreiches gefunden (AVL oder RB).
Habt ihr damit Erfahrungen?

Gruesse,
rizor

[bluecode]

Warum hast du denn überhaupt identische Knoten (und kann man die nicht künstlich ordnen?)? Und nur weil es identische Knoten gibt, kann man doch trotzdem sortieren? Und die Balance beeinflusst das sowieso überhaupt nicht, insofern hast du immernoch log(n) für lookup nach einem Knoten. Die STL benutzt für std::map einen R&B-Baum, falls das hilft.

[rizor]

Also mit identischen Knoten meinte ich Knoten, die die gleiche Speichergröße verwalten.
Bei mir liegt vor jedem Speicherblock ein Header, der den Speicherbereich beschreibt. Der Baum wird anhand der Größen und der Adresse sortiert (zwei Bäume).
Für die SPeichergröße kann es somit "identische Knoten" geben.
Bei einem selbst balancierendem Baum kann es sein, dass ein identischer Knoten auf der Rechten Baumhälfte liegt. Dadurch kann ich den ganzen Weg nicht vereinfacht abarbeiten.
Kann mir zumindest künstlich solch einen Baum aufbauen.
Das ist derzeit mein Problem.

[erik.vikinger]

Hallo,


dann nimm doch einfach die Adresse als zusätzliches Sortierkriterium. Wenn Du einen Speicherbereich mit einer bestimmten Größe suchst ist Dir doch sicher egal welcher es genau ist (solange die Größe passt) so das es keine Rolle spielt welchen Du als erstes im Baum findest und diesen einfach nimmst. Wenn Du einen bestimmten Speicherblock suchst kennst Du auch seine Adresse und nimmst eh den anderen Baum.

Ich vermute mal der Baum mit der Größe als Kriterium dient Dir fürs Allozieren von Speicher und der könnte sicher etwas kleiner und damit schneller sein wenn dort nur die freien Blöcke drin sind.


Grüße
Erik

[rizor]

dann nimm doch einfach die Adresse als zusätzliches Sortierkriterium. Wenn Du einen Speicherbereich mit einer bestimmten Größe suchst ist Dir doch sicher egal welcher es genau ist (solange die Größe passt) so das es keine Rolle spielt welchen Du als erstes im Baum findest und diesen einfach nimmst.

Wie sollte denn dann das Kriterium dafür aussehen? Dann müsste ich mir ja eine Funktion überlegen, die mir aus den Werten eindeutige Schlüssel generiert, oder?
Mir fällt da auf die Schnelle kein Algorithmus ein.

Ich vermute mal der Baum mit der Größe als Kriterium dient Dir fürs Allozieren von Speicher und der könnte sicher etwas kleiner und damit schneller sein wenn dort nur die freien Blöcke drin sind.

Richtig, so woll es auch aussehen. Ich möchte den Baum so klein wie möglich halten.

[erik.vikinger]

Hallo,

Wie sollte denn dann das Kriterium dafür aussehen?

Eigentlich meinte ich das Du bei Gleichheit der Größe einfach die Adresse als nachgeordnetes Sortierkriterium nehmen kannst (also wenn die Größe gleich ist das dann die kleinere Adresse möglichst weit rechts im Baum landet, die Adressen können ja eigentlich nicht kollidieren). Aber vergiss das wieder, das ist nach etwas überlegen eigentlich völlig unnötiger Aufwand, es sollte meiner Meinung nach völlig egal sein wie die Elemente mit gleicher Größe im Baum verteilt sind.

Ich denke mal die kritische Operation ist das Hinzufügen von neuen Elementen in den Baum. Wenn Du dabei auf ein Element triffst das genau die selbe Größe repräsentiert kannst Du ja schauen ob mindestens eines seiner Kindelemente ebenfalls diese Größe hat, wenn das bei genau einem Zutrifft gehst Du dort weiter. Wenn dieses Element nur ein oder gar keine Kinder hat dann nimmst Du einen beliebigen freien Platz. Wenn das Element nur Kinder mit anderen Größen hat dann musst Du eben an einer beliebigen Seite die Verbindung unterbrechen und einfügen so als wäre das neue Element zwischen dem aktuellem Element und dem betreffenden Kindelement einzuordnen. Wenn beide Kindelemente ebenfalls diese Größe haben kannst Du wieder zu einer beliebigen Seite weiter gehen. Wenn Du irgendwo einfügst musst Du natürlich den Baum wieder ausgleichen, falls das erforderlich wird, dabei sollte die Sortierung keine Rolle spielen da diese IMHO bei den Ausgleichsoperationen nicht gestört wird.

Ob es wirklich besser ist bei Übereinstimmung weiter nach unten zu gehen anstatt möglichst weit oben einzuhängen/zu entfernen kann ich nicht beurteilen, eventuell ist es besser möglichst dicht an der Wurzel zu ändern damit die eventuell folgende Ausgleichsoperation einen möglichst kurzen Weg bis zur Wurzel hat. Diese Frage können andere hoffentlich besser beantworten.

Jedes mal wo ich oben "beliebig" geschrieben hab meine ich auch beliebig oder besser zufällig, ein Kernel der sich nicht deterministisch verhält ist eventuell weniger anfällig gegen gezielte Attacken. In meinem Kernel möchte ich möglichst viele Dinge vom Zufall abhängig machen aber nicht die Speicherverwaltung, bei Flat-Memory ist das aber eher egal so das es IMHO nichts macht wenn auch die Speicherverwaltung etwas Zufall mit einbringt.


Grüße
Erik

[rizor]

Das Verfahren, das du beschrieben hast ist aber nicht gut für das Suchen.
Die Idee hatte ich auch, aber durch die Balancierungen weiß ich nicht mehr, wo ich nachschauen muss um ein passendes Element zu finden.
Das ist mein größtes Problem.
Es kann dann durchaus passieren, dass der Baum am Ende alles andere als sortiert ist.
Ich weiß nicht, wie ich das lösen soll, es sei denn, ich nehme einen nicht balancierten Baum. Der ist mir allerdings nicht performant genug.
Wie wird das Problem denn von anderen Speicherverwaltungen gelöst?
Habe leider keine Artikel oder Paper dazu gefunden.

[bluecode]

dann nimm doch einfach die Adresse als zusätzliches Sortierkriterium. Wenn Du einen Speicherbereich mit einer bestimmten Größe suchst ist Dir doch sicher egal welcher es genau ist (solange die Größe passt) so das es keine Rolle spielt welchen Du als erstes im Baum findest und diesen einfach nimmst.

Man sortiert halt das Paar (Größe, Adresse) wie folgt (Die Standardordnung die man so auf Paaren einführt): p1 < p2 gdw. (p1.größe < p2.größe oder (p1.größe == p2.größe und p1.adresse < p2.adresse)). Dann hast du sofort eine totale Ordnung und eindeutige Schlüssel, wobei der Schlüssel jetzt natürlich das Tupel (Größe, Adresse) ist. Wenn du nur nach der Größe suchst, kannst du das natürlich auch weiterhin genauso wie normal machen (Indem man nur nach Größe sucht). Aber jetzt kannst du auch einen Lookup auf einen eindeutig identifizierten Knoten machen (falls du aus deinem "Adressen-Baum" was gelöscht hast und die Änderung jetzt auch in dem "Größe-Baum" machen willst).
Ich seh damit ehrlichgesagt überhaupt kein Problem... Ich sehe sogar nichtmal das Problem ohne die eindeutige Identifikation der Knoten (wenn man zB Zeiger von einem Baum in den anderen hat, falls das das Problem ist, welches du siehst? Oder wann genau wird es denn relevant, dass man exakt in einem konkreten Knoten landet im "Größe-Baum" und nicht nur an einem "der größer/kleiner/gleich groß ist wie"?)

Sidenote: Für was brauchst du denn den "Adressen-Baum"?

erik: Dich könnten dann randomisierte Suchbäume interessieren. Ist aber nur "an guten Tagen" balanciert

[rizor]

dann nimm doch einfach die Adresse als zusätzliches Sortierkriterium. Wenn Du einen Speicherbereich mit einer bestimmten Größe suchst ist Dir doch sicher egal welcher es genau ist (solange die Größe passt) so das es keine Rolle spielt welchen Du als erstes im Baum findest und diesen einfach nimmst.

Man sortiert halt das Paar (Größe, Adresse) wie folgt (Die Standardordnung die man so auf Paaren einführt): p1 < p2 gdw. (p1.größe < p2.größe oder (p1.größe == p2.größe und p1.adresse < p2.adresse)). Dann hast du sofort eine totale Ordnung und eindeutige Schlüssel, wobei der Schlüssel jetzt natürlich das Tupel (Größe, Adresse) ist. Wenn du nur nach der Größe suchst, kannst du das natürlich auch weiterhin genauso wie normal machen (Indem man nur nach Größe sucht). Aber jetzt kannst du auch einen Lookup auf einen eindeutig identifizierten Knoten machen (falls du aus deinem "Adressen-Baum" was gelöscht hast und die Änderung jetzt auch in dem "Größe-Baum" machen willst).
Ich seh damit ehrlichgesagt überhaupt kein Problem... Ich sehe sogar nichtmal das Problem ohne die eindeutige Identifikation der Knoten (wenn man zB Zeiger von einem Baum in den anderen hat, falls das das Problem ist, welches du siehst? Oder wann genau wird es denn relevant, dass man exakt in einem konkreten Knoten landet im "Größe-Baum" und nicht nur an einem "der größer/kleiner/gleich groß ist wie"?)

Der Aufbau des Baumes ist ja auch nicht mein Problem. Das Problem habe ich nur bei den Rotationen.
Da geht mir dann die Sortierung verloren (Knoten1 == Knoten2 -> Knoten1 links von Knoten 2). Es kann passieren, dass nach der Rotation Knoten2 rechts von Knoten1 liegt (rechts-rotation), wobei er eigentlich links davon liegen müsste.
Somit müsste ich ja beide Kindknoten untersuchen.

Sidenote: Für was brauchst du denn den "Adressen-Baum"?

Für ein möglichst schnelles shrinken/mergen von Knoten.

[bluecode]

Der Aufbau des Baumes ist ja auch nicht mein Problem. Das Problem habe ich nur bei den Rotationen. Da geht mir dann die Sortierung verloren (Knoten1 == Knoten2 -> Knoten1 links von Knoten 2). Es kann passieren, dass nach der Rotation Knoten2 rechts von Knoten1 liegt (rechts-rotation), wobei er eigentlich links davon liegen müsste. Somit müsste ich ja beide Kindknoten untersuchen.

Ich glaube du bist hier wieder etwas verwirrt: Die inorder eines Baumes ist das aufzählen der knoten (beginnend bei der Wurzel) indem man rekursiv sein linkes Kind aufzählt, dann sich selbst nennt, dann rekursiv sein rechtes Kind. Ein Baum ist jetzt Inorder-sortiert, wenn die entstehende Folge nach einer beliebigen Ordnung < sortiert ist. Wenn du dir jetzt anschaust was die zwei Arten von (Basis)rotationen machen, dann wirst du feststellen, dass keine dabei die Inorder verändert. Insofern verändert sich auch nicht die Sortierung.
Was du für das eigentliche Problem hälst ist also, die Navigierung im Baum, denn normalerweise hat man <= des aktuellen Knotens im linken Teilbaum und > im rechten. Die Frage ist jetzt aber, ob man das in deinem Fall wirklich braucht und da sehe ich nicht warum. Insofern müsstest du mir ein Szenario zeigen, bei dem es nicht ausreicht zu wissen, dass links <= ist und rechts >=, weil für alles was ich sehen kann reicht beim Allozieren von Speicher die Suche nach >= und beim Freigeben ist es dann egal wohin man navigiert, man darf ja auf beiden Seiten einfügen (solange die Größen gleich sind).
Das einzige Szenario, das ich sehen kann, ist - wie oben bereits angesprochen - dass du in dem "Adress-Baum" was gefunden hast und löschen willst und die Änderung dann in dem "Größe-Baum" nachziehen willst. Das Problem kann man aber durch Zeiger jedes Knotens im "Adress-Baum" zu dem entsprechenden Knoten des "Größe-Baums" lösen, denn dann braucht man nichtmehr im anderen Baum suchen (nach was auch? Der Baum hat schließlich keine eindeutigen Identifikationen, da macht "ich will _genau_den_ Knoten mit Größe 5 löschen" einfach keinen Sinn), sondern kann die Abkürzung über den Zeiger nehmen.
Die andere Art das zu Lösen ist wie gesagt die Identifikationen wie oben beschrieben eindeutig zu machen.

edit: Ich kann übrigens - wie immer - nur dazu raten dir zu überlegen welche Operationen du unterstützen willst (Ein/Ausgabe genau spezifizieren) und dann zu schauen ob das mit dem geplanten Baum geht. Wo es nicht geht muss man halt eventuell den Baum aufbohren, die Sortierung ändern... zB rede ich von den Operationen (im "Größe-Baum"):
* (size, address) allocate(size) (geht ohne Probleme unter der sinnvollen Annahme, dass alle Knoten der Größe >= size akzeptabel sind [und nicht genau ein spezieller])
* void free(size, address)
* entweder void remove_from_tree(size, address) (falls man die Ordnung so wie oben ändert) oder void remove_from_tree(node_t*) (falls man Zeiger von einem Baum in den anderen hat), um wie oben beschrieben Änderungen aus dem anderen Baum nachzuziehen

[rizor]

Wieso verändert die Rotation nicht die inorder, wenn man identische Schlüssel zulässt?

Füge einfach mal dreimal den Schlüssel 1 ein.
Nach einer einfachen Rechtsrotation erhalte ich folgenden Baum:
     1
   /   \
 1      1

Somit ist das Kriterium <= hinfällig für den linken Teilbaum, oder?

[erik.vikinger]

Hallo,

erik: Dich könnten dann randomisierte Suchbäume interessieren. Ist aber nur "an guten Tagen" balanciert

Ich denke Du weißt ganz genau was ich meine.


Wenn die relativen Positionen der Elemente mit gleicher Größe (im Größe-Baum) egal ist bleibt aber noch die Frage ob man möglichst dicht oder möglichst fern der Wurzel einfügen/entfernen sollte.


Beim Suchen im Größe-Baum sucht man IMHO bevorzugt nach == und nur als zweite Wahl nach >=, man will damit "best fit" umsetzen. Eben deswegen bin ich ja auch der Meinung das man bei gleicher Größe keine zusätzliche Ordnung benötigt sondern alle Elemente mit gleicher Größe eine beliebige relative Position zueinander im Baum haben dürfen.


Grüße
Erik

[rizor]

Ist es denn garantiert, dass ich trotzdem uch nach dem entfernen eines Knoten trotzdem einen bestimmten Knoten finden kann?
Also z.B. bei einer zweiten Allokation mit der selben Größe.
Oder kann es passieren, dass mir auch Knoten "verloren" gehen?

Mirfällt zwar kein Szenario ein, das mir Knoten "verbirgt", aber ich bin mir nicht hundertprozentig sicher.

[bluecode]

Somit ist das Kriterium <= hinfällig für den linken Teilbaum, oder?

Welches? Die Inorder ist 1-1-1 (Knoten links - Knoten mitte - Knoten rechts). Und das ist für meine Begriffe sortiert (wobei ich wohl <= hätte sagen sollen nicht <). Im linken Teilbaum ist immer alles <= und im rechten alles >=.

Ist es denn garantiert, dass ich trotzdem uch nach dem entfernen eines Knoten trotzdem einen bestimmten Knoten finden kann? Also z.B. bei einer zweiten Allokation mit der selben Größe. Oder kann es passieren, dass mir auch Knoten "verloren" gehen?

Ich versteh ehrlich gesagt nicht, was du damit meinst... seit wann verliert ein Baum Knoten? Wenn der Herbst kommt? Die einzige sinnvolle Antwort die mir darauf einfällt ist, dass du immer einen Baum bekommst (zumindest bei AVL), bei dem im linken Teilbaum eines Knotens alles <= ist und im rechten alles >=. Die einzige Frage die sich stellt ist jetzt, reicht mir das als Information wenn ich von oben komme aus oder nicht um das zu finden was man will? Und das reicht wohl, um Speicher zu allozieren...

erik: Dich könnten dann randomisierte Suchbäume interessieren. Ist aber nur "an guten Tagen" balanciert grin

Ich denke Du weißt ganz genau was ich meine. Wink

Das war nicht nur als Scherz gemeint. Randomisierte Suchbäume (das ist eine konkrete Baumart, nicht irgendwas undefiniertes) haben sehr schicke Eigenschaften im Durchschnitt (über alle Eingabefolgen) und eine relativ kleine Standardabweichung von diesem Durchschnitt.

[FlashBurn]

Da ich endlich wieder ins Forum kann, will ich auch mal meinen Senf dazu beitragen.

Ich benutze für etwas ähnliches genau 2 AVL Bäume. In einem wird alles nach der Größe sortiert (malloc()) und in dem anderen, alles nach der Adresse (free()).
Um das von dir beschriebene Problem zu umgehen, besteht jede Node aus dem Baum mit der Größe aus einer Liste wo alle Objekte drin sind, die die gleiche Größe haben. Damit ist der Baum auch so klein wie möglich. Das kann im worst-case schonmal richtig was ausmachen. Stellt euch einfach vor ihr habt verdammt viele Elemente drin und weil ihr keine Listen verwendet, müsst ihr den Baum erst "ewig" durchsuchen obwohl ihr eigentlich nur 2 oder 3 verschiedene Größen habt.

Ob nun AVL oder RB ist so eine Sache, kommt immer auf das Anwendungsgebiet drauf an. Ich nutze das obige z.B. für meinen VMM, damit ich Blöcke innerhalb des Adressraumes finden kann und auch wieder mergen kann.
Für genau diesen Fall gibt es ein Paper wo man mehrere Bäume miteinander verglichen hat (AVL, RB, Splay und Binary) und rausgekommen ist, das es auf die Anwendung ankommt, aber sich RB und AVL nicht wirklich viel nehmen. Allerdings waren die Splay-Trees sehr interessant, da sie meistens nicht schlechter als RB und AVL waren, aber wenn sie besser waren dann deutlich.
Ob das allerdings heute noch gilt, wenn man von ALRS (oder wie auch immer das hieß -> erik) ausgeht, denke ich eher nicht.

[bluecode]

Um das von dir beschriebene Problem zu umgehen, besteht jede Node aus dem Baum mit der Größe aus einer Liste wo alle Objekte drin sind, die die gleiche Größe haben.

Die Idee kam mir zwar auch, ich hatte aber den Performancevorteil nicht gesehen. Klingt ansonsten sinnvoll.
Die einzige Frage ist nur, wie löscht du aus dem anderen Baum dann was (wenn es in dem einen gerade gelöscht wurde und man die Änderungen nachziehen muss)? Links von einem in den anderen Baum? Oder taucht das Problem garnicht auf (würde mich irgendwie verwundern).

Allerdings waren die Splay-Trees sehr interessant, da sie meistens nicht schlechter als RB und AVL waren, aber wenn sie besser waren dann deutlich.

Wenn auf bestimmte Dinge häufig zugegriffen wird (und das dann nicht sofort gelöscht wird, was hier wohl sehr oft vorkommt) sind die bestimmt geschickt, aber ansonsten ist der Overhead alles jedes Mal hochzusplayen wahrscheinlich nicht gering. Aber aus theoretischer Sicht ist ziemlich witzig, dass die "triviale" Regel für einen Splayschritt zu irgendwas sinnvollem führt. Achso, man sollte auch darauf hinweißen, dass das eine Datenstruktur ist die von Amortisierung (d.h. über eine Operationenfolge hat man durchschnittlich O(logn) pro Operation) lebt und worst-case trotzdem O(n) ist (aber halt selten vorkommt). Das macht es für real-time vielleicht auch nicht so sinnvoll.

[FlashBurn]

Die einzige Frage ist nur, wie löscht du aus dem anderen Baum dann was

Suchen

Deswegen nehme ich auch lieber den AVL Baum, da ich doch öfter suchen muss. Es lässt sich jetzt natürlich diskutieren ob der Vorteil (schnelles mergen und schnellens finden von Blöcken) den Nachteil (zusätzliches Suchen in dem anderen Baum) überwiegt (wäre ich sehr interessiert daran).

[bluecode]

Kommt das nicht auch andersrum vor (also was aus dem "Größe-Baum" entfernen, dass schon aus dem "Adress-Baum" gelöscht wurde)? Dann ist durch eine verkettete Liste suchen aber doof.

[FlashBurn]

Dann ist durch eine verkettete Liste suchen aber doof.

Gutes Argument!

An den worst-case habe ich noch gar nicht gedacht, aber das könnte man lösen, in dem man in der Node (von dem Baum mit der Größe) einen Baum mit allen Objekten, gleicher Größe, der Adresse nach speichert. Das dürfte dann das Optimum sein, aber ob es auch bei der Performance hilft weiß ich nicht.

Ich habe gerade mal nachgeschaut und das Problem habe ich bei mir durch Speicherverschwendung gelöst Jedes Objekt, was in den Bäumen gespeichert wird, hat auch immer 2 Pointer (prev und next) mit drin, weil das Objekt zwar in 2 Bäumen gespeichert wird, aber nur max. in einer Liste. So ist das Entfernen aus der Liste immer O(1).

Welche Variante jetzt besser ist weiß ich nicht.

[rizor]

Da ich endlich wieder ins Forum kann, will ich auch mal meinen Senf dazu beitragen.

Ich benutze für etwas ähnliches genau 2 AVL Bäume. In einem wird alles nach der Größe sortiert (malloc()) und in dem anderen, alles nach der Adresse (free()).
Um das von dir beschriebene Problem zu umgehen, besteht jede Node aus dem Baum mit der Größe aus einer Liste wo alle Objekte drin sind, die die gleiche Größe haben. Damit ist der Baum auch so klein wie möglich. Das kann im worst-case schonmal richtig was ausmachen. Stellt euch einfach vor ihr habt verdammt viele Elemente drin und weil ihr keine Listen verwendet, müsst ihr den Baum erst "ewig" durchsuchen obwohl ihr eigentlich nur 2 oder 3 verschiedene Größen habt.

Ob nun AVL oder RB ist so eine Sache, kommt immer auf das Anwendungsgebiet drauf an. Ich nutze das obige z.B. für meinen VMM, damit ich Blöcke innerhalb des Adressraumes finden kann und auch wieder mergen kann.
Für genau diesen Fall gibt es ein Paper wo man mehrere Bäume miteinander verglichen hat (AVL, RB, Splay und Binary) und rausgekommen ist, das es auf die Anwendung ankommt, aber sich RB und AVL nicht wirklich viel nehmen. Allerdings waren die Splay-Trees sehr interessant, da sie meistens nicht schlechter als RB und AVL waren, aber wenn sie besser waren dann deutlich.
Ob das allerdings heute noch gilt, wenn man von ALRS (oder wie auch immer das hieß -> erik) ausgeht, denke ich eher nicht.

Genau die Idee hatte ich auch schon.
Ich habe mir nun auch noch überlegt, ob ich es vllt noch lock-free schaffe.
Dabei ist mir halt leider aufgefallen, dass es ein Patent gibt, dass einen lock-free Baum beschreibt...

Um das von dir beschriebene Problem zu umgehen, besteht jede Node aus dem Baum mit der Größe aus einer Liste wo alle Objekte drin sind, die die gleiche Größe haben.

Die Idee kam mir zwar auch, ich hatte aber den Performancevorteil nicht gesehen. Klingt ansonsten sinnvoll.
Die einzige Frage ist nur, wie löscht du aus dem anderen Baum dann was (wenn es in dem einen gerade gelöscht wurde und man die Änderungen nachziehen muss)? Links von einem in den anderen Baum? Oder taucht das Problem garnicht auf (würde mich irgendwie verwundern).

Das Problem taucht natürlich auf, aber man kann das ja durch direkte Links lösen.
Dadurch erspart man sich sogar das Suchen, da du ja weißt, wo du löschen musst.

Darum habe ich mir überlegt als Header einen Baum orientiert anhand von Adressen zu verwenden und dann woanders den Baum anhand von Größen habe möchte.
Das Problem daran ist halt, dass wenn ich häufiger malloc als free verwende, dass mir bei der Idee die Cache-Lokalität verloren gehen kann.
Vermutlich müsste der Kernel mal Statistiken über die Allokationsgrößen führen.
Dadurch könnte man ermitteln, ob man darunter noch einen Cache legen kann, der in konstanter Zeit speicher allozieren kann und man somit den Cache ausnutzen kann.
Also im Prinzip ein SLAB-Allocator mit variablen Speicherbereichen.
Das dürfte aber vermutlich nur mit einem Mikrokernel gehen, oder?