when - atomic c++

¿Dónde está la cerradura para un std:: atomic?

Question

Si una estructura de datos tiene varios elementos, su versión atómica no puede (siempre) estar libre de bloqueos. Me dijeron que esto es cierto para los tipos más grandes porque la CPU no puede cambiar atómicamente los datos sin utilizar algún tipo de bloqueo.

por ejemplo:

#include <iostream>
#include <atomic>

struct foo {
    double a;
    double b;
};

std::atomic<foo> var;

int main()
{
    std::cout << var.is_lock_free() << std::endl;
    std::cout << sizeof(foo) << std::endl;
    std::cout << sizeof(var) << std::endl;
}

La salida (Linux / gcc) es:

0
16
16

Dado que atomic y foo son del mismo tamaño, no creo que haya un bloqueo almacenado en el atomic.

Mi pregunta es:
Si una variable atómica usa un bloqueo, ¿dónde se almacena y qué significa eso para varias instancias de esa variable?

Answer 1

A partir del 29.5.9 del estándar C ++:

Nota: La representación de una especialización atómica no necesita tener el mismo tamaño que su tipo de argumento correspondiente. Las especializaciones deben tener el mismo tamaño siempre que sea posible, ya que esto reduce el esfuerzo requerido para portar el código existente. - nota final

Es preferible hacer que el tamaño de un atómico sea igual al tamaño de su tipo de argumento, aunque no es necesario. La forma de lograr esto es evitando bloqueos o almacenando los bloqueos en una estructura separada. Como las otras respuestas ya han explicado claramente, se utiliza una tabla hash para mantener todos los bloqueos. Esta es la forma más eficiente en memoria de almacenar cualquier número de bloqueos para todos los objetos atómicos en uso.

Answer 2

La forma más fácil de responder a estas preguntas es, en general, solo mirar el ensamblaje resultante y tomarlo desde allí.

Compilando lo siguiente (hice tu estructura más grande para esquivar los chanchullos del compilador):

#include <atomic>

struct foo {
    double a;
    double b;
    double c;
    double d;
    double e;
};

std::atomic<foo> var;

void bar()
{
    var.store(foo{1.0,2.0,1.0,2.0,1.0});
}

En el lenguaje lógico 5.0.0 se obtiene lo siguiente debajo de -O3: ver en godbolt

bar(): # @bar()
  sub rsp, 40
  movaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [1.000000e+00,2.000000e+00]
  movaps xmmword ptr [rsp], xmm0
  movaps xmmword ptr [rsp + 16], xmm0
  movabs rax, 4607182418800017408
  mov qword ptr [rsp + 32], rax
  mov rdx, rsp
  mov edi, 40
  mov esi, var
  mov ecx, 5
  call __atomic_store

