Ist std :: vector so viel langsamer als einfache Arrays?

212

Ich habe immer gedacht, dass es die allgemeine Weisheit std::vectorist, die "als Array implementiert" ist, bla bla bla. Heute bin ich runtergegangen und habe es getestet, und es scheint nicht so zu sein:

Hier sind einige Testergebnisse:

UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds

Das ist ungefähr 3 - 4 mal langsamer! Rechtfertigt nicht wirklich die vectorKommentare " Kann für ein paar Nanosekunden langsamer sein".

Und der Code, den ich verwendet habe:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector()
{
    TestTimer t("UseVector");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPushBack");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        free(pixels);
    }
}

int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}

Mache ich es falsch oder so? Oder habe ich gerade diesen Performance-Mythos gesprengt?

Ich verwende den Release-Modus in Visual Studio 2005 .


In Visual C ++ , #define _SECURE_SCL 0verringert UseVectorum die Hälfte (bringt es auf 4 Sekunden nach unten). Das ist wirklich riesig, IMO.

kizzx2
quelle
23
Einige Versionen von Vektoren, wenn Sie sich im Debug-Modus befinden, fügen zusätzliche Anweisungen hinzu, um zu überprüfen, ob Sie nicht über das Ende des Arrays hinaus zugreifen. Um echte Timings zu erhalten, müssen Sie im Release-Modus erstellen und die Optimierungen aktivieren.
Martin York
40
Es ist gut, dass Sie gemessen haben, anstatt Behauptungen zu glauben, die Sie über das Internet gehört haben.
P Shved
51
Der Vektor ist als Array implementiert. Das ist keine "konventionelle Weisheit", es ist die Wahrheit. Sie haben festgestellt, dass vectores sich um ein Allzweck-Array mit veränderbarer Größe handelt. Herzliche Glückwünsche. Wie bei allen Allzweckwerkzeugen ist es möglich, spezielle Situationen zu entwickeln, in denen sie nicht optimal sind. Aus diesem Grund besteht die konventionelle Weisheit darin, mit a zu beginnenvector und gegebenenfalls Alternativen in Betracht zu ziehen.
Dennis Zickefoose
37
lol, was ist der Geschwindigkeitsunterschied zwischen "schmutziges Geschirr in eine Spüle werfen" und "schmutziges Geschirr in eine Spüle werfen und prüfen, ob es nicht kaputt gegangen ist"?
Imre L
9
Zumindest auf VC2010 scheint der Hauptunterschied darin zu liegen, dass malloc () schneller ist als resize (). Entfernen Sie die Speicherzuordnung aus dem Timing, kompilieren Sie mit _ITERATOR_DEBUG_LEVEL == 0 und die Ergebnisse sind dieselben.
Andreas Magnusson

Antworten:

260

Verwenden Sie Folgendes:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray in 2.196 Sekunden abgeschlossen
UseVector in 4.412 Sekunden abgeschlossen
UseVectorPushBack in 8.017 Sekunden abgeschlossen
Das Ganze in 14.626 Sekunden abgeschlossen

Das Array ist also doppelt so schnell wie der Vektor.

Aber nach genauer Blick auf den Code dies wird erwartet; wenn Sie zweimal über den Vektor und das Array nur einmal laufen. Hinweis: Wenn Sie resize()den Vektor verwenden, weisen Sie nicht nur den Speicher zu, sondern durchlaufen auch den Vektor und rufen den Konstruktor für jedes Element auf.

Ordnen Sie den Code leicht neu an, sodass der Vektor jedes Objekt nur einmal initialisiert:

 std::vector<Pixel>  pixels(dimensions * dimensions, Pixel(255,0,0));

Jetzt mache ich wieder das gleiche Timing:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector in 2.216 Sekunden abgeschlossen

Die Leistung des Vektors ist jetzt nur geringfügig schlechter als die des Arrays. IMO ist dieser Unterschied unbedeutend und kann durch eine ganze Reihe von Dingen verursacht werden, die nicht mit dem Test verbunden sind.

Ich würde auch berücksichtigen, dass Sie das Pixel-Objekt in der UseArrray()Methode nicht korrekt initialisieren / zerstören , da weder Konstruktor noch Destruktor aufgerufen werden (dies ist möglicherweise kein Problem für diese einfache Klasse, aber etwas etwas komplexeres (dh mit Zeigern oder Elementen) mit Zeigern) wird Probleme verursachen.

Loki Astari
quelle
48
@ kizzx2: Du musst reserve()statt verwenden resize(). Dadurch wird Platz für die Objekte zugewiesen (dh die Kapazität des Vektors wird geändert ), die Objekte werden jedoch nicht erstellt (dh die Größe des Vektors bleibt unverändert).
James McNellis
25
Sie führen 1 000 000 000 Array-Zugriffe durch. Der Zeitunterschied beträgt 0,333 Sekunden. Oder eine Differenz von 0,000000000333 pro Array-Zugriff. Angenommen, ein 2,33-GHz-Prozessor wie meiner entspricht 0,7 Befehls-Pipeline-Stufen pro Array-Zugriff. Der Vektor sieht also so aus, als würde er einen zusätzlichen Befehl pro Zugriff verwenden.
Martin York
3
@James McNellis: Sie können nicht nur ersetzen resize()mit reserve(), denn dies ist nicht der Vektor der internen Vorstellung von seiner eigenen Größe nicht anpassen, so dass nachfolgende Schreibvorgänge auf ihre Elemente technisch sind „über das Ende zu schreiben“ und UB produzieren. Obwohl sich in der Praxis jede STL-Implementierung in dieser Hinsicht "selbst verhält", wie synchronisieren Sie die Größe des Vektors neu? Wenn Sie versuchen, resize() nach dem Auffüllen des Vektors aufzurufen , werden möglicherweise alle diese Elemente mit standardmäßig erstellten Werten überschrieben!
j_random_hacker
8
@j_random_hacker: Ist das nicht genau das, was ich gesagt habe? Ich dachte, ich wäre mir sehr klar darüber, dass sich reservenur die Kapazität eines Vektors ändert, nicht seine Größe.
James McNellis
7
Okay, mach eine Figur. Bei Vektormethoden gab es viele ausnahmebedingte Kruft. Das Hinzufügen /EHsczu Kompilierungsschaltern hat das bereinigt und assign()schlägt jetzt das Array. Yay.
Pavel Minaev
55

Gute Frage. Ich kam hierher und erwartete, eine einfache Lösung zu finden, die die Vektortests beschleunigen würde. Das hat nicht ganz so geklappt, wie ich erwartet hatte!

Optimierung hilft, reicht aber nicht aus. Bei aktivierter Optimierung sehe ich immer noch einen 2-fachen Leistungsunterschied zwischen UseArray und UseVector. Interessanterweise war UseVector ohne Optimierung deutlich langsamer als UseVectorPushBack.

# g++ -Wall -Wextra -pedantic -o vector vector.cpp
# ./vector
UseArray completed in 20.68 seconds
UseVector completed in 120.509 seconds
UseVectorPushBack completed in 37.654 seconds
The whole thing completed in 178.845 seconds
# g++ -Wall -Wextra -pedantic -O3 -o vector vector.cpp
# ./vector
UseArray completed in 3.09 seconds
UseVector completed in 6.09 seconds
UseVectorPushBack completed in 9.847 seconds
The whole thing completed in 19.028 seconds

Idee 1 - Verwenden Sie new [] anstelle von malloc

Ich habe versucht malloc(), new[]in UseArray zu wechseln , damit die Objekte erstellt werden. Und von der Zuweisung einzelner Felder zur Zuweisung einer Pixelinstanz. Oh, und die innere Schleifenvariable umbenennen in j.

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {   
        int dimension = 999;

        // Same speed as malloc().
        Pixel * pixels = new Pixel[dimension * dimension];

        for(int j = 0 ; j < dimension * dimension; ++j)
            pixels[j] = Pixel(255, 0, 0);

        delete[] pixels;
    }
}

