c++ - tienda - ¿Por qué los compiladores no combinan escrituras std:: atomic redundantes?

lenguaje c++

Question

Me pregunto por qué los compiladores no están preparados para combinar escrituras consecutivas del mismo valor en una sola variable atómica, por ejemplo:

#include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
  y.store(1, order);
  y.store(1, order);
}

Cada compilador que he probado emitirá lo anterior escribe tres veces. ¿Qué observador legítimo y libre de carreras podría ver una diferencia entre el código anterior y una versión optimizada con una sola escritura (es decir, no se aplica la regla ''como si'')?

Si la variable hubiera sido volátil, obviamente no es aplicable ninguna optimización. ¿Qué es lo que lo impide en mi caso?

Aquí está el código en el explorador del compilador .

Answer 1

Caminemos un poco más lejos del caso patológico de las tres tiendas que están inmediatamente una al lado de la otra. Supongamos que se está realizando un trabajo no trivial entre las tiendas, y que ese trabajo no implica y en absoluto (por lo que el análisis de la ruta de datos puede determinar que las tres tiendas son de hecho redundantes, al menos dentro de este hilo), y no introduce barreras de memoria (para que otra cosa no obligue a las tiendas a ser visibles a otros hilos). Ahora es muy posible que otros subprocesos tengan la oportunidad de realizar el trabajo entre las tiendas, y quizás esos otros subprocesos manipulen y y que este subproceso tenga alguna razón para necesitar restablecerlo en 1 (la segunda tienda). Si se eliminaran las dos primeras tiendas, eso cambiaría el comportamiento.

Answer 2

Como se espera que las variables contenidas dentro de un objeto std :: atomic se accedan desde múltiples hilos, uno debe esperar que se comporten, como mínimo, como si estuvieran declaradas con la palabra clave volatile.

Esa era la práctica estándar y recomendada antes de que las arquitecturas de CPU introdujeran líneas de caché, etc.

[EDIT2] Se podría argumentar que std :: atomic <> son las variables volatile de la era de múltiples núcleos. Como se define en C / C ++, la volatile solo es lo suficientemente buena como para sincronizar las lecturas atómicas desde un solo hilo , con un ISR que modifica la variable (que en este caso es efectivamente una escritura atómica como se ve desde el hilo principal).

Personalmente me siento aliviado de que ningún compilador optimizaría las escrituras a una variable atómica. Si se optimiza la escritura, ¿cómo puede garantizar que cada una de estas escrituras podría ser vista por los lectores en otros subprocesos? No olvide que eso también es parte del contrato std :: atomic <>.

Considere esta pieza de código, donde el compilador podría afectar grandemente el resultado por una optimización salvaje.

#include <atomic>
#include <thread>

static const int N{ 1000000 };
std::atomic<int> flag{1};
std::atomic<bool> do_run { true };

void write_1()
{
    while (do_run.load())
    {
        flag = 1; flag = 1; flag = 1; flag = 1;
        flag = 1; flag = 1; flag = 1; flag = 1;
        flag = 1; flag = 1; flag = 1; flag = 1;
        flag = 1; flag = 1; flag = 1; flag = 1;
    }
}

void write_0()
{
    while (do_run.load())
    {
        flag = -1; flag = -1; flag = -1; flag = -1;
    }
}


int main(int argc, char** argv) 
{
    int counter{};
    std::thread t0(&write_0);
    std::thread t1(&write_1);

    for (int i = 0; i < N; ++i)
    {
        counter += flag;
        std::this_thread::yield();
    }

    do_run = false;

    t0.join();
    t1.join();

    return counter;
}

[EDITAR] Al principio, no estaba avanzando en que la volatile era fundamental para la implementación de atómicos, pero ...

Dado que parecía haber dudas sobre si la volatile tenía algo que ver con los atómicos, investigué el asunto. Aquí está la implementación atómica del stl VS2017. Como supuse, la palabra clave volátil está en todas partes.

// from file atomic, line 264...

        // TEMPLATE CLASS _Atomic_impl
