Il 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 macro (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 dans les règles de l’art, 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
| Python | C (gcc) |
C (gcc -O3) |
|
|---|---|---|---|
| Exemple R | instantané | instantané | instantané |
| Exemple M | 5m6.903s | 0m3.715s (×83) | 0m0.826s (×372) |
| Exemple L | 3h53m17.012s | 5m4.533s (×46) | 0m50.681s (×276) |
Le gain est loin d’être négligeable, un gain de ×276 dans un cas et ×372 dans l’autre ! Honnêtement, je ne m’y attendais pas. Tout au plus, j’espérais ×40~×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 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 la majorité des cas cependant, où les performances brutes ne sont pas cruciales, Python sera préféré à C.
Code source
Le programme est disponible au même endroit que la version Python : csnakesolver-0.1.c.
Par contre, désolé, cette version est beaucoup moins commentée que la version Python.
/*
* csnakesolver v0.1, 19th october 2011
*
* changelog:
* 0.1
* - initial version
*
* Solver for generalized snake-cube:
* http://en.wikipedia.org/wiki/Snake_cube
* http://fr.wikipedia.org/wiki/Cube_serpent
*
* By Romain Vimont (®om)
* rom@rom1v.com
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define EXEMPLE_L // change with EXEMPLE_M or EXEMPLE_L
#ifdef EXEMPLE_R
#define SNAKE_STRUCTURE {2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2}
#define STRUCTURE_VECTOR_COUNT 17
#define VOLUME_DIMENSIONS {3, 3, 3}
#define DIMENSIONS_COUNT 3
#endif
#ifdef EXEMPLE_M
#define SNAKE_STRUCTURE {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}
#define STRUCTURE_VECTOR_COUNT 46
#define VOLUME_DIMENSIONS {4, 4, 4}
#define DIMENSIONS_COUNT 3
#endif
#ifdef EXEMPLE_L
#define SNAKE_STRUCTURE {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}
#define STRUCTURE_VECTOR_COUNT 47
#define VOLUME_DIMENSIONS {4, 4, 4}
#define DIMENSIONS_COUNT 3
#endif
#define VARIABLES {'x', 'y', 'z', 't'}
#define VARIABLES_COUNT 4
int structure[] = SNAKE_STRUCTURE;
int dimensions[] = VOLUME_DIMENSIONS;
int variables[] = VARIABLES;
int structure_length; // sum of SNAKE_STRUCTURE
int volume_size; // product of dimensions
typedef struct vector {
int position;
int value;
} vector_s;
typedef struct volume_helper {
bool * flags; // length = product of all VOLUME_DIMENSIONS items
vector_s path[STRUCTURE_VECTOR_COUNT];
int path_length;
int init_cursor[DIMENSIONS_COUNT];
int cursor[DIMENSIONS_COUNT];
} volume_helper_s;
typedef struct symmetry_helper {
int eq_classes_path[DIMENSIONS_COUNT * STRUCTURE_VECTOR_COUNT + 2];
int * eq_classes;
} symmetry_helper_s;
vector_s new_vector(char position, char value);
void symmetry_helper_init(symmetry_helper_s * symmetry_helper);
void volume_helper_init(volume_helper_s * volume_helper);
void init();
char * vector_to_string(vector_s vector);
char * get_variable(char position);
char * get_canonical_number(char number);
char * cursor_to_string(int cursor[]);
void volume_helper_set_cursor(int cursor[]);
bool * volume_helper_get_flag_pointer(int cursor[]);
bool volume_helper_get_flag(int cursor[]);
void volume_helper_set_flag(int cursor[], bool value);
bool volume_helper_can_move(vector_s vector);
void volume_helper_move(vector_s vector);
void volume_helper_back();
void volume_helper_append_vector_in_path(vector_s vector) ;
vector_s volume_helper_pop_vector_in_path();
void symmetry_helper_init_eq_classes_from_dimensions();
bool symmetry_helper_inc_cursor(int cursor[]);
bool symmetry_helper_inc_cursor_rec(int cursor[], int index);
void symmetry_helper_set_cursor(int cursor[]);
void symmetry_helper_move(vector_s vector);
void symmetry_helper_back();
bool symmetry_helper_must_explore(int i);
bool eq_cmp(int p1, int p2, int dim);
bool solve();
bool solve_rec(int init_cursor[], int step);
bool solution(int * init_cursor, vector_s * path);
vector_s new_vector(char position, char value) {
vector_s vector;
vector.position = position;
vector.value = value;
return vector;
};
symmetry_helper_s symmetry_helper;
volume_helper_s volume_helper;
void symmetry_helper_init(symmetry_helper_s * symmetry_helper) {
symmetry_helper->eq_classes = symmetry_helper->eq_classes_path;
}
void volume_helper_init(volume_helper_s * volume_helper) {
volume_helper->flags = (bool *) malloc(volume_size * sizeof(bool));
volume_helper->path_length = 0;
}
void init() {
int i;
volume_size = 1;
for (i = 0; i < DIMENSIONS_COUNT; i++) {
volume_size *= dimensions[i];
}
structure_length = 0;
for (i = 0; i < STRUCTURE_VECTOR_COUNT; i++) {
structure_length += structure[i];
}
symmetry_helper_init(&symmetry_helper);
volume_helper_init(&volume_helper);
}
char * vector_to_string(vector_s vector) {
char * string = (char *) malloc(5 * sizeof(char));
char * variable = get_variable(vector.position);
char * canonical_number = get_canonical_number(vector.value);
sprintf(string, "%s%s", canonical_number, variable);
free(variable);
free(canonical_number);
return string;
}
char * get_variable(char position) {
char * variable = (char *) malloc(3 * sizeof(char));
if (position < VARIABLES_COUNT) {
sprintf(variable, "%c", variables[position]);
} else {
sprintf(variable, "k%i", position - VARIABLES_COUNT);
}
return variable;
}
char * get_canonical_number(char number) {
char * canonical_number = (char *) malloc(3 * sizeof(char));
if (number == (char) 1) {
sprintf(canonical_number, "");
} else if (number == (char) -1) {
sprintf(canonical_number, "-");
} else {
sprintf(canonical_number, "%i", number);
}
return canonical_number;
}
char * cursor_to_string(int cursor[]) {
char * result = (char *) malloc(255 * sizeof(char));
char * s = result;
int i;
s += sprintf(s, "(");
for (i = 0; i < DIMENSIONS_COUNT; i++) {
if (i != 0) {
s += sprintf(s, ", ");
}
s += sprintf(s, "%i", cursor[i]);
}
s += sprintf(s, ")");
return result;
}
void volume_helper_set_cursor(int cursor[]) {
volume_helper_set_flag(volume_helper.init_cursor, false);
memcpy(volume_helper.init_cursor, cursor, DIMENSIONS_COUNT * sizeof(int));
memcpy(volume_helper.cursor, cursor, DIMENSIONS_COUNT * sizeof(int));
volume_helper_set_flag(cursor, true);
}
bool * volume_helper_get_flag_pointer(int cursor[]) {
bool * p_flag = volume_helper.flags;
int product = 1;
int i;
for (i = DIMENSIONS_COUNT - 1; i >= 0; i--) {
p_flag += cursor[i] * product;
product *= dimensions[i];
}
return p_flag;
}
bool volume_helper_get_flag(int cursor[]) {
return * volume_helper_get_flag_pointer(cursor);
}
void volume_helper_set_flag(int cursor[], bool value) {
* volume_helper_get_flag_pointer(cursor) = value;
}
bool volume_helper_can_move(vector_s vector) {
int cursor_position_value = volume_helper.cursor[vector.position];
int new_value = cursor_position_value + vector.value;
int future_cursor[DIMENSIONS_COUNT];
int sign, i, abs_value;
if (new_value < 0 || new_value >= dimensions[vector.position]) {
return false;
}
memcpy(future_cursor, volume_helper.cursor, DIMENSIONS_COUNT * sizeof(int));
if (vector.value < 0) {
sign = -1;
} else {
sign = 1;
}
abs_value = sign * vector.value;
for (i = 0; i < abs_value; i++) {
future_cursor[vector.position] += sign;
if (volume_helper_get_flag(future_cursor)) {
return false;
}
}
return true;
}
void volume_helper_move(vector_s vector) {
int sign, i, abs_value;
volume_helper_append_vector_in_path(vector);
if (vector.value < 0) {
sign = -1;
} else {
sign = 1;
}
abs_value = sign * vector.value;
for (i = 0; i < abs_value; i++) {
volume_helper.cursor[vector.position] += sign;
volume_helper_set_flag(volume_helper.cursor, true);
}
}
void volume_helper_back() {
int sign, i, abs_value;
vector_s vector = volume_helper_pop_vector_in_path();
if (vector.value < 0) {
sign = -1;
} else {
sign = 1;
}
abs_value = sign * vector.value;
for (i = 0; i < abs_value; i++) {
volume_helper_set_flag(volume_helper.cursor, false);
volume_helper.cursor[vector.position] += -sign;
}
}
void volume_helper_append_vector_in_path(vector_s vector) {
vector_s * current_vector = volume_helper.path + volume_helper.path_length;
memcpy(current_vector, &vector, sizeof(vector_s));
volume_helper.path_length ++;
}
vector_s volume_helper_pop_vector_in_path() {
volume_helper.path_length --;
vector_s * current_vector = volume_helper.path + volume_helper.path_length;
vector_s vector;
memcpy(&vector, current_vector, sizeof(vector));
return vector;
}
void symmetry_helper_init_eq_classes_from_dimensions() {
// eq_classes from dimensions is the first item of eq_classes_path
int * eq_classes = symmetry_helper.eq_classes_path;
int i, j;
int value;
bool found;
for (i = 1; i < DIMENSIONS_COUNT; i++) {
value = dimensions[i];
j = 0;
found = false;
while (j < i && !found) {
if (dimensions[j] == value) {
eq_classes[i] = j;
found = true;
} else {
j++;
}
}
if (!found) {
eq_classes[j] = j;
}
}
symmetry_helper.eq_classes = eq_classes;
}
bool symmetry_helper_inc_cursor(int cursor[]) {
return symmetry_helper_inc_cursor_rec(cursor, DIMENSIONS_COUNT - 1);
}
bool symmetry_helper_inc_cursor_rec(int cursor[], int index) {
int * eq_classes = symmetry_helper.eq_classes_path;
int value = cursor[index];
int i;
if (value < (dimensions[index] - 1) / 2) {
// the last coordinate can be incremented
cursor[index] ++;
return true;
}
// we must increment recursively the previous coordinate
if (index == 0) {
// there is no more coordinate to increment
return false;
}
i = index - 1;
if (!symmetry_helper_inc_cursor_rec(cursor, i)) {
return false;
}
while (i >= 0 && eq_classes[i] != eq_classes[index]) {
i--;
}
if (i >= 0) {
// coordinate value must at least equals the previous coordinates
// in the same equivalence class
cursor[index] = cursor[i];
} else {
cursor[index] = 0;
}
return true;
}
void symmetry_helper_set_cursor(int cursor[]) {
int * eq_classes_path = symmetry_helper.eq_classes_path;
int * cursor_eq_classes = symmetry_helper.eq_classes_path + DIMENSIONS_COUNT;
int i, j, old_class;
symmetry_helper.eq_classes = cursor_eq_classes;
// copy the eq_classes computed from the dimensions into the next segment
memcpy(cursor_eq_classes, eq_classes_path, DIMENSIONS_COUNT * sizeof(int));
for (i = 0; i < DIMENSIONS_COUNT; i++) {
if (cursor_eq_classes[i] != i && !eq_cmp(cursor_eq_classes[i], cursor[i], dimensions[i])) {
old_class = cursor_eq_classes[i];
cursor_eq_classes[i] = i;
for (j = i + 1; j < DIMENSIONS_COUNT; j++) {
if (cursor_eq_classes[j] == old_class) {
cursor_eq_classes[j] = i;
}
}
}
}
}
void symmetry_helper_move(vector_s vector) {
int position = vector.position;
int * previous_eq_classes = symmetry_helper.eq_classes;
int * new_eq_classes = previous_eq_classes + DIMENSIONS_COUNT;
int new_eq_class = -1;
int i;
memcpy(new_eq_classes, previous_eq_classes, DIMENSIONS_COUNT * sizeof(int));
for (i = position + 1; i < DIMENSIONS_COUNT; i++) {
if (new_eq_classes[i] == position) {
if (new_eq_class == -1) {
new_eq_class = i;
}
new_eq_classes[i] = new_eq_class;
}
}
symmetry_helper.eq_classes = new_eq_classes;
}
void symmetry_helper_back() {
symmetry_helper.eq_classes -= DIMENSIONS_COUNT;
}
bool symmetry_helper_must_explore(int i) {
return symmetry_helper.eq_classes[i] == i;
}
bool eq_cmp(int p1, int p2, int dim) {
return p1 == p2 || p1 + p2 + 1 == dim;
}
bool solve() {
int cursor[DIMENSIONS_COUNT] = {}; // init with zeros
int i;
if (structure_length + 1 != volume_size) {
fprintf(stderr,
"Structure has not the right length (%i instead of %i)\n",
structure_length, volume_size);
return false;
}
do {
volume_helper_set_cursor(cursor);
symmetry_helper_set_cursor(cursor);
if (!solve_rec(cursor, 0)) {
return false;
}
} while (symmetry_helper_inc_cursor(cursor));
// explored all possible solutions
return true;
}
bool solve_rec(int init_cursor[], int step) {
int previous_position;
int norm = structure[step];
int vector_value;
int i, k;
vector_s possible_vector;
if (step == STRUCTURE_VECTOR_COUNT) {
if (!solution(volume_helper.init_cursor, volume_helper.path)) {
// stop searching for new solutions
return false;
}
} else {
if (volume_helper.path_length == 0) {
previous_position = -1;
} else {
previous_position = volume_helper.path[volume_helper.path_length -1].position;
}
for (i = 0; i < DIMENSIONS_COUNT; i++) {
if (i != previous_position && symmetry_helper_must_explore(i)) {
for (k = 0; k < 2; k++) {
vector_value = k == 0 ? norm : -norm;
possible_vector = new_vector(i, vector_value);
if (volume_helper_can_move(possible_vector)) {
volume_helper_move(possible_vector);
symmetry_helper_move(possible_vector);
if (!solve_rec(init_cursor, step + 1)) {
return false;
}
volume_helper_back();
symmetry_helper_back();
}
}
}
}
}
return true;
}
bool solution(int * init_cursor, vector_s * path) {
int i;
char * vector_string;
vector_s vector;
printf("(%s, [", cursor_to_string(init_cursor));
for (i = 0; i < STRUCTURE_VECTOR_COUNT; i++) {
if (i != 0) {
printf(", ");
}
vector = path[i];
vector_string = vector_to_string(vector);
printf("%s", vector_string);
free(vector_string);
}
printf("])\n");
// stop after the first solution
return false;
}
int main(void) {
init();
solve();
exit(0);
}
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/
Test très intéressant merci à toi, si tu veux pousser le test plus loin il me semble qu’il est possible d’appeler du code C depuis un programme python. Faire un test hybride pourrait être intéressant afin de comparer les temps d’exécutions et les temps de développement.
Tu dis au début, qu’il y a une fonction qui ne fonctionne pas pareil entre le python et le C. Serait-il possible de modifier le python pour avoir le même algo exactement ? Le résultat peut-aussi bien être positif que négatif.
J’ai regardé un peu le code. Ce qui me saute aux yeux, c’est que tu utilises
sprintfsans protection. On peut écrire au dela du buffer, sans forcément le voir. Je préfère personnellementint snprintf(buffer, size_buffer,const char *,…);Sans oublier de lire le retour desnprintfet de tester. En faisant bien attention à garantir le code C, tu risques de perdre quelques %.Salut,
Interessant, mais j’aurais cependant quelques remarques sur ta manière de calculer le temps d’exécution…
« time » c’est bien, mais pour mesurer des temps d’exécution autant court (<0.040s) cela ne suffit pas (dans ce cas ci). D’abord, « time » (si je me souviens bien) prend en compte les changement de contexte, donc tu auras des valeurs faussées.
Ensuite, sur des temps autant court, il faut au moins exécuté ton code plusieurs fois (10,100,1000,10000,…), sauvez chaque temps d’exécution, puis faire une moyenne afin d’avoir quelque chose de « censé ».
De plus, il serait interessant de ne calculer que le temps d’exécution de l’algorithme de résolution, donc sans prendre en compte les décalrations, initialisations,…
Par exemple, en C, tu peux utiliser la fonction
), qui ne compte que les « ticks » (les coups d’horloge du processeur) processeur au sein du processus. Par exemple, si ton algorithme dure 100 « ticks », qu’il y a un changement de contexte au milieu de ton programme d’une durée de 50 « ticks »,
gettimeofday()(je te laisse lire la mangettimeofday(), te retournera 100 et non 150.Bref, ce n’est qu’un commentaire d’un ancien élève traumatisé par son professeur de « théorie de la complexité » qui a du calculer beaucoup trop de temps d’exécution d’algorithme
La vitesse entre Python et C ne me surprends pas vraiment, par contre je suis étonner du gain avec l’option -O3 !
@Plop
gettimeofday()ne donne pas les ticks, il donne la date donc ne prend pas en compte le temps réel d’exécution du programme.La fonction que tu conseilles est
clock().@L’auteur
As-tu aussi testé le résultat avec l’optimisation
-Os?@Fred: euh oui, en effet, mes confuses, il s’agit bien de
clock()et non pasgettimeofday()(à voir j’ai pas été assez traumatisé par mes cours
)
Ici, le programme n’est composé que d’une partie calcul. Du coup, que voudrais-tu écrire en C et que voudrais-tu écrire en Python ? Ça se justifie dans certains cas, mais à mon avis pas ici.
Si j’ai bien compris le but de ta question, tu souhaiterais mettre en évidence la différence de performances dûe à la compilation, et donc supprimer tout ce qui concerne le coût de l’abstraction ?
Dans ce cas, il y aurait bien d’autres choses à modifier. Un exemple parmi d’autres, en Python j’utilise une liste de listes de listes… pour stocker les booléens (flags), alors qu’en C j’utilise un espace contigü en mémoire. De même, la liste des vecteurs est une liste de références en Python, alors qu’en C je place directement les
struct vectordans le tableau, sans déréférencement. La fonction que j’ai totalement réécrite est juste un cas extrême, où en Python j’utilise une abstraction qui facilite bien la vie (et il serait dommage de s’en passer), qu’on ne code raisonnablement pas en C (de toute façon, la fonction en question est anecdotique en temps, elle ne fait que générer les positions de départ).Et c’est volontaire : pour comparer deux langages, il me semble plus intéressant de comparer « tel que l’on code » dans ces langages (on code en haut-niveau dans un langage haut-niveau, en bas-niveau dans un langage bas-niveau). Cela empêche cependant de mettre de côté le coût de l’abstraction.
Même si j’aimerais bien connaître la part de gains dûe à la compilation et la part dûe à l’abstraction, la mesure des deux combinés me semble plus pertinente.
Tu as raison, je n’ai pas l’habitude de manipuler
sprintfet ses dérivés, mais j’ai quand même choisi une taille supérieure à celle dont on a raisonnablement besoin (je modifierai à l’occasion).Les appels à
sprintfne servent qu’une seule fois, pour générer la chaîne de caractères décrivant la solution, quand le traitement est terminé.Non, je ne connais pas essayé (je ne connaissais pas). A priori, ça devrait être plus lent mais générer un binaire plus petit, c’est cela ?
Je vais dans le même sens que certains commentaires, exécuter ton algorithme plusieurs fois, et, est-il possible avec Python, comme en Perl, de precompiler ton programme? Avec un temps d’exécution aussi court je suis sûr que cette étape est longue comparativement, ce qui fausse le résultat…
Pour l’exemple R (le plus rapide), je suis totalement d’accord. J’ai inscrit les valeurs brutes donnés par
time, mais quand il est écrit0m0.002s, il faut comprendre « résolution instantanée », et ne pas considérer la valeur elle-même. C’est d’ailleurs la raison pour laquelle je n’ai pas mis le facteur de gain pour ce premier exemple, qui n’aurait aucun sens. Je remplace dans le billet par « instantané« , ça sera plus clair.Effectivement, exécuter plusieurs fois l’algorithme permettrait de pouvoir comparer les performances sur cet exemple, mais il ne me semblait pas digne d’intérêt, vu que les exemples M et L fournissent des valeurs utilisables telles quelles (l’exemple L prend 3h53 en Python, et 50s en C (
-O3).Tout-à-fait. Cela me rappelle de vieux souvenirs, dans lesquels je ne me suis pas replongé, car je n’avais pas besoin d’une telle précision (savoir que c’est 372 fois plus rapide ou 368 fois seulement n’a pas beaucoup d’importance, je voulais surtout l’ordre de grandeur).
Effectivement, ça m’a un peu (agréablement) surpris aussi.
complexité n³ en haut niveau contre accès mémoire direct ça ne te choque pas ? Je veux bien que tu compares et le langage et la manière de coder mais bon là…
Quitte à utiliser
-O3de gcc autant comparer avec l’équivalent de Python non ?Et puis sur un aussi petit programme le temps de compilation de Python n’est certainement pas négligeable… Dur d’interpréter les chiffres.
Qui sur une matrice beaucoup grande ?
Article intéressant ! Et en Java ça donnerait quoi à votre avis ?
Désolé, je ne suis pas du tout convaincu par ce résultat et je n’ai pas l’impression qu’il donne la juste mesure du langage en question. Hormis les problèmes sur la méthode de mesure, tu vas à l’encontre des différentes études sur le sujet. Les études montre un rapport de seulement x5 entre python et C. Et j’ai appris, dans mon cas personnel, que souvent une lenteur de python par rapport à C, était due à une mauvais manipulation de python et que bien utilisé, python peut atteindre mêmes atteindre performances qu’un code C (vraiment dans certain cas précis comme pour toi).
En effet, Python est certes un langage à byte-code mais les routines C dessous sont optimales. Et en regardant ton code, des choses me font penser que ça peut être améliorer : les quadruples boucles imbriqués par exemple en python faut vraiment éviter car les boucles en python n’ont rien à voir avec celles de C. As tu pensé au recours de numpy qui est justement pensé pour utiliser de manière optimale des tableaux et matrices ?
bon ensuite t’as peut être pas que ça à faire, mais ça donnerait plus de base à l’article qui est plus choc que réaliste à mon goût.
mea culpa, ça tourne autour de x8 à x10 mais pas x300
Je ne vais pas à leur encontre, ni mon programme ni mon billet ne contredisent les résultats de ces études (que tu donnes).
Il ne s’agit pas d’une analyse générale des performances moyennes entre C et Python, mais bien des différences sur la résolution d’un problème particulier (le cube-serpent), dont le cœur de l’algorithme concerne la manipulation mémoire (ajouter et retirer des vecteurs d’une liste, et allumer ou éteindre des booléens dans un volume).
Comme je le disais, je pense que pour comparer les performances de deux langages, il faut coder tel qu’on le fait habituellement dans ces langages.
Par exemple, dans le programme Python, un chemin est stocké sous forme de listes de vecteurs, un vecteur étant lui-même une liste d’entiers, alors que dans le programme C, le chemin est stocké dans un espace mémoire contigü (les vecteurs les uns après les autres). Il me semble que c’est la manière naturelle d’implémenter cette fonctionnalité.
Mais supposons qu’on veuille coder exactement de la même manière pour « comparer ». On a alors deux solutions :
Dans le premier cas, on va s’embêter à écrire explicitement plein de
mallocs inutilement (ce n’est pas naturel, il va falloir « coder plus » pour perdre en performances).Dans le second cas, on va utiliser en Python une liste « à plat ». Mais alors, pour ajouter un vecteur, on n’utilise plus la fonction
append(): à la place il va falloir copier chaque composante une à une (dans une boucle). Mais là encore c’est injuste, car en C on utilisememcpy. Du coup, que fait-on ? On s’interdit d’utilisermemcpyet on fait une boucle aussi en C ?J’ai l’impression qu’on ne s’en sort pas, et que les résultats seraient encore plus biaisés.
J’en suis sûr ! Si certains sont motivés…
Moi, personnellement, j’ai répondu à la question qui me taraudait : combien de fois plus rapidement mon programme C résoudrait le cube-serpent que mon programme Python (juste l’ordre de grandeur m’intéressait).
Non, mais là encore, si quelqu’un veut tester, je suis intéressé par les résultats
Pingback: Le langage C | Blog elveos
Salut,
Juste une petite idée qui pourrait sans doute faire gagner un peu de temps.
Comme souvent il serait intéressant d’utiliser une sentinelle.
Ici ça pourrait permettre de réduire le nombre de comparaison à faire pour détecter qu’un nouvel emplacement est valide.
Le principe est simple, il faut rajouter créer une matrice de deux unités plus longues dans toutes les dimension et l’initialisé avec tous les éléments sur les bords déjà utilisé.
Par exemple en dimension 2, au lieu de partir avec une matrice :
On commence avec une matrice :
Comme ça à chaque fois qu’on rajoute un élément, on a juste à tester si la case est occupée et on peut supprimer les deux tests vérifiant si on a dépassé d’un côté ou de l’autre la matrice.
@Mac.aque :
Ah ouais, pas bête. J’avais déjà vu cette astuce pour un jeu d’échecs (faire un échiquier 10×10 au lieu de 8×8, pour la même raison).
Ça doit effectivement faire gagner un peu de temps…
Je suis honoré qu’un de mes commentaires ait pu donner naissance à un billet aussi intéressant!
En fait je suis un grand fan de C/C++, même si je suis loin d’en être un utilisateur expérimenté!
Du coup j’ai essayé de faire une implémentation java.
J’utilise pas le même algo donc la comparaison du temps d’execution de vaut rien, mais il a l’air assez rapide.
Ici la matrice est représentée dans un tableau unidimensionnelle de manière classique (par exemple en dimension deux avec une matrice 3*3, l’élément {x,y} est à la position 3*y+x), et comme je le proposais on rajoute une deux « bordures » au début et à la fin de chaque dimension qui servent de sentinelles.
La représentation du serpent est transformée en un tableau de boolean indiquant pour chaque element si le prochain est dans la même direction où s’il faut changer de sens.
La solution s’affiche en affichant le contenu de chaque élément de la matrice. En effet à mesure que l’on progresse dans la matrice en déployant le serpent on remplace la valeur de l’emplacement par l’indice de l’élément du serpent. Comme cela on peut au final voir comment le serpent est positionné.
Par contre l’algo ne gère pas le départ, là il part seulement d’un coin et dans une seule dimension, il faudrait le modifier pour qu’il parte de toutes les positions et dans toutes les directions non symétriques.
Voici le code :
(EDIT par ®om) SnakeSolverHyperCube.java