Java 8 mal schneller mit Arrays als std :: vector in C++. Was habe ich falsch gemacht?

Question

Ich habe den folgenden Java-Code mit mehreren großen Arrays, die nie ihre Größe ändern. Es läuft in 1100 ms auf meinem Computer.

Ich habe den gleichen Code in C++ implementiert und std::vector verwendet.

Die Zeit der C++ - Implementierung, die genau den gleichen Code ausführt, ist 8800 ms auf meinem Computer. Was habe ich falsch gemacht, so dass es langsam läuft?

Grundsätzlich ist der Code macht folgendes:

for (int i = 0; i < numberOfCells; ++i) { 
     h[i] = h[i] + 1; 
     floodedCells[i] = !floodedCells[i]; 
     floodedCellsTimeInterval[i] = !floodedCellsTimeInterval[i]; 
     qInflow[i] = qInflow[i] + 1; 
} 

Es ist mit einer Größe von etwa 20000. durch verschiedene Arrays iteriert

Sie beide Implementierungen unter den folgenden Links finden:

• Java: https://ideone.com/R8KqjT
• C++: https://ideone.com/Lu7RpE

(Am ideone konnte ich die Schleife wegen der Zeitlimitierung nur 400 mal statt 2000 mal laufen lassen. Aber auch hier gibt es einen Unterschied von drei mal)

Answer 1

ist die C++ Version mit den per-Knotendaten in eine Struktur gesammelt, und ein einzelner Vektor dieser Struktur verwendet:

#include <vector> 
#include <cmath> 
#include <iostream> 



class FloodIsolation { 
public: 
    FloodIsolation() : 
     numberOfCells(20000), 
     data(numberOfCells) 
    { 
    } 
    ~FloodIsolation(){ 
    } 

    void isUpdateNeeded() { 
    for (int i = 0; i < numberOfCells; ++i) { 
     data[i].h = data[i].h + 1; 
     data[i].floodedCells = !data[i].floodedCells; 
     data[i].floodedCellsTimeInterval = !data[i].floodedCellsTimeInterval; 
     data[i].qInflow = data[i].qInflow + 1; 
     data[i].qStartTime = data[i].qStartTime + 1; 
     data[i].qEndTime = data[i].qEndTime + 1; 
     data[i].lowerFloorCells = data[i].lowerFloorCells + 1; 
     data[i].cellLocationX = data[i].cellLocationX + 1; 
     data[i].cellLocationY = data[i].cellLocationY + 1; 
     data[i].cellLocationZ = data[i].cellLocationZ + 1; 
     data[i].levelOfCell = data[i].levelOfCell + 1; 
     data[i].valueOfCellIds = data[i].valueOfCellIds + 1; 
     data[i].h0 = data[i].h0 + 1; 
     data[i].vU = data[i].vU + 1; 
     data[i].vV = data[i].vV + 1; 
     data[i].vUh = data[i].vUh + 1; 
     data[i].vVh = data[i].vVh + 1; 
     data[i].vUh0 = data[i].vUh0 + 1; 
     data[i].vVh0 = data[i].vVh0 + 1; 
     data[i].ghh = data[i].ghh + 1; 
     data[i].sfx = data[i].sfx + 1; 
     data[i].sfy = data[i].sfy + 1; 
     data[i].qIn = data[i].qIn + 1; 


     for(int j = 0; j < nEdges; ++j) { 
     data[i].flagInterface[j] = !data[i].flagInterface[j]; 
     data[i].typeInterface[j] = data[i].typeInterface[j] + 1; 
     data[i].neighborIds[j] = data[i].neighborIds[j] + 1; 
     } 
    } 

    } 

private: 

    const int numberOfCells; 
    static const int nEdges = 6; 
    struct data_t { 
    bool floodedCells = 0; 
    bool floodedCellsTimeInterval = 0; 

    double valueOfCellIds = 0; 
    double h = 0; 