Überraschenderweise (für mich) machte keine dieser Änderungen einen Unterschied. Nicht einmal die Änderung, bei new[]der standardmäßig alle Pixel erstellt werden. Es scheint, dass gcc die Standardkonstruktoraufrufe bei Verwendung optimieren kann new[], aber nicht bei Verwendung vector.

Idee 2 - Entfernen Sie wiederholte Operator [] -Aufrufe

Ich habe auch versucht, die dreifache operator[]Suche loszuwerden und den Verweis auf zwischenzuspeichern pixels[j]. Das hat UseVector tatsächlich verlangsamt! Hoppla.

for(int j = 0; j < dimension * dimension; ++j)
{
    // Slower than accessing pixels[j] three times.
    Pixel &pixel = pixels[j];
    pixel.r = 255;
    pixel.g = 0;
    pixel.b = 0;
}

# ./vector 
UseArray completed in 3.226 seconds
UseVector completed in 7.54 seconds
UseVectorPushBack completed in 9.859 seconds
The whole thing completed in 20.626 seconds

Idee 3 - Konstruktoren entfernen

Was ist mit dem vollständigen Entfernen der Konstruktoren? Dann kann gcc vielleicht die Konstruktion aller Objekte optimieren, wenn die Vektoren erstellt werden. Was passiert, wenn wir Pixel ändern in:

struct Pixel
{
    unsigned char r, g, b;
};

Ergebnis: ca. 10% schneller. Immer noch langsamer als ein Array. Hm.

# ./vector 
UseArray completed in 3.239 seconds
UseVector completed in 5.567 seconds

Idee 4 - Verwenden Sie den Iterator anstelle des Schleifenindex

Wie wäre es mit einem vector<Pixel>::iteratoranstelle eines Schleifenindex?

for (std::vector<Pixel>::iterator j = pixels.begin(); j != pixels.end(); ++j)
{
    j->r = 255;
    j->g = 0;
    j->b = 0;
}

Ergebnis:

# ./vector 
UseArray completed in 3.264 seconds
UseVector completed in 5.443 seconds

Nein, nicht anders. Zumindest ist es nicht langsamer. Ich dachte, dies hätte eine ähnliche Leistung wie # 2, wo ich eine Pixel&Referenz verwendet habe.

Fazit

Selbst wenn einige intelligente Cookies herausfinden, wie die Vektorschleife so schnell wie die Array-Schleife gemacht werden kann, spricht dies nicht gut für das Standardverhalten von std::vector. So viel dazu, dass der Compiler intelligent genug ist, um die gesamte C ++ - Qualität zu optimieren und STL-Container so schnell wie Raw-Arrays zu machen.

Unter dem Strich kann der Compiler die No-Op-Standardkonstruktoraufrufe bei der Verwendung nicht optimieren std::vector. Wenn Sie Plain verwenden, werden new[]diese optimiert. Aber nicht mit std::vector. Selbst wenn Sie Ihren Code neu schreiben können, um die Konstruktoraufrufe zu eliminieren, die angesichts des Mantras hier herumfliegen: "Der Compiler ist schlauer als Sie. Die STL ist genauso schnell wie normal C. Machen Sie sich darüber keine Sorgen."

John Kugelman
quelle
2
Nochmals vielen Dank, dass Sie den Code tatsächlich ausgeführt haben. Es ist manchmal leicht, ohne Grund verprügelt zu werden, wenn jemand versucht, populäre Meinungen in Frage zu stellen.
kizzx2
3
"So viel dazu, dass der Compiler intelligent genug ist, um die gesamte C ++ - Qualität zu optimieren und STL-Container so schnell wie Raw-Arrays zu machen." Schöne Kommentare. Ich habe die Theorie, dass dieser "Compiler ist schlau" nur ein Mythos ist - C ++ - Parsing ist extrem schwierig und der Compiler ist nur eine Maschine.
kizzx2
3
Ich weiß nicht. Sicher, er konnte den Array-Test verlangsamen , aber er beschleunigte den Vektor- Test nicht . Ich habe oben bearbeitet, wo ich die Konstruktoren aus Pixel entfernt und daraus eine einfache Struktur gemacht habe, und es war immer noch langsam. Das sind schlechte Nachrichten für alle, die einfache Typen wie verwenden vector<int>.
John Kugelman
2
Ich wünschte, ich könnte Ihre Antwort wirklich zweimal positiv bewerten. Kluge Ideen zum Ausprobieren (obwohl keine wirklich funktionierte), an die ich nicht einmal denken konnte!
kizzx2
9
Ich wollte nur darauf hinweisen, dass die Komplexität des Parsens von C ++ (die wahnsinnig komplex ist, ja) nichts mit der Qualität der Optimierung zu tun hat. Letzteres geschieht normalerweise auf Stufen, auf denen das Analyseergebnis bereits mehrfach in eine Darstellung auf viel niedrigerer Ebene umgewandelt wird.
Pavel Minaev
44

Dies ist eine alte, aber beliebte Frage.

Zu diesem Zeitpunkt werden viele Programmierer in C ++ 11 arbeiten. Und in C ++ 11 läuft der geschriebene OP-Code für UseArrayoder genauso schnell UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

Das grundlegende Problem bestand darin, dass Ihre PixelStruktur zwar nicht initialisiert wurde, jedoch std::vector<T>::resize( size_t, T const&=T() )eine Standardkonstruktion verwendet Pixelund diese kopiert . Der Compiler bemerkte nicht, dass er aufgefordert wurde, nicht initialisierte Daten zu kopieren, und führte die Kopie tatsächlich durch.

Hat in C ++ 11 std::vector<T>::resizezwei Überladungen. Das erste ist std::vector<T>::resize(size_t), das andere ist std::vector<T>::resize(size_t, T const&). Das heißt, wenn Sie resizeohne ein zweites Argument aufrufen , werden einfach Standardkonstrukte erstellt, und der Compiler ist intelligent genug, um zu erkennen, dass die Standardkonstruktion nichts bewirkt, sodass der Durchlauf über den Puffer übersprungen wird.

(Die beiden Überladungen wurden hinzugefügt, um bewegliche, konstruierbare und nicht kopierbare Typen zu verarbeiten. Die Leistungsverbesserung bei der Arbeit an nicht initialisierten Daten ist ein Bonus.)

Die push_backLösung führt auch eine Zaunpfostenprüfung durch, wodurch sie verlangsamt wird, sodass sie langsamer als die mallocVersion bleibt .

Live-Beispiel (ich habe auch den Timer durch ersetzt chrono::high_resolution_clock).

Beachten Sie, dass Sie dies mit einem benutzerdefinierten std::vectorAllokator tun können, wenn Sie eine Struktur haben, für die normalerweise eine Initialisierung erforderlich ist, die Sie jedoch nach dem Erweitern Ihres Puffers verarbeiten möchten . Wenn Sie es dann in einen normaleren std::vectorZustand versetzen möchten , glaube ich, dass eine sorgfältige Verwendung allocator_traitsund Überschreibung dies ==möglicherweise bewirken könnte, bin mir aber nicht sicher.

