c++ - ¿Cuál es más amigable con el caché?

opengl caching

Question

Estoy tratando de tener un buen control sobre el diseño orientado a los datos y cómo programar mejor con el caché en mente. Básicamente, hay dos escenarios en los que no puedo decidir cuál es mejor y por qué: ¿es mejor tener un vector de objetos o varios vectores con los datos atómicos de los objetos?

A) Vector del ejemplo de objetos

struct A
{
    GLsizei mIndices;
    GLuint mVBO;
    GLuint mIndexBuffer;
    GLuint mVAO;

    size_t vertexDataSize;
    size_t normalDataSize;
};

std::vector<A> gMeshes;

for_each(gMeshes as mesh)
{
    glBindVertexArray(mesh.mVAO);
    glDrawElements(GL_TRIANGLES, mesh.mIndices, GL_UNSIGNED_INT, 0);
    glBindVertexArray(0);

    ....
}

B) Vectores con los datos atómicos

std::vector<GLsizei> gIndices;
std::vector<GLuint> gVBOs;
std::vector<GLuint> gIndexBuffers;
std::vector<GLuint> gVAOs;
std::vector<size_t> gVertexDataSizes;
std::vector<size_t> gNormalDataSizes;

size_t numMeshes = ...;

for (index = 0; index++; index < numMeshes)
{
    glBindVertexArray(gVAOs[index]);
    glDrawElements(GL_TRIANGLES, gIndices[index], GL_UNSIGNED_INT, 0);
    glBindVertexArray(0);

    ....
}

¿Cuál es más eficiente con la memoria y compatible con la caché, lo que resulta en menos errores de caché y un mejor rendimiento, y por qué?

Answer 1

Entiendo que esto se basa en parte en la opinión, y también que podría ser un caso de optimización prematura, pero su primera opción definitivamente tiene la mejor estética. Es un vector contra seis, no hay competencia en mi opinión.

Para el rendimiento de la memoria caché, debería ser mejor. Esto se debe a que la alternativa requiere acceso a dos vectores diferentes, que divide el acceso a la memoria cada vez que renderiza una malla.

Con el enfoque de estructura, la malla es esencialmente un objeto independiente y correctamente no implica ninguna relación con otras mallas. Al dibujar, solo tiene acceso a esa malla, y al renderizar todas las mallas, lo hace de a una por vez de una manera compatible con la caché. Sí, comerás el caché más rápidamente porque los elementos del vector son más grandes, pero no estarás impugnando.

También puede encontrar otros beneficios más adelante al usar esta representación. es decir, si desea almacenar datos adicionales sobre una malla. Agregar datos adicionales en más vectores agilizará rápidamente su código y aumentará el riesgo de cometer errores absurdos, mientras que es trivial realizar cambios en la estructura.

Answer 2

Recomiendo perfilar con perf o oprofile y publicar sus resultados aquí (suponiendo que esté ejecutando linux), incluida la cantidad de elementos que iteraba, el número de iteraciones en total y el hardware que probó.

Si tuviera que adivinar (y esto es solo una suposición), sospecho que el primer enfoque podría ser más rápido debido a la localidad de datos dentro de cada estructura, y con suerte el sistema operativo / hardware puede precargar elementos adicionales para usted. Pero, una vez más, esto dependerá del tamaño de la memoria caché, el tamaño de la línea de caché y otros aspectos.

Definir "mejor" también es interesante. ¿Está buscando tiempo global para procesar N elementos, baja varianza en cada muestra, fallas mínimas en el caché (que serán influenciadas por otros procesos que se ejecutan en su sistema), etc.

No olvide que con los vectores STL, también está a merced del asignador ... por ejemplo, puede decidir en cualquier momento reasignar la matriz, lo que invalidará su caché. ¡Otro factor para intentar aislar si puedes!

Answer 3

Con algunas variaciones según el nivel de caché del que se trate, la caché funciona de la siguiente manera:

• si los datos ya están en caché, es rápido para acceder
• si los datos no están en caché, incurrirá en un costo, pero una línea de caché completa (o página, si hablamos de RAM frente a archivo de intercambio en lugar de caché frente a RAM) se lleva a caché, por lo que accederá a la dirección perdida No se pierda.
• si tiene suerte, el subsistema de memoria detectará el acceso secuencial y la recuperación previa de los datos que cree que va a necesitar.

Tan ingenuamente las preguntas para hacer son:

