3. std::vector Specherfreigabe

std::vector Specherfreigabe

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

    0

  • 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 😉

    0
  • ?

    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

    0
  • ?

    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>

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

    0
  • K

    Edit: Da war SeppJ schneller.

    0
  • D

    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

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

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

    0
  • D

    Beispielsweise ich will Schneeflocken programmieren (fallen alle unterschiedlich schnell), bei SFML gab es mal so ein Beispiel, dann nehme ich Sprits und packe die (jedes Sprite eine Schneeflocke) in einen Vektor.
    Bei jeder Aktualisierung durchlaufe ich den Vector und prüfe bei jedem ob sie den Boden erreicht hat, wenn ja wird diese gelöscht.
    so meinte ich das 😉

    Im übrigen hab ich gerade versucht selbst einen Test zu machen, jedoch schon beim erzeugen des Vectors (mit einer For-Schleife Daten erzeugt) ist mir das Programm mit bad alloc abgeschmiert (for i<=UINT_MAX) und bei Deque ist mein PC eingefroren 😉

    MfG

    0
  • Mod

    Bzgl. Schneeflocken: Ich bin kein Grafikprogrammierer, aber die Reihenfolge sollte doch egal sein, oder? Dann vector mit den oben gezeigten Techniken:
    http://www.c-plusplus.net/forum/p2312638#2312638
    Anfügen dann am Ende. Dann hast du gegenüber anderen Strukturen sehr schnellen Zugriff, das ist doch sicherlich wichtig, oder?

    Bzgl bad_alloc: Ja, 2^24 (16 GB) ist sicherlich etwas übertrieben, so viel brauchte ich, um überhaupt bis runter zu N=1 messen zu können. Denn Allokation großer Blöcker geht eben so wahnsinnig schnell, das benötigt nur einen winzigen Bruchteil der Programmlaufzeit. Mein Rechner schafft locker 2^24, ist aber auch sehr üppig ausgestattet. Versuch mal einfach was kleineres, 2^18=256 MB, 2^12=4MB. Prinzipiell eher kleiner, da dann alles im Chache sitzt und man nur die Performance der Algorithmen sieht und weniger die Performance des RAMs.

    0
  • D

    Ok danke 😃

    Mein kleines Programm hat versagt, bez. ich 😞

    EDIT:
    Ich hatte versagt 😑 so klappt es und es beweist, dass Vecotr schneller ist 😃

    #include <iostream>
#include <vector>
#include <deque>
#include <limits.h>
#include <ctime>
#include <unistd.h>
#include <sys/time.h>
using namespace std;

