atomic_queue
1.0.0
C ++ 14 colas sin bloqueo de consumo múltiple de productor múltiple basadas en búfer circular y std::atomic .
Diseñado con un objetivo para minimizar la latencia entre un hilo que empuja un elemento en una cola y otro hilo sacándolo de la cola.
Se ha desarrollado, probado y comparado en Linux, pero debe admitir cualquier plataforma C ++ 14 que implemente std::atomic . Informado como compatible con Windows, pero las integraciones continuas alojadas por GitHub se configuran actualmente solo para la plataforma X86_64 en Ubuntu-20.04 y Ubuntu-22.04. Las solicitudes de extracción para extender las integraciones continuas para ejecutarse en otras arquitecturas y/o plataformas son bienvenidas.
Al minimizar la latencia, un buen diseño no es cuando no queda nada por agregar, sino cuando no queda nada que eliminar, como ejemplifican estas colas.
Minimizar la latencia maximiza naturalmente el rendimiento. La baja latencia recíproca es alta a través, en un sentido ideal de ingeniería matemática y práctica. La baja latencia es incompatible con cualquier retraso y/o lotes, que destruyen el orden de tiempo global original (hardware) de los eventos empujados en una cola por diferentes hilos. La maximización del rendimiento, por otro lado, se puede hacer a expensas de la latencia retrasando y un montón de actualizaciones múltiples.
El principio de diseño principal que siguen estas colas es el minimalismo , lo que resulta en opciones de diseño como:
push / pop , no se puede obtener referencia/puntero a elementos en la cola.El impacto de cada una de estas pequeñas opciones de diseño por su cuenta es apenas medible, pero su impacto total es mucho mayor que una simple suma de los impactos de los constituyentes, también conocido como compuesto súper escalar o sinergia. La sinergia que emerge de combinar múltiples de estas pequeñas opciones de diseño juntas es lo que permite que las CPU funcionen en sus capacidades máximas menos impedidas.
Estas opciones de diseño también son limitaciones:
Las aplicaciones de ultra baja latencia necesitan exactamente eso y nada más. El minimalismo vale la pena, vea los puntos de referencia de rendimiento y latencia.
Varios otros contenedores bien establecidos y populares se utilizan para referencia en los puntos de referencia:
std::mutex - un buffer de anillo de tamaño fijo con std::mutex .pthread_spinlock : un buffer de anillo de tamaño fijo con pthread_spinlock_t .boost::lockfree::spsc_queue -Una cola de consumo de un solo productor sin esperar de la biblioteca Boost.boost::lockfree::queue : una cola de consumo múltiple sin bloqueo sin bloqueo de la biblioteca Boost.moodycamel::ConcurrentQueue : una cola de consumo múltiple sin bloqueo sin bloqueo utilizada en modo no bloqueo. Esta cola está diseñada para maximizar el rendimiento a expensas de la latencia y evitar el orden de tiempo global de los elementos empujado en una cola por diferentes hilos. No es equivalente a otras colas en referencia aquí a este respecto.moodycamel::ReaderWriterQueue : una cola de consumo de un solo productor sin bloqueo utilizada en el modo sin bloqueo.xenium::michael_scott_queue : una cola de consumo múltiple sin bloqueo sin bloqueo propuesta por Michael y Scott (esta cola es similar a boost::lockfree::queue , que también se basa en la misma propuesta).xenium::ramalhete_queue : una cola de consumo múltiple sin bloqueo sin bloqueo propuesta por Ramalhete y Correia.xenium::vyukov_bounded_queue -Una cola limitada multiproducta-multi-consumo basada en la versión propuesta por Vyukov.tbb::spin_mutex : un buffer de anillo de tamaño fijo bloqueado con tbb::spin_mutex de Intel roscando bloques de construcción.tbb::concurrent_bounded_queue - cola homónima utilizada en modo no bloqueo de bloques de construcción de enhebramiento Intel.Los contenedores proporcionados son plantillas de clase solo de encabezado, no es necesario construir/instalar.
git clone https://github.com/max0x7ba/atomic_queue.git
atomic_queue/include (use la ruta completa) a las rutas de inclusión de su sistema de compilación.#include <atomic_queue/atomic_queue.h> en su fuente C ++. vcpkg install atomic-queue
Siga el tutorial oficial sobre cómo consumir paquetes de Conan. Los detalles específicos de esta biblioteca están disponibles en Conancenter.
Los contenedores proporcionados son plantillas de clase solo de encabezado que solo requieren #include <atomic_queue/atomic_queue.h> , no es necesario construir/instalar.
El edificio es necesario para ejecutar las pruebas y los puntos de referencia.
git clone https://github.com/cameron314/concurrentqueue.git
git clone https://github.com/cameron314/readerwriterqueue.git
git clone https://github.com/mpoeter/xenium.git
git clone https://github.com/max0x7ba/atomic_queue.git
cd atomic_queue
make -r -j4 run_benchmarks
El punto de referencia también requiere que la biblioteca Intel TBB esté disponible. Se supone que está instalado en /usr/local/include y /usr/local/lib . Si está instalado en otro lugar, puede modificar cppflags.tbb y ldlibs.tbb en Makefile .
AtomicQueue : un buffer de anillo de tamaño fijo para elementos atómicos.OptimistAtomicQueue : un buffer de anillo de tamaño fijo más rápido para elementos atómicos que se vuelven ocupado cuando está vacío o lleno. Es AtomicQueue utilizado con push / pop en lugar de try_push / try_pop .AtomicQueue2 : un buffer de anillo de tamaño fijo para elementos no atómicos.OptimistAtomicQueue2 : un buffer de anillo de tamaño fijo más rápido para elementos no atómicos que se vuelven ocupado cuando está vacío o lleno. Es AtomicQueue2 usado con push / pop en lugar de try_push / try_pop . Estos contenedores tienen AtomicQueueB correspondientes, OptimistAtomicQueueB , AtomicQueueB2 , Versiones OptimistAtomicQueueB2 donde el tamaño del búfer se especifica como un argumento para el constructor.
Se admite el modo totalmente ordenado. En este modo, los consumidores reciben mensajes en el mismo pedido FIFO, los mensajes fueron publicados. Este modo es compatible con las funciones push y pop , pero para no para las versiones try_ . En Intel X86, el modo totalmente ordenado tiene 0 costo, a partir de 2019.
Se admite el modo de consumidor de un solo productor. En este modo, no son necesarias instrucciones costosas de CPU de lectura atómica-modificación-escritura, solo las cargas y tiendas atómicas más baratas. Eso mejora significativamente el rendimiento de la cola.
Los tipos de elementos de cola de movimiento solo son totalmente compatibles. Por ejemplo, una cola de elementos std::unique_ptr<T> sería AtomicQueue2B<std::unique_ptr<T>> o AtomicQueue2<std::unique_ptr<T>, CAPACITY> .
Las plantillas de la clase de cola proporcionan las siguientes funciones del miembro:
try_push : agrega un elemento al final de la cola. Devuelve false cuando la cola está llena.try_pop : elimina un elemento del frente de la cola. Devuelve false cuando la cola está vacía.push (Optimist): agrega un elemento al final de la cola. Ocupado espera cuando la cola esté llena. Más rápido que try_push cuando la cola no está llena. Cola opcional de productores FIFO y orden total.pop (optimista): elimina un elemento del frente de la cola. Ocupado espera cuando la cola esté vacía. Más rápido que try_pop cuando la cola no está vacía. Cola de consumo de FIFO opcional y orden total.was_size - Devuelve el número de elementos no consumen durante la llamada. El estado puede haber cambiado cuando se examina el valor de retorno.was_empty : devuelve true si el contenedor estaba vacío durante la llamada. El estado puede haber cambiado cuando se examina el valor de retorno.was_full : devuelve true si el contenedor estaba lleno durante la llamada. El estado puede haber cambiado cuando se examina el valor de retorno.capacity : devuelve el número máximo de elementos que la cola puede mantener. Los elementos atómicos son aquellos, para los cuales std::atomic<T>{T{}}.is_lock_free() devuelve true y, cuando las características de C ++ 17 están disponibles, std::atomic<T>::is_always_lock_free se evalúa a true en el momento compilado. En otras palabras, la CPU puede cargar, almacenar y comparar y intercambiar dichos elementos atómicamente de forma nativa. En x86-64, tales elementos son todos los tipos de aritméticos y puntero estándar de C ++.
Las colas para elementos atómicos reservan un valor para servir como un marcador de elemento vacío NIL , su valor predeterminado es 0 . El valor NIL no debe ser empujado a una cola y hay una declaración assert en las funciones push para protegerse contra eso en el modo de depuración. Empujar el elemento NIL en una cola en modo de liberación construye resulta en un comportamiento indefinido, como puntos muertos y/o elementos de cola perdidos.
Tenga en cuenta que el optimismo es una elección de un flujo de control de operación de modificación de cola, en lugar de un tipo de cola. Un push optimista es más rápido cuando la cola no está llena la mayor parte del tiempo, un pop optimista, cuando la cola no está vacía la mayor parte del tiempo. Las operaciones optimistas y no así se pueden mezclar sin restricciones. OptimistAtomicQueue s en los puntos de referencia solo usan push y pop optimistas .
Vea Ejemplo.cc para un ejemplo de uso.
Operaciones push e try_push Sincronize con (como se define en std::memory_order ) con cualquier operación pop o try_pop posterior del mismo objeto de cola. Lo que significa que:
push / try_push , que es una operación memory_order::release . El mismo orden de memoria que el de std::mutex::unlock .pop / try_pop , que es una operación memory_order::acquire . El mismo orden de memoria que el de std::mutex::lock .push / try_push de un elemento en una cola se vuelven visibles en el hilo del consumidor que pop / try_pop ese elemento particular. Las colas disponibles aquí usan una matriz de timbres para almacenar elementos. La capacidad de la cola se fija en el tiempo de compilación o el tiempo de construcción.
En una producción, el escenario de consumidor de múltiples productores múltiples, la capacidad de buffer de anillo debe establecerse en el tamaño máximo de cola esperado. Cuando el bufón anillo se llena, significa que los consumidores no pueden consumir los elementos lo suficientemente rápido. Una solución para eso es cualquiera de:
push y pop siempre incurren en algunos ciclos costosos de la CPU para mantener la integridad del estado de la cola de manera atómica/consistente/aislada con respecto a otros hilos y estos costos aumentan de manera súper lineal a medida que crece la contención de la cola. El lote del productor de múltiples elementos o elementos pequeños resultantes de un evento en un mensaje de cola es a menudo una solución razonable.El uso de un tamaño de matriz de timbres de anillo de potencia de 2 permite un par de optimizaciones importantes:
% SIZE del operador binario restante. % de operador binario restante normalmente genera una instrucción de la CPU de división que no es barata, pero el uso de un tamaño de potencia de 2 convierte ese operador resto en una instrucción binaria and CPU barata y eso es tan rápido como se pone.N productores junto con los consumidores M que compiten en elementos posteriores en la misma línea de caché de buffer de anillo en el peor de los casos, es solo un productor que compite con un consumidor (pedanticamente, cuando el número de CPU no es mayor que el número de elementos que pueden caber en una línea de caché). Esta optimización escala mejor con el número de productores y consumidores, y el tamaño del elemento. Con un bajo número de productores y consumidores (hasta aproximadamente 2 de cada uno en estos puntos de referencia) deshabilitar esta optimización puede producir un mejor rendimiento (pero una mayor varianza entre las ejecuciones). Los contenedores usan el tipo unsigned para el tamaño y los índices internos. En la plataforma X86-64 unsigned tiene 32 bits de ancho, mientras que size_t tiene 64 bits de ancho. Las instrucciones de 64 bits utilizan un prefijo de instrucción de byte adicional que resulte en un poco más de presión sobre el caché de instrucciones de la CPU y el front-end. Por lo tanto, se utilizan índices unsigned de 32 bits para maximizar el rendimiento. Eso limita el tamaño de la cola a 4,294,967,295 elementos, lo que parece ser un límite difícil razonable para muchas aplicaciones.
Si bien las colas atómicas se pueden usar con cualquier tipo de elemento móvil (incluido std::unique_ptr ), para el mejor rendimiento y latencia, los elementos de la cola deben ser baratos de copiar y bloquear (por ejemplo, unsigned o T* ), de modo que las operaciones push y pop se completen más rápido.
Conceptualmente , una operación push o pop realiza dos pasos atómicos:
head , los consumidores incrementan el índice tail . Cada ranura es accedido por un productor y un solo hilos de consumo.NIL , la carga del consumidor de una ranura cambia su estado para ser NIL . La ranura es un spinlock para su único productor y un hilos de consumo. Estas colas anticipan que un hilo que realiza push o pop puede completar el Paso 1 y luego ser adelantados antes de completar el Paso 2.
Un algoritmo está libre de bloqueos si hay un progreso garantizado en todo el sistema. Estas colas garantizan el progreso en todo el sistema por las siguientes propiedades:
push es independiente de cualquier push anterior. Un push incompleto (previamente) por un hilo productor no afecta push de ningún otro hilo.pop es independiente de cualquier pop anterior. Un pop incompleto (previamente) por un hilo del consumidor no afecta pop de ningún otro hilo.push incompleto (previamente) de un hilo de productor afecta solo un hilo del consumidor que pop un elemento de esta ranura de cola en particular. Todos los demás hilos pop no se ven afectados.pop incompleto (previamente) de un hilo del consumidor afecta solo un hilo de productor push un elemento en esta ranura de cola particular mientras espera que se haya consumido hace mucho tiempo, en el escenario bastante poco probable que los productores han envuelto en todo el buffer de anillo, mientras que este consumidor no ha completado su pop . Todos los demás hilos push S y pop S no se ven afectados. La preferencia de hilo de programador de tareas de Linux es algo que ningún proceso de espacio de usuario debería poder afectar o escapar, de lo contrario, cualquiera/cada aplicación maliciosa lo explotaría.
Aún así, hay algunas cosas que uno puede hacer para minimizar la preferencia de los hilos de aplicación de la misión crítica:
SCHED_FIFO en tiempo real para sus hilos, por ejemplo, chrt --fifo 50 <app> . Un hilo SCHED_FIFO de mayor prioridad o un controlador de interrupción del kernel aún puede evitar sus hilos SCHED_FIFO .SCHED_OTHER con sus prioridades ajustadas dinámicamente derrota el propósito de usar estas colas.SCHED_FIFO se estremezcan.taskset . La gente a menudo propone limitar el espera ocupado con un llamado posterior a std::this_thread::yield() / sched_yield / pthread_yield . Sin embargo, sched_yield es una herramienta incorrecta para bloquear porque no se comunica con el kernel del sistema operativo lo que el hilo está esperando, de modo que el programador del hilo del sistema operativo nunca pueda programar el hilo de llamadas para reanudar en el momento adecuado cuando el estado compartido ha cambiado (a menos que no haya otros hilos que puedan ejecutarse en este núcleo de CPU, de modo que el llamado se reanude de inmediato). Consulte la sección de notas en man sched_yield y un hilo del kernel de Linux sobre sched_yield y SpinLocks para obtener más detalles.
En Linux, hay mutex tipo PTHREAD_MUTEX_ADAPTIVE_NP que espera un mutex bloqueado por varias iteraciones y luego hace un sistema de bloqueo en el núcleo para deseteccionar el hilo de espera. En los puntos de referencia fue el peor desempeño y no pude encontrar una manera de hacerlo funcionar mejor, y esa es la razón por la que no está incluido en los puntos de referencia.
En las CPU de Intel, uno podría usar los 4 registros de control de depuración para monitorear la región de memoria de spinlock para el acceso de escritura y esperarlo usando select (y sus amigos) o sigwait (ver perf_event_open y uapi/linux/hw_breakpoint.h para obtener más detalles). Un camarero de spinlock podría suspenderse con select o sigwait hasta que el estado de SpinLock se haya actualizado. Pero solo hay 4 de estos registros, por lo que tal solución no se escalaría.
Ver cuadros de referencia de rendimiento y latencia.
Hay algunos comportamientos del sistema operativo que complican la evaluación comparativa:
SCHED_FIFO tiempo real en tiempo real se use para deshabilitar el tiempo cuántico del horario y hacer que los subprocesos no sean anticipados por procesos/hilos de menor prioridad.benchmarks se ejecuta al menos 33 veces. Los gráficos de referencia muestran valores promedio. La información sobre herramientas del gráfico también muestra los valores de desviación estándar, mínimo y máximo. Rendimiento de referencia de las colas de contenido de un solo productor boost::lockfree::spsc_queue , moodycamel::ReaderWriterQueue y estas colas en el modo de consumo de un solo productor deben ser idénticos porque implementan exactamente el mismo algoritmo utilizando exactamente la misma carga atómica y las instrucciones de la tienda. boost::lockfree::spsc_queue La referencia de referencia en ese momento no tenía optimizaciones para minimizar la contención de caché L1D, predicción errónea de rama fría o puestos de tubería de problemas más sutilmente notables solo en el código de ensamblaje generado.
Solo tengo acceso a unas pocas máquinas X86-64. Si tiene acceso a diferentes hardware, no dude en enviar el archivo de salida de scripts/run-benchmarks.sh e incluiré sus resultados en la página de puntos de referencia.
Cuando hay enormes páginas disponibles, los puntos de referencia usan páginas enormes 1x1GB o 16x2Mb para las colas para minimizar las fallas de TLB. Para habilitar las enormes páginas, haga una de:
sudo hugeadm --pool-pages-min 1GB:1
sudo hugeadm --pool-pages-min 2MB:16
Alternativamente, es posible que desee habilitar grandes páginas transparentes en su sistema y utilizar un asignador de ADMAGE consciente, como TCMALLOC.
Por defecto, el planificador de Linux elimina los hilos en tiempo real del consumo del 100% de la CPU y eso es perjudicial para la evaluación comparativa. Los detalles completos se pueden encontrar en la programación grupal en tiempo real. Para deshabilitar el estrangulador de hilos en tiempo real: Do:
echo -1 | sudo tee /proc/sys/kernel/sched_rt_runtime_us >/dev/null
N Los hilos productores empujan un entero de 4 bytes en una misma cola, n hilos de consumo explotan los enteros de la cola. Todos los productores publican 1,000,000 mensajes en total. Se mide el tiempo total para enviar y recibir todos los mensajes. El punto de referencia se ejecuta desde 1 productor y 1 consumidor hasta productores / consumidores (total-number-of-cpus / 2) para medir la escalabilidad de diferentes colas.
Un hilo publica un entero a otro hilo a través de una cola y espera una respuesta de otra cola (2 colas en total). Los puntos de referencia miden el tiempo total de 100,000 ping-pong, lo mejor de 10 carreras. La contención es mínima aquí (1-productor-1-consumo, 1 elemento en la cola) para poder lograr y medir la latencia más baja. Informa el tiempo promedio de ida y vuelta.
Las contribuciones son más que bienvenidas. .editorconfig y .clang-format se pueden usar para hacer coincidir automáticamente el formateo del código.
Algunos libros sobre el tema de la programación multiproceso que encontré bastante instructivo:
Copyright (c) 2019 Maxim Egorushkin. Licencia MIT. Vea la licencia completa en la licencia de archivo.