template<unsigned _Bytes>
    struct _Atomic_impl
    {   // struct for managing locks around operations on atomic types
    typedef _Uint1_t _My_int;   // "1 byte" means "no alignment required"

    constexpr _Atomic_impl() _NOEXCEPT
        : _My_flag(0)
        {   // default constructor
        }

    bool _Is_lock_free() const volatile
        {   // operations that use locks are not lock-free
        return (false);
        }

    void _Store(void *_Tgt, const void *_Src, memory_order _Order) volatile
        {   // lock and store
        _Atomic_copy(&_My_flag, _Bytes, _Tgt, _Src, _Order);
        }

    void _Load(void *_Tgt, const void *_Src,
        memory_order _Order) const volatile
        {   // lock and load
        _Atomic_copy(&_My_flag, _Bytes, _Tgt, _Src, _Order);
        }

    void _Exchange(void *_Left, void *_Right, memory_order _Order) volatile
        {   // lock and exchange
        _Atomic_exchange(&_My_flag, _Bytes, _Left, _Right, _Order);
        }

    bool _Compare_exchange_weak(
        void *_Tgt, void *_Exp, const void *_Value,
        memory_order _Order1, memory_order _Order2) volatile
        {   // lock and compare/exchange
        return (_Atomic_compare_exchange_weak(
            &_My_flag, _Bytes, _Tgt, _Exp, _Value, _Order1, _Order2));
        }

    bool _Compare_exchange_strong(
        void *_Tgt, void *_Exp, const void *_Value,
        memory_order _Order1, memory_order _Order2) volatile
        {   // lock and compare/exchange
        return (_Atomic_compare_exchange_strong(
            &_My_flag, _Bytes, _Tgt, _Exp, _Value, _Order1, _Order2));
        }

private:
    mutable _Atomic_flag_t _My_flag;
    };

Todas las especializaciones en MS stl utilizan volatile en las funciones clave.

Aquí está la declaración de una de esas funciones clave:

 inline int _Atomic_compare_exchange_strong_8(volatile _Uint8_t *_Tgt, _Uint8_t *_Exp, _Uint8_t _Value, memory_order _Order1, memory_order _Order2)

Notará que es necesario volatile uint8_t*mantener el valor contenido en std :: atomic. Este patrón se puede observar a lo largo de la implementación de MS std :: atomic <>. Aquí no hay ninguna razón para que el equipo de gcc, ni ningún otro proveedor de stl lo haya hecho de manera diferente.

Answer 3

El escritor del compilador no puede simplemente realizar la optimización. También deben convencerse a sí mismos de que la optimización es válida en las situaciones en las que el escritor del compilador pretende aplicarlo, que no se aplicará en situaciones donde no es válida, que no rompe el código que de hecho está roto, pero " Funciona "en otras implementaciones. Esto es probablemente más trabajo que la optimización en sí.

Por otro lado, podría imaginar que en la práctica (es decir, en programas que deben realizar un trabajo y no en puntos de referencia), esta optimización ahorrará muy poco tiempo de ejecución.

Entonces, un escritor de compiladores analizará el costo, luego analizará los beneficios y los riesgos, y probablemente decidirá no hacerlo.

Answer 4

En resumen, debido a que el estándar (por ejemplo, los paragaraphs alrededor y por debajo de 20 en [intro.multithread] ) no lo permite.

Hay garantías antes de suceder que deben cumplirse y que, entre otras cosas, excluyen las reordenadas o las escrituras unidas (el párrafo 19 incluso lo dice explícitamente acerca de la reordenación).

Si su hilo escribe tres valores en la memoria (digamos 1, 2 y 3) uno tras otro, un hilo diferente puede leer el valor. Si, por ejemplo, su hilo se interrumpe (o incluso si se ejecuta simultáneamente) y otro hilo también escribe en esa ubicación, entonces el hilo de observación debe ver las operaciones exactamente en el mismo orden en que ocurren (ya sea por programación o por coincidencia, o cualquier razón). Eso es una garantía.

¿Cómo es esto posible si solo haces la mitad de las escrituras (o incluso solo una)? No lo es

¿Qué pasa si tu hilo escribe 1 -1 -1 pero otro escribe esporádicamente 2 o 3? ¿Qué sucede si un tercer hilo observa la ubicación y espera un valor en particular que nunca aparece porque está optimizado?

Es imposible proporcionar las garantías que se dan si las tiendas (y las cargas, también) no se realizan según lo solicitado. Todos ellos, y en el mismo orden.

Answer 5

Los estándares C ++ 11 / C ++ 14 tal como están escritos permiten que las tres tiendas se plieguen / unan en una tienda del valor final. Incluso en un caso como este:

  y.store(1, order);
  y.store(2, order);
  y.store(3, order); // inlining + constant-folding could produce this in real code