int main()
{
    timeval a;
    timeval b;
    unsigned int zugriff = 23;

  //Vector messung
  cout << "Teste Vector, hinzufügen, zugreifen, löschen" << endl;
  gettimeofday(&a, 0);
  vector<unsigned int> vec;
  for(unsigned int i=0;i<= 500000; i++){
    vec.push_back(i);
  }
  for(unsigned int i=0;i< vec.size(); i++){
    zugriff = vec[i];
  }
  for(unsigned int i=2500;i< vec.size(); i++){
    vec[i] = vec[vec.size()-1];
    vec.pop_back();
  }
  gettimeofday(&b, 0);
  cout << "difference: " << (b.tv_usec - a.tv_usec) << std::endl;

  //Deque Messung:
  cout << "Teste Deque, hinzufügen, zugreifen, löschen" << endl;
  zugriff = 23;
  gettimeofday(&a, 0);
  deque<unsigned int> deq;
  for(unsigned int i=0;i<= 500000; i++){
    deq.push_back(i);
  }
  for(unsigned int i=0;i< deq.size(); i++){
    zugriff = deq[i];
  }
  for(unsigned int i=2500;i< deq.size(); i++){
    deq[i] = deq[deq.size()-1];
    deq.pop_back();
  }
  gettimeofday(&b, 0);
  cout << "difference: " << (b.tv_usec - a.tv_usec) << std::endl;

}

    Denn meine Ausgabe:

    ferdinand@Fers-chilliger-Pinguin:~/test> ./a.out
    Teste Vector, hinzufügen, zugreifen, löschen
    difference: 3949
    Teste Deque, hinzufügen, zugreifen, löschen
    difference: 4295
    ferdinand@Fers-chilliger-Pinguin:~/test> ./a.out
    Teste Vector, hinzufügen, zugreifen, löschen
    difference: 3904
    Teste Deque, hinzufügen, zugreifen, löschen
    difference: 4337
    ferdinand@Fers-chilliger-Pinguin:~/test> ./a.out
    Teste Vector, hinzufügen, zugreifen, löschen
    difference: 4010
    Teste Deque, hinzufügen, zugreifen, löschen
    difference: 4243

    Naja ich glaube ich werde daher erst mal weiter den Vector nehmen, und sonst auf den Link zurückgreifen 😉

    MfG

    0
  • ?

    derFer schrieb:

    Ich hatte versagt 😑 so klappt es und es beweist, dass Vecotr schneller ist 😃

    Es beweist, dass du nicht mit Iteratoren umgehen kannst.

    0
  • D

    vecitti schrieb:

    Es beweist, dass du nicht mit Iteratoren umgehen kannst.

    Das auch 😉
    Aber was will man erwarten, ich bin noch bei Kapitel 5 / 28... Was die STL angeht hab ich nie viel gemacht / gelernt (was ich gerade versuche zu beheben 😉 ).
    Aber es zeigt zumindest mir, das es in den Fällen in denen ich bisher den Vector benutzt habe ich richtig lag....
    Aber ich denke das ist ein anderes Thema und gehört nicht in den Thread.
    MfG

    0
  • Mod

    derFer schrieb:

    Aber ich denke das ist ein anderes Thema und gehört nicht in den Thread.

    Ein bisschen schneller könnte die deque schon sein, wenn du ihren Iterator benutzt, insofern ist der Einwand schon berechtigt. Es wird aber keine wundersame Leistungssteigerung geben, bloß ein paar Prozent.

    0
  • N

    SeppJ schrieb:

    Es wird aber keine wundersame Leistungssteigerung geben, bloß ein paar Prozent.

    Doch, Iteratoren statt Indizes zu benutzen kann gewaltige Auswirkungen haben. Das musste ich mal im SFML-Forum jemandem beweisen, der doch tatsächlich behauptete, man solle mit Indizes statt Iteratoren iterieren, weil diese schneller seien :p

    Indizes waren für std::deque bis zu 3 mal langsamer als Iteratoren, besonders bei Visual Studio. Hier sind die genauen Ergebnisse.

    0
  • ?

    SeppJ schrieb:

    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.

    SeppJ schrieb:

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

    SeppJ schrieb:

    Ich habe stark den Eindruck, du möchtest den Benchmark manipulieren, bloß um Recht zu behalten.

    Mal als Analogie Auto vs. Lastwagen.

    • Du: Wer schnell von A nach B will soll immer ein Auto nehmen. Lastwagen braucht man nur dann, wenn man Container transportieren will, die nicht in den Kofferraum des Autos passen.
    • Ich zeige, dass sich ein Lastwagen allgemein schneller beladen lässt.
    • Du: Ja, ein Lastwagen ist gut für den, der sein Fahrzeug nur beladen will und nicht damit rumfährt.
    • Ich zeige, dass der Lastwagen schneller ist, wenn das Fahrzeug einmal mit Steinen gefüllt wird und bis zu 1000 Kurzstrecken fährt.
    • Du behauptest, mein Beispiel sei gefälscht.
    • Dann zeigst du, dass sich ein Auto rentiert, wenn man mindestens 5 mal fährt , nachdem der Kofferraum mit einem kleinen Stofftierchen beladen wurde, allerdings nur auf kurzen (aber nicht zu kurzen) Strecken, wenn man nicht tanken muss, sonst ist der Unterschied nicht mehr so gross.

    Du behauptest (vor allem am Anfang des Threads), ein Vektor sei die ultimative Lösung.
    Das mag für Fälle stimmen, in denen man sporadisch etwas push_back und pop_back aufruft und viele viele Zugriffe und Iterationen macht.
    Ansonsten hat die Deque keine grossen Nachteile gegenüber einem Vektor.

    Um Herb zu zitieren:

    <a href= schrieb:

    GotW54">I recommend that you consider preferring deque by default instead of vector, especially when the contained type is a class or struct and not a builtin type, unless you really need the container's memory to be contiguous.

    Da findest du die Argumente.

    Herr J. (Name der Redaktion bekannt) schrieb:

    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.

    0
  • Mod

    Kannst du irgendwie nicht richtig lesen? Deine Analogie passt überhaupt gar nicht, nichts von dem, was du mir in den Mund legst, habe ich je gesagt und Herb Sutter hat seine damalige Aussage schon vor Jahren widerrufen und preist nun, so wie auch Bjarne Stroutrup und Scott Meyers (da große Namen dich anscheinend beeindrucken 🙄 ), vector als Standardwahl für Container an. Sogar der Sprachstandard(!) selbst sagt explizit, dass vector der Standardcontainer sein sollte. Die Gründe wurden dir genannt und vorgeführt. Ist das so schwer zu kapieren? Du darfst auch gerne trotzdem weiter deine nicht von deque profitierenden Programme weiterhin mit deque unnötig ausbremsen, aber beschwer dich nicht, wenn man dir sagt, dass du dir selber schadest.

    0
Anmelden zum Antworten