Yakk - Adam Nevraumont
quelle
Wäre auch interessant zu sehen, wie emplace_backes gegen push_backhier geht.
Daniel
1
Ich kann Ihre Ergebnisse nicht reproduzieren. Das Kompilieren Ihres Codes clang++ -std=c++11 -O3hat UseArray completed in 2.02e-07 secondsund UseVector completed in 1.3026 seconds. Ich habe auch eine UseVectorEmplaceBackVersion hinzugefügt, die ca. ist. 2,5x so schnell wie UseVectorPushBack.
Daniel
1
@ Daniel Chancen sind, dass der Optimierer alles aus der Array-Version entfernt hat. Immer ein Risiko bei Mikro-Benchmarks.
Yakk - Adam Nevraumont
4
Ja, Sie haben Recht, haben sich nur die Baugruppe angesehen (oder das Fehlen davon). Hätte angesichts des Unterschieds von ~ 6448514x wahrscheinlich daran denken sollen! Ich frage mich, warum die Vektorversion nicht dieselbe Optimierung durchführen kann. Dies geschieht, wenn sie mit den Dimensionen erstellt und nicht in der Größe geändert wird.
Daniel
34

Um fair zu sein, können Sie eine C ++ - Implementierung nicht mit einer C-Implementierung vergleichen, wie ich Ihre Malloc-Version nennen würde. malloc erstellt keine Objekte - es weist nur Rohspeicher zu. Dass Sie diesen Speicher dann als Objekte behandeln, ohne den Konstruktor aufzurufen, ist schlechtes C ++ (möglicherweise ungültig - das überlasse ich den Sprachanwälten).

Das heißt, das einfache Ändern des Mallocs in new Pixel[dimensions*dimensions]und das freie Ändern in delete [] pixelsmacht keinen großen Unterschied bei der einfachen Implementierung von Pixel, die Sie haben. Hier sind die Ergebnisse auf meiner Box (E6600, 64-Bit):

UseArray completed in 0.269 seconds
UseVector completed in 1.665 seconds
UseVectorPushBack completed in 7.309 seconds
The whole thing completed in 9.244 seconds

Aber mit einer kleinen Änderung dreht sich der Spieß um:

Pixel.h

struct Pixel
{
    Pixel();
    Pixel(unsigned char r, unsigned char g, unsigned char b);

    unsigned char r, g, b;
};

Pixel.cc

#include "Pixel.h"

Pixel::Pixel() {}
Pixel::Pixel(unsigned char r, unsigned char g, unsigned char b) 
  : r(r), g(g), b(b) {}

main.cc

#include "Pixel.h"
[rest of test harness without class Pixel]
[UseArray now uses new/delete not malloc/free]

So zusammengestellt:

$ g++ -O3 -c -o Pixel.o Pixel.cc
$ g++ -O3 -c -o main.o main.cc
$ g++ -o main main.o Pixel.o

Wir erhalten sehr unterschiedliche Ergebnisse:

UseArray completed in 2.78 seconds
UseVector completed in 1.651 seconds
UseVectorPushBack completed in 7.826 seconds
The whole thing completed in 12.258 seconds

Mit einem nicht inlinierten Konstruktor für Pixel schlägt std :: vector jetzt ein Raw-Array.

Es scheint, dass die Komplexität der Zuordnung durch std :: vector und std: allocator zu groß ist, um so effektiv wie einfach optimiert zu werden new Pixel[n]. Wir können jedoch sehen, dass das Problem einfach in der Zuordnung und nicht im Vektorzugriff liegt, indem wir einige der Testfunktionen optimieren, um den Vektor / das Array einmal zu erstellen, indem wir ihn außerhalb der Schleife verschieben:

void UseVector()
{
    TestTimer t("UseVector");

    int dimension = 999;
    std::vector<Pixel> pixels;
    pixels.resize(dimension * dimension);

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

und

void UseArray()
{
    TestTimer t("UseArray");

    int dimension = 999;
    Pixel * pixels = new Pixel[dimension * dimension];

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
    delete [] pixels;
}

Wir erhalten jetzt diese Ergebnisse:

UseArray completed in 0.254 seconds
UseVector completed in 0.249 seconds
UseVectorPushBack completed in 7.298 seconds
The whole thing completed in 7.802 seconds

Daraus können wir lernen, dass std :: vector mit einem Raw-Array für den Zugriff vergleichbar ist. Wenn Sie den Vektor / das Array jedoch mehrmals erstellen und löschen müssen, ist das Erstellen eines komplexen Objekts zeitaufwändiger als das Erstellen eines einfachen Arrays wenn der Konstruktor des Elements nicht inline ist. Ich finde das nicht sehr überraschend.

camh
quelle
3
Sie haben noch einen Inline-Konstruktor - den Kopierkonstruktor.
Ben Voigt
26

Versuchen Sie es damit:

void UseVectorCtor()
{
    TestTimer t("UseConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
    }
}

Ich bekomme fast genau die gleiche Leistung wie mit Array.

Die Sache vectorist, dass es ein viel allgemeineres Werkzeug als ein Array ist. Und das bedeutet, dass Sie überlegen müssen, wie Sie es verwenden. Es kann auf viele verschiedene Arten verwendet werden und bietet Funktionen, die ein Array nicht einmal hat. Und wenn Sie es für Ihren Zweck "falsch" verwenden, entsteht viel Overhead. Wenn Sie es jedoch richtig verwenden, handelt es sich normalerweise um eine Datenstruktur ohne Overhead. In diesem Fall besteht das Problem darin, dass Sie den Vektor separat initialisiert haben (wodurch alle Elemente ihren Standard-Ctor aufgerufen haben) und dann jedes Element einzeln mit dem richtigen Wert überschreiben. Das ist für den Compiler viel schwieriger zu optimieren, als wenn Sie dasselbe mit einem Array tun. Aus diesem Grund bietet der Vektor einen Konstruktor, mit dem Sie genau das tun können: .NX

Und wenn Sie das verwenden, ist der Vektor genauso schnell wie ein Array.

Also nein, Sie haben den Performance-Mythos nicht gesprengt. Aber Sie haben gezeigt, dass es nur wahr ist, wenn Sie den Vektor optimal nutzen, was auch ein ziemlich guter Punkt ist. :) :)

Auf der positiven Seite ist es wirklich die einfachste Verwendung, die sich als die schnellste herausstellt. Wenn Sie mein Code-Snippet (eine einzelne Zeile) mit John Kugelmans Antwort vergleichen, die jede Menge Optimierungen und Optimierungen enthält, die den Leistungsunterschied immer noch nicht ganz beseitigen, ist es ziemlich klar, dass vectores doch ziemlich clever gestaltet ist. Sie müssen nicht durch Reifen springen, um eine Geschwindigkeit zu erreichen, die einem Array entspricht. Im Gegenteil, Sie müssen die einfachste Lösung verwenden.

jalf
quelle
1
Ich frage mich immer noch, ob dies ein fairer Vergleich ist. Wenn Sie die innere Schleife entfernen, besteht das Array-Äquivalent darin, ein einzelnes Pixelobjekt zu erstellen und dieses dann über das gesamte Array zu verteilen.
John Kugelman
1
Die Verwendung new[]führt dieselben Standardkonstruktionen aus vector.resize()wie die, ist jedoch viel schneller. new[]+ innere Schleife sollte die gleiche Geschwindigkeit haben wie vector.resize()+ innere Schleife, aber es ist nicht so, es ist fast doppelt so schnell.
John Kugelman
@ John: Es ist ein fairer Vergleich. Im ursprünglichen Code wird das Array zugewiesen, mit mallocdem nichts initialisiert oder erstellt wird. Es handelt sich also genau wie in meinem vectorBeispiel um einen Single-Pass-Algorithmus . Und was new[]die Antwort ist offensichtlich , dass beide erfordern zwei Durchgänge, aber im new[]Fall der Compiler in der Lage , zu optimieren , dass zusätzlicher Aufwand entfernt, die sie in der nicht tut vectorFall. Aber ich verstehe nicht, warum es interessant ist, was in suboptimalen Fällen passiert. Wenn Sie Wert auf Leistung legen, schreiben Sie keinen solchen Code.
Jalf
@ John: Interessanter Kommentar. Wenn ich über das gesamte Array vector::resize()hinwegblitzen wollte, ist Array wohl wieder die optimale Lösung - da ich nicht sagen kann , dass ich einen kontingenten Speicherblock erhalten soll, ohne Zeit damit zu verschwenden, nutzlose Konstruktoren aufzurufen.
Kizzx2
@ kizzx2: ja und nein. Ein Array wird normalerweise auch in C ++ initialisiert. In C würden Sie verwenden, mallocdas keine Initialisierung durchführt, aber in C ++ mit Nicht-POD-Typen nicht funktioniert. Im allgemeinen Fall wäre ein C ++ - Array genauso schlecht. Vielleicht ist die Frage, ob Sie, wenn Sie dieses Blitting häufig durchführen, nicht dasselbe Array / denselben Vektor wiederverwenden würden? Und wenn Sie das tun, zahlen Sie die Kosten für "nutzlose Konstrukteure" nur einmal zu Beginn. Das eigentliche Blitting geht doch genauso schnell.
Jalf
22

