Was schnelleres als std::list ??

Hi

20% meiner Zeit verbrat ich bei std::list.push_back().
Bin mir nicht sicher, ob es nicht was schnelleres gäbe.
Also das Objekt wird recht oft erzeugt, dann vier Einträge reingepusht, und anschliessend drüber iteriert mit remove_if() und einem Funktor Einträge entfernt, dann wird ausgelesen und die Liste wieder vernichtet.

Hoffe das versteht jemand :p

Danke schonmal für eure Hilfe

(sry für doppelpost)

Hab schon mit vector probiert, saugt glatt 48% statt 20%

Artchi

Naja, reservier doch vorher genug Elemente über reserve(). Wieviel Elemente gibst du denn hinten rein? Wenn du sagen wir mal 100.000 Elemente rein gibst, kannst du doch schon mal 100.000 reservieren.

Ansonst solltest du dir bewusst sein, das sowohl List als auch Vector bei push_back, iteration und bei remove_if jeweils vor und nachteile haben. Es gibt keine universellen Container, die alles am besten können. Du brauchst dummerweise von allem etwas.

Z.B. ist beim iterieren vector schneller als list. aber beim removen ist wieder list am schnellsten. Wenn es einen Container geben würde, der alles am besten kann, hätten wir nur diesen einen in der Standardlib.

Artchi schrieb:

Naja, reservier doch vorher genug Elemente über reserve(). Wieviel Elemente gibst du denn hinten rein?

Normalerweise maximal vier am Anfang, und dann werden welche entfernt.

Artchi schrieb:

Z.B. ist beim iterieren vector schneller als list. aber beim removen ist wieder list am schnellsten. Wenn es einen Container geben würde, der alles am besten kann, hätten wir nur diesen einen in der Standardlib.

Ja habs gemerkt, beim remove_if geht 40% der Zeit drauf. Wie findich jetzt ne idealere Lösung? Wär ev. ein simples Array schneller? Es sind immer nur maximal vier Einträge.

Erhard Henkes

Probiere C-array, vector, deque und list aus. Es hängt auch davon ab, welches Objekt man in den Container "pusht", "removet" usw.
Vorgehensweise siehe z.B.:
http://www.henkessoft.de/C++/C++ Fortgeschrittene/C++_Fortgeschrittene.htm#2.8._Die_Klasse_Stack_als_Wrapper_f�r

Badestrand

Je nachdem wie du es implementierst, müsste ein fixes Array aus 4 Elementen defintiv schneller sein. Sind die Objekte Grundelemente wie int, double oder so, oder class- bzw. struct-Objekte, die einen Konstruktor brauchen?

Bist du sicher das es nicht an fir selbst liegt.

- Legst du Pointer oder Objekte in der Liste ab.
Wenn du Objekte ablegst dann wird natürlich der Copy-Constructor
bei jedem push_back() aufgerufen. Ist dieser call teuer, sind Pointer
nicht vielleicht besser ?

- Beim remove_if() wird natürlich auch dein Funktor aufgerufen.
Kostet diese Funktion vielleicht viel Zeit, oder die Destruktion der
"gefundenen" Objekte.

Du solltest den Engpass näher identifizieren. Ich kann mir, so leicht,
keine Situation vorstellen in der eine Umstellung von vector auf array die
Lösung der Performance-Probleme bringt. Vielleicht solltest du ehr den
Algorithmus deines Programms als Ganzes nochmal überdenken.

Schneller ist nur mein Auto und ein Array

@Erhard Henkes
danke für den Link! sieht seeehr interessant aus...

@Opti
Versuch doch mal eine Liste oder ein Vector selbst zu programmieren Ist eigentlich sehr einfach (wenn man weiß wie). Da weiß man dann aber auch alles - was so am Code nebenbei "verbraten" werden muß...

Habe schon versuch selber sowas zu machen... Erst dabei lerne ich aber was die Sprache an sich eigentlich ist...

Erhard Henkes schrieb:

Probiere C-array, vector, deque und list aus. Es hängt auch davon ab, welches Objekt man in den Container "pusht", "removet" usw.
Vorgehensweise siehe z.B.:
http://www.henkessoft.de/C++/C++ Fortgeschrittene/C++_Fortgeschrittene.htm#2.8._Die_Klasse_Stack_als_Wrapper_f�r

