3. C-Array vs std::vector

C-Array vs std::vector

  • ?

    Du hast den Optimizer nicht eingeschaltet.

    0
  • F

    Hallo Shisha,

    Ich hielt deine Messergebnisse für höchst unglaubwürdig, daher habe ich den Code selbst nochmals nachgemessen.

    Ergebnisse mit MinGW-w64 GCC 7.1.0 ( -O3 -march=native -DNDEBUG ):

    Run on (12 X 3400 MHz CPU s)
06/21/17 15:55:42
---------------------------------------------------------
Benchmark                  Time           CPU Iterations
---------------------------------------------------------
ShishaMalloc/1             2 ns          2 ns  373929227   486.367M items/s
ShishaMalloc/4            16 ns         16 ns   40792279   949.995M items/s
ShishaMalloc/16          230 ns        229 ns    2991434   1063.99M items/s
ShishaMalloc/64         3944 ns       3887 ns     172583   1004.99M items/s
ShishaMalloc/256       96620 ns      98035 ns       7479   637.527M items/s
ShishaMalloc/1024    5457031 ns    5432178 ns        112   184.088M items/s
ShishaMalloc/4096  146390461 ns  148200950 ns          4   107.962M items/s
ShishaMalloc_BigO       8.71 N^2       8.82 N^2
ShishaMalloc_RMS           6 %          7 %
ShishaVector/1             2 ns          2 ns  320510766   425.949M items/s
ShishaVector/4            23 ns         23 ns   29914338   664.997M items/s
ShishaVector/16          350 ns        352 ns    1950935   693.909M items/s
ShishaVector/64         6151 ns       6119 ns     112179   638.398M items/s
ShishaVector/256      137313 ns     137666 ns       4986   453.996M items/s
ShishaVector/1024    7314861 ns    7453381 ns         90   134.167M items/s
ShishaVector/4096  159680211 ns  159901025 ns          4   100.062M items/s
ShishaVector_BigO       9.51 N^2       9.52 N^2
ShishaVector_RMS           4 %          4 %

    Der Unterschied ist zwar deutlich kleiner als der, den du zu messen gemeint hattest, besteht aber nichtsdestoweniger.

    LG

    0
  • A

    Der Vergleich ist ja auch nicht korrekt. Beim C-Beispiel machst du nirgends ein vergleichbares Resize zu Vector? (Bin kein C-Kenner)
    Sieht für mich so aus, als ob du nur immer Speicher neu anlegst? Oder wo machst du ein realloc?

    Bei der C++-Variante machst du:
    Vector anlegen (ähnlich einem malloc), und ein resize auf den Vector, was einem realloc und evtl. umkopieren der initialen Vector-Daten in das Resized-Vector enstpricht.

    Mach doch mal beides gleich. Entweder die C-Variante an die C++-Variante anpassen. Oder mal bei Vector gleich beim Konstruieren die gewünschte initiale Größe angeben.

    0
  • ?

    OK:

    Rechner : Intel i7-4770
    Compiler: g++ 5.4

    CXXFLAGS: -pthread -llikwid -fopenmp -std=c++11

    Wenn man die Optimierung noch anschaltet (-O2)
    sieht die Sache tatsächlich schon viel besser aus:

    Gesamtlaufzeiten (also nicht nur Berechnung von c):
    C-Array : 2.031s
    vector (Keine Optimierung) : 4.938s
    vector (O2) : 2.278s

    0
  • F

    @Artchi: Gemessen wird das zwischen LIKWID_MARKER_START und LIKWID_MARKER_STOP , die Speicherreservierung etc. geschieht jedoch zuvor in init() und wird somit nicht mitgemessen. Ferner liegst du mit der Aussage, dass bei seinen resize s umkopiert wird, falsch, denn er resize d lediglich leere Vektoren. Ergo wird da gar nichts umkopiert.

    Die beiden Codes bilden m.E.n. einen fairen Vergleich.

    0
  • ?

    @Artchi:

    Bei den gemessenen Zeiten im ersten Beitrag hadelte es sich nur um die Zeit, die für den Code-Teil zwischen dem LIKWID-Marker benötigt wurde.

    Im neuen Beitrag sind Gesamtlaufzeiten zu sehen, da spielen dann solche Dinge schon eine Rolle, aber der Laufzeitunterschied ist nun schon so gering, dass ich das Problem für gelöst erachte.

    0
  • ?

    Mich würde mal ein Vergleich mit Rust interessieren.

    0
  • ?

    shisha schrieb:

    Wenn man die Optimierung noch anschaltet (-O2)

    Jeder Benchmark ohne Optimierung ist irrelevant!
    Benutze -O3.

    0
  • C
    Mod

    Wo und wie wird das Messergebnis ausgegeben?
    Wie wird dieses likwid benutzt, um damit etwas zu messen? Ich habe keine Lust, 10000 man-Pages zu durchsuchen, nur um rauszufinden, wie dieses Framework einen einzelnen Benchmark starten kann.

    Wozu überhaupt der Aufwand? <chrono> tut es auch.

    Wenn ich raten müsste, würde ich sagen, dass in

    for(int i = 0; i < N; i++)
  {
    for(int j= 0; j <N; j++)
    {
      c[i][j] = a[i][j] + b[j][i];
    }
  }

    der Prozessor im Prinzip die ganze Zeit auf den Speicher wartet. Insbesondere weil b mit vertauschten Indizes benutzt wird, muss dort ständig auf das erste Level gewartet werden, bevor die endgültige Adresse bekannt ist.
    Und schließlich besteht ein vector-Objekt typischerweise aus 3 Zeiger, der Durchlauf durch b führt damit zu deutlich mehr Druck im L1-Cache - 3*8*10000=240000; das sind ja nicht zu vernachlässigende Größenordnungen.
    Das Grundproblem ist nat. dass weder double** noch vector<vector> geeignet sind, wenn man NxM-Felder behandlen möchte.

    Diese Interpretation passt auch zu Fytchs Messergebnissen. Am oberen und unteren Ende sind beide Varianten ja etwa gleich schnell.

    0
  • Mod

    camper schrieb:

    Das Grundproblem ist nat. dass weder double** noch vector<vector> geeignet sind, wenn man NxM-Felder behandlen möchte.

    Nochmal zitiert, weil es die wichtigste Aussage ist.

    Ein Zeiger ist kein Array, ein Array ist kein Zeiger. Ein Vector ist kein Array, ein Array ist kein Vector. Demnach ist ein Zeiger auf einen Zeiger ganz bestimmt kein Zeiger auf ein Array; und ein Vector von von Vectoren ist kein Vector von Arrays.

    0
Anmelden zum Antworten