¿Dónde está la cerradura para un std:: atomic?
Si una estructura de datos tiene varios elementos en ella, la versión atómica de la misma 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 usar 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 el atómico y foo son del mismo tamaño, no creo que se almacene una cerradura en el atómico.
Mi pregunta es:
Si una variable atómica utiliza un bloqueo, donde ¿se almacena y qué significa eso para múltiples instancias de esa variable ?
3 answers
La forma más fácil de responder a tales preguntas es generalmente simplemente mirar el conjunto resultante y tomarlo a partir de ahí.
Compilando lo siguiente (hice tu estructura más grande para esquivar las travesuras del compilador crafty):
#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 clang 5.0.0 se obtiene el siguiente sub-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 a un intrínseco (__atomic_store), que no nos dice lo que realmente está pasando aquí. Sin embargo, dado que el compilador es de código abierto, podemos fácilmente encontrar la implementación de lo 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 sucede en lock_for_pointer(), así que echémosle 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 átomo se utiliza para generar una clave hash para seleccionar un bloqueo pre-alocalizado.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-05-16 16:49:47
La implementación habitual es una tabla hash de mutexes (o incluso simples spinlocks sin un respaldo al sueño/despertar asistido por el sistema operativo), utilizando la dirección del objeto atómico como clave. La función hash puede 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 para que no obtenga automáticamente aliasing cuando los objetos están separados por 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 usan la misma función hash y tabla, por lo que están de acuerdo en qué bloqueo serializa el acceso a qué objeto. Sin embargo, 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 en qué nombres de función llamar, y es suficiente. (Pero tenga en cuenta que solo los objetos atómicos libres de bloqueo en la memoria compartida entre diferentes procesos funcionarán: cada proceso tiene su propia tabla hash de bloqueos. Se supone que los objetos sin bloqueo (y de hecho lo hacen) solo funcionan en memoria compartida en arquitecturas de CPU normales, incluso si la región está asignada a diferentes direcciones.)
Las colisiones Hash significan que dos objetos atómicos podrían compartir el mismo bloqueo. Esto no es un problema de corrección, pero podría ser una actuación problema: en lugar de dos pares de hilos que compiten por separado entre sí para dos objetos diferentes, podría tener los 4 hilos que compiten por el acceso a cualquiera de los objetos. Presumiblemente eso es inusual, y por lo general su objetivo es que sus objetos atómicos estén libres de bloqueo en las plataformas que te importan. Pero la mayoría de las veces no tienes mala suerte, y básicamente está bien.
Los bloqueos no son posibles porque no hay ninguna función std::atomic que intente tomar el bloqueo en dos objetos a la vez. Así que el código de la biblioteca que toma el candado nunca intenta tomar otro candado mientras sostiene uno de estos candados. La contención / serialización adicional no es un problema de corrección, solo de rendimiento.
X86-64 objetos de 16 bytes con GCC vs. MSVC :
Como hack, los compiladores pueden usar lock cmpxchg16b para implementar carga/almacenamiento atómico de 16 bytes, así como operaciones reales de lectura-modificación-escritura.
Esto es mejor que el bloqueo, pero tiene un mal rendimiento en comparación a objetos atómicos de 8 bytes (por ejemplo, cargas puras compiten con otras cargas). Es la única forma segura documentada de hacer algo atómicamente con 16 bytes1.
AFAIK, MSVC nunca usa lock cmpxchg16b para objetos de 16 bytes, y son básicamente lo mismo que un objeto de 24 o 32 bytes.
Gcc6 y líneas anteriores lock cmpxchg16b cuando compila con -mcx16 (cmpxchg16b desafortunadamente no es la línea base para x86-64; las CPU AMD K8 de primera generación no la tienen.)
Gcc7 decidió llamar siempre libatomic y nunca reportar objetos de 16 bytes como libres de bloqueo, a pesar de que las funciones libatomic todavía usarían lock cmpxchg16b en máquinas donde la instrucción está disponible. Vea is_lock_free() devolvió false después de actualizar a MacPorts gcc 7.3. El mensaje de la lista de correo gcc explicando este cambio está aquí.
Puede usar un union hack para obtener un contador ABA pointer+razonablemente barato en x86-64 con gcc/clang: ¿Cómo puedo implementar el contador ABA con CAS c++11?. lock cmpxchg16b para actualizaciones tanto del puntero como del contador, pero mov cargas simples de solo el puntero. Sin embargo, esto solo funciona si el objeto de 16 bytes está realmente libre de bloqueos usando lock cmpxchg16b.
Nota de pie de página 1: movdqa 16-la carga/almacenamiento de bytes es atómica en la práctica en algunas (pero no todas) microarquitecturas x86, y no hay una forma confiable o documentada de detectar cuándo es utilizable. Ver ¿Por qué la asignación de enteros en una variable alineada naturalmente es atómica en x86?, y ESS instrucciones: ¿qué CPU pueden hacer operaciones de memoria atómica 16B? para un ejemplo donde K10 Opteron muestra el desgarro en los límites 8B solo entre sockets con HyperTransport.
Así que los escritores de compiladores tienen que errar por el lado de la precaución y no pueden usar movdqa la forma en que usan SSE2 movq 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 atomic 16, 32 y 64 bytes alineados carga/almacenamiento vectorial (con SSE, AVX y AVX512). Tal vez los proveedores de mobo podrían desactivar el firmware en máquinas funky de muchos sockets que utilizan chips de pegamento de coherencia especiales que no transfieren líneas de caché enteras atómicamente.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-05-11 20:20:57
De 29.5.9 del estándar C++:
Nota: La representación de una especialización atómica no necesita tener la mismo tamaño que su tipo de argumento correspondiente. Especializaciones deben tener el mismo tamaño siempre que sea posible, ya que esto reduce el esfuerzo necesario para portar el código existente. - nota final
Es preferible hacer que el tamaño de un átomo sea el mismo que el tamaño de su tipo de argumento, aunque no es necesario. La manera de lograr esto es evitando bloqueos o almacenando las cerraduras en una estructura separada. Como las otras respuestas ya han explicado claramente, se usa una tabla hash para contener todos los bloqueos. Esta es la forma más eficiente de almacenar cualquier número de bloqueos para todos los objetos atómicos en uso.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-05-11 19:25:31