Es war kaum ein fairer Vergleich, als ich Ihren Code zum ersten Mal betrachtete. Ich dachte definitiv, Sie würden Äpfel nicht mit Äpfeln vergleichen. Also dachte ich, lassen Sie uns Konstruktoren und Destruktoren bei allen Tests aufrufen. und dann vergleichen.

const size_t dimension = 1000;

void UseArray() {
    TestTimer t("UseArray");
    for(size_t j = 0; j < dimension; ++j) {
        Pixel* pixels = new Pixel[dimension * dimension];
        for(size_t i = 0 ; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
        delete[] pixels;
    }
}

void UseVector() {
    TestTimer t("UseVector");
    for(size_t j = 0; j < dimension; ++j) {
        std::vector<Pixel> pixels(dimension * dimension);
        for(size_t i = 0; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
    }
}

int main() {
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();

    return 0;
}

Meine Gedanken waren, dass sie mit diesem Setup genau gleich sein sollten. Es stellt sich heraus, ich habe mich geirrt.

UseArray completed in 3.06 seconds
UseVector completed in 4.087 seconds
The whole thing completed in 10.14 seconds

Warum trat dieser Leistungsverlust von 30% überhaupt auf? Die STL enthält alles in den Headern, daher sollte es dem Compiler möglich gewesen sein, alles zu verstehen, was erforderlich war.

Meine Gedanken waren, dass die Schleife alle Werte für den Standardkonstruktor initialisiert. Also habe ich einen Test durchgeführt:

class Tester {
public:
    static int count;
    static int count2;
    Tester() { count++; }
    Tester(const Tester&) { count2++; }
};
int Tester::count = 0;
int Tester::count2 = 0;

int main() {
    std::vector<Tester> myvec(300);
    printf("Default Constructed: %i\nCopy Constructed: %i\n", Tester::count, Tester::count2);

    return 0;
}

Die Ergebnisse waren wie ich vermutet hatte:

Default Constructed: 1
Copy Constructed: 300

Dies ist eindeutig die Ursache für die Verlangsamung, die Tatsache, dass der Vektor den Kopierkonstruktor verwendet, um die Elemente eines standardmäßig erstellten Objekts zu initialisieren.

Dies bedeutet, dass während der Konstruktion des Vektors die folgende Pseudooperationsreihenfolge auftritt:

Pixel pixel;
for (auto i = 0; i < N; ++i) vector[i] = pixel;

Was aufgrund des vom Compiler erstellten impliziten Kopierkonstruktors auf Folgendes erweitert wird:

Pixel pixel;
for (auto i = 0; i < N; ++i) {
    vector[i].r = pixel.r;
    vector[i].g = pixel.g;
    vector[i].b = pixel.b;
}

So Standard Pixelbleibt un-initialisiert, während der Rest initialisiert wird mit dem Standard Pixel‚s un initialisiert Werte.

Im Vergleich zur alternativen Situation mit New[]/ Delete[]:

int main() {
    Tester* myvec = new Tester[300];

    printf("Default Constructed: %i\nCopy Constructed:%i\n", Tester::count, Tester::count2);

    delete[] myvec;

    return 0;
}

Default Constructed: 300
Copy Constructed: 0

Sie werden alle ihren nicht initialisierten Werten überlassen und ohne die doppelte Iteration über die Sequenz.

Wie können wir diese Informationen testen? Versuchen wir, den impliziten Kopierkonstruktor zu überschreiben.

Pixel(const Pixel&) {}

Und die Ergebnisse?

UseArray completed in 2.617 seconds
UseVector completed in 2.682 seconds
The whole thing completed in 5.301 seconds

Wenn Sie also sehr oft Hunderte von Vektoren erstellen, überdenken Sie Ihren Algorithmus .

In jedem Fall ist die STL- Implementierung aus einem unbekannten Grund nicht langsamer, sondern macht genau das, was Sie verlangen. Ich hoffe du weißt es besser.

verzögert kaviar
quelle
3
Nach dem Spaß, den wir (Sie und ich und andere kluge Leute hier) hatten, zu urteilen, ist die "Hoffnung" der STL-Implementierung tatsächlich eine ziemlich anspruchsvolle: P Grundsätzlich können wir übertreiben und daraus schließen, dass ich alle Quellen gelesen und analysiert habe Code. Wie auch immer: P
kizzx2
1
Ehrfürchtig! In VS 2013 war der Vektor dadurch schneller als bei Arrays. Obwohl es den Anschein hat, dass Sie für leistungskritische Systeme STL häufig testen müssen, um es effektiv nutzen zu können.
Rozina
7

Versuchen Sie, aktivierte Iteratoren zu deaktivieren und im Release-Modus zu erstellen. Sie sollten keinen großen Leistungsunterschied feststellen.

kloffy
quelle
1
Versucht #define _SECURE_SCL 0. Das hat UseVectorungefähr 4 Sekunden gedauert (ähnlich wie gccunten), aber es ist immer noch doppelt so langsam.
kizzx2
Dies ist mit ziemlicher Sicherheit die Ursache. Microsoft lässt uns den Iterator standardmäßig sowohl für das Debuggen als auch für das Release standardmäßig debuggen. Wir haben festgestellt, dass dies die Hauptursache für eine massive Verlangsamung nach dem Upgrade von 2003 auf 2008 ist. Auf jeden Fall eine der schädlichsten Fallstricke von Visual Studio.
Doug T.
2
@ kizzx2 Es gibt ein anderes Makro zum Deaktivieren: HAS_ITERATOR_DEBUGGING oder ähnliches.
Doug T.
Wie @Martin und meine Antworten zeigen, zeigt gcc das gleiche Muster, auch bei Optimierung bei -O3.
John Kugelman
1
@ Doug: Wenn ich mir das Dokument anschaue, denke ich, dass _HAS_ITERATOR_DEBUGGINGes im Release-Build deaktiviert ist: msdn.microsoft.com/en-us/library/aa985939(VS.80).aspx
kizzx2
4

GNU STL (und andere), gegeben vector<T>(n), default konstruieren ein prototypische Objekt T()- der Compiler den leeren Konstruktor optimiert weg - aber dann eine Kopie jegliche Mülls passiert ist in den Speicheradressen nun für das Objekt reserviert sein wird von der STL genommen __uninitialized_fill_n_aux, die Schleifen, die Kopien dieses Objekts als Standardwerte im Vektor füllen. "Meine" STL ist also kein Schleifenkonstruieren, sondern Konstruieren und dann Schleifen / Kopieren. Es ist nicht intuitiv, aber ich hätte mich daran erinnern müssen, als ich eine aktuelle Frage zum Stapelüberlauf zu diesem Punkt kommentierte: Das Konstrukt / die Kopie kann für referenzgezählte Objekte usw. effizienter sein.

So:

vector<T> x(n);

oder

vector<T> x;
x.resize(n);

ist - bei vielen STL-Implementierungen - so etwas wie:

T temp;
for (int i = 0; i < n; ++i)
    x[i] = temp;

Das Problem ist, dass die aktuelle Generation von Compiler-Optimierern nicht aus der Erkenntnis heraus zu funktionieren scheint, dass Temp nicht initialisierter Müll ist, und die Schleifen- und Standardaufrufe des Kopierkonstruktors nicht optimieren kann. Sie könnten glaubwürdig argumentieren, dass Compiler dies auf keinen Fall optimieren sollten, da ein Programmierer, der das Obige schreibt, eine vernünftige Erwartung hat, dass alle Objekte nach der Schleife identisch sind, selbst wenn es sich um Müll handelt (übliche Einschränkungen bezüglich 'identisch' / operator == vs. memcmp / operator = etc gelten). Es ist nicht zu erwarten, dass der Compiler einen zusätzlichen Einblick in den größeren Kontext von std :: vector <> oder die spätere Verwendung der Daten erhält, die diese Optimierung für sicher halten würden.

Dies kann der offensichtlicheren, direkteren Implementierung gegenübergestellt werden:

for (int i = 0; i < n; ++i)
    x[i] = T();

Was wir von einem Compiler erwarten können, um zu optimieren.

Beachten Sie Folgendes, um die Rechtfertigung für diesen Aspekt des Verhaltens des Vektors etwas genauer zu erläutern:

std::vector<big_reference_counted_object> x(10000);

Es ist eindeutig ein großer Unterschied, ob wir 10000 unabhängige Objekte gegenüber 10000 Objekten erstellen, die auf dieselben Daten verweisen. Es gibt ein vernünftiges Argument dafür, dass der Vorteil des Schutzes gelegentlicher C ++ - Benutzer vor versehentlichem Handeln etwas so Teueres die sehr geringen realen Kosten einer schwer zu optimierenden Kopierkonstruktion überwiegt.

ORIGINAL ANTWORT (als Referenz / Sinn für die Kommentare): Keine Chance. Der Vektor ist so schnell wie ein Array, zumindest wenn Sie sinnvoll Platz reservieren. ...

Tony Delroy
quelle
6
Ich kann es wirklich nicht rechtfertigen, dass diese Antwort für irgendjemanden etwas Nützliches ist. Ich hoffe ich konnte zweimal abstimmen.
kizzx2
-1, da geht meine Unterstützung auf kizzx2. Vektor wird nie so schnell wie Array sein, aufgrund der zusätzlichen Funktion, die es bietet, Regel des Universums, alles hat einen Preis!
YeenFei
Sie verpassen es, Tony ... es ist ein Beispiel für einen künstlichen Benchmark, aber es beweist, was es vorgibt.
Potatoswatter
Rosen sind grün, Veilchen sind orange, die Abstimmungen sind bitter, aber die Antwort bittet sie.
Pavel Minaev
3

Die Antwort von Martin York stört mich, weil es wie ein Versuch erscheint, das Initialisierungsproblem unter den Teppich zu streichen. Zu Recht identifiziert er jedoch redundante Standardkonstruktionen als Ursache für Leistungsprobleme.

[EDIT: Martins Antwort schlägt nicht mehr vor, den Standardkonstruktor zu ändern.]

Für das unmittelbare Problem könnten Sie sicherlich vector<Pixel>stattdessen die 2-Parameter-Version des ctor aufrufen :

std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));