La norma no garantiza que un observador que gire en y (con una carga atómica o CAS) verá alguna vez y == 2 . Un programa que dependiera de esto tendría un error en la carrera de datos, pero solo el tipo de raza de error de variedad de jardín, no el tipo de carrera de datos del comportamiento indefinido de C ++. (Es UB solo con variables no atómicas). Un programa que espera verlo a veces no es necesariamente incluso defectuoso. (Ver abajo re: barras de progreso).

Cualquier orden que sea posible en la máquina abstracta de C ++ se puede seleccionar (en tiempo de compilación) como la ordenación que siempre sucederá . Esta es la regla como si en acción. En este caso, es como si los tres almacenes ocurrieran seguidos en el orden global, sin que ocurrieran cargas o almacenes de otros subprocesos entre y=1 y y=3 .

No depende de la arquitectura o hardware de destino; al igual que en tiempo de compilación, se permite el reordenamiento de operaciones atómicas relajadas incluso cuando se dirige a x86 fuertemente ordenado. El compilador no tiene que preservar nada de lo que podría esperar al pensar en el hardware que está compilando, por lo que necesita barreras. Las barreras pueden compilarse en cero instrucciones asm.

Entonces, ¿por qué los compiladores no hacen esta optimización?

Es un problema de calidad de implementación y puede cambiar el rendimiento / comportamiento observado en el hardware real.

El caso más obvio donde es un problema es una barra de progreso . Agarrar las tiendas fuera de un bucle (que no contiene otras operaciones atómicas) y juntarlas todas en una resultaría en una barra de progreso que se quedaría en 0 y luego iría al 100% justo al final.

No hay una forma std::atomic C ++ 11 std::atomic para impedir que lo hagan en los casos en que no lo desea, por lo que, por ahora, los compiladores simplemente eligen nunca unir varias operaciones atómicas en una sola. (Unirlos a todos en una sola operación no cambia su orden entre sí).

Los compiladores y escritores han notado correctamente que los programadores esperan que una tienda atómica pase a la memoria cada vez que la fuente hace y.store() . (Vea la mayoría de las otras respuestas a esta pregunta, que afirman que las tiendas deben suceder por separado debido a los posibles lectores que esperan ver un valor intermedio). Es decir, viola el principio de menos sorpresa .

Sin embargo, hay casos en los que sería muy útil, por ejemplo, evitar el inútil shared_ptr ref count inc / dec en un bucle.

Obviamente, cualquier reordenamiento o unión no puede violar ninguna otra regla de pedido. Por ejemplo, num++; num--; num++; num--; aún tendría que ser una barrera total para el tiempo de ejecución y el reordenamiento en tiempo de compilación, incluso si ya no tocaba la memoria en num .

Se está llevando a cabo una discusión para extender la API std::atomic para que los programadores puedan controlar tales optimizaciones, en cuyo punto los compiladores podrán optimizar cuando sea útil, lo que puede suceder incluso en un código escrito cuidadosamente que no sea intencionalmente ineficaz. Algunos ejemplos de casos útiles para la optimización se mencionan en los siguientes enlaces de discusión / propuesta de grupos de trabajo:

• http://wg21.link/n4455 : N4455 Ningún compilador sane optimizaría la atómica
• http://wg21.link/p0062 : WG21 / P0062R1: ¿Cuándo deberían los compiladores optimizar los atómicos?

Consulte también la discusión sobre este mismo tema en la respuesta de Richard Hodges a ¿Puede num ++ ser atómico para ''int num''? (ver los comentarios). Ver también la última sección de mi respuesta a la misma pregunta, donde sostengo con más detalle que esta optimización está permitida. (Dejándolo corto aquí, porque los enlaces de los grupos de trabajo de C ++ ya reconocen que el estándar actual tal como está escrito lo permite, y que los compiladores actuales simplemente no se optimizan a propósito).

Dentro de la norma actual, volatile atomic<int> y sería una forma de garantizar que no se permita la optimización de las tiendas. (Como señala Herb Sutter en una respuesta SO , volatile y atomic ya comparten algunos requisitos, pero son diferentes). Vea también la relación de std::memory_order con volatile en cppreference.

Los accesos a objetos volatile no pueden optimizarse (porque podrían ser registros IO asignados en memoria, por ejemplo).

