New und Delete

knivil

Vor allem das ich mir das alles selber bei bringen muss. So richtig "gelehrt" werde ich nicht.

Und den meisten hier hats auch niemand beigebracht. Das Wissen musst du dir selbst aneignen, das Internet hilft und Artikel gibt es genug.

Eisflamme

Die Geschwindigkeit von den Speicherallokationen ist überhaupt nicht maßgeblich. Das, was da langsam wäre, wäre die Speicherallokation selbst. Das ist aber in beiden Fällen gegeben, somit spielt das keine Rolle. Wenn new wirklich performancekritisch eingesetzt wird, sollte man ohnehin einen eigenen Allocator schreiben und der ist mit unique_ptr wieder gut kompatibel.

SeppJ schrieb:

Nun komm, 3 Pointer vs. 1 Pointer + Größe: Das ist so was von Pillepalle.

Ist so. Aber man kann Ennos Kollegen ohne schlechtes Gewissen sagen, dass RAII nie langsamer ist.

SeppJ schrieb:

Dafür kann man den vector in O(1) wachsen lassen, was bei new nur in O(N) geht.

Viel kann natürlich auf genau auf das Problem zugeschnittene Container herausgeholt werden (ein reserve kann den Speicher bis um Faktor 2 schrumpfen). Oder durch eigene Allocators.

Fuchs aus dem Wald

@SeppJ:
Bitte neuen Namen nehmen.
Ja DEN hab ich hier gefunden. Ist eine Person.

knivil schrieb:

Vor allem das ich mir das alles selber bei bringen muss. So richtig "gelehrt" werde ich nicht.

Und den meisten hier hats auch niemand beigebracht. Das Wissen musst du dir selbst aneignen, das Internet hilft und Artikel gibt es genug.

Da hast aber wunderbar nur das gelesen was du wolltest. Ich mach das auch. UUHH! Aber ich mache eine Ausbildung da könnte man meinen man wird in gewissermaßen "gelehrt" und nicht nur gesagt: geht so mach so!

Eisflamme schrieb:

Die Geschwindigkeit von den Speicherallokationen ist überhaupt nicht maßgeblich. Das, was da langsam wäre, wäre die Speicherallokation selbst. Das ist aber in beiden Fällen gegeben, somit spielt das keine Rolle. Wenn new wirklich performancekritisch eingesetzt wird, sollte man ohnehin einen eigenen Allocator schreiben und der ist mit unique_ptr wieder gut kompatibel.

Danke das klärt mich weiter auf.

Allgemein danke schon mal das ihr mich noch mal genau aufklärt. Muss ich nun hier zwar durch aber ich hab kein bock mich für mein späteres Berufsleben zu versauen.

Werner Salomon

Fuchs aus dem Wald schrieb:

SeppJ schrieb:

Es ist langsamer oder gleich schnell, niemals schneller. Besonders gegen automatische Speicherverwaltung (in meiner Übersetzungstabelle "Kleine, statische Arrays" und "Nicht-Arrays") ist der Geschwindigkeitsverlust nicht mehr lustig.

D.h. der erzählt mir hier scheiße??
Oh man ...
Also noch mal für mich. New und delete ist sogar langsamer? Ahhhhhh

Schreibe eine eigene einfach(!) verkettet Liste mit eigenem new und delete und eigener Speicherverwaltung (lässt sich auch C-like hübsch machen)). Und dann lasse sie gegen die doppelt(!) verkette std::list<> aus dem C++-Standard antreten. Letztere ist im Nachteil, da sie bei jeder Element-Operation mehr Zeiger aktualisieren muss, als die einfach verkettete Liste.

Mache bitte einen fairen Benschmark mit vielen (möglichst kleinen) Elementen rein und raus aus der Liste. Und lege auch viele solcher Listen an und lösche sie wieder ... alles was in 'großen' Programmen so passiert.

