Java 8 vezes mais rápido com arrays do que std :: vector em C ++. O que eu fiz errado?

88

Eu tenho o seguinte código Java com vários grandes arrays que nunca mudam de tamanho. Ele roda em 1100 ms no meu computador.

Implementei o mesmo código em C ++ e usei std::vector.

O tempo de implementação do C ++ que executa exatamente o mesmo código é 8.800 ms em meu computador. O que eu fiz de errado, para que funcione tão lentamente?

Basicamente, o código faz o seguinte:

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

Ele itera por meio de diferentes matrizes com um tamanho de cerca de 20.000.

Você pode encontrar ambas as implementações nos seguintes links:

(No ideone eu só pude executar o loop 400 vezes em vez de 2.000 vezes por causa da limitação de tempo. Mas mesmo aqui há uma diferença de três vezes)

java c++ arrays performance stdvector RobinXSI
fonte
42
std::vector<bool>usa um bit por elemento para economizar espaço, o que leva a muitas mudanças de bits. Se você quer velocidade, deve ficar longe dela. Use em seu std::vector<int>lugar.
molbdnilo
44
@molbdnilo Ou std :: vector <char>. Não há necessidade de desperdiçar que muito ;-)
Stefan
7
Curiosamente. A versão c ++ é mais rápida quando o número de células é 200. Localidade do cache?
Capitão Girafa,
9
Parte II: Seria muito melhor criar uma classe / estrutura separada que contenha um de cada membro das matrizes e, em seguida, ter uma única matriz de objetos dessa estrutura, porque então você está realmente iterando através da memória apenas uma vez, em uma direção.
Timo Geusch
9
@TimoGeusch: Embora eu pense h[i] += 1;ou (melhor ainda) ++h[i]seja mais legível do que h[i] = h[i] + 1;, ficaria um pouco surpreso se ver qualquer diferença significativa na velocidade entre eles. Um compilador pode "descobrir" que ambos estão fazendo a mesma coisa e gerar o mesmo código de qualquer maneira (pelo menos na maioria dos casos comuns).
Jerry Coffin

Respostas:

36

Aqui está a versão C ++ com os dados por nó reunidos em uma estrutura e um único vetor dessa estrutura usado:

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

exemplo vivo

O tempo agora é 2x a velocidade da versão Java. (846 vs 1631).

As probabilidades são de que o JIT percebeu a queima do cache de dados de acesso em todo o lugar e transformou seu código em uma ordem logicamente semelhante, mas mais eficiente.

Também desativei a sincronização do stdio, pois ela só é necessária se você misturar printf/ scanfcom C ++ std::coute std::cin. Acontece que você imprime apenas alguns valores, mas o comportamento padrão do C ++ para impressão é excessivamente paranóico e ineficiente.

Se nEdgesnão for um valor constante real, os 3 valores da "matriz" terão que ser retirados do struct. Isso não deve causar um grande impacto no desempenho.

Você pode conseguir outro aumento de desempenho classificando os valores structdiminuindo o tamanho, reduzindo assim o consumo de memória (e classificando o acesso também quando não importa). Mas não tenho certeza.

Uma regra prática é que uma única falha de cache é 100 vezes mais cara do que uma instrução. Organizar seus dados para ter coerência de cache tem muito valor.

Se reorganizar os dados em um structfor inviável, você pode alterar sua iteração para ser sobre cada contêiner por vez.

Como um aparte, observe que as versões Java e C ++ tinham algumas diferenças sutis. O que descobri foi que a versão Java tem 3 variáveis ​​no loop "for each edge", enquanto a C ++ tinha apenas 2. Fiz a minha corresponder ao Java. Não sei se existem outros.

Yakk - Adam Nevraumont
fonte
44

Sim, o cache na versão c ++ leva um martelar. Parece que o JIT está melhor equipado para lidar com isso.

Se você alterar o outer forin isUpdateNeeded () para snippets mais curtos. A diferença vai embora.

O exemplo abaixo produz um aumento de 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;
        }
    }

}

Isso mostra, em um grau razoável, que falhas de cache são o motivo da lentidão. Também é importante observar que as variáveis ​​não são dependentes, portanto, uma solução encadeada é facilmente criada.

Ordem restaurada

De acordo com o comentário de Stefans, tentei agrupá-los em uma estrutura usando os tamanhos originais. Isso remove a pressão imediata do cache de maneira semelhante. O resultado é que a versão c ++ (CCFLAG -O3) é cerca de 15% mais rápida do que a versão java.

Varning nem baixo nem bonito.

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

Meu resultado difere ligeiramente de Jerry Coffins para os tamanhos originais. Para mim, as diferenças permanecem. Pode muito bem ser minha versão java, 1.7.0_75.