No cambie todas sus variables atomic a volatile atomic todavía; el comité de normas podría elegir otra cosa (ya que el volatile atomic es feo y abusa del significado de volatile ). Creo que podemos estar seguros de que los compiladores no comenzarán a hacer esta optimización hasta que haya una manera de controlarla. Con suerte, será un tipo de memory_order_release_coalesce (como memory_order_release_coalesce ) que no cambie el comportamiento del código existente C ++ memory_order_release_coalesce cuando se compila como C ++. Pero podría ser como la propuesta en wg21 / p0062, etiquetar los casos de no optimización con [[brittle_atomic]] .

wg21 / p0062 advierte que incluso el volatile atomic no resuelve todo, y desalienta su uso para este propósito . Da este ejemplo:

if(x) {
    foo();
    y.store(0);
} else {
    bar();
    y.store(0);  // release a lock before a long-running loop
    for() {...} // loop contains no atomics or volatiles
}
// A compiler can merge the stores into a y.store(0) here.

Incluso con volatile atomic<int> y , se permite que un compilador y.store() del if/else y lo haga solo una vez, porque todavía está haciendo exactamente 1 tienda con el mismo valor. (Que sería después del bucle largo en la rama else).

volatile detiene la fusión analizada en la pregunta, pero esto indica que otras optimizaciones en atomic<> también pueden ser problemáticas para el rendimiento real.

Otras razones para no optimizar incluyen: nadie escribió el código complicado que permitiría al compilador realizar estas optimizaciones de forma segura (sin que nunca se equivoque). Esto no es suficiente, porque N4455 dice que LLVM ya implementa o podría implementar fácilmente varias de las optimizaciones que mencionó.

Sin embargo, la razón confusa para los programadores es ciertamente plausible. El código sin bloqueo es lo suficientemente difícil como para escribirlo correctamente en primer lugar.

No sea casual en su uso de armas atómicas: no son baratas y no optimizan mucho (actualmente no lo son). Sin embargo, no siempre es fácil evitar operaciones atómicas redundantes con std::shared_ptr<T> , ya que no hay una versión no atómica de la misma (aunque una de las respuestas aquí ofrece una manera fácil de definir un shared_ptr_unsynchronized<T> para gcc ).

Answer 6

Mientras cambia el valor de un atómico en un subproceso, es posible que otro subproceso lo compruebe y realice una operación basada en el valor del atómico. El ejemplo que dio es tan específico que los desarrolladores de compiladores no consideran que valga la pena optimizarlo. Sin embargo, si un hilo está estableciendo, por ejemplo, valores consecutivos para un atómico: 0 , 1 , 2 , etc., el otro hilo puede poner algo en las ranuras indicadas por el valor del atómico.

Answer 7

NB: Iba a comentar esto pero es un poco demasiado prolijo.

Un hecho interesante es que este comportamiento no está en los términos de C ++ en una carrera de datos.

La nota 21 en la p.14 es interesante: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf (mi énfasis):

La ejecución de un programa contiene una carrera de datos si contiene dos acciones en conflicto en subprocesos diferentes, al menos una de las cuales no es atómica.

También en la p.11 nota 5:

Las operaciones atómicas "relajadas" no son operaciones de sincronización, aunque, como las operaciones de sincronización, no pueden contribuir a las carreras de datos.

Por lo tanto, una acción conflictiva en un atómico nunca es una carrera de datos, en términos del estándar C ++.

¡Todas estas operaciones son atómicas (y específicamente relajadas) pero no hay carrera de datos aquí!

Estoy de acuerdo en que no hay una diferencia confiable / predecible entre estos dos en cualquier plataforma (razonable):

include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
  y.store(1, order);
  y.store(1, order);
}

y

include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
}

Pero dentro de la definición proporcionada en el modelo de memoria C ++ no es una carrera de datos.

No entiendo fácilmente por qué se proporciona esa definición, pero le da al desarrollador algunas tarjetas para que se involucre en una comunicación aleatoria entre hilos que pueden saber (en su plataforma) funcionará estadísticamente.

Por ejemplo, establecer un valor 3 veces y luego leerlo de nuevo mostrará cierto grado de contención para esa ubicación. Tales enfoques no son deterministas pero muchos algoritmos concurrentes efectivos no son deterministas. Por ejemplo, un try_lock_until() agotado en el try_lock_until() es siempre una condición de carrera pero sigue siendo una técnica útil.

Lo que parece que el C ++ Standard le brinda certeza con respecto a las "carreras de datos", pero permite ciertas diversiones y juegos con condiciones de carrera que en el análisis final son diferentes.

