Optimisation vitesse pure
Ok, topic simple : ça fait longtemps que je programme, et ça fait un peu trop longtemps que je vois des gens taper du code pas optimisé du tout.
Donc, je souhaiterai partager les techniques simples que j'ai apprises au fil des ans.
A noter : j'optimise plutot en vitesse pure, vu que c'est ce dont j'ai besoin le plus souvent.
Participation a ce sujet : si vous voulez proposer des solutions differentes ou si vous trouvez que mes solutions sont mauvaises, des arguments sont obligatoires.Je ne suis pas parfait, mes algos non plus, mais ne venez pas me dire "c'est plus lent que ce que j'ecris" sans arguments pour le justifier ...
Page 1 : ici
Page 2 : Quelques techniques d'implementation, en vrac
Sous-sujet du jour : utilisation de la STL, version speed.
Généralités :
Pour les iterateurs , la preincrémentation est toujours plus rapide que la post incrémentation.
En terme de vitesse pure : tableau de base > vector > list > [ set > map > multimap ] pour du parcours simple.
Set / Map > Multimap > [ vector / tableau ] > list pour une recherche par clef.
Set > [ vector / tableau ] > list > [ map / multimap ] pour une recherche par element( sans connaitre la clef).
La FAQ C++ a un joli diagramme pour vous aider a choisir votre conteneur
La complexité des operations sur les conteneurs de la stl sont dispos sur le net.
i++ et ++i, si i est un type de base ( int , float, etc), est strictement equivalent en vitesse.
Insertion d'un element dans une map / set :
Edit : version optimisé par Screetch, merci.
Code:
1
2
3
4
5
| const std::pair< MapType::iterator, bool > & result = map.insert( clef, element );
if(!result.second)
{
//Element existant déja, result.first pointe dessus
} |
Si vous savez déja que l'element n'existe pas ( premier remplissage d'une map par exemple) :
Code:
map.insert( MapType::value_type( clef , element ) );
A noter que ça revient presque au même que la version precedante. Par contre c'est plus court a ecrire.
A noter aussi : l'operateur [] sur une map est a eviter. En effet il crée un element avec le constructeur par default, puis vous renvoie la reference, que là vous changez. Donc construction par default + copie au lieu de construction par copie.
Parcours d'une map / set :
Code:
1
2
3
4
5
6
| MapType :: iterator iter = map.begin();
const MapType :: iterator & iend = map.end();
for( ; iter != iend ; ++ iter )
{
//boucle
} |
Parcours d'un vector:
Code:
1
2
3
4
5
| unsigned int imax = vector.size();
for( unsigned int i = 0 ; i < imax ; ++ i )
{
boucle avec vector[i]
} |
Vider une map / set / multimap
Si votre map ne contient pas de pointeurs : map.clear() suffit.
Sinon :
Code:
1
2
3
4
5
6
7
| MapType :: iterator iter = map.begin();
const MapType :: iterator & iend = map.end();
for( ; iter != iend ; ++ iter )
{
delete iter->second;
}
map.clear(); |
Simple recherche sur map / set :
Code:
1
2
3
4
5
| const MapType :: iterator & ifind = map.find( clef );
if( ifind != map.end() )
{
//code
} |
Optimisations Generales :
Optimisations Basiques :
En vrac :
-> Utilisez les reference sur les structures / classes. C'est facile de l'oublier, et on le paye d'une copie. Tres couteux quand on l'oublie sur une map ...
Code:
void fonction( std::string p_name )
->
Code:
void fonction( const std::string & p_name )
Virez le const si vous souhaitez modifier le parametre.
-> Utilisez les liste d'initialisation dans les constructeurs
Un exemple vaut plus qu'un discours:
Code:
1
2
3
4
5
6
7
| class A
{
private:
std::string m_name;
public:
A( const std::string & p_name ){m_name = p_name;}
}; |
Fait appel au constructeur par defaut de std::string, puis fait une copie.
Code:
1
2
3
4
5
6
7
| class A
{
private:
std::string m_name;
public:
A( const std::string & p_name ) : m_name (p_name){}
}; |
Ne fait appel qu'au constructeur par copie.
-> Evitez les objets temporaires si possible :
Code:
1
2
3
4
5
6
7
8
| Vector3 V3_Add( const Vector3 & p_a , const Vector3 & p_b )
{
Vector3 a;
a.x = p_a.x + p_b.x;
a.y = p_a.y + p_b.y;
a.z = p_a.z + p_b.z;
return a;
} |
Profitez des constructeurs avec parametres :
Code:
1
2
3
4
| Vector3 V3_Add( const Vector3 & p_a , const Vector3 & p_b )
{
return Vector3( p_a.x + p_b.x , p_a.y + p_b.y , p_a.z + p_b.z )
} |
-> Utilisez les references temporaires :
Code:
1
2
3
4
5
| void Function( const std::string & p_filename , const std::string & p_directory )
{
std::string l_fullname;
l_fullname = p_filename + p_directory;
} |
Ici, vous faitent appel a un constructeur par defaut, puis une copie.
Code:
1
2
3
4
| void Function( const std::string & p_filename , const std::string & p_directory )
{
const std::string & l_fullname = p_filename + p_directory;
} |
Alors que la, plus de constructeur pour rien, plus de copie.
Inutilisable si vous devez faire des modifications sur l_fullname, par contre.
-> Profitez des constructeurs par copie :
Code:
1
2
3
4
5
| void Function( const std::string & p_filename )
{
std::string l_name;
l_name = p_filename;
} |
Admettons que vous ayez besoin de l_name pour le modifier.Vous auriez du ecrire :
Code:
1
2
3
4
| void Function( const std::string & p_filename )
{
std::string l_name = std::string(p_filename);
} |
Le compilateur optimisera en faisant appel directement au constructeur par copie, plutot que l'habituel couple constructeur defaut + copie.
-> Utilisation des tableaux a 2 dimensions :
Attention a cela.Si les 2 dimensions sont assez faibles, preferez un tableau a une dimension ( remplacez un 16x16 par un 256 directement), ça evite des allocations mémoires en plus, des dereferencements compliqués, des boucles for imbriquées, etc.
Exception : les très grand tableaux, du genre 4000 x 4000.doubles.
Dans la pluspart des cas pour ce genre de tableaux, ils sont tellements gros qu'il ne rentrent pas dans le cache du proc, donc le decouper en morceaux peut eventuellement etre utile. A tester au cas par cas.
-> Groupez les traitements sur une donnée.
Pour avoir testé moi même :
Code:
1
2
3
4
| X = caller->m_childs[0];
Y = caller->m_childs[1];
if(X->m_hasFunction)X->m_function(X);
if(Y->m_hasFunction)Y->m_function(Y); |
Est plus rapide ( d'un cycle proc exactement, d'apres mes tests), que :
Code:
1
2
3
4
| X = caller->m_childs[0];
if(X->m_hasFunction)X->m_function(X);
Y = caller->m_childs[1];
if(Y->m_hasFunction)Y->m_function(Y); |
Probablement parceque m_childs reste dans les registres dans la premiere version et pas dans la deuxième.
Choses a ne pas faire : : ( liste non exhaustive ).
A noter que cette liste n'est valable que sur des compilateurs performants( vc++, gcc), si vous travaillez sur des compilos alternatifs, a vous de tester.
-> Remplacer les multiplications par des decalages de bits +/- additions.
-> Utiliser ++i au lieu de i++ sur des types de base( int, float).
-> Remplacer un truc du genre :
Code:
1
2
3
| const int a = 4;
const int b = 3;
const int c = a * b |
Par const int c = 12;
Le compilateur optimise de lui même tout ce qui est const a la compilation, et tout les calculs qui en découlent.Remplacer a * b par son resultat ne sert qu'a perdre de vu que c'est le resultat d'un calcul et non un chiffre "magique".
-> Utiliser __forceinline sans etre sur ce que l'on fait. Le compilateur est souvent meilleur que nous a ce jeu la.
-> Derouler les boucles. Exception pour les boucles courtes ( genre 3 tours).
-> Faire des boucles for avec des char et des short. Dans ce genre de boucle, l'index est geré par les registres.Les registres sont 32 bits minimum, donc int ou unsigned int.
-> Faire des boucles for du genre
Code:
for( unsigned int i = MAX ; i ; --i ){code;}
Une legende urbaine court selon laquelle decrementer un entier et verifier par rapport a zero est plus rapide que le bon vieux for ( i = 0 ; i < MAX ; i++ ). En fait non, puisque le compilateur l'optimise pour vous...
