¿Cómo evitar "spaghetti puntero del montón" en gráficos dinámicos?
algorithm data-structures (4)
El problema genérico
Supongamos que está codificando un sistema que consiste en un gráfico, más reglas de reescritura de gráficos que se pueden activar dependiendo de la configuración de los nodos vecinos. Es decir, tiene un gráfico dinámico que crece / se reduce de forma impredecible durante el tiempo de ejecución. Si usa ingenuamente malloc , los nuevos nodos se asignarán en posiciones aleatorias en la memoria; después de suficiente tiempo, su montón será un spaghetti de puntero, que le dará una terrible eficacia de caché. ¿Hay alguna técnica ligera e incremental para hacer que los nodos que se unen permanezcan juntos en la memoria ?
Lo que probé
Lo único que se me ocurre es incrustar los nodos en un espacio cartesiano con alguna simulación elástica física que rechaza / atrae nodos. Eso mantendría unidos los nodos conectados, pero parece tonto y supongo que la sobrecarga de la simulación sería más grande que la aceleración de la eficiencia del caché.
El ejemplo sólido
This es el sistema que estoy tratando de implementar. This es un breve fragmento del código que estoy tratando de optimizar en C. This repositorio es una implementación prototípica y operativa en JS, con una terrible eficacia de caché (y del lenguaje mismo). Este video muestra el sistema en acción gráficamente.
Esto se puede ver como un problema de particionamiento de gráficos , donde intenta agrupar nodos de gráficos vinculados en el mismo bloque de memoria. METIS es un buen algoritmo de partición de gráficos que probablemente no sea apropiado para su caso de uso porque requiere operaciones globales en todo el gráfico, sin embargo, dos algoritmos de partición de gráficos distribuidos que pueden ser modificados para su caso de uso son DIDIC y Ja-Be-Ja : el primero intenta minimizar el número de bordes que cruzan particiones sin importar el tamaño de la partición, mientras que el segundo intenta crear particiones de igual tamaño. Ambos algoritmos solo requieren conocimiento local del gráfico para agrupar cada nodo, por lo que si tiene ciclos de repuesto, puede usarlos para reequilibrar gradualmente el gráfico. Fennel es un algoritmo relacionado que opera en gráficos de transmisión, de modo que, por ejemplo, puede usar Fennel o un algoritmo similar al asignar inicialmente un nodo de gráfico, y luego usar DIDIC / Ja-Be-Ja al reequilibrar el gráfico.
Lo que estás buscando resolver es el Problema del Arreglo Lineal . Las soluciones perfectas se consideran NP-duras, pero existen algunas buenas aproximaciones. Aquí hay un paper que debería ser un buen lugar para comenzar.
Puede ver esto en términos de recolección de basura de medio espacio. Esto no es difícil de implementar (lo he hecho por un intérprete), especialmente porque solo lo está haciendo para estructuras de nodo de tamaño fijo. Asignar desde un bloque grande (llamado medio espacio) de memoria. Cuando se llena demasiado o se fragmenta, deténgase y copie todo a la otra (que también puede agrandar). El truco es actualizar todos los punteros. Para esto hay un algoritmo muy elegante y eficiente llamado copia escaneada. Hay una buena discusión sobre esto en Cornell . Básicamente, cruza primero el ancho del gráfico, copiando sobre la marcha, sin más espacio que el que está copiando. Una buena propiedad del algoritmo es que los primeros niveles de anchura terminan adyacentes después de cada copia. Si este es un nivel de localidad suficientemente bueno, lo obtendrás de manera muy eficiente con este método.
Si realmente está preocupado por el diseño de la memoria, podría valer la pena administrarlo usted mismo.
Puede malloc un gran bloque de memoria al inicio, luego asigna espacio desde ese bloque. Necesitará una estructura separada para realizar un seguimiento de lo que tiene y lo que no ha sido asignado. Si sabe que todas las estructuras asignadas tienen un tamaño determinado que puede simplificar la administración de espacio asignado / libre, es decir, una matriz de índices, de lo contrario, podría usar una lista de punteros enlazados en el espacio libre. Dado que es probable que esté asignando estructuras de a una por vez, probablemente no tenga que preocuparse por hacer un seguimiento del bloque contiguo más pequeño y / o más grande de espacio libre.
Una cosa de la que deberá tener cuidado es la alineación. De nuevo, si siempre va a asignar memoria en múltiplos del tamaño de una única estructura, eso facilita las cosas, de lo contrario probablemente sea una buena idea asegurarse de que todas las asignaciones comiencen en un límite de 4 bytes, es decir, la diferencia entre la dirección que asignar y la dirección de inicio recibida de malloc es un múltiplo de 4.
Puede pasar parámetros adicionales a sus funciones de asignación personalizadas para dar pistas sobre dónde debe colocarse el bloque, como la dirección de uno o más nodos cercanos.