Dies funktioniert, wenn Sie mit einem konstanten Wert initialisieren möchten, was häufig der Fall ist. Das allgemeinere Problem ist jedoch: Wie können Sie effizient mit etwas Komplizierterem als einem konstanten Wert initialisieren?

Hierfür können Sie back_insert_iteratoreinen Iteratoradapter verwenden. Hier ist ein Beispiel mit einem Vektor von ints, obwohl die allgemeine Idee für Pixels genauso gut funktioniert :

#include <iterator>
// Simple functor return a list of squares: 1, 4, 9, 16...
struct squares {
    squares() { i = 0; }
    int operator()() const { ++i; return i * i; }

private:
    int i;
};

...

std::vector<int> v;
v.reserve(someSize);     // To make insertions efficient
std::generate_n(std::back_inserter(v), someSize, squares());

Alternativ können Sie copy()oder transform()anstelle von verwenden generate_n().

Der Nachteil ist, dass die Logik zum Erstellen der Anfangswerte in eine separate Klasse verschoben werden muss, was weniger praktisch ist als das Einrichten (obwohl Lambdas in C ++ 1x dies viel schöner machen). Ich gehe auch davon aus, dass dies immer noch nicht so schnell sein wird wie eine malloc()Nicht-STL-basierte Version, aber ich gehe davon aus, dass es eng wird, da nur eine Konstruktion für jedes Element ausgeführt wird.

j_random_hacker
quelle
2

Die Vektoraufrufe rufen zusätzlich Pixelkonstruktoren auf.

Jedes verursacht fast eine Million ctor-Läufe, die Sie planen.

edit: dann gibt es die äußere 1 ... 1000 Schleife, also mach, dass eine Milliarde ctor anruft!

Bearbeiten 2: Es wäre interessant, die Demontage für den UseArray-Fall zu sehen. Ein Optimierer könnte das Ganze weg optimieren, da es keine andere Wirkung hat als das Brennen der CPU.

Graham Perks
quelle
Sie haben Recht, aber die Frage ist: Wie können diese sinnlosen CTOR-Anrufe deaktiviert werden? Es ist einfach für den Nicht-STL-Ansatz, aber schwierig / hässlich für den STL-Weg.
j_random_hacker
1

So funktioniert die push_backMethode in Vektor:

  1. Der Vektor weist bei der Initialisierung X Speicherplatz zu.
  2. Wie unten angegeben, wird geprüft, ob im aktuellen zugrunde liegenden Array Platz für das Element vorhanden ist.
  3. Es erstellt eine Kopie des Elements im Push_back-Aufruf.

Nach dem Aufruf von push_backX Elementen:

  1. Der Vektor ordnet kX Platz in ein zweites Array um.
  2. Es kopiert die Einträge des ersten Arrays auf das zweite.
  3. Verwirft das erste Array.
  4. Verwendet jetzt das zweite Array als Speicher, bis es kX-Einträge erreicht.

Wiederholen. Wenn du nicht bistreserving Weltraum sind, wird es definitiv langsamer. Mehr noch, wenn es teuer ist, den Gegenstand zu kopieren, dann wird dich 'push_back' so lebendig essen.

In vectorBezug auf die Sache mit dem Array muss ich den anderen Leuten zustimmen. Führen Sie das Release aus, aktivieren Sie die Optimierungen und setzen Sie ein paar weitere Flags ein, damit die freundlichen Mitarbeiter von Microsoft es nicht für Sie tun.

Wenn Sie die Größe nicht ändern müssen, verwenden Sie Boost.Array.

Wheaties
quelle
Ich verstehe, dass die Leute nicht gerne eine Menge Code lesen, wenn er wörtlich veröffentlicht wird. Aber ich habe verwendet, reservewie ich sollte.
kizzx2
Entschuldigung, ich habe es verpasst. War nichts anderes, was ich dort aufstellte, überhaupt hilfreich?
Wheaties
push_backhat konstante Zeit amortisiert. Es hört sich so an, als würden Sie einen O (N) -Prozess beschreiben. (Die Schritte 1 und 3 scheinen völlig fehl am Platz zu sein.) Was push_backOP langsam macht, ist die Bereichsprüfung, um festzustellen, ob eine Neuzuweisung erforderlich ist, die Aktualisierung der Zeiger, die Überprüfung gegen NULL innerhalb der Platzierung newund andere kleine Dinge, die normalerweise übertönt werden die eigentliche Arbeit des Programms.
Potatoswatter
Es wird langsamer, auch reservewenn es immer noch diese Überprüfung (ob es neu zugewiesen werden muss) bei jedem durchführen muss push_back.
Pavel Minaev
Alles gute Punkte. Was ich beschreibe, klingt wie ein O (N) -Prozess, ist es aber nicht, na ja, nicht ganz. Die meisten Leute, die ich kenne, verstehen nicht, wie avector Benutzer seine Größenänderungsfunktion ausführt, es ist nur "Magie". Lassen Sie mich das hier etwas näher erläutern.
Wheaties
1

