c++ - tipos - que es cache en informatica

Estructura de datos para O(registro N), búsqueda y actualización, considerando un pequeño caché L1

Question

Actualmente estoy trabajando en un proyecto de dispositivo integrado donde tengo problemas de rendimiento. El perfil ha localizado una operación O (N) que me gustaría eliminar.

Básicamente tengo dos arreglos int A[N] y short B[N] . Las entradas en A son únicas y están ordenadas por restricciones externas. La operación más común es verificar si un valor particular a aparece en A[] . Menos frecuentemente, pero aún común es un cambio a un elemento de A[] . El nuevo valor no está relacionado con el valor anterior.

Dado que la operación más común es el hallazgo, es donde entra B[] . Es una matriz ordenada de índices en A[] , de manera que A[B[i]] < A[B[j]] si y solo si i<j . Eso significa que puedo encontrar valores en A utilizando una búsqueda binaria.

Por supuesto, cuando actualizo A[k] , tengo que encontrar k en B y moverlo a una nueva posición, para mantener el orden de búsqueda. Como conozco los valores antiguos y nuevos de A[k] , eso es solo un memmove() de un subconjunto de B[] entre la posición antigua y nueva de k . Esta es la operación O (N) que necesito arreglar; ya que los valores antiguos y nuevos de A[k] son esencialmente aleatorios, me estoy moviendo en promedio alrededor de N / 2 elementos N / 3.

Busqué en std::make_heap usando [](int i, int j) { return A[i] < A[j]; } [](int i, int j) { return A[i] < A[j]; } como el predicado. En ese caso, puedo hacer que B[0] apunte fácilmente al elemento más pequeño de A , y la actualización de B es ahora una operación de reequilibrio O (log N) barata. Sin embargo, generalmente no necesito el valor más pequeño de A, necesito encontrar si algún valor dado está presente. Y eso es ahora una búsqueda O (N log N) en B (La mitad de mis elementos N están en el registro de profundidad N del montón, un cuarto en (registro N) -1, etc.), lo cual no es una mejora sobre una búsqueda O (N) estúpida directamente en A

Teniendo en cuenta que std::set tiene O (registro N) inserción y búsqueda, diría que debería ser posible obtener el mismo rendimiento aquí para actualizar y encontrar. Pero, ¿cómo hago eso? ¿Necesito otra orden para B ? ¿Un tipo diferente?

B es actualmente una short [N] porque A y B juntas son aproximadamente del tamaño de mi caché de CPU, y mi memoria principal es mucho más lenta. Pasar de 6 * N a 8 * N bytes no sería bueno, pero sería aceptable si mi búsqueda y actualización van a O (registro N) ambas.

Answer 1

Si las únicas operaciones son (1) verificar si el valor ''a'' pertenece a A y (2) actualizar los valores en A, ¿por qué no usa una tabla hash en lugar de la matriz ordenada B? Especialmente si A no aumenta o disminuye su tamaño y los valores solo cambian, esta sería una solución mucho mejor. Una tabla hash no requiere significativamente más memoria que una matriz. (Alternativamente, B debería cambiarse no a un montón, sino a un árbol de búsqueda binario, que podría ser auto-equilibrado, por ejemplo, un árbol de distribución o un árbol rojo-negro. Sin embargo, los árboles requieren memoria adicional debido a la izquierda y la derecha punteros.)

Una solución práctica que aumenta el uso de la memoria de 6N a 8N bytes es apuntar a una tabla hash rellena exactamente al 50%, es decir, usar una tabla hash que consiste en una matriz de cortos 2N. Recomendaría implementar el mecanismo de Cuckoo Hashing (ver http://en.wikipedia.org/wiki/Cuckoo_hashing ). Siga leyendo el artículo y encontrará que puede obtener factores de carga superiores al 50% (es decir, reducir el consumo de memoria de 8N a, digamos, 7N) usando más funciones hash. " Usar solo tres funciones hash aumenta la carga al 91% " .

De Wikipedia:

Un estudio de Zukowski et al. ha demostrado que el hash cuco es mucho más rápido que el hashing encadenado para las pequeñas tablas hash residentes en caché en los procesadores modernos. Kenneth Ross ha mostrado que las versiones de hash de cuco (variantes que usan cubos que contienen más de una clave) son más rápidas que los métodos convencionales, también para tablas hash grandes, cuando la utilización del espacio es alta. El rendimiento de la tabla hash de cuco en cubos fue investigado más a fondo por Askitis, con su rendimiento comparado con esquemas de hashing alternativos.

Answer 2

Ya que tienes un N limitado, ¿no puedes usar std::set<short, cmp, pool_allocator> B con el pool_allocator de Boost ?

Answer 3

std::set usualmente proporciona la inserción y eliminación O (log (n)) utilizando un árbol de búsqueda binario. Desafortunadamente, esto utiliza el espacio 3 * N para la mayoría de las implementaciones basadas en punteros. Suponiendo datos de tamaño de palabra, 1 para los datos, 2 para los punteros a los elementos secundarios izquierdo y derecho en cada nodo.

Si tiene alguna N constante y puede garantizar que ceil(log2(N)) es menor que la mitad del tamaño de palabra, puede usar una matriz de longitud fija de nodos de árbol cada tamaño 2 * N. Use 1 para los datos, 1 para los índices de los dos nodos secundarios, almacenados como la mitad superior e inferior de la palabra. Si esto le permitiría usar un árbol de búsqueda binaria de equilibrio automático de alguna manera depende de su N y el tamaño de la palabra. Para un sistema de 16 bits solo obtienes N = 256, pero para 32 su 65k.