    double h0 = 0; 
    double vU = 0; 
    double vV = 0; 
    double vUh = 0; 
    double vVh = 0; 
    double vUh0 = 0; 
    double vVh0 = 0; 
    double ghh = 0; 
    double sfx = 0; 
    double sfy = 0; 
    double qInflow = 0; 
    double qStartTime = 0; 
    double qEndTime = 0; 
    double qIn = 0; 
    double nx = 0; 
    double ny = 0; 
    double floorLevels = 0; 
    int lowerFloorCells = 0; 
    bool floorCompleteleyFilled = 0; 
    double cellLocationX = 0; 
    double cellLocationY = 0; 
    double cellLocationZ = 0; 
    int levelOfCell = 0; 
    bool flagInterface[nEdges] = {}; 
    int typeInterface[nEdges] = {}; 
    int neighborIds[nEdges] = {}; 
    }; 
    std::vector<data_t> data; 

}; 

int main() { 
    std::ios_base::sync_with_stdio(false); 
    FloodIsolation isolation; 
    clock_t start = clock(); 
    for (int i = 0; i < 400; ++i) { 
    if(i % 100 == 0) { 
     std::cout << i << "\n"; 
    } 
    isolation.isUpdateNeeded(); 
    } 
    clock_t stop = clock(); 
    std::cout << "Time: " << difftime(stop, start)/1000 << "\n"; 
} 

live example

Es ist jetzt 2x die Geschwindigkeit der Java-Version. (846 gegen 1631).

Quoten sind die JIT bemerkte das Cache-Brennen von Zugriff auf Daten überall, und verwandelte Ihren Code in eine logisch ähnliche, aber effizientere Reihenfolge.

drehte ich mich auch stdio Synchronisation ausgeschaltet, so dass nur dann, wenn Sie printf/scanf mit C++ std::cout und std::cin mischen benötigt wird. Wie dem so ist, drucken Sie nur ein paar Werte aus, aber das Standardverhalten von C++ beim Drucken ist zu paranoid und ineffizient.

Wenn kein tatsächlicher konstanter Wert ist, müssen die 3 "Array" -Werte aus dem struct entfernt werden. Das sollte keinen großen Leistungseinbruch verursachen.

Sie können möglicherweise einen weiteren Leistungsschub erhalten, indem Sie die Werte in diesem struct sortieren, indem Sie die Größe verringern und so den Speicherbedarf verringern (und auch den Zugriff sortieren, wenn es nicht darauf ankommt). Aber ich bin unsicher.

Eine Faustregel besagt, dass ein einzelner Cache-Fehltreffer 100 Mal teurer ist als ein Befehl. Die Daten so anzuordnen, dass sie die Cache-Kohärenz haben, ist sehr wertvoll.

Wenn das Umordnen der Daten in eine struct nicht durchführbar ist, können Sie die Iteration so ändern, dass sie nacheinander für jeden Container gilt.

Als Nebenbemerkung, beachten Sie, dass die Java-und C++ - Versionen einige feine Unterschiede in ihnen hatten. Der eine, den ich entdeckte, war, dass die Java-Version 3 Variablen in der "für jede Kante" -Schleife hat, während der C++ nur 2 hatte. Ich machte meine Übereinstimmung mit Java. Ich weiß nicht, ob es andere gibt.

Answer 2

Ja, der Cache in der C++ Version nimmt einen Hammerschlag. Es scheint, dass das JIT dafür besser gerüstet ist.

Wenn Sie die äußere for in isUpdateNeeded() zu kürzeren Snippets ändern. Der Unterschied geht weg.

Das folgende Beispiel erzeugt eine vierfache Beschleunigung.

