std::vector Specherfreigabe



  • Ah OK, das habe ich mir schon gedacht... Danke 🙂
    Aber es macht keinen Unterschied ob ich std::swap benutze oder ob ich einfach vec.at(x) = vec.back() benutze, oder?
    MfG,
    derFer



  • derFer schrieb:

    Aber es macht keinen Unterschied ob ich std::swap benutze oder ob ich einfach vec.at(x) = vec.back() benutze, oder?

    Bei komplexen Objekten kann swap() effizienter sein, weil keine Kopie benötigt wird. Für int s ist die Zuweisung schneller.

    Übrigens solltest du wenn schon operator[] statt at() verwenden. In C++11 kannst du zudem das Objekt verschieben, was ebenfalls sehr effizient ist, allerdings einen Move-Zuweisungsoperator erfordert:

    vec[x] = std::move(vec.back());
    

    GorbGorb schrieb:

    Dekonstruktor

    Uuh.. 😮 Destruktor!



  • wenn du unnötige Kopier- und Speicher-Operationen vermeiden möchtest, verwende nicht std::vector. nutze dieses kleine Testprogramm zum Prüfen, welche unnötigen Kopieroperationen im Hintergrund ablaufen. verschiedene Stdlib Implementierungen liefern da übrigens unterschiedliche Ergebnisse (MSVC, gcc usw.)

    #include <iostream>
    #include <vector>
    using namespace std;
    
    class MyInt
      {
    public:
      MyInt()
        { m_Value = 0;
          cout << "MyInt() "; Cout(); }
      MyInt(const MyInt& myCopy)
        { m_Value = myCopy.m_Value;
          cout << "MyInt(c& " << &myCopy << ") "; Cout(); }
      MyInt(MyInt&& myCopy)
        { m_Value = myCopy.m_Value;
          cout << "MyInt(&& " << &myCopy << ") "; Cout(); }
      MyInt(int i)
        { m_Value = i;
          cout << "MyInt(" << i << ") "; Cout(); }
      ~MyInt()
        { cout << "~MyInt() "; Cout(); }
      MyInt& operator=(const MyInt& myCopy)
        { m_Value = myCopy.m_Value;
          cout << "operator=(c& " << &myCopy << ") "; Cout();
          return *this; }
      MyInt& operator=(MyInt&& myCopy)
        { m_Value = myCopy.m_Value;
          cout << "operator=(&& " << &myCopy << ") "; Cout();
          return *this; }
      void setValue(int i)
        { m_Value = i;
          cout << "setValue(" << i << ") "; Cout(); }
    private:
      void Cout()
        { cout << m_Value << " " << this << endl; }
      int m_Value;
      };
    
    int main ()
      {
      {
      vector <MyInt> myVector;
      cout << "--- vector <MyInt> myVector;" << endl;
      MyInt myInt;
      cout << "--- MyInt myInt;" << endl;
      myVector.push_back(myInt);
      cout << "--- myVector.push_back(myInt);" << endl;
      myVector.push_back(myInt);
      cout << "--- myVector.push_back(myInt);" << endl;
      myVector.push_back(myInt);
      cout << "--- myVector.push_back(myInt);" << endl;
      vector<MyInt>::iterator it = myVector.begin();
      myVector.erase(it);
      cout << "--- myVector.erase(it);" << endl;
      myVector.shrink_to_fit();
      cout << "--- myVector.shrink_to_fit();" << endl;
      }
      cout << "--- ~myInt(); ~myVector();" << endl;
      return 0;
      }
    


  • wenn du unnötige Kopier- und Speicher-Operationen vermeiden möchtest, verwende nicht std::vector.

    Worauf willst Du hinaus? vector hat doch supergeringen Overhead. Das Einzige, was mir einfällt, ist, dass der vector häufig wächst, wenn man sehr viele Elemente einfügt und das kann man durch reserve doch umgehen.


  • Mod

    dd++ schrieb:

    wenn du unnötige Kopier- und Speicher-Operationen vermeiden möchtest, verwende nicht std::vector.

    Das halte ich für einen gefährlichen Tipp. Denn viele Leute wissen nicht, warum sie Kopien vermeiden sollten, sondern finden einfach nur, dass das toll klingt. Sehen aber nicht die Nachteile. Dann nehmen sie am Ende std::list oder ähnliches und wundern sich, warum ihr Programm so lahm ist.

    Von vector sollte man nur abweichen, wenn man einen wirklich, wirklich guten Grund hat.



  • SeppJ schrieb:

    dd++ schrieb:

    wenn du unnötige Kopier- und Speicher-Operationen vermeiden möchtest, verwende nicht std::vector.

    Das halte ich für einen gefährlichen Tipp. Denn viele Leute wissen nicht, warum sie Kopien vermeiden sollten, sondern finden einfach nur, dass das toll klingt. Sehen aber nicht die Nachteile. Dann nehmen sie am Ende std::list oder ähnliches und wundern sich, warum ihr Programm so lahm ist.

    Der Tipp ist ja nicht std::list verwenden. Wer das aus Versehen macht, findet schnell raus, dass der operator[] fehlt. Die std::deque ist schon besser, da wird nie etwas kopiert bei push_* (ausser ev. das einzufügende Element, aber dafür gibt es emplace).



  • SeppJ schrieb:

    Von vector sollte man nur abweichen, wenn man einen wirklich, wirklich guten Grund hat.

    Performance? 😃

    Ich meine, einerseits beschäftigen sich viele hier mit nichts anderem, als der Fragestellung, wie man unnötige Kopien vermeidet
    und im gleichen Atemzug wird für fast jeden Anwendungsfall der vector empfohlen... Da beißt sich die Katze ja irgendwo in den Schwanz. 😃


  • Mod

    It0101 schrieb:

    SeppJ schrieb:

    Von vector sollte man nur abweichen, wenn man einen wirklich, wirklich guten Grund hat.

    Performance? 😃

    😮 Eben drum vector benutzen? Performance ist doch gerade der Grund, deque & Co. wirklich nur dann zu benutzen, wenn man die speziellen Eigenschaften (zum Beispiel löschen am Anfang) ganz dringend braucht. Bei Normalbenutzung hängt ein vector eine deque ganz locker ab.



  • Es wäre super wenn jemand mal genau schreiben könnte wann man Vector benutzt, wann list und wann deque.
    Damit das immer wiederkehrende Fragen danach ein Ende hat 😉

    MfG



  • 😮 Eben drum vector benutzen? Performance ist doch gerade der Grund, deque & Co. wirklich nur dann zu benutzen, wenn man die speziellen Eigenschaften (zum Beispiel löschen am Anfang) ganz dringend braucht. Bei Normalbenutzung hängt ein vector eine deque ganz locker ab.[/quote]Naja, was man halt so Normalbenutzung nennt.

    int main()
    {
        typedef std::array<int, 999> data;
        std::vector<data> container; // bzw. deque
        for (int i=0; i<40000; ++i)
           container.push_back(data{});
    }
    

    Vektor: 0.39s
    Deque: 0.15s



  • Bevor jetzt der Kommentar kommt, man könne auch reserve benutzen: In diesem Fall ist Vektor einem Dynarray unterlegen. Das kann nämlich bei einer moderaten Anzahl Elemente auf dem Stack allokieren, was oft um EINIGES schneller ist.


  • Mod

    @abweichler:
    Super. Du hast eine der beiden Sachen gemessen, die deque besser als vector kann. Einfügen. 🙄

    Nun miss mal die Zugriffszeiten.

    Was kommt in normalen Programmen häufiger vor? Einfügen oder Zugriff?

    Falls dein Programm tatsächlich nur Daten in Container speichern soll (write only 🙂 ), dann ist deque natürlich der richtige Container. Das ist einer der erwähnten guten Gründe, bei denen man vector nicht nutzen sollte.

    @derFer:
    Das ist doch nun wirklich leicht bei Google zu finden. Unter anderem:
    http://stackoverflow.com/questions/10699265/how-can-i-efficiently-select-a-standard-library-container-in-c11
    Das Bild und die Antworten von Matthieu M. und Nicol Bolas (diese Antwort ganz besonders!) sollten alle Fragen beantworten.



  • Im Zweifelsfalle kann man ja zum shared_ptr greifen, wenn das Objekt wirklich viel hin und her kopiert werden soll. Wenn man so wie ich einen Anwendungsfall mit einem Durchsatz von 80.000 pro Sekunde hat, überlegt man sich zwei mal ob man die Objekte nackig in einen Container ( egal welcher ) knallt, oder doch lieber smartpointer nutzt 😉



  • SeppJ schrieb:

    @abweichler:
    Super. Du hast eine der beiden Sachen gemessen, die deque besser als vector kann. Einfügen. 🙄

    Nun miss mal die Zugriffszeiten.

    Was kommt in normalen Programmen häufiger vor? Einfügen oder Zugriff?

    Klar, Zugriff kommt häufiger vor. Aber der ist ungefähr gleich schnell. Das Einfügen ist das, was Zeit braucht.

    10*2^12 Elemente, 2^18 Zugriffe:
    Vektor: 0.55s
    Deque: 0.23s

    10*2^12 Elemente, 2^20 Zugriffe:
    Vektor: 0.72s
    Deque: 0.43s

    10*2^12 Elemente, 2^24 Zugriffe:
    Vektor: 4.78s
    Deque: 4.49s



  • It0101 schrieb:

    Im Zweifelsfalle kann man ja zum shared_ptr greifen, wenn das Objekt wirklich viel hin und her kopiert werden soll. Wenn man so wie ich einen Anwendungsfall mit einem Durchsatz von 80.000 pro Sekunde hat, überlegt man sich zwei mal ob man die Objekte nackig in einen Container ( egal welcher ) knallt, oder doch lieber smartpointer nutzt 😉

    Für shared_ptr ist das nie ein Grund und ein vector<unique_ptr<nackig> > hat in diesem Fall nur Nachteile gegenüber einer deque<nackig>


  • Mod

    abweichler schrieb:

    SeppJ schrieb:

    @abweichler:
    Super. Du hast eine der beiden Sachen gemessen, die deque besser als vector kann. Einfügen. 🙄

    Nun miss mal die Zugriffszeiten.

    Was kommt in normalen Programmen häufiger vor? Einfügen oder Zugriff?

    Klar, Zugriff kommt häufiger vor. Aber der ist ungefähr gleich schnell. Das Einfügen ist das, was Zeit braucht.

    10*2^12 Elemente, 2^18 Zugriffe:
    Vektor: 0.55s
    Deque: 0.23s

    10*2^12 Elemente, 2^20 Zugriffe:
    Vektor: 0.72s
    Deque: 0.43s

    10*2^12 Elemente, 2^24 Zugriffe:
    Vektor: 4.78s
    Deque: 4.49s

    Dir ist schon klar, dass ideone ohne Optimierungen compiliert? Niemanden interessiert es, wie schnell unoptimierter Code läuft. Wenn ich bei mir am Rechner mit O3 compiliere, dann ist der vector im letzten Beispiel fast 25% schneller als deque. Außerdem misst du hier vor allem die Geschwindigkeit von rand. Die Schachtelung ist ebenfalls verdächtig, wenn man die Performance von Einfügen und Zugriffen vergleichen will. Ich habe stark den Eindruck, du möchtest den Benchmark manipulieren, bloß um Recht zu behalten.



  • Edit: Da war SeppJ schneller.



  • Hallo,
    Wenn ich den Link richtig verstanden habe (vor allem M. M.) dann nimmt man einen Vector wenn man es dynamisch sein soll, keine Suche per ID und wenn man nur am Ende löscht.
    Das selbe gilt für Deque, aber hier sollte man es nehmen wenn man am Ende und am Anfang löscht.

    Also für z.B. Daten die dynamisch sind, immer wieder neue die auch gelöscht werden müssen, auch aus der Mitte, nehme ich dann einen Vector? Weil ich ja einfach Ende auf Mitte kopieren kann und das Ende löschen. Oder nehme ich ein Deque?
    Die Daten die Abweichler liefert, zweigen ja eher das Deque bis zu einer sehr hohen Zahl von Zugriffen deutlich dem Vector überlegen ist, oder?

    Edit: Da scheint ja ein Problem beim Benchmark zu sein, die Frage bleibt trotzdem 😉

    MfG


  • Mod

    derFer schrieb:

    Also für z.B. Daten die dynamisch sind, immer wieder neue die auch gelöscht werden müssen, auch aus der Mitte, nehme ich dann einen Vector? Weil ich ja einfach Ende auf Mitte kopieren kann und das Ende löschen. Oder nehme ich ein Deque?

    Da braucht man mehr Informationen. Tendenziell: Keines von beiden. Woher weiß man, wo eingefügt und gelöscht werden soll? Löschen aus der Mitte ist ein eher ungewöhnliches Vorhaben für einen sequentiellen Container, da muss man deine genauen Gründe kennen, um die Frage zu beantworten.

    Die Daten die Abweichler liefert, zweigen ja eher das Deque bis zu einer sehr hohen Zahl von Zugriffen deutlich dem Vector überlegen ist, oder?

    Edit: Da scheint ja ein Problem beim Benchmark zu sein, die Frage bleibt trotzdem 😉

    Traue den Daten nicht, die sind so Vertrauenswürdig wie der Armutsbericht der Bundesregierung.


  • Mod

    Hier ist ein direkterer Benchmark. er benutzt int (was zugegeben eher günstig ist für den vector, aber int ist etwas, was man häufig speichert). Ich konnte keine Veränderung der Verhältnisse bei long long feststellen. Wer Spaß hat, möge größere Datentypen einsetzen und berichten:

    #include <vector>
    #include <cstdlib>
    #include <iostream>
    
    int main()
    {
      const int N = 5;
    
      std::vector<long long int> container;
      for (int j=rand() % 2; j<=(1<<24); ++j)
        container.push_back(j);
    
      unsigned sum = 0;
      for (int n = 0; n < N; ++n)
        for (auto i : container)
          sum += i;
      std::cout << sum << std::endl;
    }
    

    (Äquivalent für deque)

    Bei mir wird mit optimierter Executable bis ungefähr N=1 (Anzahl der Zugriffe pro Element) die deque etwas schneller (17% bei N=0, 10% bei N=1). Dann ungefähr gleich. Ab ungefähr 5 beginnt der vector dann davon zu ziehen. Bei N=10 ist er ~20% schneller. Bein N=100 um 50%. Danach wird die Kurve langsam flacher, N=1000 bringt "nur" noch ~56%.

    Wie schon gesagt: deque ist gut für write-only 🙂 .

    Die Ergebnisse hängen auch noch von der Anzahl der Elemente ab. So lange die deque komplett in eine ihrer Seiten passt, ist es günstig für die deque, weil sie nicht so sehr wegen ihrer schlechteren Lokalität leidet. Wird die Zahl der Elemente sehr groß, so beginnen andere Effekte (RAM-Geschwindigkeit) eine Rolle zu spielen und dominieren die Performance.

    Das alles aufzuschreiben und in jeder erdenklichen Konfiguration zu testen ist mir aber zu viel Arbeit. Außerdem habe ich es bereits zigmal gemacht und erwarte nichts neues. Siehe alte Beiträge hier im Forum. Das Thema deque vs. vector kommt jedes Jahr ein paar Mal vor.


Anmelden zum Antworten