L'optimisation du compilateur casse le code multi-thread

Question

Après avoir appris à la dure que shared variables are currently not guarded by memory barriers, j'ai maintenant rencontré un autre problème. Soit je fais quelque chose de mal, soit l'optimisation de compilateur existante dans dmd peut casser le code multi-thread en réorganisant les lectures de variables shared.

À titre d'exemple, lorsque je compile un fichier exécutable avec dmd -O (optimisation complète), le compilateur permet d'optimiser joyeusement la variable locale o dans ce code (où cas est la fonction de comparaison et-swap de core.atomic)

shared uint cnt; 
void atomicInc () { uint o; do { o = cnt; } while (!cas(&cnt, o, o + 1));} 

à quelque chose comme cela (voir démontage ci-dessous):

shared uint cnt; 
void atomicInc () { while (!cas(&cnt, cnt, cnt + 1)) { } } 

Dans le code « optimisé » cnt est lue deux fois à partir de la mémoire, ainsi courir le risque qu'un autre thread a modifié cnt entre. L'optimisation détruit fondamentalement l'algorithme compare-and-swap.

Est-ce un bug ou existe-t-il un moyen correct d'obtenir le résultat souhaité? La seule solution que j'ai trouvée jusqu'ici est d'implémenter le code en utilisant l'assembleur.

code de test complet et les détails supplémentaires
Pour être complet, voici un code de test complet qui montre les deux questions (sans mémoire barrières, et le problème d'optimisation). Elle produit la sortie suivante sur trois machines Windows pour les DMD 2.049 et DMD 2.050 (en supposant que l'algorithme de Dekker n'interblocage pas, ce qui pourrait se produire):

dmd -O -run optbug.d 
CAS : failed 
Dekker: failed 

Et la boucle à l'intérieur atomicInc est compilée à cela avec plein optimisation:

; cnt is stored at 447C10h 
; while (!cas(&cnt, o, o + 1)) o = cnt; 
; 1) prepare call cas(&cnt, o, o + 1): &cnt and o go to stack, o+1 to eax 
402027: mov ecx,447C10h   ; ecx = &cnt 
40202C: mov eax,[447C10h]  ; eax = o1 = cnt 
402031: inc eax     ; eax = o1 + 1 (third parameter) 
402032: push ecx     ; push &cnt (first parameter) 
    ; next instruction pushes current value of cnt onto stack 
    ; as second parameter o instead of re-using o1 
402033: push [447C10h]  
402039: call 4020BC    ; 2) call cas  
40203E: xor al,1    ; 3) test success 
402040: jne 402027    ; no success try again 
; end of main loop 

Voici le code de test:

import core.atomic; 
import core.thread; 
import std.stdio; 

enum loops = 0xFFFF; 
shared uint cnt; 

/* ***************************************************************************** 
Implement atomicOp!("+=")(cnt, 1U); with CAS. The code below doesn't work with 
the "-O" compiler flag because cnt is read twice while calling cas and another 
thread can modify cnt in between. 
*/ 
enum threads = 8; 

void atomicInc () { uint o; do { o = cnt; } while (!cas(&cnt, o, o + 1));} 
void threadFunc () { foreach (i; 0..loops) atomicInc; } 

void testCas () { 
    cnt = 0; 
    auto tgCas = new ThreadGroup; 
    foreach (i; 0..threads) tgCas.create(&threadFunc); 
    tgCas.joinAll; 
    writeln("CAS : ", cnt == loops * threads ? "passed" : "failed"); 
} 

/* ***************************************************************************** 
Dekker's algorithm. Fails on ia32 (other than atom) because ia32 can re-order 
read before write. Most likely fails on many other architectures. 
*/ 
shared bool flag1 = false; 
shared bool flag2 = false; 
shared bool turn2 = false; // avoids starvation by executing 1 and 2 in turns 

void dekkerInc () { 
    flag1 = true; 
    while (flag2) if (turn2) { 
     flag1 = false; while (turn2) { /* wait until my turn */ } 
     flag1 = true; 
    } 
    cnt++;     // shouldn't work without a cast 
    turn2 = true; flag1 = false; 
} 

void dekkerDec () { 
    flag2 = true; 
    while (flag1) if (!turn2) { 
     flag2 = false; while (!turn2) { /* wait until my turn */ } 
     flag2 = true; 
    } 
    cnt--;     // shouldn't work without a cast 
    turn2 = false; flag2 = false; 
} 

void threadDekkerInc () { foreach (i; 0..loops) dekkerInc; } 
void threadDekkerDec () { foreach (i; 0..loops) dekkerDec; } 

void testDekker () { 
    cnt = 0; 
    auto tgDekker = new ThreadGroup; 
    tgDekker.create(&threadDekkerInc); 
    tgDekker.create(&threadDekkerDec); 
    tgDekker.joinAll; 
    writeln("Dekker: ", cnt == 0 ? "passed" : "failed"); 
} 

/* ************************************************************************** */ 
void main() { 
    testCas; 
    testDekker; 
} 

Answer 1

Alors que les problèmes semblent toujours exister, core.atomic expose maintenant atomicLoad, ce qui permet une solution de contournement relativement simple.Pour faire fonctionner l'exemple cas, il suffit de charger cnt atomiquement:

void atomicInc () { 
    uint o; 
    do { 
     o = atomicLoad(cnt); 
    } while (!cas(&cnt, o, o + 1)); 
} 

De même, pour faciliter le travail de l'algorithme de Dekker:

// ... 
while (atomicLoad(flag2)) if (turn2) { 
// ... 
while (atomicLoad(flag1)) if (!turn2) { 
// ... 

Pour les architectures autres que ia32 (en ignorant les opérations de chaîne et SSE) qui peut également re-commander

• lit par rapport à lit
• ou écrit rela tive à l'écrit
• ou écrit et lit au même emplacement mémoire

barrières de mémoire supplémentaires seraient nécessaires.

Answer 2

Oui, le code en assembleur. Si vous ignorez la fonction cas() et que vous écrivez simplement la totalité de votre fonction atomicInt dans l'assemblage, il ne vous reste plus que quelques lignes de code. Jusqu'à ce que vous le fassiez, vous allez probablement vous battre contre les optimisations du compilateur. En plus de tout cela, vous pouvez utiliser l'instruction x86 LOCK INC au lieu de CAS et vous devriez être capable de réduire la fonction à seulement une ligne ou deux d'assemblage.