1. ¿Cuántas fallas de caché ocurren? - B gana, porque en A se capturan algunos datos no utilizados por registro, mientras que en B se obtiene nada más que un pequeño error de redondeo al final de la iteración. Entonces, para visitar todos los datos necesarios, B obtiene menos líneas de caché, asumiendo un número significativo de registros. Si el número de registros es insignificante, entonces el rendimiento del caché puede tener poco o nada que ver con el rendimiento de su código, porque un programa que usa una cantidad de datos suficientemente pequeña encontrará que todo está en caché todo el tiempo.
2. es el acceso secuencial? - sí en ambos casos, aunque esto podría ser más difícil de detectar en el caso B porque hay dos secuencias intercaladas en lugar de solo una.

Por lo tanto, esperaría que B sea más rápido para este código . Sin embargo:

• si este es el único acceso a los datos, entonces podría acelerar A eliminando la mayoría de los miembros de datos de la struct . Entonces haz eso. Presumiblemente, de hecho, no es el único acceso a los datos en su programa, y ​​los otros accesos pueden afectar el rendimiento de dos maneras: el tiempo que realmente toman y si completan el caché con los datos que necesita.
• lo que espero y lo que realmente sucede son cosas diferentes, y no tiene mucho sentido confiar en la especulación si tienes la capacidad de probarlo. En el mejor de los casos, el acceso secuencial significa que no hay errores de caché en ninguno de los códigos. El rendimiento de las pruebas no requiere una herramienta especial (aunque pueden hacerlo más fácil), solo un reloj con segundero. En caso de apuro, forme un péndulo desde el cargador de su teléfono.
• hay algunas complicaciones que ignoré Dependiendo del hardware, si tienes mala suerte con B, entonces en el nivel de caché más bajo podrías encontrar que los accesos a un vector están desalojando los accesos al otro vector, porque la memoria correspondiente simplemente usa la misma ubicación en el caché. Esto causaría dos fallas de caché por registro . Esto solo ocurrirá en lo que se llama "caché de mapeo directo". La "caché bidireccional" o superior salvaría el día, al permitir que coexistan trozos de ambos vectores, incluso si la ubicación de su primera preferencia en la memoria caché es la misma. No creo que el hardware para PC generalmente use caché de mapeo directo, pero no estoy seguro y no sé mucho sobre las GPU.

Answer 4

Depende de tus patrones de acceso. Su primera versión es AoS (matriz de estructuras) , la segunda es SoA (estructura de matrices) .

SoA tiende a usar menos memoria (a menos que almacene tan pocos elementos que la sobrecarga de los arreglos no sea realmente trivial) si hay algún tipo de relleno de estructura que normalmente obtendría en la representación de AoS. También tiende a ser un PITA mucho más grande para codificar ya que tiene que mantener / sincronizar matrices paralelas.

AoS tiende a sobresalir para el acceso aleatorio . Como ejemplo, para simplificar, digamos que cada elemento encaja en una línea de caché y está alineado correctamente (tamaño de 64 bytes y alineación, por ejemplo). En ese caso, si está accediendo aleatoriamente a un nth elemento, obtendrá todos los datos relevantes para el elemento en una sola línea de caché. Si utilizó un SoA y dispersó esos campos en matrices separadas, tendría que cargar memoria en múltiples líneas de caché solo para cargar los datos para ese elemento. Y debido a que estamos accediendo a los datos en un patrón aleatorio, no nos beneficiamos mucho de la localidad espacial ya que el próximo elemento al que vamos a acceder podría estar en algún otro lugar en la memoria.

Sin embargo, SoA tiende a sobresalir para el acceso secuencial, principalmente porque a menudo hay menos datos para cargar en la memoria caché de la CPU en primer lugar para todo el ciclo secuencial porque excluye el relleno de la estructura y los campos fríos . Por campos fríos, quiero decir campos a los que no necesita acceder en un bucle secuencial particular. Por ejemplo, un sistema de física podría no interesarse por los campos de partículas relacionados con la apariencia de la partícula para el usuario, como el color y el mango de un sprite. Eso es información irrelevante. Solo se preocupa por las posiciones de las partículas. El SoA le permite evitar cargar esos datos irrelevantes en las líneas de caché. Le permite cargar la mayor cantidad de datos relevantes en una línea de caché a la vez, por lo que termina con menos errores de caché obligatorios (así como fallas de página para datos suficientemente grandes) con el SoA.

Eso también solo cubre los patrones de acceso a la memoria. Con representantes de SoA, también tiende a ser capaz de escribir instrucciones SIMD más eficientes y más simples. Pero nuevamente es principalmente adecuado para el acceso secuencial .

También puedes mezclar los dos conceptos. Puede usar un AoS para campos calientes a los que se accede con frecuencia juntos en patrones de acceso aleatorio, luego izar los campos fríos y almacenarlos en paralelo.