Lowlevel
Lowlevel => OS-Design => Thema gestartet von: rizor am 02. September 2011, 23:11
-
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
-
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.
-
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.
-
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
-
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.
-
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
-
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.
-
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 :-D
-
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.
-
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
-
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?
-
Hallo,
erik: Dich könnten dann randomisierte Suchbäume interessieren. Ist aber nur "an guten Tagen" balanciert :-D
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
-
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.
-
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.
-
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.
-
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.
-
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).
-
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.
-
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.
-
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?
-
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...
Also von nem lock-free AVL Baum habe ich noch nichts gehört, aber von nem lock-free RB-Baum (was mir auch einleuchtet). Wenn du irgendwelche Informationen dazu hast, dann immer her damit.
Was die Patente angeht, ist dass tatsächlich ein Problem mit den lock-free Sachen (im Sinne von, fast alle Algos sind irgendwie patentiert), aber in Dtl. dürfte das doch eigentlich kein Ding sein, da bei uns ja Softwarepatente meines Wissens nach nicht gelten.
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.
Ansich ja, aber das erhöht ja wieder den Speicherverbrauch. Ich meine bei meinem VMM geht das ja noch, aber eigentlich würde ich bei einem malloc() andere Algos verwenden (guck dir dochmal dlmalloc() an).
-
Ich kenne nur eine Implementation die iirc software transactional memory benutzt um einen Baum hinzukriegen (von hier (http://www.cl.cam.ac.uk/research/srg/netos/lock-free/)). Mit (einfachem) CAS alleine erscheint mir das prinzipiell nicht möglich bzw. nur wenn man sich erstmal ein CAS für mehrere Speicherstellen daraus zusammenbaut (was soweit ich weiß möglich ist).
Wie du auf Patente auf Algorithmen kommst weiß ich nicht, aber laut Wikipedia (http://en.wikipedia.org/wiki/Algorithm#Legal_issues) ist das unmöglich (selbst in den USA) und ich glaube auch nicht, dass das einen Europäer zu interessieren hat.
-
Wie du auf Patente auf Algorithmen kommst weiß ich nicht, aber laut Wikipedia ist das unmöglich (selbst in den USA) und ich glaube auch nicht, dass das einen Europäer zu interessieren hat.
Softwarepatente? Zumal ja sogar in dem Eintrag drin steht, das es durchaus Bsp. gibt wo es halt doch passiert ist, das Algos patentiert wurden.
Allerdings würde ich auch mal sagen, dass das ganze für ein Hobby OS eher uninteressant ist, für Linux dürfte das schon problematisch werden (warum eigentlich?).
-
Allerdings würde ich auch mal sagen, dass das ganze für ein Hobby OS eher uninteressant ist, für Linux dürfte das schon problematisch werden (warum eigentlich?).
Das Problem besteht bei allen Projekten, die irgendwie in den USA vertreten sind.
Wenn nur etwas Code davon in die Staaten kommt, könnte der Programmierer bei der Einreise Probleme bekommen.
Für Linux gilt das ganze natürlich auch.
Es wird sogar angenommen, dass Linux gegen mehrere Patente verstößt.
Habe da mal eine Artikel drüber gelesen, habe ihn nur leider nicht auf die Schnelle gefunden.
-
Das Problem besteht bei allen Projekten, die irgendwie in den USA vertreten sind.
Wenn nur etwas Code davon in die Staaten kommt, könnte der Programmierer bei der Einreise Probleme bekommen.
Daran dachte ich zwar auch, aber dann gilt das für alles was im Internet ist oder?
-
Das Problem besteht bei allen Projekten, die irgendwie in den USA vertreten sind.
Wenn nur etwas Code davon in die Staaten kommt, könnte der Programmierer bei der Einreise Probleme bekommen.
Daran dachte ich zwar auch, aber dann gilt das für alles was im Internet ist oder?
Richtig. Das ist ja grade das bekloppte an diesen Softwarepatenten.
Hier ist einer der Artikel. Ich weiß nicht, ob es genau der war, aber er beschreibt das Ding mit Linux recht gut.
http://www.welt.de/wirtschaft/webwelt/article873934/Microsoft_klagt_ueber_Linux_Patentverstoesse.html
-
Zumal es unrealistisch ist, dass jemand alle Patente aus allen Ländern kennt (was ja auch die rechtliche Situation mit betrifft). Ich wette sogar, dass man dafür mehr als nur einen Anwalt braucht um sowas weltweit prüfen zu lassen und damit wären eigentlich alle kleinen "Firmen" raus, weil die sich das gar nicht leisten können.
-
Naja, du als Entwickler bist dazu verpflichtet dich über die Patentlage zu informieren.
Kleinere Firmen sind vermutlich kaum im Interesse eines großen Konzerns.
Der geht ja mit jeder Patentklage das Risiko ein, dass ihm Patente aberkannt werden (z.B. Oracle vs. Google).
Erst wenn die Firmen größer werden, kriegen sie ärger (z.B. HTC)
-
Naja, du als Entwickler bist dazu verpflichtet dich über die Patentlage zu informieren.
Das ist schon klar, aber halt unrealistisch. Genauso wie bei unserem Steuerrecht. Nicht mal das Finanzamt kennt sich da wirklich aus, aber der dumme durchschnitts Bürger soll sich auskennen.
-
Stimmt, das ist ja leider das allgemeine Problem.
Es tritt sich halt immer leichter von oben nach unten ;).
-
Was mir bei dlmalloc aufgefallen ist... das ist doch so eine Art SLAB-Allocator, oder?
Davon würde ich ganz gerne weggehen, da mir da der Speicheroverhead zu groß ist.
Der Kernel soll natürlich auch einen haben, aber halt wirklich nur für feste Allokationen.
-
Baumstrukturen sind meiner Ansicht nach nicht sehr robust. Es gibt zu viele Faktoren, welche das Verhalten beeinflussen könnten. Man sollte meiner Ansicht nach immer mit einem Fehler oder Defekt der Hardware rechnen und die Auswirkungen minimieren. Im Zweifelsfall kann das Risiko auch durch Redundanz weiter verringert werden.
Aus diesem Grund verwende ich lieber Vektor-Arrays als verlinkte Listen bzw. lieber Hashmaps als Baumstrukturen.
-
Hallo,
Man sollte meiner Ansicht nach immer mit einem Fehler oder Defekt der Hardware rechnen und die Auswirkungen minimieren.
Das würde ich persönlich nur dann bejahen wenn Performance eine höhere Priorität hat, als SW-Entwickler sollte man IMHO die HW als Fehlerfrei ansehen dürfen. Wenn man z.B. mit Problemen im RAM rechnet dann gibt es ECC, aber gegen ein falsches Rechenergebnis in der CPU kann man nichts unternehmen. Bei Dingen wo es wirklich drauf ankommt (Medizin oder Raumfahrt) werden einfach ganze Systeme mehrfach aufgebaut und redundant betrieben.
Ein Dateisystem sollte sich meiner persönlichen Meinung nach auch keine Gedanken über defekte Sektoren machen sondern das Block-Device einfach als riesiges Array betrachten und fertig, wenn defekte Sektoren nich zum Problem werden dürfen dann gibt es RAID und wenn die Daten "Mission-Critical" sind dann liegen sie mit guten Prüfsummen abgesichert auf mehreren unabhängigen System an verschiedenen Orten.
Ich habe nichts dagegen wenn auch der SW-Entwickler sich Gedanken über HW-Sicherheit macht, hier ist Redundanz immer gut, aber es ist IMHO nicht seine vordringlichste Aufgabe. Wenn ich mich zwischen Performance und Robustheit gegen HW-Fehler entscheiden muss nehme ich immer Performance.
Grüße
Erik
-
Für den Heimrechner sicherlich keine unvorteilhafte Alternative. Wer sein System allerdings professionell einsetzen möchte, wird sich lieber 2x überlegen, ob er günstige Performance haben möchte, oder lieber mehrere Systeme verbindet um zu parallelisieren und somit die Performance erhöht bzw. das Risiko vermindert.
Edit: das setzt natürlich voraus, dass sowohl die verwendete Plattform als auch seine Aufgabenstellung massive Parallelisierung unterstützen und sein Code vom Compiler nach Abhängigkeiten analysiert und auf mehre Cores oder das Netzwerk verteilt werden kann.
-
Btw: man kann die Elemente einer Baumstruktur auch in einer Tabelle halten und mit Indices auf diese zugreifen, oder zum Pfad eines Elements den Hash bilden und über Hashtables gehen.
-
Hallo,
sorry wenn ich das so direkt schreibe aber ich finde Du übertreibst ein ganz klein wenig.
Gerade im professionellen Umfeld ist Zeit oft gleich Geld und damit spielt dort Performance eine sehr wichtige Rolle. Ich hab z.B. beruflich (und auch privat) sehr viel mit FPGA-Programmierung zu tun und ein kompletter Synthese-Durchlauf kann da schon mal ne Stunde dauern und viele Simulationen (die oft nur wenige µs an Real-Zeit simulieren) laufen mehrere Stunden bis ein Ergebnis vorliegt. Aus diesem Grund hatte ich bei diesen Tätigkeiten immer einen Top-PC vor der Nase zu stehen, einfach weil ein paar Stunden Untätigkeit teurer sind als der PC. Wegen der Wichtigkeit der erzeugten Ergebnisse waren diese PCs auch immer mit ECC-tauglichem Speicher und Chipsatz ausgestattet, auch wenn das wieder einen Teil der Performance gekostet hat (ECC verursacht beim Speicherzugriff immer ein paar Takte zusätzliche Latenz).
Ich persönlich hab es noch nicht erlebt das eine ordentlich betriebene CPU (ohne Übertaktung und mit angemessener Kühlung auf einen anständigen Main-Board mit adäquater Energieversorgung) sich mal verrechnet hätte (ja ich weiß es gab da mal den FDIV-Bug in einigen Pentiums aber so eine CPU hatte ich nie benutzt) von daher erachte ich die Investition in einen guten Work-Station-PC als ausreichend. Nebst dessen das jedes FPGA-Image immer erst gründlich getestet wird bevor es ausgeliefert wird.
Grüße
Erik
-
Wer sein System allerdings professionell einsetzen möchte
Kannst du das konkretisieren? Was ist "professioneller Einsatz"?
-
Wer sein System allerdings professionell einsetzen möchte
Kannst du das konkretisieren? Was ist "professioneller Einsatz"?
Lass es mich so formulieren: Jemand der seine CPU übertaktet zieht Performance der Reliabiliy vor.
-
Hallo,
Kannst du das konkretisieren? Was ist "professioneller Einsatz"?
Lass es mich so formulieren: Jemand der seine CPU übertaktet zieht Performance der Reliabiliy vor.
Das ist zwar richtig aber keine Antwort auf die Frage.
Grüße
Erik