Résoudre le cube-serpent 300 fois plus rapidement en C
18 Oct 2011Il y a 3 semaines, j’avais écrit un solveur de cube-serpent en Python.
Un commentaire, en apparence anodin, m’a mis dans la tête une question que je ne pouvais pas laisser sans réponse : combien de fois plus rapidement s’exécuterait le même algorithme implémenté en C que celui en Python (interprêté) ? 2× ? 10× ? 50× ?
Pour y répondre, il fallait donc implémenter le même algorithme en C. En plus, c’était l’occasion de rendre hommage à Dennis Ritchie. Après avoir découvert Python, j’ai donc (ré)appris le C (et ça fait drôle de rejouer avec les pointeurs après plusieurs années !).
Implémentation
Je ne vais pas m’attarder sur l’algorithme, c’est exactement le même principe que sur mon billet précédent, et j’ai essayé de garder les mêmes noms de fonctions.
La structure du cube et ses dimensions (à modifier selon votre cube-serpent)
sont définies par macros (les fameux #define). Par rapport au programme
Python, il faut en plus préciser la taille des tableaux.
La seule partie que j’ai réimplémentée complètement différemment est la fonction
get_useful_points de la version Python (souvenez-vous, avec des yields
dans une fonction récursive). La fonction équivalente dans la version C
s’appelle symmetry_helper_inc_cursor(int cursor[]) : au lieu de retourner au
fur et à mesure chacun des points à traiter, elle donne le point “suivant” de
celui passé en paramètre.
De même, les solutions trouvées sont données dans un callback (la fonction
solution), toujours dans l’objectif de supprimer simplement les yields.
J’ai tout mis dans un seul fichier csnakesolver.c (par simplicité, même si
plusieurs fichiers .c avec leurs .h auraient été préférables).
Performances
Passons maintenant à ce qui nous intéresse : les performances.
Exemples de référence
Je fais mes tests sur 3 exemples : un rapide, un moyen et un long.
Le rapide est un 3×3×3, les deux autres sont des 4×4×4. Voici leurs structures respectives :
// (R)apide
{2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2}
// (M)oyen
{2, 1, 2, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1,
1, 2, 3, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1}
// (L)ong
{1, 1, 2, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 ,1, 2, 2, 1, 1,
1, 1, 1, 2, 3, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3}Protocole
Je vais comparer, grâce à la commande time, le temps nécessaire pour trouver
une solution :
time ./csnakesolver
Le programme doit s’arrêter après avoir trouvé la première. Les programmes Python et C trouveront forcément les mêmes et dans le même ordre, vu qu’ils implémentent le même algorithme.
Compilation
Il est intéressant de tester les performances en compilant sans optimisations :
gcc csnakesolver.c -o csnakesolver
et avec :
gcc -O3 csnakesolver.c -o csnakesolver
Résultats
(au format h:mm:ss.ms)
| Python | C (gcc) |
C (gcc -O3) |
|
|---|---|---|---|
| R | ~0:00:00.000 |
~0:00:00.000 |
~0:00:00.000 |
| M | 0:05:06.903 |
0:00:03.715 (×83) |
0:00:00.826 (×372) |
| L | 3:53:17.012 |
0:05:04.533 (×46) |
0:00:50.681 (×276) |
Le gain est loin d’être négligeable : ×276 dans un cas et ×372 dans l’autre ! Honnêtement, je ne m’y attendais pas. Tout au plus, j’espérais peut-être ×10 ou ×50, sans trop y croire.
Origines des gains de performances
Deux différences expliquent ces gains :
- Python est interprêté, alors que C est compilé.
- En tant que langage de haut-niveau, Python subit le coût de l’abstraction.
Il serait intéressant de savoir dans quelle mesure les gains proviennent de la
compilation et dans quelle mesure ils proviennent de l’abstraction (nous savons
déjà que le facteur de gain entre les programmes compilés avec et sans -O3
provient uniquement de la compilation).
Une approche intéressante pour répondre à cette question serait de compiler le programme Python en code natif (je n’ai encore jamais fait).
Débogueur
Travailler sur un mini-projet personnel permet toujours d’apprendre des choses.
En dehors du langage lui-même, j’ai découvert le
débogueur gdb.
N’ayant toujours utilisé des débogueurs qu’en mode graphique (pour d’autres langages), je m’attendais à ce qu’il soit un peu long à prendre en main. Mais en fait, pas du tout, j’ai été agréablement surpris par sa simplicité d’utilisation.
Avec certains langages, on peut se passer de débogueur pour de petits programmes. C ne fait pas partie de ceux-là, par exemple dans ce cas précis :
$ ./csnakesolver
Erreur de segmentation
Il faut d’abord compiler le programme avec l’option de debug :
gcc -g csnakesolver.c -o csnakesolver
Puis lancer le programme avec le débogueur :
gdb csnakesolver
Un prompt permet d’entrer des commandes :
(gdb)
Pour placer un point d’arrêt à la ligne 215 :
(gdb) break 215
Pour démarrer le programme :
(gdb) run
Le programme s’arrête sur le point d’arrêt :
Breakpoint 1, volume_helper_can_move (vector=...) at csnakesolver.c:215
215 int cursor_position_value = volume_helper.cursor[vector.position];
Pour afficher le bout de code source concerné :
(gdb) l
210 void volume_helper_set_flag(int cursor[], bool value) {
211 * volume_helper_get_flag_pointer(cursor) = value;
212 }
213
214 bool volume_helper_can_move(vector_s vector) {
215 int cursor_position_value = volume_helper.cursor[vector.position];
216 int new_value = cursor_position_value + vector.value;
217 int future_cursor[DIMENSIONS_COUNT];
218 int sign, i, abs_value;
219 if (new_value < 0 || new_value >= dimensions[vector.position]) {
Il est possible de consulter les valeurs des variables (éventuellement en les
formattant) grâce à p (print) :
(gdb) p vector.position
$1 = 0
(gdb) p vector
$2 = {position = 0, value = 1}
Pour afficher des tableaux, il faut indiquer le pointeur et la longueur du tableau à afficher (ici 3) :
(gdb) p * volume_helper.cursor @ 3
$3 = {0, 0, 0}
Pour obtenir la pile d’exécution :
(gdb) bt
#0 volume_helper_can_move (vector=...) at csnakesolver.c:215
#1 0x0000000000401294 in solve_rec (init_cursor=0x7fffffffe210, step=0)
at csnakesolver.c:438
#2 0x0000000000401191 in solve () at csnakesolver.c:407
#3 0x00000000004013de in main () at csnakesolver.c:475
Pour avancer dans le programme, 3 commandes sont indispensables :
c(continue) pour dérouler le programme jusqu’au prochain point d’arrêt ;n(next) pour exécuter la ligne suivante complètement ;s(step) pour rentrer dans la fonction sur la ligne suivante et l’exécuter ligne à ligne.
Ces commandes essentielles permettent déjà de se sortir de beaucoup de situations.
Conclusion
Un programme écrit en C est plus rapide qu’un programme écrit en Python (ah bon ?), dans une proportion plus importante que je ne l’imaginais. Ce n’est qu’un test sur un exemple particulier, mais il donne déjà une petite idée.
La morale de l’histoire est qu’il faut bien choisir son langage suivant le programme à réaliser. Et pour du calcul brut, évidemment un langage bas niveau est préférable (même si le développement est plus laborieux). Dans certains cas cependant, où les performances brutes ne sont pas cruciales, Python sera préféré à C.
Code source
Le code source est disponible sur ce dépôt git : csnakesolver.
Par contre, désolé, cette version est beaucoup moins commentée que la version Python.
Ce serait intéressant de voir le temps de Python quand il est interprété par le JIT PyPy.
Selon les tests on peut obtenir des performances allant jusqu’à 5x celles de CPython : http://speed.pypy.org/