Dann wirst Du Dich wundern, um wie viel schneller die std::list<> das gegenüber Deiner selbst gebastelten erledigt. Und ich rede nicht von 5 oder 10% - die std::list<> ist richtig schneller - und die Ursache liegt in der besseren Speicherverwaltung!
Probiere es aus - nachdem ich das gemacht hatte, musste ich mich auch erst mal setzen!
(Ausprobiert mit MS Visual C++ und Dinkumware STL)

SeppJ

Werner Salomon schrieb:

und die Ursache liegt in der besseren Speicherverwaltung!

Nanu? Kannst du konkreter werden? Ich hätte eigentlich nicht erwartet, dass man bei einer list viel durch die Implementierung rausholen kann. Arbeitet die deque-artig?

Werner Salomon schrieb:

Dann wirst Du Dich wundern, um wie viel schneller die std::list<> das gegenüber Deiner selbst gebastelten erledigt. Und ich rede nicht von 5 oder 10% - die std::list<> ist richtig schneller - und die Ursache liegt in der besseren Speicherverwaltung!

Kann ich nicht bestätigen (GCC/libstdc++).

Meine List: 0.75s auf ideone
std::list: 0.88s auf ideone

cooky451

Kein unique_ptr? Ich muss doch bitten!

cooky451 schrieb:

Kein unique_ptr? Ich muss doch bitten!

Ich gebe zu, die PODs vom Betriebssystem aufräumen zu lassen war nicht so freundlich.

Meine List ohne Leaks und UB: 0.75s auf ideone

Den unique_ptr innerhalb von node einzusetzen kostet leider ein paar Prozessortakte mehr.

cooky451

wtf, ne, so war das jetzt nicht gemeint. Eine node sollte aus T + unique_ptr<node> bestehen, die liste sollte nur nen unique_ptr<node> halten. Damit werden alle Einfüge/Löschoperationen auch nur noch zu Zuweisungen zwischen unique_ptr. Ist die Frage, ob das langsamer ist, denke aber nicht.

cooky451 schrieb:

wtf, ne, so war das jetzt nicht gemeint. Eine node sollte aus T + unique_ptr<node> bestehen, die liste sollte nur nen unique_ptr<node> halten. Damit werden alle Einfüge/Löschoperationen auch nur noch zu Zuweisungen zwischen unique_ptr. Ist die Frage, ob das langsamer ist, denke aber nicht.

Versuchs doch mal und zeig es mir.

Mit meiner Implementation geht es nicht, die ist dafür zu trickreich. Die Liste ist als Zyklus implementiert, um die ganzen if-Abfragen zu sparen, die man hätte, wenn das letzte Element auf NULL zeigen würde. Bevor man den Destruktor von unique_ptr ans Werk lassen könnte, müsste man zuerst den Zyklus aufbrechen. Das kostet. Alternativ könnte man was mit speziellen Deletern machen. Aber auch das kostet und wäre umständlicher.

camper

cooky451 schrieb:

wtf, ne, so war das jetzt nicht gemeint. Eine node sollte aus T + unique_ptr<node> bestehen, die liste sollte nur nen unique_ptr<node> halten. Damit werden alle Einfüge/Löschoperationen auch nur noch zu Zuweisungen zwischen unique_ptr. Ist die Frage, ob das langsamer ist, denke aber nicht.

Das halte ich für eine schlechte Idee.
Abgesehen davon, dass es Abstraktionsebenen durcheinander bringt, wäre ich nicht überrascht, wenn das Löschen einer großen Liste zum Stacküberlauf führen würde.

node* pointer_to_first;

  // das geht gut, solange nie auf data()->data zugegriffen wird.
  node* data() { return reinterpret_cast<node*>(&pointer_to_first); }

Das ist leider (im Allgemeinen) undefiniert (es ist zum Glück nicht schwierig, das standardkonform aufzuschreiben).

camper schrieb:

node* pointer_to_first;
 
  // das geht gut, solange nie auf data()->data zugegriffen wird.
  node* data() { return reinterpret_cast<node*>(&pointer_to_first); }
Das ist leider (im Allgemeinen) undefiniert (es ist zum Glück nicht schwierig, das standardkonform aufzuschreiben).

