push_back bei std::list 3X langsamer als bei std::vector

Es macht mich bei theoretisch 10^7 möglichen re-alloks alelrdings schon stutzig, dass vector 10x schneller ist, als list.

Ich werde das mal mit größeren Daten testen. Es kann nicht bei jeder typ-größe dermaßen vorreserviert werden.

Dein ganzes Vorgehen ist ziemlich sinnlos. Du nimmst eine std::list um daraus ein vector zu machen. Warum nimmst du nicht gleich den std::vector?

Und dann erbst du von std::list und überschreibst irgendwelche Methoden... Damit zerstörst du evtl. die interne Struktur der std::list und lässt sie erst so ineffizient werden.

Mein Vorschlag: Nimm was aus der STL und programmier erst mal weiter. Sollte es später tatsächlich Probleme geben, kannst du das ganze noch immer austauschen.

Ethon

dgrat_87 schrieb:

Es macht mich bei theoretisch 10^7 möglichen re-alloks alelrdings schon stutzig, dass vector 10x schneller ist, als list.

Wenn du den gcc/clang verwendest, die libstdc++ Implementierung allokiert immer doppelt so viel. Also nichtmal annähernd so viele Allokationen.

Dabei ist Faktor 2 eine schlechte Idee, wie hier erklärt wird: https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md

Ethon

dfgdfg schrieb:

Und dann erbst du von std::list und überschreibst irgendwelche Methoden... Damit zerstörst du evtl. die interne Struktur der std::list und lässt sie erst so ineffizient werden.

Er überschreibt nix ... at() und operator[] wurden absichtlich bei std::list nicht implementiert, weil eine Liste eben nur extrem ineffizient random-access anbieten kann.

std::list<int> list = ...;
for(int i = 0; i < n; ++i)
    do_something(list[i]);

hätte eine Komplexität von n!, totale Katastrophe also.

Edit: Nix Fakultät, gerade etwas daneben, aber immer noch katastrophale Laufzeit.

Dobi

dgrat_87 schrieb:

Es kann nicht bei jeder typ-größe dermaßen vorreserviert werden.

Warum kann nicht?
Ob

#include <vector>
#include <iostream>
int main()
{
    std::vector<int> v;
    auto c(v.capacity());
    // Wir push_backend tausend mal was in einen Vector.
    for (int i(0); i < 1000; ++i)
    {
        v.push_back(i);
        // Wenn sie die Kapazitaet geaendert hat,
        // also neu allokiert und umkopiert wurde ....
        if (v.capacity()!=c)
        {
            c = v.capacity();
            // ... geben wir das aus.
            std::cout << c << std::endl;
        }
    }
}

oder

#include <vector>
#include <iostream>
#include <array>
int main()
{
    std::vector<std::array<int,3000>> v;
    auto c(v.capacity());
    // Wir push_backend tausend mal was in einen Vector.
    for (int i(0); i < 1000; ++i)
    {
        v.push_back(std::array<int,3000>());
        // Wenn sie die Kapazitaet geaendert hat,
        // also neu allokiert und umkopiert wurde ....
        if (v.capacity()!=c)
        {
            c = v.capacity();
            // ... geben wir das aus.
            std::cout << c << std::endl;
        }
    }
}

die Ausgabe des executables, das mein Compiler daraus macht, ist in beiden Fällen diese:

Wie ich vermutet habe. Die Liste wird schneller, wenn die Objektgröße steigt.
Ab einer gewissen Größe wirft vector zudem nen bad alloc.

cooky451

Wenn die Objektgröße auf was steigt? 100MB?

Ganz so schlimm ist es nicht

Kellerautomat

Reservier halt mit reserve(). Dann kannste in den vector vermutlich mehr reinstopfen.

Sone

Kellerautomat schrieb:

Reservier halt mit reserve(). Dann kannste in den vector vermutlich mehr reinstopfen.

Das bringt nichts. reserve() vergrößert max_size() nicht. reserve() kann lediglich viele Reallokationen verhindern.

Kellerautomat

Das bringt sehr wohl was, wenn der benoetigte Speicher + der momentane Speicher = temporaer waehrend einer Reallokation gebrauchte Speicher den verfuegbaren Speicher ueberschreiten, aber der benoetigte Speicher geringer ist als der verfuegbare.

Wie die meisten hier vermuten lag das Problem nicht an std::vector, sondern an einer andern Stelle begraben.
Von daher bleibe ich beim gewohnten std::vector
Reserve benutze ich btw. soweit es geht immer Es sei denn ich stell hier nen kleines snippet rein.
Ich wusste allerdings nicht, dass der std::vector in zweierpotenzen von allein reserved

BTW: Eigentlich benutz ich resize() statt reserve().

Dobi

Du weißt aber schon, dass resize was ganz anderes macht als reseve?
http://en.cppreference.com/w/cpp/container/vector/resize
http://en.cppreference.com/w/cpp/container/vector/reserve

Mittlerweile schon Vielleicht werde ich zukünftig auch mal reserv-ieren.

hustbaer

dgrat_87 schrieb:

Ich wusste allerdings nicht, dass der std::vector in zweierpotenzen von allein reserved

MSVC nimmt soweit ich weiss 3/2.
Es muss aber immer abhängig von der vorherigen Grösse sein - mit fixen Schritten könnte man die Forderungen des Standards nicht hinbekommen (amortisiert konstante Zeit für push_back ).

hustbaer schrieb:

Es muss aber immer abhängig von der vorherigen Grösse sein - mit fixen Schritten könnte man die Forderungen des Standards nicht hinbekommen

Könnte auch abhängig von den Ticks seit Systemstart sein. Oder abhängig von den bisher erledigten Reallokationen des Vektors (ist unabhängig von der Grösse wenn es durch swap() nicht verändert wird).

Jedenfalls muss immer mehr allokiert werden je grösser der Vektor wird.

hustbaer

@americanjurist
Ja std::vector könnte sich auch gleich den gesamten Speicher der Maschine grabschen. Unsinnige Alternativen sind leicht zu finden. Wenn du was an meinem immer zu kritisieren hast, dann bitte mit einen realistischen Gegenvorschlag.

Wir können uns aber auch gerne darauf einigen dass es keine sinnvolle Alternative gibt als die Wachstumsschritte von der alten Grösse abhängig zu machen.

americanjurist schrieb:

Könnte auch abhängig von den Ticks seit Systemstart sein. Oder abhängig von den bisher erledigten Reallokationen des Vektors (ist unabhängig von der Grösse wenn es durch swap() nicht verändert wird).

Beides erfüllt die Vorgaben des Standards über das Laufzeitverhalten der Operationen auf std::vector nicht, also könnte das gerade nicht sein.