Genial, el compilador delega en un intrínseco ( __atomic_store ), eso no nos dice lo que realmente está sucediendo aquí. Sin embargo, dado que el compilador es de código abierto, podemos encontrar fácilmente la implementación del intrínseco (lo encontré en https://github.com/llvm-mirror/compiler-rt/blob/master/lib/builtins/atomic.c ):

void __atomic_store_c(int size, void *dest, void *src, int model) {
#define LOCK_FREE_ACTION(type) /
    __c11_atomic_store((_Atomic(type)*)dest, *(type*)dest, model);/
    return;
  LOCK_FREE_CASES();
#undef LOCK_FREE_ACTION
  Lock *l = lock_for_pointer(dest);
  lock(l);
  memcpy(dest, src, size);
  unlock(l);
}

Parece que la magia ocurre en lock_for_pointer() , así que lock_for_pointer() un vistazo:

static __inline Lock *lock_for_pointer(void *ptr) {
  intptr_t hash = (intptr_t)ptr;
  // Disregard the lowest 4 bits.  We want all values that may be part of the
  // same memory operation to hash to the same value and therefore use the same
  // lock.  
  hash >>= 4;
  // Use the next bits as the basis for the hash
  intptr_t low = hash & SPINLOCK_MASK;
  // Now use the high(er) set of bits to perturb the hash, so that we don''t
  // get collisions from atomic fields in a single object
  hash >>= 16;
  hash ^= low;
  // Return a pointer to the word to use
  return locks + (hash & SPINLOCK_MASK);
}

Y aquí está nuestra explicación: la dirección del atómico se utiliza para generar una clave hash para seleccionar un bloqueo pre-asignado.

Answer 3

La implementación habitual es una tabla hash de mutexes (o incluso simples cierres giratorios sin un retroceso al sueño / activación asistida por el sistema operativo), utilizando la dirección del objeto atómico como clave . La función hash podría ser tan simple como usar los bits bajos de la dirección como un índice en una matriz de tamaño de potencia de 2, pero la respuesta de @ Frank muestra que la implementación std :: atomic de LLVM hace XOR en algunos bits más altos, por lo que no lo hace. t Obtiene automáticamente el alias cuando los objetos están separados por una gran potencia de 2 (que es más común que cualquier otro arreglo aleatorio).

Creo (pero no estoy seguro) que g ++ y clang ++ son compatibles con ABI; es decir, que utilizan la misma función y tabla hash, por lo que acuerdan qué bloqueo serializa el acceso a qué objeto. libatomic embargo, todo el bloqueo se realiza en libatomic , por lo que si vincula dinámicamente libatomic , todo el código dentro del mismo programa que llama a __atomic_store_16 usará la misma implementación; clang ++ y g ++ definitivamente están de acuerdo con los nombres de las funciones a llamar, y eso es suficiente. (Pero tenga en cuenta que solo funcionarán los objetos atómicos sin bloqueo en la memoria compartida entre diferentes procesos: cada proceso tiene su propia tabla hash de bloqueos . Se supone que los objetos sin bloqueo deben (y de hecho lo hacen) Simplemente Trabajar en la memoria compartida en la CPU normal arquitecturas, incluso si la región está asignada a direcciones diferentes.)

Las colisiones de hash significan que dos objetos atómicos pueden compartir el mismo bloqueo. Este no es un problema de corrección, pero podría ser un problema de rendimiento : en lugar de dos pares de subprocesos que compiten entre sí por dos objetos diferentes, puede tener los 4 subprocesos compitiendo para acceder a cualquiera de los objetos. Es de suponer que eso es inusual y, por lo general, apunta a que sus objetos atómicos estén libres de bloqueos en las plataformas que le interesan. Pero la mayoría de las veces no tienes mala suerte, y está básicamente bien.

Los interbloqueos no son posibles porque no hay ninguna función std::atomic que intente bloquear los dos objetos a la vez. Por lo tanto, el código de la biblioteca que toma el bloqueo nunca intenta tomar otro bloqueo mientras mantiene uno de estos bloqueos. La contención / serialización adicional no es un problema de corrección, solo el rendimiento.

Objetos x86-64 de 16 bytes con GCC frente a MSVC :

Como hack, los compiladores pueden usar el lock cmpxchg16b para implementar la carga / almacenamiento atómico de 16 bytes, así como las operaciones reales de lectura-modificación-escritura.

Esto es mejor que el bloqueo, pero tiene un mal rendimiento en comparación con los objetos atómicos de 8 bytes (por ejemplo, las cargas puras compiten con otras cargas). Es la única forma segura documentada de hacer atómicamente cualquier cosa con 16 bytes ¹ .

AFAIK, MSVC nunca usa el lock cmpxchg16b para lock cmpxchg16b de 16 bytes, y son básicamente lo mismo que un objeto de 24 o 32 bytes.

gcc6 y el lock cmpxchg16b línea anterior lock cmpxchg16b cuando compilas con -mcx16 (cmpxchg16b lamentablemente no es la línea de base para x86-64; a la CPU AMD K8 de primera generación le falta).

gcc7 decidió llamar siempre a libatomic y nunca reportar objetos de 16 bytes como libres de bloqueo, incluso aunque las funciones libatomic aún usarían el lock cmpxchg16b en máquinas donde la instrucción esté disponible. Ver is_lock_free () devuelto falso después de actualizar a MacPorts gcc 7.3 . El mensaje de la lista de correo de gcc que explica este cambio está aquí .

Puede usar un hack de unión para obtener un puntero ABA + contador razonablemente barato en x86-64 con gcc / clang: ¿Cómo puedo implementar el contador ABA con c ++ 11 CAS? . lock cmpxchg16b para actualizaciones de puntero y contador, pero simplemente mov cargas del puntero. Sin embargo, esto solo funciona si el objeto de 16 bytes en realidad está libre de lock cmpxchg16b utilizando el lock cmpxchg16b .

Nota al pie 1 : movdqa 16 bytes de carga / almacenamiento es atómico en la práctica en algunas (pero no en todas) las microarquitecturas x86, y no hay una forma confiable o documentada de detectar cuándo es utilizable. Consulte ¿Por qué la asignación de enteros en una variable naturalmente alineada es atómica en x86? , e instrucciones de SSE: ¿qué CPU pueden realizar operaciones atómicas de memoria 16B? para un ejemplo donde K10 Opteron muestra rasgado en 8B límites solo entre sockets con HyperTransport.

Por lo tanto, los escritores de compiladores tienen que errar por el lado de la precaución y no pueden usar movdqa la manera en que usan movq SSE2 para carga / almacenamiento atómico de 8 bytes en código de 32 bits. Sería genial si los proveedores de CPU pudieran documentar algunas garantías para algunas microarquitecturas, o agregar bits de características de CPUID para carga / almacenamiento vectorial atómica de 16, 32 y 64 bytes (con SSE, AVX y AVX512). Tal vez los proveedores de mobo podrían deshabilitar el firmware en máquinas funky de muchos zócalos que utilizan chips de pegamento de coherencia especial que no transfieren atómicamente líneas de caché completas.