WOW! Na wenn das nicht ein genialer Tutorial für C++ ist ;). Sowas habe ich noch nie zu lesen bekommen.

Sehr gut Dr. Henkes!

Erhard Henkes

Thx.

Martin Richter

Man kann einen Pool-Allokator verwenden. Das größte Problem bei kleinen Elementen in std::list ist das für jedes Element ein eigenes new aufgerufen wird. Die MFC geht hier effektiver mit um, denn hier werden die Elemente in größeren Speichblocks zusammengefasst (plex-Code).

Wenn man einen eigenen Allokator für die std::list verwendet, der einen eignen Pool nutzt, dann kann man bis zu 100% Performance gewinnen.

THX 1138

Martin Richter schrieb:

Man kann einen Pool-Allokator verwenden. Das größte Problem bei kleinen Elementen in std::list ist das für jedes Element ein eigenes new aufgerufen wird. Die MFC geht hier effektiver mit um, denn hier werden die Elemente in größeren Speichblocks zusammengefasst (plex-Code).

Wenn man einen eigenen Allokator für die std::list verwendet, der einen eignen Pool nutzt, dann kann man bis zu 100% Performance gewinnen.

Tönt spannend, wie geht sowas? Gibts da schon was fertiges?

plex-Code

peterchen

Tönt spannend, wie geht sowas? Gibts da schon was fertiges?

http://www.codeproject.com/vcpp/stl/blockallocator.asp

"Bis zu 100% Performance" ist aber etwas viel versprochen. Wo die Zeit wirklich bleibt, hängt von deinem Listenelement ab - siehe Redheads Antwort.

Martin Richter

Schlechterster Fall für new/delete ist z.B. eine Pointerliste. Wenn davon 1Mio Pointer allokiert ist solch ein Blockallokator wirklich um 100% schneller. Ganz besonders wenn es um das Zerstören der Liste geht.

peterchen

Schlechtester Fall für den Pool Allocator: Durch die Überallokation des Pools muß der Speichermanager swappen und du bist 10x langsamer.

Ich will ja nur vermeiden, daß Du überzogene Hoffnungen weckst Für sehr viele primitive Elemente ist sogar weniger als die halbe Zeit drin. aber bei 4 Elementen unbekannten Typs würde ich nix versprechen.

CStoll

Ein Problem bei der Geschwindigkeit könnte remove_if() sein - da die Algorithmen nichts über die unterliegende Datenstruktur wissen, können sie die Vorteile der Liste auch nicht ausnutzen (remove_if() "löscht", indem es alle nachfolgenden Elemente umkopiert - und je nach Größe kann das teuer werden). Da ist es vermutlich am besten, du gehst in einer Schleife über die Liste und löschst sie selber per erase().

Ansonsten: Für vier Elemente so eine aufwendige Verarbeitung? Ist es da nicht einfacher, von vornherein nur die Elemente in die Liste aufzunehmen, die deine Kriterien erfüllen?

So erstmal frohes Neues
und besten Dank für die vielen Antworten.
Hab beim Googlen die Boost Pool Library gefunden, werd mir das mal anlesen.
Wegem remove_if() und so, ich glaub langsam auch, dass ich es zu kompliziert mache...nur füllen was ich brauch tönt gut. Ev mach ich das lieber alles mit nem Array und mit Zeigern oder mit nem Buchstaben oder ner Zahl als Platzhalter, statt dem Objekt selbst.
Es handelt sich übrigens um relativ kleine Klassen mit nur einem statischen Member und 2 - 3 Methoden, Daten gibts sonst keine.

CStoll

Opti schrieb:

Daten gibts sonst keine.

Und woran unterscheidest du dann deine Objekte ;)? Wenn sie keine eigenen Daten haben, sind sie doch faktisch identisch.

CStoll schrieb:

Opti schrieb:

Daten gibts sonst keine.

Und woran unterscheidest du dann deine Objekte ;)? Wenn sie keine eigenen Daten haben, sind sie doch faktisch identisch.

Naja, am Typ..hehe..sind halt Repräsentanten und -onkels einer Art..man könnt auch einfach chars nehmen, aber der Autor des Buches wird sich schon was dabei gedacht haben..gell Marc++us