Java 8 veces más rápido con matrices que std :: vector en C ++. ¿Qué hice mal?

88

Tengo el siguiente código Java con varias matrices grandes que nunca cambian de tamaño. Funciona en 1100 ms en mi computadora.

Implementé el mismo código en C ++ y usé std::vector.

El tiempo de la implementación de C ++ que ejecuta exactamente el mismo código es 8800 ms en mi computadora. ¿Qué hice mal para que funcione tan lentamente?

Básicamente, el código hace lo siguiente:

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

Itera a través de diferentes matrices con un tamaño de alrededor de 20000.

Puede encontrar ambas implementaciones en los siguientes enlaces:

(En ideone solo pude ejecutar el bucle 400 veces en lugar de 2000 veces debido a la limitación de tiempo. Pero incluso aquí hay una diferencia de tres veces)

java c++ arrays performance stdvector RobinXSI
fuente
42
std::vector<bool>utiliza un bit por elemento para ahorrar espacio, lo que conduce a muchos cambios de bits. Si quieres velocidad, debes mantenerte alejado de ella. Úselo en su std::vector<int>lugar.
molbdnilo
44
@molbdnilo O std :: vector <char>. No hay necesidad de perder que mucho ;-)
Stefan
7
Curiosamente. La versión de C ++ es más rápida cuando el número de celdas es 200. ¿Localidad de caché?
Captain Giraffe
9
Parte II: sería mucho mejor crear una clase / estructura separada que contenga uno de cada miembro de las matrices y luego tener una única matriz de objetos de esta estructura, porque entonces en realidad está iterando a través de la memoria solo una vez, en una sola dirección.
Timo Geusch
9
@TimoGeusch: Si bien creo que h[i] += 1;o (mejor aún) ++h[i]es más legible que h[i] = h[i] + 1;, me sorprendería un poco ver una diferencia significativa en la velocidad entre ellos. Un compilador puede "darse cuenta" de que ambos están haciendo lo mismo y generar el mismo código de cualquier manera (al menos en los casos más comunes).
Jerry Coffin

Respuestas:

36

Aquí está la versión C ++ con los datos por nodo reunidos en una estructura y un solo vector de esa estructura utilizado:

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

ejemplo vivo

El tiempo es ahora el doble de la velocidad de la versión de Java. (846 frente a 1631).

Lo más probable es que el JIT notó la quema de caché de los datos de acceso por todas partes y transformó su código en un orden lógicamente similar pero más eficiente.

También desactivé la sincronización de stdio, ya que solo es necesaria si mezcla printf/ scanfcon C ++ std::couty std::cin. Da la casualidad de que solo imprime unos pocos valores, pero el comportamiento predeterminado de C ++ para imprimir es demasiado paranoico e ineficaz.

Si nEdgesno es un valor constante real, entonces los 3 valores de "matriz" tendrán que ser eliminados del struct. Eso no debería causar un gran impacto en el rendimiento.

Es posible que pueda obtener otro impulso de rendimiento clasificando los valores en eso structal disminuir el tamaño, reduciendo así la huella de memoria (y clasificando el acceso también cuando no importa). Pero no estoy seguro.

Una regla general es que una sola falta de caché es 100 veces más cara que una instrucción. Organizar sus datos para tener coherencia en la caché tiene mucho valor.

Si reorganizar los datos en a no structes factible, puede cambiar su iteración para que sea sobre cada contenedor a su vez.

Como comentario aparte, tenga en cuenta que las versiones de Java y C ++ tenían algunas diferencias sutiles. El que vi fue que la versión de Java tiene 3 variables en el ciclo "para cada borde", mientras que la de C ++ solo tenía 2. Hice que la mía coincidiera con la de Java. No sé si hay otros.

Yakk - Adam Nevraumont
fuente
44

Sí, el caché en la versión c ++ tiene un martilleo. Parece que el JIT está mejor equipado para manejar esto.

Si cambia el exterior foren isUpdateNeeded () a fragmentos más cortos. La diferencia desaparece.

El siguiente ejemplo produce una aceleración 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;
        }
    }

}

Esto muestra en un grado razonable que las fallas de caché son la razón de la desaceleración. También es importante tener en cuenta que las variables no son dependientes, por lo que se crea fácilmente una solución de subprocesos.

Orden restaurado

Según el comentario de Stefans, intenté agruparlos en una estructura usando los tamaños originales. Esto elimina la presión de caché inmediata de forma similar. El resultado es que la versión c ++ (CCFLAG -O3) es aproximadamente un 15% más rápida que la versión java.

Varning ni corto ni 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";
}

Mi resultado difiere ligeramente de Jerry Coffins por los tamaños originales. Para mí las diferencias permanecen. Bien podría ser mi versión de Java, 1.7.0_75.

