¿Son rentables las matrices no contiguas?

En C #, cuando un usuario crea List<byte>y le agrega bytes, existe la posibilidad de que se quede sin espacio y necesite asignar más espacio. Asigna el doble (o algún otro multiplicador) del tamaño de la matriz anterior, copia los bytes y descarta la referencia a la matriz anterior. Sé que la lista crece exponencialmente porque cada asignación es costosa y esto lo limita a las O(log n)asignaciones, donde solo agregar 10elementos adicionales cada vez daría como resultado O(n)asignaciones.

Sin embargo, para tamaños de matriz grandes puede haber mucho espacio desperdiciado, tal vez casi la mitad de la matriz. Para reducir la memoria, escribí una clase similar NonContiguousArrayListque utiliza List<byte>como almacén de respaldo si había menos de 4 MB en la lista, y luego asignaría conjuntos de bytes de 4 MB adicionales a medida que NonContiguousArrayListcreciera.

A diferencia de List<byte>estos arreglos, no son contiguos, por lo que no hay copia de datos, solo una asignación adicional de 4M. Cuando se busca un elemento, el índice se divide por 4M para obtener el índice de la matriz que contiene el elemento, luego el módulo 4M para obtener el índice dentro de la matriz.

¿Puedes señalar problemas con este enfoque? Aquí está mi lista:

• Las matrices no contiguas no tienen localidad de caché, lo que resulta en un mal rendimiento. Sin embargo, con un tamaño de bloque de 4M, parece que habría suficiente localidad para un buen almacenamiento en caché.
• Acceder a un elemento no es tan simple, hay un nivel adicional de indirección. ¿Se optimizaría esto? ¿Causaría problemas de caché?
• Dado que hay un crecimiento lineal después de alcanzar el límite de 4M, podría tener muchas más asignaciones de las que tendría normalmente (por ejemplo, un máximo de 250 asignaciones por 1 GB de memoria). No se copia memoria adicional después de 4M, sin embargo, no estoy seguro de si las asignaciones adicionales son más caras que copiar grandes porciones de memoria.

En las escalas que mencionó, las preocupaciones son totalmente diferentes de las que ha mencionado.

Localidad de caché

• Hay dos conceptos relacionados:
  1. Localidad, la reutilización de datos en la misma línea de caché (localidad espacial) que se visitó recientemente (localidad temporal)
  2. Búsqueda previa de caché automática (transmisión).
• En las escalas que mencionó (cientos de MB a gigabytes, en fragmentos de 4 MB), los dos factores tienen más que ver con el patrón de acceso al elemento de datos que el diseño de la memoria.
• Mi predicción (desorientada) es que estadísticamente puede no haber mucha diferencia de rendimiento que una asignación de memoria contigua gigante. Sin ganancia, sin pérdida.

Patrón de acceso al elemento de datos

• Este artículo ilustra visualmente cómo los patrones de acceso a la memoria afectarán el rendimiento.
• En resumen, solo tenga en cuenta que si su algoritmo ya está bloqueado por el ancho de banda de la memoria, la única forma de mejorar el rendimiento es hacer un trabajo más útil con los datos que ya están cargados en la memoria caché.
• En otras palabras, incluso si YourList[k]y YourList[k+1]tienen una alta probabilidad de ser consecutiva (uno de cada cuatro millones de posibilidades de ser no), este hecho no ayuda el rendimiento si accede a su lista completamente al azar, o en grandes zancadas por ejemplo impredecibleswhile { index += random.Next(1024); DoStuff(YourList[index]); }

Interacción con el sistema GC.

• En mi opinión, aquí es donde debes concentrarte más.
• Como mínimo, comprenda cómo interactuará su diseño con:
  • Recolección generacional de basura ,
  • Montón de objetos grandes
• No conozco estos temas, así que dejaré que otros contribuyan.

Gastos generales de cálculo de desplazamiento de dirección

