Thema: Optimale Baumstrukturen fuer malloc/free

[FlashBurn]

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).

[bluecode]

Ich kenne nur eine Implementation die iirc software transactional memory benutzt um einen Baum hinzukriegen (von hier). 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 ist das unmöglich (selbst in den USA) und ich glaube auch nicht, dass das einen Europäer zu interessieren hat.

[FlashBurn]

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?).

[rizor]

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.

[FlashBurn]

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?

[rizor]

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

[FlashBurn]

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.

[rizor]

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)

[FlashBurn]

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.

[rizor]

Stimmt, das ist ja leider das allgemeine Problem.
Es tritt sich halt immer leichter von oben nach unten .

[rizor]

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.

[Dimension]

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.

[erik.vikinger]

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

[Dimension]

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.

[Dimension]

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.

[erik.vikinger]

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

[Jidder]

Wer sein System allerdings professionell einsetzen möchte

Kannst du das konkretisieren? Was ist "professioneller Einsatz"?

[Dimension]

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.

[erik.vikinger]

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