Si tengo un árbol como el siguiente
struct tree_t { //data tree_t *left; tree_t *right; };y quiero comenzar a asignar memoria para las hojas, ¿hay alguna manera de garantizar que cuando atraviese el árbol, las hojas se almacenen en caché? Si estuviera usando malloc, creo que las hojas estarían esparcidas por el montón y habría un error de caché cada vez que intentara acceder a una.
Otros dieron la respuesta adecuada, un grupo de tamaño fijo ( https://en.wikipedia.org/wiki/Memory_pool ), pero hay algunas advertencias adicionales que merecen una explicación más detallada. Todavía es posible o incluso probable que las hojas asignadas mediante un grupo de memoria tengan una tasa de aciertos de caché baja. Los bloques de 8*n tree_t alineados en límites de 64 bytes son ideales, aunque no hay ningún beneficio por encima de n == 1024.
Como nota al margen, mire las matrices Judy, que son una estructura de datos tipo árbol optimizada para caché ( https://en.wikipedia.org/wiki/Judy_array ).
Es útil revisar (brevemente) cómo funciona el caché. Los cachés se dividen en conjuntos de líneas de tamaño fijo. Normalmente, el tamaño de la línea es de 64 bytes en L1; Intel y AMD han usado cachés L1 de 64 bytes durante 15 años, y los procesadores ARM modernos como el A15 también usan líneas de 64 bytes. La asociatividad determina cuántas líneas corresponden a un conjunto. Cuando los datos se introducen en la memoria caché, alguna función convierte la dirección en un conjunto. Los datos pueden almacenarse en cualquiera de las líneas del conjunto. Por ejemplo, en una memoria caché asociativa de conjunto bidireccional, cualquier dirección dada se puede almacenar en una de dos posibles líneas de memoria caché.
Maximizar la capacidad de caché implica reducir las capturas de línea de caché:
1. Organizar los datos en fragmentos del tamaño de una línea de caché.
2. Alineación de fragmentos en un límite de línea de caché.
3. Asignar fragmentos en direcciones que se asignan a diferentes conjuntos de caché.
4. Almacenar datos con localidad temporal (es decir, accedidos aproximadamente al mismo tiempo) en la misma línea de caché.
5. Reducir el tamaño de los datos, si es posible, para aumentar la densidad.
Si no hace (1), entonces las recuperaciones traerán datos cercanos, probablemente inútiles, reduciendo la cantidad de espacio para los datos que le interesan. Si no hace (2), es probable que sus objetos se extiendan a lo largo de las líneas de caché, lo que requerirá el doble de búsquedas. Si no hace (3), entonces es probable que algunos conjuntos de caché se infrautilicen, con un efecto similar al de (1). Si no lo hace (4), aunque esté maximizando la utilización de la memoria caché, la mayoría de los datos obtenidos no son útiles cuando se obtienen, y es probable que la línea se desaloje antes de que los datos sean útiles. (5) aumenta la cantidad de objetos que caben en el caché al empaquetarlos en menos espacio. Por ejemplo, si puede garantizar que tendrá menos de 2^32 hojas, podría almacenar un índice uint32_t en una matriz tree_t[] en lugar de punteros, lo que es una mejora del 100 % en las plataformas de 64 bits.
Nota: malloc() normalmente devuelve bloques alineados de 8 o 16 bytes, que no son adecuados; use posix_memalign() en GCC o _aligned_malloc() en MSVC.
En su caso, está atravesando un árbol, presumiblemente un recorrido en orden. A menos que su conjunto de datos encaje en el caché, es probable que las hojas se distribuyan de manera uniforme y, por lo tanto, es poco probable que tengan una localidad temporal con nodos en la misma línea de caché. En ese caso, lo mejor que puede hacer es asegurarse de que sus objetos no se extiendan entre las líneas de caché asignando bloques del tamaño de línea de caché y alineados con línea de caché.
Elegí bloques de 8*n tree_t con la suposición conservadora de una línea de caché de 64 bytes y punteros de 4 bytes, lo que da como resultado un tree_t de 8 bytes y 64 / 8 = 8 tree_t/line. El límite superior de n == 1024 se debe a una CPU x86 particular (que se me escapa en este momento) que ignora el bit 18 de la dirección con el fin de elegir un conjunto.
Puede ser posible en una plataforma seleccionada mejorar los aciertos de caché, pero, por supuesto, hay poco para garantizar el éxito constante de una ejecución a otra.
Pero probemos algunas ideas:
Cree tree_alloc() y tree_free() que asignen/administren múltiples struct tree_t en un grupo, digamos 256 en la primera llamada y luego las distribuya para las próximas 255 asignaciones. Esto complicará las llamadas aleatorias de asignación/libre, pero si el árbol es grande y su crecimiento/reducción uniforme, puede valer la pena el esfuerzo.
Haz tree_t pequeño. Hacer de los datos un puntero.
struct tree_t { data_T *data tree_t *left; tree_t *right; };¡Ups! GTG - hará este wiki
malloc no garantiza dónde se asignará la memoria. Si desea que los datos se coloquen para aprovechar la localidad de caché, una alternativa simple es asignar una matriz de la estructura y luego asignar desde esa matriz, es decir, el conjunto de objetos. Esto es básicamente como escribir su propio asignador de memoria, excepto que se simplifica enormemente ya que todos los elementos tienen el mismo tamaño. También simplificaría enormemente las cosas si supiera la cantidad máxima de elementos que necesitará para no tener que agregar la capacidad de aumentar el tamaño de su "grupo de memoria". También tendrá que considerar la seguridad de subprocesos si diferentes subprocesos acceden a sus funciones de asignación/liberación. Hay muchas otras cosas a considerar, estas son solo algunas.
Nota: como han dicho otros en los comentarios, la optimización prematura generalmente no vale la pena o es peor contraproducente, pero si quieres probar, esta es una forma.
Aquí hay un enlace útil que puede encontrar con respecto a los grupos de objetos