Résultats incohérents avec GCC > 5

[efournival]

Dans le cadre de mon TER (travail d'étude et de recherche), je dois distribuer le calcul effectué par NumericMonoid sur plusieurs machines. C'est codé en Go et fait appel à des bindings Go <-> C/C++ afin d'appeler le code original optimisé et laisser la partie distribution à un langage plus haut niveau. Le dépôt est ici.

En mettant en place des tests unitaires, j'ai remarqué que les résultats renvoyés étaient incohérents. Voici ce qui se passe quand on compile avec GCC 5 :

edgar@arch:~/sources/NumericMonoid/src/Cilk++$ g++-5 --version
g++-5 (GCC) 5.4.0
[...]
edgar@arch:~/sources/NumericMonoid/src/Cilk++$ CXX=g++-5 make MAX_GENUS=40
[...]
edgar@arch:~/sources/NumericMonoid/src/Cilk++$ ./treewalk 
Computing number of numeric monoids for genus <= 40 using 8 workers

============================

1 2 4 7 12 23 39 67 118 204 343 592 1001 1693 2857 4806 8045 13467 22464 37396 62194 103246 170963 282828 467224 770832 1270267 2091030 3437839 5646773 9266788 15195070 24896206 40761087 66687201 109032500 178158289 290939807 474851445 774614284 
Total = 1998799014, computation time = 2.844 s.

Par contre, avec GCC 6 :

edgar@arch:~/sources/NumericMonoid/src/Cilk++$ make clean
rm -rf treewalk *.o build cysignals numeric_monoid.so numeric_monoid.html numeric_monoid.cpp
edgar@arch:~/sources/NumericMonoid/src/Cilk++$ g++ --version
g++ (GCC) 6.3.1 20170109
[...]
edgar@arch:~/sources/NumericMonoid/src/Cilk++$ make MAX_GENUS=40
[...]
edgar@arch:~/sources/NumericMonoid/src/Cilk++$ ./treewalk 
Computing number of numeric monoids for genus <= 40 using 8 workers

============================

1 2 4 8 16 28 50 82 114 140 155 151 143 114 89 82 89 95 131 166 251 325 314 385 373 311 237 164 160 178 621 4322 29007 156432 692222 2584594 8346052 23813846 61202249 144172201 
Total = 241005904, computation time = 1.658 s.
edgar@arch:~/sources/NumericMonoid/src/Cilk++$ ./treewalk 
Computing number of numeric monoids for genus <= 40 using 8 workers

============================

1 2 4 8 16 28 49 66 106 139 223 323 418 386 355 360 386 445 448 376 328 307 380 417 418 431 434 496 538 599 1238 5484 32210 166379 720544 2656001 8506744 24141454 61816530 145247558 
Total = 243302629, computation time = 1.663 s.
edgar@arch:~/sources/NumericMonoid/src/Cilk++$ ./treewalk 
Computing number of numeric monoids for genus <= 40 using 8 workers

============================

1 2 4 8 16 31 58 89 132 151 200 249 333 433 490 635 711 722 670 708 731 714 648 567 486 456 492 539 581 334 633 4295 28940 156353 692145 2584508 8345992 23813813 61202227 144172183 
Total = 241012280, computation time = 1.664 s.

Les résultats semblent aléatoires et il est intéressant de constater que le temps de calcul est fortement réduit. À noter que le problème ne se pose pas lorsque l'on passe -n 1 en argument.

J'ai pris le temps de tester à l'aide de GCC 7 (7.0.1 20170307), on obtient le même comportement.

objdump_treewalk_gcc5.txt
objdump_treewalk_gcc6.txt
perf_data_treewalk_gcc5.txt
perf_data_treewalk_gcc6.txt

CC @hivert @jfromentin

[efournival]

En utilisant cette manière de calculer le total :

init_full_N(N);
list_children(N, MAX_GENUS);
cout << "Total = " << cilk_list_results.get_value().size();

Voici la sortie sous GCC 5 :

edgar@archtop:~/sources/NumericMonoid/src/Cilk++$ ./treewalk 
Computing number of numeric monoids for genus <= 30 using 4 workers
Total = 5646773, computation time = 0.7987 s.
edgar@archtop:~/sources/NumericMonoid/src/Cilk++$ ./treewalk 
Computing number of numeric monoids for genus <= 30 using 4 workers
Total = 5646773, computation time = 0.7977 s.
edgar@archtop:~/sources/NumericMonoid/src/Cilk++$ ./treewalk -n 1
Computing number of numeric monoids for genus <= 30 using 1 workers
Total = 5646773, computation time = 2.381 s.

Sous GCC 6 :

edgar@archtop:~/sources/NumericMonoid/src/Cilk++$ ./treewalk 
Computing number of numeric monoids for genus <= 30 using 4 workers
Total = 937, computation time = 0.0007016 s.
edgar@archtop:~/sources/NumericMonoid/src/Cilk++$ ./treewalk 
Computing number of numeric monoids for genus <= 30 using 4 workers
Total = 898, computation time = 0.0005886 s.
edgar@archtop:~/sources/NumericMonoid/src/Cilk++$ ./treewalk -n 1
Computing number of numeric monoids for genus <= 30 using 1 workers
Total = 5646773, computation time = 2.39 s.

Et... sous GCC 7 :

edgar@archtop:~$ ./treewalk 
Computing number of numeric monoids for genus <= 30 using 4 workers
Total = 5646773, computation time = 0.7866 s.
edgar@archtop:~$ ./treewalk 
Computing number of numeric monoids for genus <= 30 using 4 workers
Total = 5646773, computation time = 0.7915 s.
edgar@archtop:~$ ./treewalk -n 1
Computing number of numeric monoids for genus <= 30 using 1 workers
Total = 5646773, computation time = 2.395 s.

Pour rappel, voici la sortie du programme original compilé à l'aide de GCC 7 :

edgar@archtop:~$ ./treewalk 
Computing number of numeric monoids for genus <= 30 using 4 workers

============================

1 2 4 8 14 22 33 45 59 67 71 77 100 118 141 181 216 245 259 258 412 1402 5662 19837 58682 150861 348147 741916 1492326 2877609 
Total = 5698775, computation time = 0.07317 s.
edgar@archtop:~$ ./treewalk 
Computing number of numeric monoids for genus <= 30 using 4 workers

============================

1 2 4 8 14 23 35 47 59 67 82 105 140 207 258 334 456 619 857 1096 1489 2729 7104 21080 59635 151541 348558 742105 1492268 2877545 
Total = 5708468, computation time = 0.07196 s.
edgar@archtop:~$ ./treewalk -n 1
Computing number of numeric monoids for genus <= 30 using 1 workers

============================

1 2 4 7 12 23 39 67 118 204 343 592 1001 1693 2857 4806 8045 13467 22464 37396 62194 103246 170963 282828 467224 770832 1270267 2091030 3437839 5646773 
Total = 14396337, computation time = 0.1374 s.

[efournival]

La correction de ce bug a été de passer le monoïde par valeur (avec une copie) plutôt que par référence. En effet, il peut s'agir d'un problème de synchronisation (la valeur est modifiée autre part) ou d'optimisation, introduit dans GCC 6.

Ceci induit donc des copies supplémentaires et augmente le temps de calcul total d'environ 5 %.

S'agissant probablement d'un bug de GCC ou de Cilk, l'objectif est de circonscrire le problème sur un exemple simple afin de le soumettre au bugtracker de GCC par exemple.