SPSCQueue
Increased throughput
Una cola de tamaño fijo sin esperas ni bloqueos, de un solo productor, un solo consumidor, escrita en C++11. Esta implementación es más rápida que boost::lockfree::spsc y folly::ProducerConsumerQueue .
SPSCQueue< int > q ( 1 );
auto t = std::thread([&] {
while (!q. front ());
std::cout << *q. front () << std::endl;
q. pop ();
});
q.push( 1 );
t.join(); Consulte src/SPSCQueueExample.cpp para ver el ejemplo completo.
SPSCQueue<T>(size_t capacity);
Cree una SPSCqueue que contenga elementos de tipo T con capacity capacidad. La capacidad debe ser al menos 1.
void emplace(Args &&... args);
Poner en cola un elemento mediante construcción in situ. Se bloquea si la cola está llena.
bool try_emplace(Args &&... args);
Intente poner en cola un elemento mediante construcción in situ. Devuelve true en caso de éxito y false si la cola está llena.
void push(const T &v);
Poner en cola un elemento mediante construcción de copia. Se bloquea si la cola está llena.
template <typename P> void push(P &&v);
Poner en cola un elemento mediante construcción de movimiento. Participa en la resolución de sobrecarga solo si std::is_constructible<T, P&&>::value == true . Se bloquea si la cola está llena.
bool try_push(const T &v);
Intente poner en cola un elemento mediante la construcción de copias. Devuelve true en caso de éxito y false si la cola está llena.
template <typename P> bool try_push(P &&v);
Intente poner en cola un elemento mediante la construcción de movimiento. Devuelve true en caso de éxito y false si la cola está llena. Participa en la resolución de sobrecarga solo si std::is_constructible<T, P&&>::value == true .
T *front();
Devuelve el puntero al frente de la cola. Devuelve nullptr si la cola está vacía.
void pop();
Quitar de la cola el primer elemento de la cola. Debe asegurarse de que la cola no esté vacía antes de llamar a pop. Esto significa que front() debe haber devuelto un valor no nullptr antes de cada llamada a pop() . Requiere std::is_nothrow_destructible<T>::value == true .
size_t size();
Devuelve el número de elementos disponibles en la cola.
bool empty();
Devuelve verdadero si la cola está actualmente vacía.
Solo un subproceso de escritura puede realizar operaciones de puesta en cola y solo un subproceso de lector puede realizar operaciones de retirada de cola. Cualquier otro uso no es válido.
Además de admitir la asignación personalizada a través de la interfaz del asignador personalizado estándar, esta biblioteca también admite la propuesta estándar P0401R3 Proporciona información sobre el tamaño en la interfaz del asignador. Esto permite un uso conveniente de páginas enormes sin desperdiciar el espacio asignado. El uso de comentarios de tamaño solo se admite cuando C++17 está habilitado.
Actualmente, la biblioteca no incluye un asignador de páginas grandes, ya que las API para asignar páginas grandes dependen de la plataforma y el manejo de páginas de gran tamaño y el reconocimiento de NUMA son específicos de la aplicación.
A continuación se muestra un ejemplo de asignador de páginas enorme para Linux:
# include < sys/mman.h >
template < typename T> struct Allocator {
using value_type = T;
struct AllocationResult {
T *ptr;
size_t count;
};
size_t roundup ( size_t n) { return (((n - 1 ) >> 21 ) + 1 ) << 21 ; }
AllocationResult allocate_at_least ( size_t n) {
size_t count = roundup ( sizeof (T) * n);
auto p = static_cast <T *>( mmap ( nullptr , count, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
- 1 , 0 ));
if (p == MAP_FAILED) {
throw std::bad_alloc ();
}
return {p, count / sizeof (T)};
}
void deallocate (T *p, size_t n) { munmap (p, roundup ( sizeof (T) * n)); }
}; Consulte src/SPSCQueueExampleHugepages.cpp para ver el ejemplo completo sobre cómo utilizar páginas enormes en Linux.
La implementación subyacente se basa en un búfer circular.
Se ha tenido cuidado para evitar problemas relacionados con el intercambio falso. Los índices de cabeza y cola están alineados y rellenados hasta el rango de intercambio falso (tamaño de línea de caché). Además, el búfer de ranuras se rellena con el rango de uso compartido falso al principio y al final, lo que evita el uso compartido falso con asignaciones adyacentes.
Esta implementación tiene un mayor rendimiento que un búfer de anillo concurrente típico al almacenar en caché localmente los índices inicial y final en el escritor y el lector, respectivamente. El almacenamiento en caché aumenta el rendimiento al reducir la cantidad de tráfico de coherencia de caché.
Para entender cómo funciona esto, primero considere una operación de lectura en ausencia de almacenamiento en caché: el índice principal (índice de lectura) debe actualizarse y, por lo tanto, esa línea de caché se carga en la caché L1 en estado exclusivo. Es necesario leer la cola (índice de escritura) para verificar que la cola no esté vacía y, por lo tanto, esté cargada en la caché L1 en estado compartido. Dado que una operación de escritura en cola necesita leer el índice principal, es probable que una operación de escritura requiera algo de tráfico de coherencia de caché para devolver la línea de caché del índice principal al estado exclusivo. En el peor de los casos, habrá una transición de línea de caché de compartida a exclusiva para cada operación de lectura y escritura.
A continuación, considere un lector de cola que almacena en caché el índice de cola: si el índice de cola almacenado en caché indica que la cola está vacía, cargue el índice de cola en el índice de cola almacenado en caché. Si la cola no estaba vacía, se realizan múltiples operaciones de lectura hasta que el índice de cola almacenado en caché pueda completarse sin robar el estado exclusivo de la línea de caché del índice de cola del escritor. Por lo tanto, se reduce el tráfico de coherencia de caché. Se puede hacer un argumento análogo para la operación de escritura en cola.
Esta implementación permite la falta arbitraria de dos capacidades, en lugar de asignar una ranura de cola adicional para indicar la cola llena. Si no desea desperdiciar almacenamiento en un espacio de cola adicional, debe utilizar una implementación diferente.
Referencias:
Probar algoritmos sin bloqueos es difícil. Estoy usando dos enfoques para probar la implementación:
El punto de referencia de rendimiento mide el rendimiento entre 2 subprocesos para una cola de elementos int .
El punto de referencia de latencia mide el tiempo de ida y vuelta entre 2 subprocesos que se comunican mediante 2 colas de elementos int .
Resultados de las pruebas comparativas para un procesador AMD Ryzen 9 3900X de 12 núcleos, los 2 subprocesos se ejecutan en diferentes núcleos en el mismo chiplet:
| Cola | Rendimiento (ops/ms) | RTT de latencia (ns) |
|---|---|---|
| Cola SPSC | 362723 | 133 |
| impulso::lockfree::spsc | 209877 | 222 |
| locura::ProductorConsumerQueue | 148818 | 147 |
SPSCQueue ha sido citado en los siguientes artículos:
Este proyecto fue creado por Erik Rigtorp <[email protected]>.
