Java 8 fois plus rapide avec des tableaux que std :: vector en C ++. Qu'ai-je fait de mal?

88

J'ai le code Java suivant avec plusieurs grands tableaux qui ne changent jamais de taille. Il tourne en 1100 ms sur mon ordinateur.

J'ai implémenté le même code en C ++ et utilisé std::vector.

Le temps de l'implémentation C ++ qui exécute exactement le même code est de 8800 ms sur mon ordinateur. Qu'est-ce que j'ai fait de mal, pour que cela fonctionne lentement?

Fondamentalement, le code effectue les opérations suivantes:

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

Il parcourt différents tableaux d'une taille d'environ 20000.

Vous pouvez trouver les deux implémentations sous les liens suivants:

(Sur ideone, je ne pouvais exécuter la boucle que 400 fois au lieu de 2000 fois à cause de la limitation de temps. Mais même ici, il y a une différence de trois fois)

java c++ arrays performance stdvector RobinXSI
la source
42
std::vector<bool>utilise un bit par élément pour économiser de l'espace, ce qui entraîne beaucoup de décalage de bits. Si vous voulez de la vitesse, vous devez vous en tenir à l'écart. Utilisez std::vector<int>plutôt.
molbdnilo
44
@molbdnilo Ou std :: vector <char>. Il n'y a pas besoin de perdre que beaucoup ;-)
stefan
7
Assez amusant. La version c ++ est plus rapide lorsque le nombre de cellules est de 200. Localité du cache?
Captain Giraffe
9
Partie II: Vous feriez bien mieux de créer une classe / structure distincte qui contient un de chaque membre des tableaux, puis d'avoir un seul tableau d'objets de cette structure, car alors vous n'effectuez une itération dans la mémoire qu'une seule fois, en une direction.
Timo Geusch
9
@TimoGeusch: Bien que je pense h[i] += 1;ou (mieux encore) ++h[i]soit plus lisible que h[i] = h[i] + 1;, je serais un peu surpris de voir une différence de vitesse significative entre eux. Un compilateur peut "comprendre" qu'ils font tous les deux la même chose et générer le même code dans les deux cas (au moins dans la plupart des cas courants).
Jerry Coffin

Réponses:

36

Voici la version C ++ avec les données par nœud rassemblées dans une structure, et un seul vecteur de cette structure utilisé:

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

exemple en direct

Le temps est maintenant 2x la vitesse de la version Java. (846 contre 1631).

Il y a de fortes chances que le JIT ait remarqué la gravure du cache pour accéder aux données partout et a transformé votre code en un ordre logiquement similaire mais plus efficace.

J'ai également désactivé la synchronisation stdio, car cela n'est nécessaire que si vous mélangez printf/ scanfavec C ++ std::coutet std::cin. En l'occurrence, vous n'imprimez que quelques valeurs, mais le comportement par défaut de C ++ pour l'impression est trop paranoïaque et inefficace.

Si nEdges n'est pas une valeur constante réelle, alors les 3 valeurs de «tableau» devront être supprimées du struct. Cela ne devrait pas causer un énorme impact sur les performances.

Vous pourrez peut-être obtenir une autre amélioration des performances en triant les valeurs dans ce struct diminuant la taille, réduisant ainsi l'empreinte mémoire (et en triant également l'accès lorsque cela n'a pas d'importance). Mais je ne suis pas sûr.

En règle générale, un seul échec de cache coûte 100 fois plus cher qu'une instruction. Organiser vos données pour avoir la cohérence du cache a beaucoup de valeur.

Si réarranger les données dans un structest infaisable, vous pouvez changer votre itération pour être sur chaque conteneur à son tour.

En passant, notez que les versions Java et C ++ présentaient des différences subtiles. Celui que j'ai repéré était que la version Java a 3 variables dans la boucle "for each edge", alors que celle en C ++ n'en avait que 2. J'ai fait correspondre la mienne à Java. Je ne sais pas s'il y en a d'autres.

Yakk - Adam Nevraumont
la source
44

Oui, le cache dans la version c ++ prend un martèlement. Il semble que le JIT soit mieux équipé pour gérer cela.

Si vous changez l'extérieur for de isUpdateNeeded () en extraits de code plus courts. La différence disparaît.

L'exemple ci-dessous produit une accélération 4x.

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

}

Cela montre à un degré raisonnable que les échecs de cache sont la raison du ralentissement. Il est également important de noter que les variables ne sont pas dépendantes, de sorte qu'une solution threadée est facilement créée.

Commande rétablie

Selon le commentaire de stefans, j'ai essayé de les regrouper dans une structure en utilisant les tailles d'origine. Cela supprime la pression immédiate du cache de la même manière. Le résultat est que la version c ++ (CCFLAG -O3) est environ 15% plus rapide que la version java.

Varning ni court ni joli.

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

Mon résultat diffère légèrement de Jerry Coffins pour les tailles d'origine. Pour moi, les différences demeurent. Cela pourrait bien être ma version java, 1.7.0_75.