Einige Profilerdaten (Pixel sind auf 32 Bit ausgerichtet):

g++ -msse3 -O3 -ftree-vectorize -g test.cpp -DNDEBUG && ./a.out
UseVector completed in 3.123 seconds
UseArray completed in 1.847 seconds
UseVectorPushBack completed in 9.186 seconds
The whole thing completed in 14.159 seconds

Blah

andrey@nv:~$ opannotate --source libcchem/src/a.out  | grep "Total samples for file" -A3
Overflow stats not available
 * Total samples for file : "/usr/include/c++/4.4/ext/new_allocator.h"
 *
 * 141008 52.5367
 */
--
 * Total samples for file : "/home/andrey/libcchem/src/test.cpp"
 *
 *  61556 22.9345
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_vector.h"
 *
 *  41956 15.6320
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_uninitialized.h"
 *
 *  20956  7.8078
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_construct.h"
 *
 *   2923  1.0891
 */

In allocator:

               :      // _GLIBCXX_RESOLVE_LIB_DEFECTS
               :      // 402. wrong new expression in [some_] allocator::construct
               :      void
               :      construct(pointer __p, const _Tp& __val)
141008 52.5367 :      { ::new((void *)__p) _Tp(__val); }

vector::

               :void UseVector()
               :{ /* UseVector() total:  60121 22.3999 */
...
               :
               :
 10790  4.0201 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
   495  0.1844 :            pixels[i].r = 255;
               :
 12618  4.7012 :            pixels[i].g = 0;
               :
  2253  0.8394 :            pixels[i].b = 0;
               :
               :        }

Array

               :void UseArray()
               :{ /* UseArray() total:  35191 13.1114 */
               :
...
               :
   136  0.0507 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
  9897  3.6874 :            pixels[i].r = 255;
               :
  3511  1.3081 :            pixels[i].g = 0;
               :
 21647  8.0652 :            pixels[i].b = 0;

Der größte Teil des Overheads entfällt auf den Kopierkonstruktor. Beispielsweise,

    std::vector < Pixel > pixels;//(dimension * dimension, Pixel());

    pixels.reserve(dimension * dimension);

    for (int i = 0; i < dimension * dimension; ++i) {

        pixels[i].r = 255;

        pixels[i].g = 0;

        pixels[i].b = 0;
    }

Es hat die gleiche Leistung wie ein Array.

Anycorn
quelle
2
Leider wird nach der "Lösung", die Sie gegeben haben, pixels.size()gebrochen.
Kizzx2
1
Dies ist falsch, Sie können nicht Reserve aufrufen und dann die Elemente verwenden, Sie müssen immer noch push_back verwenden, um Elemente hinzuzufügen
Paulm
1

Mein Laptop ist Lenova G770 (4 GB RAM).

Das Betriebssystem ist Windows 7 64-Bit (das mit Laptop)

Compiler ist MinGW 4.6.1.

Die IDE lautet Code :: Blocks .

Ich teste die Quellcodes des ersten Beitrags.

Die Ergebnisse

O2-Optimierung

UseArray in 2.841 Sekunden abgeschlossen

UseVector in 2,548 Sekunden abgeschlossen

UseVectorPushBack wurde in 11,95 Sekunden abgeschlossen

Das Ganze war in 17.342 Sekunden erledigt

Systempause

O3-Optimierung

UseArray in 1.452 Sekunden abgeschlossen

UseVector in 2,514 Sekunden abgeschlossen

UseVectorPushBack wurde in 12.967 Sekunden abgeschlossen

Das Ganze war in 16.937 Sekunden erledigt

Es sieht so aus, als ob die Leistung des Vektors unter O3-Optimierung schlechter ist.

Wenn Sie die Schleife auf ändern

    pixels[i].r = i;
    pixels[i].g = i;
    pixels[i].b = i;

Die Geschwindigkeit von Array und Vektor unter O2 und O3 ist nahezu gleich.

StereoMatching
quelle
Selbst wenn ich malloc in new ändere, ist im ersten Testfall unter O3 die Leistung des Vektors immer noch langsamer als die des Arrays. Wenn Sie jedoch den Zuweisungswert von (255, 0, 0) in (i, i, i) ändern, wird die Leistung von Vektor und Array sind unter O2 und O3 fast gleich, es ist ziemlich seltsam
StereoMatching
Entschuldigung, ich habe vergessen, frei zu löschen, um zu löschen. Nachdem ich frei geändert habe, um zu löschen, ist die Leistung von Vektor und Array unter O3 jetzt gleich. Sieht aus, als wäre der Allokator der Hauptgrund?
StereoMatching
1

Als besserer Benchmark (glaube ich ...) kann der Compiler aufgrund von Optimierungen den Code ändern, da die Ergebnisse der zugewiesenen Vektoren / Arrays nirgendwo verwendet werden. Ergebnisse:

$ g++ test.cpp -o test -O3 -march=native
$ ./test 
UseArray inner completed in 0.652 seconds
UseArray completed in 0.773 seconds
UseVector inner completed in 0.638 seconds
UseVector completed in 0.757 seconds
UseVectorPushBack inner completed in 6.732 seconds
UseVectorPush completed in 6.856 seconds
The whole thing completed in 8.387 seconds

Compiler:

gcc version 6.2.0 20161019 (Debian 6.2.0-9)

ZENTRALPROZESSOR:

model name  : Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz

Und der Code:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVector inner");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel>& pixels = results.at(i);
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVectorPushBack inner");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel>& pixels = results.at(i);
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray(Pixel** results)
{
    TestTimer t("UseArray inner");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        results[i] = pixels;

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        // free(pixels);
    }
}

void UseArray()
{
    TestTimer t("UseArray");
    Pixel** array = (Pixel**)malloc(sizeof(Pixel*)* 1000);
    UseArray(array);
    for(int i=0;i<1000;++i)
        free(array[i]);
    free(array);
}

void UseVector()
{
    TestTimer t("UseVector");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVector(vector);
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPush");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVectorPushBack(vector);
    }
}


int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}
Michał Szczepaniak
quelle
1

Ich habe einige umfangreiche Tests durchgeführt, die ich jetzt schon eine Weile machen wollte. Könnte dies auch teilen.

Dies ist meine Dual-Boot-Maschine i7-3770, 16 GB RAM, x86_64, unter Windows 8.1 und unter Ubuntu 16.04. Weitere Informationen und Schlussfolgerungen finden Sie weiter unten. Getestet sowohl MSVS 2017 als auch g ++ (sowohl unter Windows als auch unter Linux).

Testprogramm

#include <iostream>
#include <chrono>
//#include <algorithm>
#include <array>
#include <locale>
#include <vector>
#include <queue>
#include <deque>

// Note: total size of array must not exceed 0x7fffffff B = 2,147,483,647B
//  which means that largest int array size is 536,870,911
// Also image size cannot be larger than 80,000,000B
constexpr int long g_size = 100000;
int g_A[g_size];


