___        _   _    ______            
 / _ \ _ __ | |_(_)  / / ___| _     _   
| | | | '_ \| __| | / / |   _| |_ _| |_ 
| |_| | |_) | |_| |/ /| |__|_   _|_   _|
 \___/| .__/ \__|_/_/  \____||_|   |_|  
      |_|                             
C++, sauce optimisée !

	
  ____              _____        _   _           _           _   _             
 / ___| _     _    / / _ \ _ __ | |_(_)_ __ ___ (_)___  __ _| |_(_) ___  _ __  
| |   _| |_ _| |_ / / | | | '_ \| __| | '_ ` _ \| / __|/ _` | __| |/ _ \| '_ \ 
| |__|_   _|_   _/ /| |_| | |_) | |_| | | | | | | \__ \ (_| | |_| | (_) | | | |
 \____||_|   |_|/_/  \___/| .__/ \__|_|_| |_| |_|_|___/\__,_|\__|_|\___/|_| |_|
                          |_|                                                  

C++, sauce optimisée !

	

Sommaire



Descriptif

Ce document suit le développement du projet Cracker-ng afin d'avoir des exemples concrêts d'optimisations C++.
Étant un utilitaire permettant de trouver le mot de passe de certains fichiers (ZIP, CPT), il faut donc optimiser au maximum les routines.
Ce document sera mis à jour régulièrement suivant l'évolution du logiciel ainsi que de nos connaissances.
Toutefois, si tu as parcouru le code source et que tu vois une partie qui pourrait être améliorée, n'hésite pas à faire une requête sur GitHub ou envoyer un courriel :)


Note : tous les fichiers tests seront compilé à l'aide de la commande g++ fichier.cc -o fichier, càd sans optimisation de la part du compilateur (G++ version 4.7.2). Vous pouvez télécharger le fichier pour les tests.

Environnement : une Debian de la mort qui tue avec un noyau 3.2.35, le tout propulsé par un i5 750 @ 2.66GHz.



char* et std::string

Situation :

Cracker-ng peut récupérer les mots de passe à tester depuis l'entrée standard (STDIN).
Le mot est ensuite stocké dans une variable pwd qui est du type std::string.

Code (char_string_1.cc) :

#include <iostream>
#include <string>

int main(int argc, char *argv[]) {
	std::string pwd;
	
	while ( getline(std::cin, pwd) ) {
		// Traitement
	}
}

Code avec un while complet (char_string_2.cc) :

#include <iostream>
#include <string>

int main(int argc, char *argv[]) {
	std::string pwd;
	
	while ( !getline(std::cin, pwd).eof() ) {
		// Traitement
	}
}

L'inconvénient ici, c'est que le type std::string est surchargé, plusieurs fonctions lui sont ajoutées telles que c_str(), data(), size() ou encore length(). Bien que cela puisse être pratique, ici c'est du gaspillage de ressources.
L'idéal serait d'avoir notre variable pwd sans toute ces fioritures.

Passons pwd en type char* (char_string_3.cc) :

#include <iostream>

int main(int argc, char *argv[]) {
	int len = 32;
	char *pwd = new char[len];
	
	while ( std::cin.getline(pwd, '\n') ) {
		// Traitement
	}
	
	delete[] pwd;
}
MàJ du 2013/08/03 : essayons d'abord de spécifier de ne pas synchroniser std::cin avec les fonctions native du C en utilisant std::ios_base::sync_with_stdio(false);.
Voici le codes des deux tests (char_string_4.cc) :

#include <iostream>
#include <string>

int main(int argc, char *argv[]) {
	std::ios_base::sync_with_stdio(false);
	std::string password;
	
	while ( getline(std::cin, password) ) {
		// Traitement
	}
}
Code avec un while complet (char_string_5.cc)
#include <iostream>
#include <string>

int main(int argc, char *argv[]) {
	std::ios_base::sync_with_stdio(false);
	std::string password;
	
	while ( !getline(std::cin, password).eof() ) {
		// Traitement
	}
}

Comparatif des tests
Script 10^8 mots %
char_string_1.cc 41.31 sec 100.00%
char_string_2.cc 41.91 sec 101.45%
char_string_3.cc 35.87 sec 86.83%
char_string_4.cc 5.5 sec 13.31%
char_string_5.cc 5.49 sec 13.29%

Résultat : un gain de 86.71% sur le nombre de mots / seconde.


Lire depuis l'entrée standard ou un fichier

Même situation et même code que la partie précédente (§ char* et std::string).

Idem, std::cin est surchargée et non optimisée (l'utilisation de iostream n'est pas la bon choix pour ce genre de situation).
Nous allons donc passer par une fonction optimisée pour la lecture depuis un descripteur de fichier (w) (FILE*) comme le sont STDIN (l'entrée standard) ou n'importe quel fichier (tel un dictionnaire).

Voici donc la fonction en question (src) :

bool read_stdin(char *buffer, int len, FILE *input) {
	if ( fgets(buffer, len, input) != NULL ) {
		char *lf = strchr(buffer, '\n');
		if ( lf != NULL ) {
			 *lf = '\0';
		}
		return true;
	}
	return false;
}

Elle permet de récupérer une chaîne de caractères correctement terminée par \0.
Les arguments de la fonction :

Code avec la nouvelle fonction (stdin_fichier.cc) :

#include <cstdio>
#include <cstring>

bool read_stdin(char *buffer, int len, FILE *input) {
	if ( fgets(buffer, len, input) != NULL ) {
		char *lf = strchr(buffer, '\n');
		if ( lf != NULL ) {
			 *lf = '\0';
		}
		return true;
	}
	return false;
}

int main(int argc, char *argv[]) {
	int len = 32;
	char *pwd = new char[len];
	FILE *input = stdin;
	// Pour un fichier, input se déclare tel que :
	// FILE *input = fopen("fichier", "r");

	while ( read_stdin(pwd, len, input) ) {
		// Traitement
	}

	delete[] pwd;
	// Si input != stdin, alors il faut libérer le descripteur
	// fclose(input);
}

Comparons ce code à celui qui a eu les meilleurs résultats au chapitre précédent (§ char* et std::string).

Comparatif des tests
Script 10^8 mots %
char_string_5.cc 5.49 sec 100.00%
stdin_fichier.cc  4.33 sec 78.87%

Résultat : un gain de 21.13% sur le nombre de mots / seconde.


Le mot clef inline

Même situation et même code que la partie précédente (§ Lire depuis l'entrée standard ou un fichier).

Ce coup-ci, intéressons-nous au mot clef inline.
D'après le très bon site Developpez.com :

Quand le compilateur évalue l'appel d'une fonction inline, le code complet de cette fonction est inséré dans le code de l'appelant (c'est le même principe que ce qui se passe avec un #define). Cela peut, parmi beaucoup d'autres choses, améliorer les performances, étant donné que l'optimiseur peut intégrer directement le code appelé, voire optimiser le code appelé en fonction du code appelant.

Pour plus d'informations, voir la FAQ dédiée.
Rappelons qu'il n'est pas conseillé de mettre une fonction inline si celle-ci contient plus de 10 lignes.

Code avec la fonction inline (inline.cc) :

#include <cstdio>
#include <cstring>

inline bool read_stdin(char *buffer, int len, FILE *input) {
	if ( fgets(buffer, len, input) != NULL ) {
		char *lf = strchr(buffer, '\n');
		if ( lf != NULL ) {
			 *lf = '\0';
		}
		return true;
	}
	return false;
}

int main(int argc, char *argv[]) {
	int len = 32;
	char *pwd = new char[len];
	FILE *input = stdin;
	// Pour un fichier, input se déclare tel que :
	// FILE *input = fopen("fichier", "r");

	while ( read_stdin(pwd, len, input) ) {
		// Traitement
	}

	delete[] pwd;
	// Si input != stdin, alors il faut libérer le descripteur
	// fclose(input);
}

Comparons ce code à celui de stdin_fichier.cc.

Comparatif des tests
Script 10^8 mots %
stdin_fichier.cc 4.33 sec 100,00%
inline.cc 4.32 sec 99.77%

Résultat : un gain de 0.23% sur le nombre de mots / seconde.



Conseils en vrac

Voici une liste de pratiques et conseils qui ne nécessitent pas de chapitre à part entière.

  1. Variables lourdes et les boucles : il est préférable de sortir une variable gourmande d'une boucle plutôt que de la redéfinir constamment.

    C'est pas terrible :
    while ( read_stdin(pwd, 32, input) ) {
    	std::stringstream compressed;
    	// Traitement
    }
    C'est mieux :
    std::stringstream compressed;
    while ( read_stdin(pwd, 32, input) ) {
    	// Traitement
    	compressed.str(std::string());  // Réinitilisation
    }
    Comme ça il n'y a qu'une seule allocation mémoire de compressed. Il faut garder à l'esprit que ce type (std::stringstream) est déjà bien lourd de base.
  2. Structures lourdes : dans la même idée, pour les structures, il vaut mieux passer un pointeur ou une référence à une fonction plutôt que de la définir au sein de cette dernière.

    Exemple tiré du module CPT.
    Avant :
    inline void hashstring(const char *k, word32 *h) {
    	register unsigned int i;
    	roundkey rkk;  // Cet objet fait 512 octets !
    	word32 key[8] = {0};  // rijndael key
    	// Opérations
    }
    
    while ( read_stdin(pwd, 32, input) ) {
    	// Traitement
    	hashstring(pwd, hash);
    }
    Après :
    inline void hashstring(
    	const char *k, word32 *h, roundkey rkk
    ) {
    	register unsigned int i;
    	word32 key[8] = {0};  // rijndael key
    	// Opérations
    }
    
    roundkey rkk;
    while ( read_stdin(pwd, 32, input) ) {
    	// Traitement
    	hashstring(pwd, hash, rkk);
    }
    Résultat : un gain de 13.5% sur le nombre de mots / seconde.


GCC, sauce optimisée !

GCC permet de choisir certaines optimisations lors de la compilation.

Voici celles utilisées pour Cracker-ng :



Références et sources diverses



Historique


Contenu modifié le 01/10/2013.
moc.liamg@gitobob - Philosophie.

congregational