C++, formas de comparar las mejoras en la localidad de caché?

Question

Tengo una implementación de una clase X, que tiene dos punteros a dos piezas de información. He escrito una nueva implementación, clase Y, que tiene solo un puntero a una estructura que contiene las dos piezas de información juntas como miembros adyacentes. Los métodos de X e Y generalmente solo necesitan manipular una de las piezas de información, pero proporcionan un método get() que devuelve un puntero a la segunda pieza (en este caso, la clase X simplemente devuelve su puntero a esa pieza y la clase Y devuelve la dirección del segundo miembro de la estructura). En el uso normal, las llamadas a los métodos de X e Y se intercalarán con llamadas a get() y haciendo el trabajo en esa segunda pieza devuelta.

Espero que en situaciones de la vida real se produzca una mejora en el rendimiento, ahora que las dos piezas de información están una junto a la otra en la memoria en la implementación de la clase Y (porque son miembros adyacentes de una estructura), pero No veo ninguna diferencia en los puntos de referencia que he escrito (intercalando llamadas a los métodos de X e Y con el trabajo en sus segundas piezas en grandes loops). Sospecho que esto es porque todo encaja en el caché en cualquier caso en mis pruebas. No quiero probar esto en mi aplicación real todavía porque la semántica de X e Y difieren en otras formas sutiles no relacionadas con esta optimización y portar la aplicación que lo usa será un trabajo, y se supone que estos puntos de referencia ayudan a justificarlo. trabajar en primer lugar.

Cuál es la mejor manera de observar la diferencia en el rendimiento debido a una mejor localidad caché? Si hago un montón de trabajo ficticio en una matriz igual al tamaño de la caché entre llamadas ¿es suficiente? ¿O quiero trabajar en una matriz un poco menor que el tamaño de la memoria caché, para que el trabajo en mis instancias de mi clase haga que las cosas entren y salgan de la memoria caché? No estoy seguro de cómo codificar algo que sea robusto contra las optimizaciones del compilador y los diferentes tamaños de caché.

Answer 1

Si estoy entendiendo su situación correctamente (y corríjanme si no), entonces son seis de una, o media docena de la otra.

En la clase X, es necesario un puntero de búsqueda, ya sea para pieza de información. En la clase Y, necesitas una búsqueda para el primero y dos (obtener el primero y luego compensar) para el segundo. Eso es sacrificar la "localidad" por otro acceso a la memoria. Los compiladores todavía son, lamentablemente, muy buenos para perder el tiempo del bus buscando palabras en la memoria RAM.

Si es posible, obtendrá los mejores resultados al mantener las dos piezas de información de destino directamente dentro de la clase en cuestión (es decir, cada miembro de la clase), en lugar de utilizar esos punteros para la indirección innecesaria. No ver ningún código, eso es todo lo que puedo decir.

En cualquier caso, usted obtendrá un montón más rendimiento de estudiar la complejidad algorítmica de la aplicación de lo que nunca lo hará con micro-optimización de dos variables en una definición de clase. También es una buena idea utilizar una herramienta de creación de perfiles para ver (objetivamente) dónde están los cuellos de botella (gprof es común en los sistemas * nix). ¿Hay alguna razón clara por la que esté buscando aumentar el almacenamiento en caché de la localidad específicamente?

Answer 2

Si se encuentra en Linux, entonces el uso de Cachegrind junto con KCacheGrind podría proporcionar más información sobre cómo se está comportando su caché.

Answer 3

podría diseñar un punto de referencia concreto para reventar la caché. Por ejemplo, asigne los bloques de datos apuntados de modo que todos estén garantizados en diferentes líneas de caché (por ejemplo, mediante el uso de un asignador de memoria personalizado que rellene las asignaciones hasta al menos unos cientos de bytes). Luego itere repetidamente sobre una cantidad de objetos demasiado grande para caber todo incluso en la caché L2 (muy dependiente de la plataforma, ya que depende del número de líneas en caché, pero 1 millón cubriría la mayoría de arquitecturas y solo requeriría unos pocos cientos de megabytes de RAM total).

Esto le dará un límite superior en la ganancia de rendimiento obtenida por el cambio de X a Y. Pero lo hace degradando el rendimiento de X a un nivel inferior al probable uso en el mundo real. Y para probar su caso necesita una estimación de límite inferior, no una estimación de límite superior. Así que no estoy seguro de que logre mucho, a menos que descubra que incluso este peor caso aún no marca una diferencia significativa y no necesita preocuparse por la optimización.

Aunque no apunte al peor rendimiento teórico de X, cualquier punto de referencia diseñado para exceder el caché simplemente está eligiendo un punto arbitrario de mal rendimiento de X, y está buscando si Y es mejor. No está lejos de simular el punto de referencia para que Y se vea bien. Realmente no importa cómo se desempeña su código en los puntos de referencia dudosos, excepto tal vez con fines de comercialización mentiras literatura.

La mejor manera de observar la diferencia en el rendimiento en el mundo real es medir un cliente del mundo real de su clase. Usted dice que "la semántica de X e Y difiere en otras formas sutiles no relacionadas con esta optimización", en cuyo caso solo puedo recomendarle que escriba una clase Z que difiera de X solo con respecto a esta optimización, y use eso en tu aplicación como la comparación.

Una vez que las pruebas intentan representar el peor uso realista, entonces, si no observa ninguna diferencia en el rendimiento, probablemente no se obtenga ninguna ganancia de rendimiento.

Dicho todo esto, si tiene sentido lógico (es decir, no hace que el código sea más sorprendente), entonces recomendaría minimizar el número de asignaciones de heap en C++ simplemente como una regla práctica. No tiende a empeorar la velocidad o el uso total de la memoria, y tiende a simplificar el manejo de los recursos. Una regla empírica no justifica una reescritura del código de trabajo, por supuesto.