void isUpdateNeeded() { 
    for (int i = 0; i < numberOfCells; ++i) { 
     h[i] = h[i] + 1; 
     floodedCells[i] = !floodedCells[i]; 
     floodedCellsTimeInterval[i] = !floodedCellsTimeInterval[i]; 
     qInflow[i] = qInflow[i] + 1; 
     qStartTime[i] = qStartTime[i] + 1; 
     qEndTime[i] = qEndTime[i] + 1; 
    } 

    for (int i = 0; i < numberOfCells; ++i) { 
     lowerFloorCells[i] = lowerFloorCells[i] + 1; 
     cellLocationX[i] = cellLocationX[i] + 1; 
     cellLocationY[i] = cellLocationY[i] + 1; 
     cellLocationZ[i] = cellLocationZ[i] + 1; 
     levelOfCell[i] = levelOfCell[i] + 1; 
     valueOfCellIds[i] = valueOfCellIds[i] + 1; 
     h0[i] = h0[i] + 1; 
     vU[i] = vU[i] + 1; 
     vV[i] = vV[i] + 1; 
     vUh[i] = vUh[i] + 1; 
     vVh[i] = vVh[i] + 1; 
    } 
    for (int i = 0; i < numberOfCells; ++i) { 
     vUh0[i] = vUh0[i] + 1; 
     vVh0[i] = vVh0[i] + 1; 
     ghh[i] = ghh[i] + 1; 
     sfx[i] = sfx[i] + 1; 
     sfy[i] = sfy[i] + 1; 
     qIn[i] = qIn[i] + 1; 
     for(int j = 0; j < nEdges; ++j) { 
      neighborIds[i * nEdges + j] = neighborIds[i * nEdges + j] + 1; 
     } 
     for(int j = 0; j < nEdges; ++j) { 
      typeInterface[i * nEdges + j] = typeInterface[i * nEdges + j] + 1; 
     } 
    } 

} 

Dies zeigt zu einem vernünftigen Grad, dass Cache-Misses der Grund für die Verlangsamung sind. Es ist auch wichtig zu beachten, dass die Variablen nicht abhängig sind, so dass eine Threading-Lösung leicht erstellt werden kann.

Ordnung wiederhergestellt

Per stefans Kommentar Ich habe versucht, sie in einer Struktur unter Verwendung der ursprünglichen Größe zu gruppieren. Dies entfernt den unmittelbaren Cache-Druck in ähnlicher Weise. Das Ergebnis ist, dass die Version C++ (CCFLAG -O3) etwa 15% schneller ist als die Java-Version.

Varning weder kurz noch hübsch.

#include <vector> 
#include <cmath> 
#include <iostream> 



class FloodIsolation { 
    struct item{ 
     char floodedCells; 
     char floodedCellsTimeInterval; 
     double valueOfCellIds; 
     double h; 
     double h0; 
     double vU; 
     double vV; 
     double vUh; 
     double vVh; 
     double vUh0; 
     double vVh0; 
     double sfx; 
     double sfy; 
     double qInflow; 
     double qStartTime; 
     double qEndTime; 
     double qIn; 
     double nx; 
     double ny; 
     double ghh; 
     double floorLevels; 
     int lowerFloorCells; 
     char flagInterface; 
     char floorCompletelyFilled; 
     double cellLocationX; 
     double cellLocationY; 
     double cellLocationZ; 
     int levelOfCell; 
    }; 
    struct inner_item{ 
     int typeInterface; 
     int neighborIds; 
    }; 

    std::vector<inner_item> inner_data; 
    std::vector<item> data; 

public: 
    FloodIsolation() : 
      numberOfCells(20000), inner_data(numberOfCells * nEdges), data(numberOfCells) 
    { 

    } 
    ~FloodIsolation(){ 
    } 

