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

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.

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.

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."

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.

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.

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.

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.

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

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. ...

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.

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.

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:

3. Der Vektor ordnet kX Platz in ein zweites Array um.
4. Es kopiert die Einträge des ersten Arrays auf das zweite.
5. Verwirft das erste Array.
6. 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.

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.

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.

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;
}

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.

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.

Ü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.

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).

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.

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.

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.

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[][].