Capitão girafa
fonte
12
Pode ser uma boa ideia agrupar esses dados em uma estrutura e ter apenas um vetor
stefan
Bem, estou no celular, então não posso fazer medições ;-) mas o único vetor deve ser bom (também em termos de alocações)
stefan
1
Usar ++ajuda de alguma forma? x = x + 1parece terrivelmente desajeitado em comparação com ++x.
tadman
3
Corrija a palavra incorreta "resultado". Isso está me matando .. :)
FleetC0m
1
Se todo o iterador couber em um único registro, fazer uma cópia pode ser realmente mais rápido em alguns casos do que atualizar no local. Se você estiver atualizando no local, é muito provável que esteja usando o valor atualizado logo em seguida. Portanto, você tem uma dependência Read-after-Write. Se você atualizar, mas precisar apenas do valor antigo, essas operações não dependem umas das outras e a CPU tem mais espaço para fazê-las em paralelo, por exemplo, em diferentes pipelines, aumentando o IPC efetivo.
Piotr Kołaczkowski
20

Como @Stefan adivinhou em um comentário sobre a resposta de @CapitãoGiraffe, você ganha bastante usando um vetor de estruturas em vez de uma estrutura de vetores. O código corrigido fica assim:

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

Compilado com o compilador de VC ++ 2015 CTP, usando -EHsc -O2b2 -GL -Qpar, obtenho resultados como:

0
100
200
300
Time: 0.135

Compilar com g ++ produz um resultado um pouco mais lento:

0
100
200
300
Time: 0.156

No mesmo hardware, usando o compilador / JVM do Java 8u45, obtenho resultados como:

0
100
200
300
Time: 181

Isso é cerca de 35% mais lento do que a versão do VC ++ e cerca de 16% mais lento do que a versão do g ++.

Se aumentarmos o número de iterações para as 2.000 desejadas, a diferença cai para apenas 3%, sugerindo que parte da vantagem do C ++ neste caso é simplesmente um carregamento mais rápido (um problema perene com Java), não realmente na execução em si. Isso não me parece surpreendente neste caso - o cálculo que está sendo medido (no código postado) é tão trivial que duvido que a maioria dos compiladores possa fazer muito para otimizá-lo.

Jerry Coffin
fonte
1
Ainda há espaço para melhorias, embora isso provavelmente não afete o desempenho de forma significativa: agrupando as variáveis ​​booleanas (em geral agrupando as variáveis ​​do mesmo tipo).
stefan,
1
@stefan: Sim, mas eu estava intencionalmente evitando fazer qualquer otimização pesada do código e, em vez disso, fazendo (aproximadamente) o mínimo necessário para remover os problemas mais óbvios na implementação original. Se eu realmente quisesse otimizar, adicionaria um #pragma ompe (talvez) um pouco de trabalho para garantir que cada iteração de loop seja independente. Isso exigiria um trabalho mínimo para obter um aumento de velocidade ~ Nx, onde N é o número de núcleos de processador disponíveis.
Jerry Coffin de
Bom ponto. Isso é bom o suficiente para uma resposta a esta pergunta
stefan,
Como 181 unidades de tempo são 35% mais lentas do que 0,135 unidades de tempo e 16% mais lentas do que 0,156 unidades de tempo? Você quis dizer que a duração da versão do Java é 0,181?
Jamesdlin
1
@jamesdlin: eles estão usando unidades diferentes (deixados assim, porque é como as coisas eram no original). O código C ++ fornece tempo em segundos, mas o código Java fornece tempo em milissegundos.
Jerry Coffin
9

Suspeito que se trate de alocação de memória.

Estou pensando que Javapega um grande bloco contíguo na inicialização do programa, ao passo que C++pede ao sistema operacional bits e peças à medida que avança.

Para colocar essa teoria em teste, fiz uma modificação na C++versão e, de repente, ela começou a funcionar um pouco mais rápido do que a Javaversão:

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

Tempo de execução sem o vetor de pré-alocação:

0
100
200
300
Time: 1250.31

Tempo de execução com o vetor de pré-alocação:

0
100
200
300
Time: 331.214

Tempo de execução para a Javaversão:

0
100
200
300
Time: 407
Galik
fonte
Bem, você realmente não pode confiar nisso. Os dados em FloodIsolationainda podem ser alocados em outro lugar.
stefan,
@stefan Ainda é um resultado interessante.
Capitão Girafa,
@CaptainGiraffe é, eu não disse que é inútil ;-)
stefan
2
@stefan Não estou propondo isso como uma solução, apenas investigando o que acho que é o problema. Parece que pode não ter nada a ver com cache, mas como o C ++ RTS difere do Java.
Galik
1
@Galik Nem sempre é a causa, embora seja bastante interessante ver que ela tem um grande impacto em sua plataforma. No ideone, não consigo reproduzir seu resultado (ao que parece, o bloco alocado não é reutilizado): ideone.com/im4NMO No entanto, a solução de vetor de estruturas tem um impacto de desempenho mais consistente: ideone.com/b0VWSN
stefan