Dada una matriz compartida de contadores enteros, me interesa saber si un hilo puede buscar y agregar atómicamente un elemento de matriz sin bloquear toda la matriz.

Aquí hay una ilustración del modelo de trabajo que usa mutex para bloquear el acceso a toda la matriz.

// thread-shared class members
std::mutex count_array_mutex_;
std::vector<int> counter_array_( 100ish );

// Thread critical section
int counter_index = ... // unpredictable index
int current_count;
{
  std::lock_guard<std::mutex> lock(count_array_mutex_);
  current_count = counter_array_[counter_index] ++;
}
// ... do stuff using current_count.

Me gustaría que varios subprocesos puedan buscar y agregar elementos de matriz separados simultáneamente.

Hasta ahora, en mi investigación de std::atomic<int> me ha confundido que la construcción del objeto atómico también construye el miembro protegido. (Y muchas respuestas que explican por qué no puedes hacer un std::vector<std::atomic<int> >)

4
NoahR 5 feb. 2019 a las 18:18

2 respuestas

La mejor respuesta

De una sola mano:

// Create.
std::vector<std::atomic<int>> v(100);
// Initialize.
for(auto& e : v)
    e.store(0, std::memory_order_relaxed);

// Atomically increment.
auto unpredictable_index = std::rand() % v.size();
int old = v[unpredictable_index].fetch_add(1, std::memory_order_relaxed);

Tenga en cuenta que se elimina el constructor de copia std::atomic<>, por lo que el vector no se puede cambiar de tamaño y debe inicializarse con el recuento final de elementos.

Dado que la funcionalidad de cambio de tamaño de std::vector se pierde, en lugar de std::vector también puede usar std::unique_ptr<std::atomic<int>[]>, por ejemplo:

// Create.
unsigned const N = 100;
std::unique_ptr<std::atomic<int>[]> p(new std::atomic<int>[N]);
// Initialize.
for(unsigned i = 0; i < N; ++i)
    p[i].store(0, std::memory_order_relaxed);

// Atomically increment.
auto unpredictable_index = std::rand() % N;
int old = p[unpredictable_index].fetch_add(1, std::memory_order_relaxed);
4
Maxim Egorushkin 5 feb. 2019 a las 19:42

C ++ 20 / C ++ 2a (o como quieras llamarlo) agregará std::atomic_ref<T> que te permite realizar operaciones atómicas en un objeto que no era atomic<T> para empezar.

No está disponible yet como parte de la biblioteca estándar para la mayoría de los compiladores, pero hay una implementación funcional para gcc / clang / ICC / otros compiladores con extensiones GNU.

Anteriormente, el acceso atómico a datos "sin formato" solo estaba disponible con algunas funciones específicas de la plataforma como LONG InterlockedExchange(LONG volatile *Target, LONG Value); o GNU C / C ++
type __atomic_add_fetch (type *ptr, type val, int memorder) (las mismas incorporaciones que las bibliotecas C ++ para GNU los compiladores usan para implementar std::atomic<T>.)

http: //www.open-std. org / jtc1 / sc22 / wg21 / docs / papers / 2018 / p0019r8.html incluye algunas cosas de introducción sobre la motivación. Las CPU pueden hacer esto fácilmente, los compiladores ya pueden hacerlo, y ha sido molesto que C ++ no haya expuesto esta capacidad de manera portátil.

Entonces, en lugar de tener que luchar con C ++ para obtener toda la asignación no atómica y la inicialización en un constructor, puede hacer que cada acceso cree un atomic_ref al elemento al que desea acceder. (Es gratis crear una instancia como local, al menos cuando no tiene bloqueos, en cualquier implementación "normal" de C ++).

Esto incluso te permitirá hacer cosas como cambiar el tamaño del std::vector<int> después de asegurarte de que ningún otro hilo esté accediendo a los elementos vectoriales o al bloque de control vector en sí. Y luego puede indicar a los otros hilos que se reanuden.

Aún no está implementado en libstdc ++ o libc ++ para gcc / clang.

#include <vector>
#include <atomic>

#define Foo std   // this atomic_ref.hpp puts it in namespace Foo, not std.
// current raw url for https://github.com/ORNL/cpp-proposals-pub/blob/master/P0019/atomic_ref.hpp
#include "https://raw.githubusercontent.com/ORNL/cpp-proposals-pub/580934e3b8cf886e09accedbb25e8be2d83304ae/P0019/atomic_ref.hpp"


void inc_element(std::vector<int> &v, size_t idx)
{
    v[idx]++;
}

void atomic_inc_element(std::vector<int> &v, size_t idx)
{
    std::atomic_ref<int> elem(v[idx]);
    static_assert(decltype(elem)::is_always_lock_free,
           "performance is going to suck without lock-free atomic_ref<T>");

    elem.fetch_add(1, std::memory_order_relaxed);  // take your pick of memory order here
}

Para x86-64, se compilan exactamente de la forma que esperamos con GCC, utilizando la implementación de muestra (para compiladores que implementan extensiones GNU) vinculada en la propuesta del grupo de trabajo de C ++. https://github.com/ORNL/cpp- propuestas-pub / blob / master / P0019 / atomic_ref.hpp

Desde el explorador del compilador Godbolt con g ++ 8.2 -Wall -O3 -std=gnu++2a :

inc_element(std::vector<int, std::allocator<int> >&, unsigned long):
    mov       rax, QWORD PTR [rdi]          # load the pointer member of std::vector
    add       DWORD PTR [rax+rsi*4], 1      # and index it as a memory destination
    ret

atomic_inc_element(std::vector<int, std::allocator<int> >&, unsigned long):
    mov       rax, QWORD PTR [rdi]
    lock add  DWORD PTR [rax+rsi*4], 1     # same but atomic RMW
    ret

La versión atómica es idéntica excepto que usa un prefijo lock para hacer que la lectura-modificación-escritura sea atómica, asegurándose de que ningún otro núcleo pueda leer o escribir la línea de caché mientras este núcleo está en medio de modificarlo atómicamente. En caso de que tenga curiosidad por saber cómo funcionan los atómicos en asm.

La mayoría de las ISA que no son x86 como AArch64, por supuesto, requieren un bucle de reintento LL / SC para implementar un RMW atómico, incluso con un orden de memoria relajado.

El punto aquí es que construir / destruir el atomic_ref no cuesta nada. Su puntero de miembro se optimiza completamente. Así que esto es exactamente tan barato como un vector<atomic<int>> , pero sin dolor de cabeza.

Siempre y cuando tenga cuidado de no crear UB de carrera de datos cambiando el tamaño del vector o accediendo a un elemento sin pasar por atomic_ref. (Se manifestaría potencialmente como un uso después de libre en muchas implementaciones reales si std :: vector reasignara la memoria en paralelo con otro hilo indexado en él, y por supuesto, estaría modificando atómicamente una copia obsoleta).

Esto definitivamente le da una cuerda para ahorcarse si no respeta cuidadosamente el hecho de que el objeto std::vector en sí mismo no es atómico, y también que el compilador no le impedirá realizar un acceso no atómico al { {X1}} después de que otros hilos hayan comenzado a usarlo.

4
Peter Cordes 6 feb. 2019 a las 07:21