• El código C # típico ya está haciendo muchos cálculos de desplazamiento de dirección, por lo que la sobrecarga adicional de su esquema no sería peor que el código C # típico que funciona en una sola matriz.
  • Recuerde que el código C # también realiza la comprobación del rango de matriz; y este hecho no impide que C # alcance un rendimiento de procesamiento de matriz comparable con código C ++.
  • La razón es que el rendimiento se ve afectado principalmente por el ancho de banda de la memoria.
  • El truco para maximizar la utilidad del ancho de banda de la memoria es usar las instrucciones SIMD para las operaciones de lectura / escritura de la memoria. Ni C # típico ni C ++ típico hace esto; tienes que recurrir a bibliotecas o complementos de idiomas.

Para ilustrar por qué:

• Hacer el cálculo de la dirección
• (En el caso de OP, cargue la dirección base del fragmento (que ya está en la memoria caché) y luego haga más cálculos de dirección)
• Leer desde / escribir en la dirección del elemento

El último paso todavía toma la mayor parte del tiempo.

Sugerencia personal

• Puede proporcionar una CopyRangefunción, que se comportaría como una Array.Copyfunción pero funcionaría entre dos instancias de su NonContiguousByteArray, o entre una instancia y otra normal byte[]. estas funciones pueden hacer uso del código SIMD (C ++ o C #) para maximizar la utilización del ancho de banda de la memoria, y luego su código C # puede operar en el rango copiado sin la sobrecarga de múltiples desreferencias o cálculos de direcciones.

Problemas de usabilidad e interoperabilidad

• Aparentemente, no puede usar esto NonContiguousByteArraycon ninguna biblioteca de C #, C ++ o en un idioma extranjero que espere matrices de bytes contiguas o matrices de bytes que se puedan anclar.
• Sin embargo, si escribe su propia biblioteca de aceleración C ++ (con P / Invoke o C ++ / CLI), puede pasar una lista de direcciones base de varios bloques de 4MB en el código subyacente.
  • Por ejemplo, si necesita dar acceso a elementos que comienzan (3 * 1024 * 1024)y terminan en (5 * 1024 * 1024 - 1), esto significa que el acceso abarcará chunk[0]y chunk[1]. Luego puede construir una matriz (tamaño 2) de matrices de bytes (tamaño 4M), anclar estas direcciones de fragmentos y pasarlas al código subyacente.
• Otra preocupación de usabilidad es que no podrá implementar la IList<byte>interfaz de manera eficiente: Inserty Removetomará demasiado tiempo procesarla porque requerirá O(N)tiempo.
  • De hecho, parece que no puede implementar nada más que IEnumerable<byte>, es decir, puede escanearse secuencialmente y eso es todo.

Vale la pena señalar que el C ++ ya tiene una estructura equivalente de Standard, std::deque. Actualmente, se recomienda como la opción predeterminada para necesitar una secuencia de cosas de acceso aleatorio.

La realidad es que la memoria contigua es casi completamente innecesaria una vez que los datos superan un cierto tamaño: una línea de caché tiene solo 64 bytes y un tamaño de página de solo 4-8 KB (valores típicos actualmente). Una vez que comience a hablar sobre unos pocos MB, realmente se va por la ventana como una preocupación. Lo mismo se aplica al costo de asignación. El precio de procesar todos esos datos, incluso solo leerlos, eclipsa el precio de las asignaciones de todos modos.

La única otra razón para preocuparse es la interfaz con las API de C. Pero de todos modos no puede obtener un puntero al búfer de una Lista, por lo que no hay preocupación aquí.

Cuando se asignan fragmentos de memoria en diferentes momentos, como en los subconjuntos dentro de su estructura de datos, pueden ubicarse lejos uno del otro en la memoria. Si esto es un problema o no depende de la CPU y es muy difícil de predecir por más tiempo. Tienes que probarlo.

Esta es una excelente idea, y es una que he usado en el pasado. Por supuesto, solo debe usar potencias de dos para los tamaños de su subarreglo y desplazamiento de bits para la división (puede ocurrir como parte de la optimización). Encontré este tipo de estructura un poco más lento, ya que los compiladores pueden optimizar una sola indirección de matriz más fácilmente. Tienes que probar, ya que este tipo de optimizaciones cambian todo el tiempo.

La principal ventaja es que puede correr más cerca del límite superior de memoria en su sistema, siempre que use este tipo de estructuras de manera consistente. Siempre que amplíe sus estructuras de datos y no produzca basura, evitará recolecciones de basura adicionales que se producirían para una Lista ordinaria. Para una lista gigante, podría hacer una gran diferencia: la diferencia entre continuar ejecutándose y quedarse sin memoria.

Las asignaciones adicionales son un problema solo si sus fragmentos de subarreglos son pequeños, porque hay una sobrecarga de memoria en cada asignación de matriz.

He creado estructuras similares para diccionarios (tablas hash). El Diccionario provisto por el framework .net tiene el mismo problema que List. Los diccionarios son más difíciles en el sentido de que también debes evitar repetir.

Con un tamaño de bloque de 4M, incluso un solo bloque no garantiza que sea contiguo en la memoria física; es más grande que un tamaño de página de VM típico. Localidad no significativa a esa escala.

Tendrá que preocuparse por la fragmentación del montón: si las asignaciones ocurren de manera que sus bloques no sean contiguos en el montón, entonces, cuando son reclamados por el GC, terminará con un montón que puede estar demasiado fragmentado para adaptarse a un asignación posterior Esa suele ser una situación peor porque las fallas ocurrirán en lugares no relacionados y posiblemente forzarán un reinicio de la aplicación.

Giro algunas de las partes más centrales de mi base de código (un motor ECS) en torno al tipo de estructura de datos que describiste, aunque usa bloques contiguos más pequeños (más como 4 kilobytes en lugar de 4 megabytes).

Utiliza una lista doble gratuita para lograr inserciones y eliminaciones de tiempo constante con una lista libre para bloques libres que están listos para insertarse (bloques que no están completos) y una lista sublibre dentro del bloque para índices en ese bloque Listo para ser recuperado tras la inserción.

Cubriré los pros y los contras de esta estructura. Comencemos con algunos inconvenientes porque hay varios de ellos:

Contras

1. Se tarda aproximadamente 4 veces más en insertar un par de cientos de millones de elementos en esta estructura que std::vector(una estructura puramente contigua). Y soy bastante decente con las micro optimizaciones, pero conceptualmente solo hay más trabajo por hacer, ya que el caso común tiene que inspeccionar primero el bloque libre en la parte superior de la lista libre de bloques, luego acceder al bloque y extraer un índice libre de los bloques lista libre, escriba el elemento en la posición libre, y luego verifique si el bloque está lleno y saque el bloque de la lista libre de bloques si es así. Sigue siendo una operación de tiempo constante pero con una constante mucho mayor que presionar de nuevo std::vector.
2. Se tarda aproximadamente el doble en acceder a elementos utilizando un patrón de acceso aleatorio, dada la aritmética adicional para la indexación y la capa adicional de indirección.
3. El acceso secuencial no se asigna de manera eficiente a un diseño de iterador ya que el iterador tiene que realizar ramificaciones adicionales cada vez que se incrementa.
4. Tiene un poco de sobrecarga de memoria, generalmente alrededor de 1 bit por elemento. 1 bit por elemento puede no parecer mucho, pero si está usando esto para almacenar un millón de enteros de 16 bits, entonces eso es 6.25% más de uso de memoria que una matriz perfectamente compacta. Sin embargo, en la práctica, esto tiende a usar menos memoria que a std::vectormenos que esté compactando vectorpara eliminar el exceso de capacidad que reserva. Además, generalmente no lo uso para almacenar elementos tan pequeños.

Pros

1. El acceso secuencial usando una for_eachfunción que toma un rango de procesamiento de devolución de llamada de elementos dentro de un bloque casi rivaliza con la velocidad de acceso secuencial std::vector(solo como una diferencia del 10%), por lo que para mí no es mucho menos eficiente en los casos de uso más críticos para el rendimiento ( la mayor parte del tiempo pasado en un motor ECS es en acceso secuencial).
2. Permite eliminaciones de tiempo constante desde el medio con la estructura desasignando bloques cuando se vuelven completamente vacíos. Como resultado, generalmente es bastante decente para asegurarse de que la estructura de datos nunca use significativamente más memoria de la necesaria.
3. No invalida los índices de elementos que no se eliminan directamente del contenedor, ya que solo deja agujeros utilizando un enfoque de lista libre para recuperar esos agujeros en la inserción posterior.
4. No tiene que preocuparse tanto por quedarse sin memoria, incluso si esta estructura contiene un número épico de elementos, ya que solo solicita pequeños bloques contiguos que no representan un desafío para el sistema operativo para encontrar una gran cantidad de elementos contiguos sin usar páginas
5. Se presta bien a la concurrencia y seguridad de subprocesos sin bloquear toda la estructura, ya que las operaciones generalmente se localizan en bloques individuales.

Ahora, uno de los mayores pros para mí fue que se volvió trivial hacer una versión inmutable de esta estructura de datos, como esta:

Desde entonces, eso abrió todo tipo de puertas para escribir más funciones desprovistas de efectos secundarios que hicieron que fuera mucho más fácil lograr la seguridad de excepciones, seguridad de hilos, etc. La inmutabilidad fue algo que descubrí que podía lograr fácilmente con esta estructura de datos en retrospectiva y por accidente, pero podría decirse que es uno de los mejores beneficios que obtuvo, ya que hizo que el mantenimiento de la base de código fuera mucho más fácil.

Las matrices no contiguas no tienen localidad de caché, lo que resulta en un mal rendimiento. Sin embargo, con un tamaño de bloque de 4M, parece que habría suficiente localidad para un buen almacenamiento en caché.

La localidad de referencia no es algo de lo que deba preocuparse en bloques de ese tamaño, y mucho menos bloques de 4 kilobytes. Una línea de caché suele tener solo 64 bytes. Si desea reducir las pérdidas de caché, solo concéntrese en alinear esos bloques correctamente y favorezca más patrones de acceso secuencial cuando sea posible.

Una forma muy rápida de convertir un patrón de memoria de acceso aleatorio en uno secuencial es usar un conjunto de bits. Digamos que tiene una gran cantidad de índices y están en orden aleatorio. Simplemente puede abrirlos y marcar bits en el conjunto de bits. Luego puede iterar a través de su conjunto de bits y verificar qué bytes no son cero, verificando, digamos, 64 bits a la vez. Una vez que encuentre un conjunto de 64 bits, de los cuales al menos un bit está configurado, puede usar las instrucciones de FFS para determinar rápidamente qué bits están configurados. Los bits le dicen a qué índices debe acceder, excepto que ahora obtiene los índices ordenados en orden secuencial.

Esto tiene algunos gastos generales, pero puede ser un intercambio que valga la pena en algunos casos, especialmente si vas a recorrer estos índices muchas veces.

Acceder a un elemento no es tan simple, hay un nivel adicional de indirección. ¿Se optimizaría esto? ¿Causaría problemas de caché?

No, no se puede optimizar. El acceso aleatorio, al menos, siempre costará más con esta estructura. Sin embargo, a menudo no aumentará demasiado la pérdida de caché, ya que tenderá a obtener una alta localidad temporal con la matriz de punteros a bloques, especialmente si sus rutas de ejecución de casos comunes usan patrones de acceso secuenciales.

Dado que hay un crecimiento lineal después de alcanzar el límite de 4M, podría tener muchas más asignaciones de las que tendría normalmente (por ejemplo, un máximo de 250 asignaciones por 1 GB de memoria). No se copia memoria adicional después de 4M, sin embargo, no estoy seguro de si las asignaciones adicionales son más caras que copiar grandes porciones de memoria.

En la práctica, la copia es a menudo más rápida porque es un caso raro, solo ocurre algo así como el log(N)/log(2)tiempo total, mientras que al mismo tiempo simplifica el caso común muy barato donde simplemente puede escribir un elemento en la matriz muchas veces antes de que se llene y deba reasignarse nuevamente. Por lo general, no obtendrá inserciones más rápidas con este tipo de estructura porque el trabajo de caso común es más costoso incluso si no tiene que lidiar con ese costoso caso raro de reasignación de matrices enormes.

El principal atractivo de esta estructura para mí, a pesar de todos los inconvenientes, es el uso reducido de la memoria, no tener que preocuparme por OOM, poder almacenar índices y punteros que no se invalidan, la concurrencia y la inmutabilidad. Es bueno tener una estructura de datos donde pueda insertar y eliminar cosas en tiempo constante mientras se limpia por sí mismo y no invalida punteros e índices en la estructura.