    void isUpdateNeeded() { 
     for (int i = 0; i < numberOfCells; ++i) { 
      data[i].h = data[i].h + 1; 
      data[i].floodedCells = !data[i].floodedCells; 
      data[i].floodedCellsTimeInterval = !data[i].floodedCellsTimeInterval; 
      data[i].qInflow = data[i].qInflow + 1; 
      data[i].qStartTime = data[i].qStartTime + 1; 
      data[i].qEndTime = data[i].qEndTime + 1; 
      data[i].lowerFloorCells = data[i].lowerFloorCells + 1; 
      data[i].cellLocationX = data[i].cellLocationX + 1; 
      data[i].cellLocationY = data[i].cellLocationY + 1; 
      data[i].cellLocationZ = data[i].cellLocationZ + 1; 
      data[i].levelOfCell = data[i].levelOfCell + 1; 
      data[i].valueOfCellIds = data[i].valueOfCellIds + 1; 
      data[i].h0 = data[i].h0 + 1; 
      data[i].vU = data[i].vU + 1; 
      data[i].vV = data[i].vV + 1; 
      data[i].vUh = data[i].vUh + 1; 
      data[i].vVh = data[i].vVh + 1; 
      data[i].vUh0 = data[i].vUh0 + 1; 
      data[i].vVh0 = data[i].vVh0 + 1; 
      data[i].ghh = data[i].ghh + 1; 
      data[i].sfx = data[i].sfx + 1; 
      data[i].sfy = data[i].sfy + 1; 
      data[i].qIn = data[i].qIn + 1; 
      for(int j = 0; j < nEdges; ++j) { 
       inner_data[i * nEdges + j].neighborIds = inner_data[i * nEdges + j].neighborIds + 1; 
       inner_data[i * nEdges + j].typeInterface = inner_data[i * nEdges + j].typeInterface + 1; 
      } 
     } 

    } 

    static const int nEdges; 
private: 

    const int numberOfCells; 

}; 

const int FloodIsolation::nEdges = 6; 

int main() { 
    FloodIsolation isolation; 
    clock_t start = clock(); 
    for (int i = 0; i < 4400; ++i) { 
     if(i % 100 == 0) { 
      std::cout << i << "\n"; 
     } 
     isolation.isUpdateNeeded(); 
    } 

    clock_t stop = clock(); 
    std::cout << "Time: " << difftime(stop, start)/1000 << "\n"; 
} 

Mein Ergebnis unterscheidet sich von Jerry Särge leicht für die ursprünglichen Größen. Für mich bleiben die Unterschiede bestehen. Das könnte meine Java-Version 1.7.0_75 sein.

Answer 3

Wie @Stefan in einem Kommentar auf @ CaptainGiraffes Antwort erraten hat, gewinnen Sie ziemlich viel, indem Sie einen Vektor von Strukturen anstelle einer Struktur von Vektoren verwenden.Korrigierte Code wie folgt aussieht:

#include <vector> 
#include <cmath> 
#include <iostream> 
#include <time.h> 

class FloodIsolation { 
public: 
    FloodIsolation() : 
      h(0), 
      floodedCells(0), 
      floodedCellsTimeInterval(0), 
      qInflow(0), 
      qStartTime(0), 
      qEndTime(0), 
      lowerFloorCells(0), 
      cellLocationX(0), 
      cellLocationY(0), 
      cellLocationZ(0), 
      levelOfCell(0), 
      valueOfCellIds(0), 
      h0(0), 
      vU(0), 
      vV(0), 
      vUh(0), 
      vVh(0), 
      vUh0(0), 
      vVh0(0), 
      ghh(0), 
      sfx(0), 
      sfy(0), 
      qIn(0), 
      typeInterface(nEdges, 0), 
      neighborIds(nEdges, 0) 
    { 
    } 

    ~FloodIsolation(){ 
    } 

    void Update() { 
     h = h + 1; 
     floodedCells = !floodedCells; 
     floodedCellsTimeInterval = !floodedCellsTimeInterval; 
     qInflow = qInflow + 1; 
     qStartTime = qStartTime + 1; 
     qEndTime = qEndTime + 1; 
     lowerFloorCells = lowerFloorCells + 1; 
     cellLocationX = cellLocationX + 1; 
     cellLocationY = cellLocationY + 1; 
     cellLocationZ = cellLocationZ + 1; 
     levelOfCell = levelOfCell + 1; 
     valueOfCellIds = valueOfCellIds + 1; 
     h0 = h0 + 1; 
     vU = vU + 1; 
     vV = vV + 1; 
     vUh = vUh + 1; 
     vVh = vVh + 1; 
     vUh0 = vUh0 + 1; 
     vVh0 = vVh0 + 1; 
     ghh = ghh + 1; 
     sfx = sfx + 1; 
     sfy = sfy + 1; 
     qIn = qIn + 1; 
     for(int j = 0; j < nEdges; ++j) { 
      ++typeInterface[j]; 
      ++neighborIds[j]; 
     }  
    } 

private: 