En resumen, la norma parece especificar que cuando otras hebras pueden ver el efecto de "martilleo" de un valor que se establece 3 veces, otras hebras deben poder ver ese efecto (¡incluso si a veces no!). Es el caso donde casi todas las plataformas modernas que otros hilos pueden, bajo ciertas circunstancias, ver el martilleo.

Answer 8

Te refieres a la eliminación de tiendas muertas.

No está prohibido eliminar una tienda muerta atómica, pero es más difícil probar que una tienda atómica califica como tal.

Las optimizaciones tradicionales del compilador, como la eliminación del almacén muerto, se pueden realizar en operaciones atómicas, incluso en secuencias coherentes.
Los optimizadores deben tener cuidado de evitar hacerlo en los puntos de sincronización, ya que otro hilo de ejecución puede observar o modificar la memoria, lo que significa que las optimizaciones tradicionales deben tener en cuenta más instrucciones de las que deberían al considerar optimizaciones para operaciones atómicas.
En el caso de la eliminación de la tienda muerta, no es suficiente demostrar que una tienda atómica domina y alias a otra para eliminar la otra tienda.

^{de N4455 No Sane Compiler Optimiza Atomics}

El problema de la DSE atómica, en el caso general, es que implica buscar puntos de sincronización, en mi entendimiento, este término significa puntos en el código donde hay una relación antes- suceso entre una instrucción en un hilo A y una instrucción en otro hilo B .

Considere este código ejecutado por un hilo A:

y.store(1, std::memory_order_seq_cst);
y.store(2, std::memory_order_seq_cst);
y.store(3, std::memory_order_seq_cst);

¿Se puede optimizar como y.store(3, std::memory_order_seq_cst) ?

Si un subproceso B está esperando ver y = 2 (por ejemplo, con un CAS), nunca observará que si el código se optimiza.

Sin embargo, a mi entender, tener B looping y CASsing en y = 2 es una carrera de datos ya que no hay un orden total entre las instrucciones de los dos hilos.
Una ejecución en la que las instrucciones de A se ejecutan antes de que el bucle de B sea observable (es decir, permitido) y, por lo tanto, el compilador puede optimizar para y.store(3, std::memory_order_seq_cst) .

Si los subprocesos A y B están sincronizados, de alguna manera, entre las tiendas en el subproceso A, la optimización no se permitiría (se induciría un orden parcial, posiblemente llevando a B a observar potencialmente y = 2 ).

Probar que no existe tal sincronización es difícil, ya que implica considerar un alcance más amplio y tener en cuenta todas las peculiaridades de una arquitectura.

En cuanto a mi comprensión, debido a la edad relativamente pequeña de las operaciones atómicas y la dificultad de razonar sobre el orden de memoria, la visibilidad y la sincronización, los compiladores no realizan todas las optimizaciones posibles en atómica hasta un marco más sólido para detectar y comprender lo necesario. Se construyen condiciones.

Creo que su ejemplo es una simplificación del subproceso de conteo dado anteriormente, ya que no tiene ningún otro subproceso o punto de sincronización, por lo que puedo ver, supongo que el compilador podría haber optimizado las tres tiendas.

Answer 9

Un caso de uso práctico para el patrón, si el hilo hace algo importante entre las actualizaciones que no dependen de o modifican y , podría ser: * El hilo 2 lee el valor de y para verificar cuánto progreso ha hecho el hilo 1 ».

Por lo tanto, tal vez Thread 1 deba cargar el archivo de configuración como paso 1, colocar su contenido analizado en una estructura de datos como paso 2 y mostrar la ventana principal como paso 3, mientras Thread 2 está esperando en el paso 2 para completar. Realizar otra tarea en paralelo que dependa de la estructura de datos. (Concedido, este ejemplo requiere la semántica de adquisición / liberación, no un pedido relajado).

Estoy bastante seguro de que una implementación conforme permite que el subproceso 1 no actualice y en cualquier paso intermedio, aunque no he revisado el estándar de idioma, me sorprendería si no fuera compatible con hardware en el que tal vez no vea otro sondeo de subprocesos el valor 2.

Sin embargo, esa es una instancia hipotética en la que podría ser pessimal optimizar las actualizaciones de estado. Tal vez un desarrollador de compiladores vendrá aquí y dirá por qué ese compilador optó por no hacerlo, pero una posible razón es dejar que te dispares en el pie o, al menos, te pegues en el dedo.