Uso una implementación de montón personalizada en uno de mis proyectos. Consta de dos partes principales:Heap optimizado para (aunque sin limitarse a) uso de un único subproceso
Montón de tamaño de bloque fijo. Es decir. un montón que asigna bloques de un tamaño específico solamente. Asigna bloques de memoria más grandes (ya sea páginas de memoria virtual o de otro montón), y luego los divide en unidades de asignación atómica.
Realiza asignación/liberación rápida (en O (1)) y no hay gastos generales de uso de memoria, sin tomar en cuenta las cosas impuestas por el montón externo.
Global de uso general montón. Consiste en cubos de los montones anteriores (tamaño fijo). WRT el tamaño de asignación solicitado elige el segmento adecuado y realiza la asignación a través de él.
Dado que toda la aplicación es (en gran medida) de múltiples subprocesos: el montón global bloquea el contenedor correspondiente durante su funcionamiento.
Nota: a diferencia de los montones tradicionales, este montón requiere el tamaño de asignación no solo para la asignación, sino también para la liberación. Esto permite identificar el depósito apropiado sin búsquedas ni sobrecarga adicional de memoria (como guardar el tamaño de bloque que precede al bloque asignado). Aunque algo menos conveniente, esto está bien en mi caso. Además, dado que la "configuración del depósito" es conocida en tiempo de compilación (implementada a través del vudú de plantillas C++), el depósito apropiado se determina en tiempo de compilación.
Hasta ahora todo se ve (y funciona) bien.
Recientemente trabajé en un algoritmo que realiza operaciones de almacenamiento en gran cantidad y, naturalmente, se ve afectado significativamente por el rendimiento del montón. La creación de perfiles reveló que su rendimiento se ve considerablemente afectado por el bloqueo . Es decir, el almacenamiento en sí funciona muy rápido (la asignación típica implica solo algunas instrucciones de eliminación de referencias de memoria), pero como toda la aplicación es de subprocesos múltiples, el depósito apropiado está protegido por la sección crítica, que se basa en instrucciones interbloqueadas, que son mucho más pesados
Lo he arreglado mientras tanto dando a este algoritmo su propio montón dedicado, que no está protegido por una sección crítica. Pero esto impone varios problemas/restricciones en el nivel de código. Tal como la necesidad de pasar la información de contexto en el interior de la pila donde sea que sea necesario. También se puede usar TLS para evitar esto, pero esto puede causar algunos problemas con el reingreso en mi caso específico.
Esto me hace preguntarme: ¿Existe una técnica conocida para optimizar el montón (pero no se limita a) el uso de un único subproceso?
EDIT:
agradecimiento especial a @Voo por sugerir retirar tcmalloc del google.
Parece que funciona de manera similar a lo que hice más o menos (al menos para objetos pequeños). Pero además resuelven el problema exacto que tengo, al mantener por subproceso caché.
Yo también pensé en esta dirección, pero pensé en mantener por montones. Entonces liberar un bloque de memoria asignado desde el montón que pertenece a otro subproceso es algo complicado: uno debe insertarlo en una especie de cola bloqueada, y ese otro subproceso debe notificarse, y liberar las asignaciones pendientes de forma asincrónica. La desasignación asíncrona puede causar problemas: si ese hilo está ocupado por algún motivo (por ejemplo, realiza cálculos agresivos), no se produce una desasignación de memoria. Además en el escenario de subprocesos múltiples, el costo de la desasignación es significativamente mayor.
OTOH la idea del almacenamiento en caché parece mucho más simple y más eficiente. Trataré de resolverlo.
Muchas gracias.
P.S .:
De hecho tcmalloc de Google es grande. Creo que se implementó de manera muy similar a lo que hice (al menos parte de tamaño fijo).
Pero, para ser pedante, hay una cuestión en la que mi montón es superior. De acuerdo con los documentos, tcmalloc impone una sobrecarga de aproximadamente 1% (asintóticamente), mientras que mi sobrecarga es 0.0061%. Es 4/64K para ser exacto.
:)
Esto recuerda a mi las pruebas que he hecho hace años. El mecanismo estándar "pobre" comúnmente utilizado ocupa más de 100 veces una buena implementación "personalizada". –
Me encantaría ver lo que ha hecho si es más rápido que el asignador de memoria estándar. Como la mayoría de las implementaciones estándar ya hacen lo que afirma hacer (y mucho más). Encuentro que el reclamo O (1) es curioso, especialmente cuando usted dice que no tiene gastos generales (estoy seguro de que ganará un centavo cuando lo haga su patente). –
La idea de cubo completo es básicamente tcmalloc de Google (aunque dado que es un asignador general, debe decidir dinámicamente qué depósito usar). tcmalloc utiliza el almacenamiento local de subprocesos para evitar exactamente su problema y solo rara vez asigna desde el montón general y por lo tanto evita bloqueos. – Voo