    static const int nEdges = 6; 
    bool floodedCells; 
    bool floodedCellsTimeInterval; 

    std::vector<int> neighborIds; 
    double valueOfCellIds; 
    double h; 
    double h0; 
    double vU; 
    double vV; 
    double vUh; 
    double vVh; 
    double vUh0; 
    double vVh0; 
    double ghh; 
    double sfx; 
    double sfy; 
    double qInflow; 
    double qStartTime; 
    double qEndTime; 
    double qIn; 
    double nx; 
    double ny; 
    double floorLevels; 
    int lowerFloorCells; 
    bool flagInterface; 
    std::vector<int> typeInterface; 
    bool floorCompleteleyFilled; 
    double cellLocationX; 
    double cellLocationY; 
    double cellLocationZ; 
    int levelOfCell; 
}; 

int main() { 
    std::vector<FloodIsolation> isolation(20000); 
    clock_t start = clock(); 
    for (int i = 0; i < 400; ++i) { 
     if(i % 100 == 0) { 
      std::cout << i << "\n"; 
     } 

     for (auto &f : isolation) 
      f.Update(); 
    } 
    clock_t stop = clock(); 
    std::cout << "Time: " << difftime(stop, start)/1000 << "\n"; 
} 

Zusammengestellt mit dem Compiler von VC++ 2015 CTP, mit -EHsc -O2b2 -GL -Qpar, erhalte ich Ergebnisse wie:

0 
100 
200 
300 
Time: 0.135 

mit g Kompilieren ++ ein Ergebnis erzeugt, die etwas langsamer ist:

0 
100 
200 
300 
Time: 0.156 

Auf der gleichen Hardware, mit dem Compiler/JVM von Java 8u45, bekomme ich Ergebnisse wie:

0 
100 
200 
300 
Time: 181 

Dies ist etwa 35% langsamer als die Version von VC++ und etwa 16% langsamer als die Version von g ++.

Wenn wir die Anzahl der Iterationen auf die gewünschten 2000 erhöhen, sinkt der Unterschied auf nur 3%, was darauf hindeutet, dass ein Teil des Vorteils von C++ in diesem Fall einfach schneller Laden (ein mehrjähriges Problem mit Java) ist Ausführung selbst. Das überrascht mich in diesem Fall nicht - die Berechnung, die gemessen wird (im geposteten Code) ist so trivial, dass ich bezweifle, dass die meisten Compiler eine Menge tun können, um sie zu optimieren. Hier

Answer 4

Ich vermute, dies ist über die Zuweisung von Speicher.

Ich denke, dass Java einen großen zusammenhängenden Block bei Programmstart ergreift, während C++ fragt das Betriebssystem für Bits und Stücke, wie es geht.

Um diese Theorie auf die Probe gestellt ich eine Änderung an der C++ Version gemacht und es begann plötzlich etwas schneller als die Java Version ausgeführt wird:

int main() { 
    { 
     // grab a large chunk of contiguous memory and liberate it 
     std::vector<double> alloc(20000 * 20); 
    } 
    FloodIsolation isolation; 
    clock_t start = clock(); 
    for (int i = 0; i < 400; ++i) { 
     if(i % 100 == 0) { 
      std::cout << i << "\n"; 
     } 
     isolation.isUpdateNeeded(); 
    } 
    clock_t stop = clock(); 
    std::cout << "Time: " << (1000 * difftime(stop, start)/CLOCKS_PER_SEC) << "\n"; 
} 

Runtime ohne den vorbelegen Vektor:

0 
100 
200 
300 
Time: 1250.31 

Runtime mit der Vorbelegung Vektor:

0 
100 
200 
300 
Time: 331.214 

Runtime für Java Version:

0 
100 
200 
300 
Time: 407