int main()
{
    std::locale loc("");
    std::cout.imbue(loc);
    constexpr int long size = 100000;  // largest array stack size

    // stack allocated c array
    std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
    int A[size];
    for (int i = 0; i < size; i++)
        A[i] = i;

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style stack array size=" << sizeof(A) << "B\n\n";

    // global stack c array
    start = std::chrono::steady_clock::now();
    for (int i = 0; i < g_size; i++)
        g_A[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "global c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "global c-style stack array size=" << sizeof(g_A) << "B\n\n";

    // raw c array heap array
    start = std::chrono::steady_clock::now();
    int* AA = new int[size];    // bad_alloc() if it goes higher than 1,000,000,000
    for (int i = 0; i < size; i++)
        AA[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style heap array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style heap array size=" << sizeof(AA) << "B\n\n";
    delete[] AA;

    // std::array<>
    start = std::chrono::steady_clock::now();
    std::array<int, size> AAA;
    for (int i = 0; i < size; i++)
        AAA[i] = i;
    //std::sort(AAA.begin(), AAA.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::array size=" << sizeof(AAA) << "B\n\n";

    // std::vector<>
    start = std::chrono::steady_clock::now();
    std::vector<int> v;
    for (int i = 0; i < size; i++)
        v.push_back(i);
    //std::sort(v.begin(), v.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::vector duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::vector size=" << v.size() * sizeof(v.back()) << "B\n\n";

    // std::deque<>
    start = std::chrono::steady_clock::now();
    std::deque<int> dq;
    for (int i = 0; i < size; i++)
        dq.push_back(i);
    //std::sort(dq.begin(), dq.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::deque duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::deque size=" << dq.size() * sizeof(dq.back()) << "B\n\n";

    // std::queue<>
    start = std::chrono::steady_clock::now();
    std::queue<int> q;
    for (int i = 0; i < size; i++)
        q.push(i);

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::queue duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::queue size=" << q.size() * sizeof(q.front()) << "B\n\n";
}

Ergebnisse

//////////////////////////////////////////////////////////////////////////////////////////
// with MSVS 2017:
// >> cl /std:c++14 /Wall -O2 array_bench.cpp
//
// c-style stack array duration=0.15ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.130ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.90ms
// c-style heap array size=4B
//
// std::array duration=0.20ms
// std::array size=400,000B
//
// std::vector duration=0.544ms
// std::vector size=400,000B
//
// std::deque duration=1.375ms
// std::deque size=400,000B
//
// std::queue duration=1.491ms
// std::queue size=400,000B
//
//////////////////////////////////////////////////////////////////////////////////////////
//
// with g++ version:
//      - (tdm64-1) 5.1.0 on Windows
//      - (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609 on Ubuntu 16.04
// >> g++ -std=c++14 -Wall -march=native -O2 array_bench.cpp -o array_bench
//
// c-style stack array duration=0ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.124ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.648ms
// c-style heap array size=8B
//
// std::array duration=1ms
// std::array size=400,000B
//
// std::vector duration=0.402ms
// std::vector size=400,000B
//
// std::deque duration=0.234ms
// std::deque size=400,000B
//
// std::queue duration=0.304ms
// std::queue size=400,000
//
//////////////////////////////////////////////////////////////////////////////////////////

Anmerkungen

  • Zusammengebaut von durchschnittlich 10 Läufen.
  • Ich habe anfangs auch Tests mit durchgeführt std::sort()(Sie können sehen, dass dies auskommentiert ist), sie aber später entfernt, da es keine signifikanten relativen Unterschiede gab.

Meine Schlussfolgerungen und Bemerkungen

  • Beachten Sie, dass das globale Array im C-Stil fast so viel Zeit in Anspruch nimmt wie das Heap-Array im C-Stil
  • Bei allen Tests habe ich eine bemerkenswerte Stabilität festgestellt std::array Zeitschwankungen zwischen aufeinanderfolgenden Läufen fest, während andere, insbesondere die Standardstrukturen von std :: data, im Vergleich stark variierten
  • Die O3-Optimierung zeigte keine nennenswerten Zeitunterschiede
  • Das Entfernen der Optimierung unter Windows cl (no -O2) und unter g ++ (Win / Linux no -O2, no -march = native) erhöht die Zeiten erheblich. Besonders für std :: data Strukturen. Insgesamt höhere Zeiten unter MSVS als unter g ++, aber std::arrayArrays im C-Stil unter Windows ohne Optimierung schneller
  • g ++ produziert schnelleren Code als der Microsoft-Compiler (anscheinend läuft er sogar unter Windows schneller).

Urteil

Dies ist natürlich Code für einen optimierten Build. Und da ging es um die Fragestd::vector dann war, ist es! Viel! langsamer als normale Arrays (optimiert / nicht optimiert). Wenn Sie jedoch einen Benchmark durchführen, möchten Sie natürlich optimierten Code erstellen.

Der Star der Show war für mich jedoch std::array.

Nikos
quelle
0

Mit den richtigen Optionen können Vektoren und Arrays identische Asm erzeugen . In diesen Fällen haben sie natürlich die gleiche Geschwindigkeit, da Sie in beiden Fällen dieselbe ausführbare Datei erhalten.


quelle
1
In diesem Fall scheinen sie nicht dieselbe Assembly zu generieren. Insbesondere scheint es keine Möglichkeit zu geben, den Aufruf von Konstruktoren unter Verwendung von Vektoren zu unterdrücken. Sie können sich hier auf die Antworten für dieses Problem beziehen (es ist eine lange Lektüre, aber es erklärt, warum es in anderen Fällen als dem einfachen Testfall in dem von Ihnen angegebenen Link einen Leistungsunterschied gibt.) (Tatsächlich scheint es einen Weg zu geben - - Schreiben eines benutzerdefinierten STL-Allokators, wie vorgeschlagen. Persönlich finde ich es unnötig mehr Arbeit als mit malloc)
kizzx2
1
@ kizzx2: Dass man sich so viel Mühe geben muss, um nicht konstruierte Objekte zu verwenden, ist eine gute Sache, denn das ist ein Fehler, der 99% (ich kann es grob unterschätzen) der Zeit ist. Ich habe die anderen Antworten gelesen und festgestellt, dass ich Ihre spezifische Situation nicht anspreche (keine Notwendigkeit, die anderen Antworten sind korrekt), aber ich wollte Ihnen dennoch dieses Beispiel geben, wie sich Vektoren und Arrays genau gleich verhalten können.
@ Roger: das ist toll! Danke für den Link
kizzx2
0

Übrigens tritt die Verlangsamung Ihres Sehens in Klassen mit Vektor auch bei Standardtypen wie int auf. Hier ist ein Multithread-Code:

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <typeinfo>
#include <vector>
#include <pthread.h>
#include <sstream>
#include <fstream>
using namespace std;

//pthread_mutex_t map_mutex=PTHREAD_MUTEX_INITIALIZER;

long long num=500000000;
int procs=1;

struct iterate
{
    int id;
    int num;
    void * member;
    iterate(int a, int b, void *c) : id(a), num(b), member(c) {}
};

//fill out viterate and piterate
void * viterate(void * input)
{
    printf("am in viterate\n");
    iterate * info=static_cast<iterate *> (input);
    // reproduce member type
    vector<int> test= *static_cast<vector<int>*> (info->member);
    for (int i=info->id; i<test.size(); i+=info->num)
    {
        //printf("am in viterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

void * piterate(void * input)
{
    printf("am in piterate\n");
    iterate * info=static_cast<iterate *> (input);;
    int * test=static_cast<int *> (info->member);
    for (int i=info->id; i<num; i+=info->num) {
        //printf("am in piterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

int main()
{
    cout<<"producing vector of size "<<num<<endl;
    vector<int> vtest(num);
    cout<<"produced  a vector of size "<<vtest.size()<<endl;
    pthread_t thread[procs];

    iterate** it=new iterate*[procs];
    int ans;
    void *status;

    cout<<"begining to thread through the vector\n";
    for (int i=0; i<procs; i++) {
        it[i]=new iterate(i, procs, (void *) &vtest);
    //  ans=pthread_create(&thread[i],NULL,viterate, (void *) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the vector";
    //reuse the iterate structures

    cout<<"producing a pointer with size "<<num<<endl;
    int * pint=new int[num];
    cout<<"produced a pointer with size "<<num<<endl;

    cout<<"begining to thread through the pointer\n";
    for (int i=0; i<procs; i++) {
        it[i]->member=&pint;
        ans=pthread_create(&thread[i], NULL, piterate, (void*) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the pointer\n";

    //delete structure array for iterate
    for (int i=0; i<procs; i++) {
        delete it[i];
    }
    delete [] it;

    //delete pointer
    delete [] pint;

    cout<<"end of the program"<<endl;
    return 0;
}

Das Verhalten aus dem Code zeigt, dass die Instanziierung des Vektors der längste Teil des Codes ist. Sobald Sie durch diesen Flaschenhals kommen. Der Rest des Codes läuft extrem schnell. Dies gilt unabhängig davon, auf wie vielen Threads Sie ausgeführt werden.

Ignorieren Sie übrigens die absolut verrückte Anzahl von Includes. Ich habe diesen Code verwendet, um Dinge für ein Projekt zu testen, damit die Anzahl der Includes weiter wächst.

Zachary Kraus
quelle
0

Ich möchte nur erwähnen, dass vector (und smart_ptr) nur eine dünne Schicht ist, die über Raw-Arrays (und Raw-Zeigern) hinzugefügt wird. Und tatsächlich ist die Zugriffszeit eines Vektors im kontinuierlichen Speicher schneller als die eines Arrays. Der folgende Code zeigt das Ergebnis der Initialisierung und des Zugriffs auf Vektor und Array.

#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <vector>
#define SIZE 20000
int main() {
    srand (time(NULL));
    vector<vector<int>> vector2d;
    vector2d.reserve(SIZE);
    int index(0);
    boost::posix_time::ptime start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        vector2d.push_back(vector<int>(SIZE));
    }
    boost::posix_time::ptime start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            vector2d[index][index]++;
        }
    }
    boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time();
    boost::posix_time::time_duration msdiff = end - start_total;
    cout << "Vector total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Vector access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 


    int index(0);
    int** raw2d = nullptr;
    raw2d = new int*[SIZE];
    start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        raw2d[i] = new int[SIZE];
    }
    start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            raw2d[index][index]++;
        }
    }
    end = boost::posix_time::microsec_clock::local_time();
    msdiff = end - start_total;
    cout << "Array total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Array access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 
    for (int i = 0; i < SIZE; i++) {
        delete [] raw2d[i];
    }
    return 0;
}

Die Ausgabe ist:

    Vector total time: 925milliseconds.
    Vector access time: 4milliseconds.
    Array total time: 30milliseconds.
    Array access time: 21milliseconds.

Die Geschwindigkeit ist also fast gleich, wenn Sie sie richtig verwenden. (wie andere mit Reserve () oder Resize () erwähnt).

Charles Chow
quelle
0

Nun, weil vector :: resize () viel mehr verarbeitet als die einfache Speicherzuweisung (von malloc).

Versuchen Sie, einen Haltepunkt in Ihren Kopierkonstruktor einzufügen (definieren Sie ihn so, dass Sie einen Haltepunkt setzen können!), Und es entsteht zusätzliche Verarbeitungszeit.

YeenFei
quelle
0

Ich muss sagen, dass ich kein Experte für C ++ bin. Aber um einige Versuchsergebnisse hinzuzufügen:

kompilieren: gcc-6.2.0 / bin / g ++ -O3 -std = c ++ 14 vector.cpp

Maschine:

Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz 

Betriebssystem:

2.6.32-642.13.1.el6.x86_64

Ausgabe:

UseArray completed in 0.167821 seconds
UseVector completed in 0.134402 seconds
UseConstructor completed in 0.134806 seconds
UseFillConstructor completed in 1.00279 seconds
UseVectorPushBack completed in 6.6887 seconds
The whole thing completed in 8.12888 seconds

Hier ist das einzige, was ich seltsam finde, die Leistung von "UseFillConstructor" im Vergleich zu "UseConstructor".

Der Code:

void UseConstructor()
{
    TestTimer t("UseConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension*dimension);
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}


void UseFillConstructor()
{
    TestTimer t("UseFillConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension*dimension, Pixel(255,0,0));
    }
}

Der zusätzliche "Wert" verlangsamt die Leistung erheblich, was meiner Meinung nach auf den mehrfachen Aufruf des Kopierkonstruktors zurückzuführen ist. Aber...

Kompilieren:

gcc-6.2.0/bin/g++ -std=c++14 -O vector.cpp

Ausgabe:

UseArray completed in 1.02464 seconds
UseVector completed in 1.31056 seconds
UseConstructor completed in 1.47413 seconds
UseFillConstructor completed in 1.01555 seconds
UseVectorPushBack completed in 6.9597 seconds
The whole thing completed in 11.7851 seconds

In diesem Fall ist die gcc-Optimierung sehr wichtig, kann Ihnen jedoch nicht viel helfen, wenn standardmäßig ein Wert angegeben wird. Das ist eigentlich gegen meinen Unterricht. Hoffentlich hilft es neuen Programmierern bei der Auswahl des Vektorinitialisierungsformats.

user2189731
quelle
0

Es scheint von den Compiler-Flags abzuhängen. Hier ist ein Benchmark-Code:

#include <chrono>
#include <cmath>
#include <ctime>
#include <iostream>
#include <vector>


int main(){

    int size = 1000000; // reduce this number in case your program crashes
    int L = 10;

    std::cout << "size=" << size << " L=" << L << std::endl;
    {
        srand( time(0) );
        double * data = new double[size];
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C style heap array:    " << duration << "ms\n";
        delete data;
    }

    {
        srand( 1 + time(0) );
        double data[size]; // technically, non-compliant with C++ standard.
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C99 style stack array: " << duration << "ms\n";
    }

    {
        srand( 2 + time(0) );
        std::vector<double> data( size );
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of std::vector array:     " << duration << "ms\n";
    }

    return 0;
}

Unterschiedliche Optimierungsflags geben unterschiedliche Antworten:

$ g++ -O0 benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181182
Duration of C style heap array:    118441ms
Calculation result is 181240
Duration of C99 style stack array: 104920ms
Calculation result is 181210
Duration of std::vector array:     124477ms
$g++ -O3 benchmark.cpp
$ ./a.out 
size=1000000 L=10
Calculation result is 181213
Duration of C style heap array:    107803ms
Calculation result is 181198
Duration of C99 style stack array: 87247ms
Calculation result is 181204
Duration of std::vector array:     89083ms
$ g++ -Ofast benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181164
Duration of C style heap array:    93530ms
Calculation result is 181179
Duration of C99 style stack array: 80620ms
Calculation result is 181191
Duration of std::vector array:     78830ms

Ihre genauen Ergebnisse variieren, aber dies ist auf meinem Computer recht typisch.

Shuhalo
quelle
0

Nach meiner Erfahrung kann manchmal, nur manchmal vector<int>um ein Vielfaches langsamer sein als int[]. Eine Sache zu beachten ist, dass Vektoren von Vektoren sehr unterschiedlich sind int[][]. Da die Elemente im Speicher wahrscheinlich nicht zusammenhängend sind. Dies bedeutet, dass Sie die Größe verschiedener Vektoren innerhalb des Hauptvektors ändern können, die CPU jedoch möglicherweise nicht so gut Elemente zwischenspeichern kann wie im Fall von int[][].

Mhor Mé
quelle