Liste - Performance verbessern

[volkard]

seldon schrieb:

Ansonsten bietet es sich bei einer verketteten Liste an, Dummy-Elemente am Anfang und Ende zu benutzen; sie fügen der Liste eine Invariante zu (head und tail sind nie NULL), die Operationen an den Enden stark vereinfachen. So spart man sich einen Haufen Gebranche und hat leichter verständlichen Code.

Ja. Und weil ich bemerkt habe, daß der Nachfolgerzeiger des Endeknotens und der Vorgängerzeigers des Anfangsknotens unbenutzt sind, schlage ich sogar vor, deinen Plan ein winziges Bißchen zu ändern und nur einen einzigen Grenzknoten zu nehmen, daß also der selbe Grenzknoten die Liste auf beiden Seiten begrenzt.

[seldon]

Das ergibt auf den ersten Blick eine Menge Sinn, gerade bei kurzen Listen - und wenn ich mich nicht verkucke, ist das in der Anwendung identisch, sofern der Anker bei einer leeren Liste mit prev und next sich selbst referenziert.

Guter Plan! Den muss ich mir merken.

[hustbaer]

@mnimda:
Ich bin mir auch nicht sicher, ob für dich eine Liste die beste Datenstruktur ist.
Wird wirklich so häufig mitten drin gelöscht/eingefügt?

[Superlexx]

Naja, ich will nicht nörgeln, aber eine Liste, die einen Bruchteil der Features und ein Vielfaches der Bugs einer guten std::list hat, nein, darauf hat die Welt nicht gewartet :).

Die XGenList hat keine Iteratoren ergo sehr wenige Algorithmen. Auch nicht die einfachste exception safety. Verlangt default-constructible Type. Kein custom allocator. Wenn man Iteratoren hat, dann will man auch die Laufzeitprüfungen haben wie sie die großen STLs anbieten.

Wenn man was schnelles braucht, dann dürfte die EASTL einen Blick wert sein. STLport ist auch nicht von schlechten Eltern. Dinkumware ist Hausmannskost :D. Ansonsten immer schön LTCG und PGO machen, bringt bei STL-Code locker Faktor 3 :).

[hustbaer]

Superlexx schrieb:

Kein custom allocator.

Will ja nicht kleinlich sein, aber das Feature (bzw. das Fehlen davon) interessiert glaube ich nicht wirklich viele Leute.

[seldon]

Du wärst erstaunt. Erwähn das mal jemandem gegenüber, der ein paar Dutzend Threads zu bedienen hat; der hätte ernsthafte Probleme damit, wenn die sich alle um den selben Heap prügeln müssten.

[hustbaer]

seldon schrieb:

Du wärst erstaunt. Erwähn das mal jemandem gegenüber, der ein paar Dutzend Threads zu bedienen hat; der hätte ernsthafte Probleme damit, wenn die sich alle um den selben Heap prügeln müssten.

In so einem Fall nimmt man einen Allocator (globales new/malloc Replacement) der damit gut umgehen kann.
Irgendwas ala tcmalloc, jemalloc etc.

Das über std::allocator zu lösen halte ich für eine relativ schlechte Idee, das schreit geradezu nach Bugs.
std::allocator wird mit Containern mitkopiert.
Stell dir mal vor was passiert wenn Worker-Thread X eine std::list mit custom Allocator kopiert um sie in eine Queue zu stopfen, wo Thread Y sie rausnimmt und munter weiterbearbeitet.
Sieht alles ganz sicher aus, da ja kopiert wurde.
Dummerweise wurde auch der Allocator mitkopiert. Der greift dann auch munter auf die Datenstrukturen zu, die eigentlich für Thread X gedacht sind, ganz ohne Locking, weil wir ja optimieren wollten. -> BUMM

Was man natürlich machen kann, ist einen Allocator zu schreiben, der einfach nur tcmalloc o.ä. kapselt. Dabei sind die Instanzen des Allocator selbst nicht Thread-affin, und können gefahrlos kopiert werden. Allerdings würde ich in dem Fall vorziehen gleich global new/malloc zu ersetzen. Ist speziell unter Windows nicht ganz trivial, aber einige fertige Allocator bringen den nötigen Code mit.

p.S.: std::list ist auch ein ganz heisses Eisen wenn's um Allocator mit State geht: nicht alle STL Implementierungen unterstützen in dem Fall splice() korrekt.

[DocShoe]

Superlexx schrieb:

...
Wenn man was schnelles braucht, dann dürfte die EASTL einen Blick wert.
...

Hat EA die inzwischen freigegeben? Habe nirgends was gefunden, ausser einem Whitepaper.

