Asignadores de pila personalizados

La mayoría de los programas pueden ser bastante informales acerca de la asignación de almacenamiento dinámico, incluso en la medida en que los lenguajes de programación funcionales prefieran asignar nuevos objetos que modificar los antiguos, y dejar que el recolector de basura se preocupe por liberar cosas.

Sin embargo, en la programación integrada, el sector silencioso, hay muchas aplicaciones en las que no se puede usar la asignación de montón en absoluto, debido a la memoria y las restricciones de tiempo real; El número de objetos de cada tipo que se manejarán es parte de la especificación, y todo está asignado estáticamente.

La programación de juegos (al menos con aquellos juegos que son ambiciosos sobre empujar el hardware) a veces se encuentra en el medio: puede usar la asignación dinámica, pero hay suficiente memoria y restricciones suaves en tiempo real que no puede tratar al asignador como una caja negra , y mucho menos usar la recolección de basura, por lo que debe usar asignadores personalizados. Esta es una de las razones por las que C ++ todavía se usa ampliamente en la industria de los juegos; te permite hacer cosas como http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

¿Qué otros dominios hay en ese territorio intermedio? ¿Dónde, aparte de los juegos, se usan mucho los asignadores personalizados?

Cada vez que tenga una aplicación que tenga una ruta crítica intensiva en rendimiento, debe preocuparse cómo trata la memoria. La mayoría de las aplicaciones del lado del cliente del usuario final no entran en esta categoría porque son impulsadas por eventos primarios y la mayoría de los eventos provienen de interacciones con el usuario, y eso no tiene tantas restricciones de rendimiento (si es que tiene alguna).

Sin embargo, una gran cantidad de software de back-end debería centrarse en cómo se maneja la memoria porque gran parte de ese software puede ampliarse para manejar un mayor número de clientes, un mayor número de transacciones, más fuentes de datos ... Una vez que comience Al superar los límites, puede comenzar a analizar cómo la memoria de los usuarios de su software y escribir esquemas de asignación personalizados adaptados a su software en lugar de confiar en un asignador de memoria completamente genérico que fue escrito para manejar cualquier caso de uso imaginable.

Para darle algunos ejemplos ... en mi primera empresa trabajé en un paquete Historian, software responsable de recopilar / almacenar / archivar datos de control de procesos (piense en una fábrica, planta de energía nuclear o refinería de petróleo con 10 de millones de sensores, almacenaríamos esos datos). Cada vez que analizamos cualquier cuello de botella de rendimiento que impedía al Historian procesar más datos, la mayoría de las veces el problema estaba en cómo se manejaba la memoria. Hemos hecho grandes esfuerzos para asegurarnos de que no se llamara a malloc / free a menos que fuera absolutamente necesario.

En mi trabajo actual, trabajo en la grabadora digital de video de vigilancia y el paquete de análisis. A 30 fps, cada canal recibe un cuadro de video cada 33 milisegundos. En el hardware que vendemos, podemos grabar fácilmente 100 canales de video. Así que ese es otro caso para asegurarse de que en la ruta crítica (llamada de red => componentes de captura => software de gestión de grabadora => componentes de almacenamiento => disco) no haya asignaciones de memoria dinámica. Tenemos un asignador de trama personalizado, que contiene cubos de búferes de tamaño fijo y utiliza LIFO para reutilizar los búferes previamente asignados. Si necesita 600Kb de almacenamiento, puede terminar con un buffer de 1024Kb, lo que desperdicia espacio, pero debido a que está diseñado específicamente para nuestro uso donde cada asignación es muy efímera, funciona muy bien porque se usa el buffer,

En el tipo de aplicaciones que describí (mover muchos datos de A a B y manejar grandes cantidades de solicitudes de clientes) ir al montón y viceversa es una fuente importante de cuellos de botella en el rendimiento de la CPU. Mantener la fragmentación del montón al mínimo es un beneficio secundario, sin embargo, por lo que puedo decir, la mayoría de los sistemas operativos modernos ya implementan montones de baja fragmentación (como mínimo, sé que Windows lo hace, y espero que otros también lo hagan). Personalmente, en más de 12 años trabajando en este tipo de entornos, he visto problemas de uso de CPU relacionados con el montón con bastante frecuencia, mientras que nunca he visto un sistema que realmente sufriera un montón fragmentado.

Procesamiento de video, efectos visuales, sistemas operativos, etc. Sin embargo, a menudo las personas los usan en exceso. La estructura de datos y el asignador no necesitan separarse para lograr una asignación eficiente.

Por ejemplo, está introduciendo una gran cantidad de complejidad adicional para dividir la asignación eficiente de nodos de árbol en un octárbol lejos del propio octárbol y confiar en un asignador externo. No es necesariamente una violación de SRP fusionar estas dos preocupaciones y responsabilizar al octree de asignar muchos nodos a la vez de manera contigua, ya que hacerlo no aumenta la cantidad de razones para cambiar. Puede, prácticamente hablando, disminuirlo.

En C ++, por ejemplo, uno de los efectos secundarios retardados de tener contenedores estándar se basan en un asignador externa ha hecho ligado estructuras como std::mapy std::listconsiderado casi inútil por la comunidad de C ++, ya que ellos están en contra de la evaluación comparativastd::allocatormientras que estas estructuras de datos asignan un nodo a la vez. Por supuesto, sus estructuras vinculadas funcionarán mal en ese caso, pero las cosas habrían resultado muy diferentes si la asignación eficiente de nodos para estructuras vinculadas se considerara una responsabilidad de la estructura de datos en lugar de la de un asignador. Todavía pueden usar una asignación personalizada por otras razones, como el seguimiento / perfil de memoria, pero confiar en el asignador para hacer que las estructuras vinculadas sean eficientes al intentar asignar nodos uno por uno los hace, por defecto, extremadamente ineficientes, lo que estaría bien si viniera con una advertencia bien conocida de que las estructuras vinculadas ahora necesitan un asignador personalizado, como una lista libre, para ser razonablemente eficiente y evitar la activación de errores de caché a izquierda y derecha. Mucho más prácticamente aplicable podría haber sido algo así comostd::list<T, BlockSize, Alloc>, donde BlockSizeindica el número de nodos contiguos para asignar a la vez para la lista libre (especificar 1 conduciría efectivamente a std::listlo que es ahora).

Pero no existe tal advertencia, lo que lleva a toda una comunidad de cabezas de bloque que hacen eco de un mantra de culto de que las listas vinculadas son inútiles, por ejemplo

Otra área donde es posible que desee un asignador personalizado es evitar la fragmentación del montón . Con el tiempo, su montón puede asignar pequeños objetos fragmentados en todo el montón. Si su programa no puede mantener unida la memoria del montón, cuando su programa va a asignar un objeto más grande, tiene que reclamar más memoria del sistema ya que no puede encontrar un bloque libre entre su montón fragmentado existente (demasiados pequeños los objetos están en el camino). El uso total de la memoria de su programa aumentará con el tiempo y consumirá páginas adicionales de memoria innecesariamente. Por lo tanto, este es un problema bastante grande para los programas que se espera que se ejecuten durante largos períodos de tiempo (piense en bases de datos, servidores, etc., etc.).

¿Dónde, aparte de los juegos, se usan mucho los asignadores personalizados?

Facebook

Echa un vistazo a jemalloc que Facebook está comenzando a usar para mejorar su rendimiento de almacenamiento dinámico y disminuir la fragmentación.