Capitán Jirafa
fuente
12
Podría ser una buena idea agrupar esos datos en una estructura y tener solo un vector
stefan
Bueno, yo estoy en el móvil, así que no puedo hacer mediciones ;-) pero el vector de uno debe ser bueno (también en términos de asignaciones)
Stefan
1
¿El uso ++ayuda de alguna manera? x = x + 1parece terriblemente torpe comparado con ++x.
tadman
3
Corrija la palabra "resultado" mal escrita. Me está matando .. :)
fleetC0m
1
Si todo el iterador cabe en un solo registro, hacer una copia podría ser más rápido en algunos casos que actualizar en el lugar. Si está realizando una actualización en su lugar, esto se debe a que es muy probable que esté usando el valor actualizado justo después. Entonces tiene una dependencia de lectura tras escritura. Si actualiza, pero solo necesita el valor anterior, esas operaciones no dependen entre sí y la CPU tiene más espacio para hacerlas en paralelo, por ejemplo, en diferentes tuberías, aumentando la IPC efectiva.
Piotr Kołaczkowski
20

Como @Stefan adivinó en un comentario sobre la respuesta de @ CaptainGiraffe, se gana bastante al usar un vector de estructuras en lugar de una estructura de vectores. El código corregido se ve así:

#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 con el compilador de VC ++ 2015 CTP, usando -EHsc -O2b2 -GL -Qpar, obtengo resultados como:

0
100
200
300
Time: 0.135

Compilar con g ++ produce un resultado que es un poco más lento:

0
100
200
300
Time: 0.156

En el mismo hardware, usando el compilador / JVM de Java 8u45, obtengo resultados como:

0
100
200
300
Time: 181

Esto es alrededor de un 35% más lento que la versión de VC ++, y alrededor de un 16% más lento que la versión de g ++.

Si aumentamos el número de iteraciones al 2000 deseado, la diferencia cae a solo el 3%, lo que sugiere que parte de la ventaja de C ++ en este caso es simplemente una carga más rápida (un problema perenne con Java), no realmente en la ejecución en sí. Esto no me sorprende en este caso: el cálculo que se mide (en el código publicado) es tan trivial que dudo que la mayoría de los compiladores puedan hacer mucho para optimizarlo.

Jerry Coffin
fuente
1
Todavía hay margen de mejora, aunque lo más probable es que esto no afecte significativamente el rendimiento: agrupar las variables booleanas (en general, agrupar las variables del mismo tipo).
stefan
1
@stefan: La hay, pero intencionalmente estaba evitando hacer una gran optimización del código, y en su lugar estaba haciendo (aproximadamente) el mínimo necesario para eliminar los problemas más obvios en la implementación original. Si realmente quisiera optimizar, agregaría un #pragma omp, y (quizás) un poco de trabajo para asegurar que cada iteración de bucle sea independiente. Eso requeriría un trabajo bastante mínimo para obtener una aceleración de ~ Nx, donde N es la cantidad de núcleos de procesador disponibles.
Jerry Coffin
Buen punto. Esto es lo suficientemente bueno para una respuesta a esta pregunta
stefan
¿Cómo es 181 unidades de tiempo un 35% más lento que 0,135 unidades de tiempo y un 16% más lento que 0,156 unidades de tiempo? ¿Quiso decir que la duración de la versión de Java es 0.181?
jamesdlin
1
@jamesdlin: están usando diferentes unidades (se dejaron así, porque así eran las cosas en el original). El código C ++ da tiempo en segundos, pero el código Java da tiempo en milisegundos.
Jerry Coffin
9

Sospecho que se trata de la asignación de memoria.

Estoy pensando que Javatoma un gran bloque contiguo al inicio del programa, mientras que C++le pide al sistema operativo bits y piezas a medida que avanza.

Para poner esa teoría a prueba, hice una modificación a la C++versión y de repente comenzó a funcionar un poco más rápido que la Javaversión:

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

Tiempo de ejecución sin el vector de preasignación:

0
100
200
300
Time: 1250.31

Tiempo de ejecución con el vector de preasignación:

0
100
200
300
Time: 331.214

Tiempo de ejecución de la Javaversión:

0
100
200
300
Time: 407
Galik
fuente
Bueno, realmente no puedes confiar en eso. Los datos de FloodIsolationtodavía pueden asignarse a otro lugar.
stefan
@stefan Sigue siendo un resultado interesante.
Captain Giraffe
@CaptainGiraffe lo es, no dije que fuera inútil ;-)
stefan
2
@stefan no lo estoy proponiendo como una solución, simplemente investigando cuál creo que es el problema. Parece que puede que no tenga nada que ver con el almacenamiento en caché, pero en qué se diferencia C ++ RTS de Java.
Galik
1
@Galik No siempre es la causa, aunque es bastante interesante ver que tiene un gran impacto en su plataforma. En ideone, no puedo reproducir su resultado (como parece, el bloque asignado no se reutiliza): ideone.com/im4NMO Sin embargo, la solución de vector de estructuras tiene un impacto de rendimiento más consistente: ideone.com/b0VWSN
stefan