France-IOI
Travailler efficacement avec le compilateur et le shell
Arthur Charguéraud pour www.france-ioi.org
Introduction
Ce document décrit diverses techniques destinées à vous faire gagner du temps lorsque vous travaillez sur vos algorithmes.
Plan
- Ligne de commande de compilation C/C++
- Ligne de commande de compilation Caml
- Redirection des flux de données
- Compilation et exécution en une commande
- Gérer plusieurs fichiers tests
- Mesurer le temps d'exécution
- Vérifier la mémoire utilisée
- [C/C++] Redirection des flux de données avec freopen
- [C/C++] Préprocesseur C/C++ pour commenter
- [C/C++] Préprocesseur C/C++ pour déboguer
- [Avancé] Utiliser 'diff' pour comparer des résultats
- [Avancé] Script bash pour tester en batch
- [Avancé] Script bash pour évaluer en batch
Notations
En C/C++ :
- fichier source : "algo.cpp"
- compilateur : "g++" ou "gcc" (resp. compilateurs C++ et C)
En Caml :
- fichier source : "algo.ml"
- compilateur : "ocamlc" ou "ocamlopt" (respectivement compilateur en bytecode et en code natif)
Dans tous les cas :
- exécutable : "output.exe"
- fichier d'entrée : "test.in"
- fichier de sortie : "test.out"
On suppose que votre fichier source s'appelle si vous codez en C++, et "algo.ml" si vous codez en Caml.
Ligne de commande de compilation C/C++
g++ -Wall -O2 -o output.exe algo.cpp
Remarque : si vous voulez vraiment faire du C et non du C++, remplacez "g++" par "gcc".
L'option -Wall active un maximum de warnings, ce qui permet de minimiser le nombre de bugs potentiels. Il est plus que fortement déconseillé de travailler avec un code qui produit des warnings.
L'option -O2 (c'est un 'O' et non un '0') indique au compilateur qu'il faut qu'il se fatigue un peu plus pour essayer de produire du code plus performant. On peut gagner un facteur 2 ou 3 en vitesse dans certain cas.
Ligne de commande de compilation Caml
En mode "bytecode" (compilation rapide, programme peu performant) :
ocamlc -o output.exe algo.ml
En mode "code natif" (compilation plus lente, programme beaucoup plus performant) :
ocamlopt -o output.exe algo.ml
Le rapport de performance entre ocamlc et ocamlopt est compris généralement entre 5 et 10. Autrement dit, un programme en bytecode (ocamlc) est toujours au moins 5 fois plus lent que le même programme compilé en code natif (ocamlopt).
En conclusion, le plus simple c'est de travailler avec ocamlc, et d'utiliser ocamlopt uniquement lorsque vous avez besoin de tester votre programme dans des cas extrêmes.
Attention, pour que "ocamlopt" marche, vous devez avoir installé "MinGW". Pour tous les détails, allez voir sur la page du cours Caml.
Redirection des flux de données
- Votre programme peut lire des données :
- soit sur l'entrée standard, avec scanf
- soit dans des fichiers, avec fscanf
- Votre programme peut écrire des données :
- soit sur la sortie standard, avec printf
- soit dans des fichiers, avec fprintf
Sur notre site, presque tout se fait avec l'entrée standard, et nous vous recommandons donc de travailler exclusivement avec des scanf et des printf. N'utilisez pas les entrées-sorties C++ (cin et cout) qui peuvent être beaucoup plus lentes dans certains cas (jusqu'à un facteur 10 !).
Pour tester votre programme sur des fichiers tests, il faut donc envoyer les données d'un fichier ("test.in") vers l'entrée standard de votre programme. Et si votre programme affiche beaucoup d'informations, il faut rediriger la sortie standard vers un fichier ("test.out"). Voici comment faire :
- Pour envoyer les données du fichier test.in sur l'entrée standard, et obtenir les résultats dans la console :
output.exe < test.in
- Pour simplement rediriger la sortie du programme vers le fichier test.out :
output.exe > test.out
- Pour faire les deux à la fois, c'est-à-dire donner le fichier test.in sur l'entrée standard et écrire la sortie du programme dans le fichier test.out :
output.exe < test.in > test.out
Compilation et exécution en une commande
Ce que l'on montre ici marche dans une console Linux, mais pas sous Windows. On peut aussi faire la même chose sous Windows si on installe les outils "MSys". Mais en pratique, on utilise un IDE avec des bons raccourcis claviers, et il n'y a donc pas besoin de faire ce qui est décrit ici.
La séquence que vous allez utiliser le plus souvent est la suivante :
Essayer de compiler le programme
Si ça marche
Alors tester le programme
Sinon aller corriger le code
Il existe un moyen très efficace d'automatiser cela à l'aide d'une seule ligne de commande. L'idée est de lancer la commande de compilation, et si elle réussit, demander à ce que soit automatiquement lancé la commande d'exécution. Pour cela on utilise l'opérateur && (c'est le même opérateur qu'en C/C++ ou Caml).
g++ -Wall -O2 -o output.exe algo.ml && output.exe < test.in > test.out
L'intérêt c'est que le programme "output.exe" n'est pas exécuté si la compilation ne réussit pas.
Gérer plusieurs fichiers tests
En pratique vous devez avoir plusieurs fichiers tests, car un seul test n'est jamais suffisant. Pour tester votre programme sur différents fichiers tests, utilisez les commandes :
output.exe < test1.in output.exe < test2.in output.exe < test3.in
Pour afficher le contenu du fichier d'entrée juste avant de voir le résultat, utilisez "cat"
cat test1.in ; output.exe < test1.in
Vous pouvez en ajoutez un trait pour séparer l'entrée et la sortie en utilisant "echo" :
cat test1.in ; echo ; echo ---- ; output.exe < test1.in
On verra plus tard comment automatiser cette commande avec un script.
Mesurer le temps d'exécution
On décrit la méthode sous Linux. Sous Windows, c'est plus délicat; la solution simple : sortez votre chronomètre ;)Pour évaluer le temps d'exécution de votre programme sur votre machine, utilisez la commande "time" :
time output.exe < big1.in
Cette commande affichera trois lignes, du genre :
real 0m0.522s user 0m0.324s sys 0m0.051s
Le temps real correspond au temps qui s'est effectivement écoulé, dans le monde réel, entre le début et la fin de l'exécution de votre programme. Il peut dépendre de nombreux facteurs, comme par exemple les autres programmes exécutés au même moment par la machine.
Le temps user correspond au temps que le processeur a passé à exécuter les instructions de votre programme, sans compter les appels systèmes.
Le temps sys correspond au temps que le processeur a passé à exécuter les appels systèmes, c'est à dire une partie du temps utilisé par des fonctions systèmes comme malloc, printf ou scanf.
Le temps qui vous intéresse est le total du temps user et du temps sys.
N'oubliez pas que votre machine n'est pas nécessairement du même type que celle sur laquelle votre programme sera évalué, et donc le temps d'exécution du programme sur votre machine ne sera pas le même que le temps d'exécution sur le serveur. Nous vous invitons à faire quelques tests pour établir une correspondance.
[Unix] Vérifier la mémoire utilisée
Pour vérifier que votre programme n'utilise pas trop de mémoire, sous linux, vous pouvez utiliser la commande bash "ulimit", qui permet de fixer une limite pour certaines ressources. Ces limites seront appliquées à tout programme lancé à partir de ce shell.
Attention : une fois que vous avez fixé une limite, vous ne pouvez pas la réaugmenter sans quitter le shell. Lancer donc un nouveau shell temporairement (commande sh) pour faire votre test.
>Pour fixer une limite globale à l'utilisation de la mémoire :
ulimit -v taille_memoire
où taille_memoire est une valeur en kilo-octets. Par exemple pour limiter à 16 Mo :
ulimit -v 16000
Si vous exécutez ensuite votre programme dans ce shell, une erreur sera affichée si la mémoire est insuffisante. Il peut s'agir d'un simple message "Killed", ou d'une erreur d'allocation, ou de segmentation. Si vous utilisez des mallocs, vérifiez qu'ils n'ont pas renvoyé un pointeur nul.
Dans certain cas, on peut vous indiquer une limite séparée pour la taille de la pile. Vous pouvez la fixer avec l'option -s :
ulimit -s taille_pile
où taille_pile est en kilo-octets.
A tout moment, vous pouvez afficher les limites actuelles du shell en appelant "ulimit -v" ou "ulimit -s" sans indiquer la taille. Pour plus de détails, utilisez la commande "ulimit -a" qui permet d'afficher toutes les limites qu'il est possible de fixer.
[Windows] Vérifier la mémoire utilisée
Pour commencer, ajoutez à votre programme une instruction pour l'empêcher de se terminer :
en C/C++ : system("PAUSE"); // nécessite #include <stdlib.h>
en Caml : Sys.command "PAUSE";
Attention, si vous exécutez le programme dans un IDE avec une redirection de l'entrée standard, il sera nécessaire de killer le programme pour le terminer (soit à l'aide d'un bouton adapté dans votre IDE, soit par ALT+CTLR+SUPPR).
Ensuite, lancez votre programme, et faîtes ALT+CTRL+SUPPR pour accéder au gestionnaire de tâches. Là, allez dans l'onglet "processus". Là cherchez la ligne contenant le nom de votre programme, c'est-à-dire "output.exe". Regardez dans la colonne "utilisation de mémoire". Cela vous donne la mémoire utilisée à ce moment là.
Dans la plupart des cas, cela suffit. Cependant, si vous utilisez allocations dynamiques (des malloc et des free en C++, ou alors si vous codez en Caml), il faut afficher une autre colonne. Pour cela, allez dans le menu "Affichage", sur "Sélection des colonnes", et cochez "utilisation maximale de la mémoire". Vous pouvez maintenant visualiser la consommation maximale de mémoire d'un programme au cours de son exécution.
[C/C++] Redirection des flux de données avec freopen
Si le sujet vous impose de lire et écrire dans des fichiers, il existe un moyen pratique pour le gérer. L'idée est d'utiliser une instruction à l'intérieur de votre programme pour rediriger l'entrée et la sortie standard. Cette fonction s'appelle "freopen". Voici un exemple de programme, où l'on montre comment lire un entier dans un fichier puis en écrire la valeur dans un autre fichier, le tout en utilisant "scanf" et "prinf" et non "fscanf" et "fprintf" qui sont plus lourds à manipuler.
int main()
{
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
int unEntier;
scanf("%d", &unEntier);
printf("%d\n", unEntier);
return 0;
}
[C/C++] Préprocesseur C/C++ pour commenter
Le préprocesseur permet d'ignorer un certain nombre de lignes du programme. Cela peut être utile si vous désirez conserver dans le code certaines fonctions que vous n'utilisez plus. On pourrait utiliser la syntaxe /* ... */, mais elle ne gère pas les imbrications.
En bref, il suffit d'écrire :
#if 0 lignes complètement ignorées ... #endif
Non seulement ce système permet d'imbriquer les zones ignorées les unes dans les autres, mais en plus on peut rétablir un passage très facilement : il suffit de changer le 0 en 1 pour annuler le commentaire.
[C/C++] Préprocesseur C/C++ pour déboguer
Le préprocesseur peut aussi servir à maintenir dans un même fichier une version de test, avec des affichages permettant de debugger, et une version finale contenant uniquement ce qui sera soumis à la fin. Concrètement, on met dans le code les instructions d'affichage entre les balises #ifdef DEBUG et #endif:
#ifdef DEBUG
printf("Distances des noeuds\n");
for (int noeud = 0; noeud < nbNoeuds; noeud++)
print("%d\t", noeud);
printf("\n");
for (int noeud = 0; noeud < nbNoeuds; noeud++)
print("%d\t", dist[noeud]);
printf("\n");
#endif
Par défaut, la variable DEBUG n'est pas définie, et toutes ces lignes sont donc ignorées. Si l'on souhaite que ces lignes soient exécutées, on ajoute une ligne en haut du source pour définir DEBUG :
#define DEBUG
Pour passer rapidement du mode déboguage au mode normale, on commente ou décommente cette ligne
// #define DEBUG
Surtout, n'oubliez pas d'enlever ou de commenter la ligne #define DEBUG au moment de soumettre le code de votre programme !
Une autre solution très pratique permet de gérer la définition ou non de la variable DEBUG. Le truc, c'est de spécifier une option au compilateur pour qu'il définisse la valeur DEBUG. Cette option est "-DDEBUG".
g++ -Wall -O2 -DDEBUG -o output.exe algo.cpp
[Avancé] Utiliser 'diff' pour comparer des résultats
Le programme 'diff' est disponible par défaut sous Linux. Sous Windows, trois possibilités : a) récupérer le programme diff.exe, b) installer MSys, diff viendra avec, c) utiliser "fc" un programme équivalent préinstallé sous Windows.
Si vous souhaitez comparer les résultats de deux algorithmes différents sur un même fichier test et que les sorties des programmes sont trop grosses pour être comparées à la main, le programme 'diff' est là pour vous aider. C'est très simple, donnez à 'diff' deux fichiers, et il vous montrera les différences entre les deux fichiers.
diff fichier1 fichier2
Si vous voulez juste savoir si les fichiers sont égaux ou non et ne pas visualiser tous les détails, utilisez l'option "-q" (q comme quiet) :
diff -q fichier1 fichier2
Si vous souhaitez ignorer les différences qui sont simplement des caractères d'espacement comme ' ', '\t', '\n', utilisez l'option "-w" (w comme white-space) :
diff -w fichier1 fichier2
Remarque, notre serveur d'évaluation utilise en général ces deux options pour déterminer si votre programme passe le test ou non :
diff -q -w sortie_attendue votre_sortie
[Avancé] Script bash pour tester en batch
Les scripts bash marchent sous Linux, et sous Windows à condition que MSys soit installé (ou cygwin).
Si vous avez plusieurs fichiers tests et que vous voulez regarder ce que donne votre programme sur tous ces tests, un petit script peut vous faire gagner beaucoup de temps. On suppose que tous les fichiers tests ont pour extension ".in" et on va générer pour chaque fichier test la sortie dans un fichier ".out" correspondant. On écrit le script dans un fichier "test_all.sh", dont voici le contenu :
g++ -Wall -O2 -o output.exe $1
for test_in in *.in; do
echo Solving $test_in ...;
./output.exe < $test_in > `basename $test_in .in`.out;
done
La syntaxe est difficile à lire, mais en gros on fait une boucle sur tous les fichiers ".in", on affiche un petit message pour afficher le nom du fichier que l'on va traiter, et ensuite on exécute le programme sur ce fichier. Le $1 sur la première ligne fait référence à l'argument donné au script.
Pour utiliser ce script, il suffit d'appeler avec en argument votre fichier source :
./test_all.sh algo.cpp
Si vous êtes sous unix et que cette commande ne marche pas, vérifiez que le fichier est marqué comme exécutable. Faites éventuellement "chmod +x test_all.sh" pour régler le problème.
Si vous souhaitez vérifier que votre fichier source compile effectivement avant de lancer son exécution, utilisez un "if" :
if g++ -Wall -O2 -o output.exe algo.cpp
then
for test_in in *.in; do
echo Solving $test_in ...;
./output.exe < $test_in > `basename $test_in .in`.out;
done
else
echo Erreur de compilation
fi
[Avancé] Script bash pour évaluer en batch
On va combiner l'utilisation du script et du diff pour évaluer un programme de la même manière que c'est fait sur notre serveur :
- le dossier courant contient votre source, des fichiers tests (*.in), et les solutions correspondantes (*.out)
- le source va être compilé
- le programme va être exécuté sur tous les fichiers tests (*.res)
- les sorties de votre programme vont être comparées au solutions attendues (*.out vs *.res)
Voici le contenu du script "evaluate.sh" :
g++ -Wall -O2 -o output.exe $1
for test_in in *.in; do
echo Checking $test_in ...;
./output.exe < $test_in > `basename $test_in .in`.res;
diff -q -w `basename $test_in .in`.out `basename $test_in .in`.res;
done
Pour utiliser ce script, il suffit d'appeler avec en argument votre fichier source :
./evaluate.sh algo.cpp
Un message sera donné pour chaque fichier test utilisé, et une ligne supplémentaire précise si la sortie du programme n'est pas identique à la sortie attendue.
Regardons le résultat sur un exemple complet. On suppose que dans le dossier courant on a :
- algo.cpp le source du programme - test1.in contenant "5 4 20 25" - test1.out contenant "45 1" (sortie attendue pour test1.in) - test2.in contenant "8 3 41 67" - test2.out contenant "17 12" (sortie attendue pour test2.in)
On lance alors la commande "./evaluate algo.cpp", et ceci produit dans le dossier courant :
- output.exe le programme compilé - test1.res la sortie du programme exécuté sur le fichier test1.in - test2.res la sortie du programme exécuté sur le fichier test2.in
on va par exemple supposer que :
- test1.res contient "45 1" (le résultat attendu pour ce test) - test2.res contient "20 4" (autre chose que le résultat attendu)
Le message affiché sera dans ce cas :
Checking test1.in ... Checking test2.in ... Files test2.out and test2.res differ
À ce moment, vous souhaitez probablement connaître les différences entre test2.out et test2.res. Si les fichiers sont petits, un "cat" sera le plus pratique :
cat test2.out cat test2.res
Ou bien en une seule commande :
cat test2.out ; echo --- ; cat test2.res
Et dans le cas où les fichiers tests sont plus gros, utilisez diff :
diff test2.out test2.res