Capitaine Girafe
la source
12
Ce pourrait être une bonne idée de regrouper ces données dans une structure et d'avoir juste un vecteur
stefan
Eh bien, je suis sur mobile, donc je ne peux pas faire de mesures ;-) mais le vecteur devrait être bon (également en termes d'allocations)
stefan
1
Est-ce que l'utilisation ++aide à quelque titre que ce soit? x = x + 1semble terriblement maladroit par rapport à ++x.
tadman
3
Veuillez corriger le mot "résultat" mal orthographié. Ça me tue .. :)
flotteC0m
1
Si l'ensemble de l'itérateur tient dans un seul registre, la création d'une copie peut être en fait plus rapide dans certains cas que la mise à jour sur place. Si vous effectuez une mise à jour sur place, c'est parce que vous utilisez très probablement la valeur mise à jour juste après. Vous avez donc une dépendance de lecture après écriture. Si vous mettez à jour, mais que vous n'avez besoin que de l'ancienne valeur, ces opérations ne dépendent pas les unes des autres et le CPU a plus de place pour les faire en parallèle, par exemple sur différents pipelines, augmentant ainsi l'IPC efficace.
Piotr Kołaczkowski
20

Comme @Stefan l'a deviné dans un commentaire sur la réponse de @ CaptainGiraffe, vous gagnez beaucoup à utiliser un vecteur de structures au lieu d'une structure de vecteurs. Le code corrigé ressemble à ceci:

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

Compilé avec le compilateur de VC ++ 2015 CTP, en utilisant -EHsc -O2b2 -GL -Qpar, j'obtiens des résultats comme:

0
100
200
300
Time: 0.135

La compilation avec g ++ produit un résultat légèrement plus lent:

0
100
200
300
Time: 0.156

Sur le même matériel, en utilisant le compilateur / JVM de Java 8u45, j'obtiens des résultats comme:

0
100
200
300
Time: 181

C'est environ 35% plus lent que la version de VC ++, et environ 16% plus lent que la version de g ++.

Si nous augmentons le nombre d'itérations aux 2000 souhaités, la différence tombe à seulement 3%, ce qui suggère qu'une partie de l'avantage de C ++ dans ce cas est simplement un chargement plus rapide (un problème éternel avec Java), pas vraiment dans l'exécution elle-même. Cela ne me semble pas surprenant dans ce cas - le calcul mesuré (dans le code affiché) est si trivial que je doute que la plupart des compilateurs puissent faire beaucoup pour l'optimiser.

Jerry Coffin
la source
1
Il y a encore place à l'amélioration, bien que cela n'affectera probablement pas les performances de manière significative: regrouper les variables booléennes (en général, regrouper les variables de même type).
stefan
1
@stefan: Oui, mais j'évitais intentionnellement de faire une optimisation lourde du code, et plutôt de faire (à peu près) le minimum nécessaire pour éliminer les problèmes les plus évidents dans l'implémentation d'origine. Si je voulais vraiment optimiser, j'ajouterais un #pragma omp, et (peut-être) un peu de travail pour m'assurer que chaque itération de boucle est indépendante. Cela prendrait un travail assez minime pour obtenir une accélération de ~ Nx, où N est le nombre de cœurs de processeur disponibles.
Jerry Coffin
Bon point. C'est assez bien pour une réponse à cette question
stefan
Comment 181 unités de temps sont-elles 35% plus lentes que 0,135 unités de temps et 16% plus lentes que 0,156 unités de temps? Vouliez-vous dire que la durée de la version Java est de 0,181?
jamesdlin
1
@jamesdlin: ils utilisent des unités différentes (à gauche, car c'est comme ça que les choses étaient dans l'original). Le code C ++ donne le temps en secondes, mais le code Java donne le temps en millisecondes.
Jerry Coffin
9

Je soupçonne qu'il s'agit d'allocation de mémoire.

Je pense que Javasaisit un gros bloc contigu au démarrage du programme alors queC++ le système d'exploitation demande des morceaux au fur et à mesure.

Pour mettre cette théorie à l'épreuve, j'ai apporté une modification à la C++version et elle a soudainement commencé à fonctionner légèrement plus vite que la Javaversion:

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 sans le vecteur de pré-allocation:

0
100
200
300
Time: 1250.31

Runtime avec le vecteur de pré-allocation:

0
100
200
300
Time: 331.214

Runtime pour la Javaversion:

0
100
200
300
Time: 407
Galik
la source
Eh bien, vous ne pouvez pas vraiment vous y fier. Les données FloodIsolationpeuvent encore être attribuées ailleurs.
stefan
@stefan Encore un résultat intéressant.
Captain Giraffe
@CaptainGiraffe ça l'est, je n'ai pas dit que c'était inutile ;-)
stefan
2
@stefan Je ne le propose pas comme solution, je me contente d'enquêter sur ce que je pense être le problème. Il semble que cela n'ait rien à voir avec la mise en cache, mais en quoi le C ++ RTS diffère de Java.
Galik
1
@Galik Ce n'est pas toujours la cause, même s'il est assez intéressant de le voir avoir un tel impact sur votre plate-forme. Sur ideone, je ne peux pas reproduire votre résultat (il semble que le bloc alloué n'est pas réutilisé): ideone.com/im4NMO Cependant, le vecteur de la solution structs a un impact sur les performances plus cohérent: ideone.com/b0VWSN
stefan