[Christoph]

otze schrieb:

Deine Liste mact genau das, was std::list macht.

Nicht ganz: Eine std::list speichert ihre Länge im allgemeinen nicht, sondern berechnet sie ad-hoc bei einem length()-Aufruf.

Der Grund ist, dass die Funktion std::list::splice(iterator p, list<T>& x, iterator f, iterator l) laut C++-Standard in Konstantzeit laufen muss. Das ist nicht zu erreichen, wenn eine std::list zu jedem Zeitpunkt ihre Länge wüsste.
Die Aufgabe der Funktion ist: Verschiebe alle Elemente im Range [f,l) aus der Liste x heraus und in die aktuelle Liste direkt vor Position p hinein. Das ist nur ein bisschen Pointer-Gebastel und ist in Konstantzeit implementierbar. Wenn aber x und *this ihre Länge speichern würden, müsste splice() zählen wie viele Elemente denn gerade verschoben wurden.

[ipsec]

Christoph schrieb:

otze schrieb:

Deine Liste mact genau das, was std::list macht.

Nicht ganz: Eine std::list speichert ihre Länge im allgemeinen nicht, sondern berechnet sie ad-hoc bei einem length()-Aufruf.

Der Grund ist, dass die Funktion std::list::splice(iterator p, list<T>& x, iterator f, iterator l) laut C++-Standard in Konstantzeit laufen muss. Das ist nicht zu erreichen, wenn eine std::list zu jedem Zeitpunkt ihre Länge wüsste.
Die Aufgabe der Funktion ist: Verschiebe alle Elemente im Range [f,l) aus der Liste x heraus und in die aktuelle Liste direkt vor Position p hinein. Das ist nur ein bisschen Pointer-Gebastel und ist in Konstantzeit implementierbar. Wenn aber x und *this ihre Länge speichern würden, müsste splice() zählen wie viele Elemente denn gerade verschoben wurden.

http://cplusplus.com/reference/stl/list/splice/ schrieb:

Complexity: Constant on all cases, except when x is a list object different than *this in the third function version, in which case it is linear in the range between first and last (iterator advance).

Mit 3. Variante ist dabei die Variante von dir gemeint. Wie du siehst, hat diese also (wahrscheinlich aus genau dem Grund mit der Länge) lineare Laufzeit.

[life]

Dinkumware hat jedenfalls constant time size Methode.

[Christoph]

ipsec schrieb:

Christoph schrieb:

otze schrieb:

Deine Liste mact genau das, was std::list macht.

Nicht ganz: Eine std::list speichert ihre Länge im allgemeinen nicht, sondern berechnet sie ad-hoc bei einem length()-Aufruf.

Der Grund ist, dass die Funktion std::list::splice(iterator p, list<T>& x, iterator f, iterator l) laut C++-Standard in Konstantzeit laufen muss. Das ist nicht zu erreichen, wenn eine std::list zu jedem Zeitpunkt ihre Länge wüsste.
Die Aufgabe der Funktion ist: Verschiebe alle Elemente im Range [f,l) aus der Liste x heraus und in die aktuelle Liste direkt vor Position p hinein. Das ist nur ein bisschen Pointer-Gebastel und ist in Konstantzeit implementierbar. Wenn aber x und *this ihre Länge speichern würden, müsste splice() zählen wie viele Elemente denn gerade verschoben wurden.

http://cplusplus.com/reference/stl/list/splice/ schrieb:

Complexity: Constant on all cases, except when x is a list object different than *this in the third function version, in which case it is linear in the range between first and last (iterator advance).

Mit 3. Variante ist dabei die Variante von dir gemeint. Wie du siehst, hat diese also (wahrscheinlich aus genau dem Grund mit der Länge) lineare Laufzeit.

Ah, stimmt, so war das. Der Standard verlangt weder, dass std::list::splice() noch dass std::list::length() in konstanter Zeit laufen, er empfiehlt wohl nur, dass std::list::length besser in konstanter Zeit laufen sollte ("should", nicht "must").
Die Implementierungen haben also die Wahl, eine dieser beiden Funktionen in Konstantzeit zu implementieren. Die andere wird zwangsläufig langsamer laufen. Manche Implementierungen lassen std::list::length in Konstantzeit laufen, andere std::list::splice.

[Nexus]

Möglich wäre ja auch ein Kompromiss, sodass sowohl size() als auch splice() in den meisten Fällen eine Laufzeit von O(1) haben. Nämlich, indem die gespeicherte Grösse bei splice() ungültig gemacht und bei Aufruf von size() neu berechnet wird. Aber das dafür notwendige if lohnt sich wahrscheinlich nicht.