Im darauf folgenden Post hatte ich das geändert. Allerdings war noch ein Fehler drin.

Meine List hoffentlich ohne UB

camper schrieb:

wäre ich nicht überrascht, wenn das Löschen einer großen Liste zum Stacküberlauf führen würde.

Ich war überrascht, dem GCC hätte ich Tail Rekursion zugetraut.

cooky451

So, ist nur schnell zusammen-gefrickelt um die Idee zu zeigen, fehlt sicher einiges: https://ideone.com/hQgd90
Scheint auch tatsächlich etwas langsamer zu sein, interessant. Vielleicht gucke ich mir später mal an, was genau der jetzt anders macht. (Edit: Jetzt ist es fast genau so schnell. Sollte man vielleicht doch eher lokal messen. )

camper schrieb:

Abgesehen davon, dass es Abstraktionsebenen durcheinander bringt,

Wie genau meinst du das?

camper schrieb:

wäre ich nicht überrascht, wenn das Löschen einer großen Liste zum Stacküberlauf führen würde.

Das ist eben die Frage. Man sollte sich natürlich schon darauf verlassen können, dass der da nicht ernsthaft rekursiv durchgeht. Muss man gucken denke ich, wie weit die üblichen Compiler das raffen.

volkard

camper schrieb:

cooky451 schrieb:

wtf, ne, so war das jetzt nicht gemeint. Eine node sollte aus T + unique_ptr<node> bestehen, die liste sollte nur nen unique_ptr<node> halten. Damit werden alle Einfüge/Löschoperationen auch nur noch zu Zuweisungen zwischen unique_ptr. Ist die Frage, ob das langsamer ist, denke aber nicht.

Das halte ich für eine schlechte Idee.
Abgesehen davon, dass es Abstraktionsebenen durcheinander bringt,

Sehe ich auch so. Es spart zwar ein wenig Code, macht die Liste aber nur komplizierter.

Werner Salomon

Werner Salomon schrieb:

.. die std::list<> ist richtig schneller - und die Ursache liegt in der besseren Speicherverwaltung!

Ich muss das relativieren. Die Info ist ziemlich alt, und stammt wahrscheinlich noch aus Zeiten von MS VS6 plus Windows NT.

Der Vorteil der std::list<> lag darin, bei Konstruktor- oder assign-Aufrufen, wo mehr als ein Element an die Liste übergeben wurde, gleich für alle Elemente einen einzigen Speicherbereich zu reservieren. Die std::list machte damals einen eigenen kleinen Memorypool - inklusive Verwaltung auf.
So weit ich das einschätzen kann, ist aber das Bereitstellen von Speicher seitdem signifikant besser geworden, so dass sich dieser Aufwand wohl nicht mehr lohnt. Dies gilt insbesondere für viele Alloc's von kleinen Speicherbereichen.

Das war irgendwann durchaus ein Flaschenhals, und wohl auch die Motivation für Andrei Alexandrescus 'small object allocator' - siehe Modern C++ Design | ISBN: 9780201704310.
Dem ist aber heute nicht mehr so (ich rede jetzt nur von Windows und MS VS). Ich hatte den 'small object allocator' in einem Projekt verwenden wollen, aber dann festgestellt, dass der erreichte Geschwindigkeitsvorteil den Aufwand nicht lohnt.

Die aktuellen Implementierungen der std::list (VS8-VS10) reservieren für jedes Element einen eigenen Speicher. Aktuelle Messungen zeigen einen leichten Geschwindigkeitsvorteil für eine eigene SList gegenüber std::list und gegen eine std::forward_list ist kein Unterschied messbar.

Aber um zum Thema zurück zu kommen: Die Behauptung ein eigenes new/delete hätte gegenüber den Containern des C++-Standard Vorteile bei der Geschwindigkeit ist sicher falsch. Abgesehen davon handelt man sich so viele Nachteile ein, dass das in keiner Weise zu rechtfertigen ist. Bei 'großen' Projekten schon gar nicht.

Gruß
Werner