Vu le manque de documentation a ces sujets en francais sur le net, je me suis attele a la tache.
Liste des optimisations connues (en C)
Minimisation Kit (Comment faire un serveur web de 16ko)
Les Lois qui régissent la réussite d'un développement logiciel
Définition du programmeur
Livres de sciences et de programmation
Tous ces articles sont sur http://tuan.kuranes.free.fr/#ik
Voila, j'ai regroupe mes connaissances, experiences et infos glanes sur le net a ces sujet ne faisant des articles en francais (enfin la plupart).
J'attends vos reactions, ajouts, precision et autres commentaires constructif.
(je cherche particulierement des optimisations binaires sur low endian ?)
Journal Informatique : Optimisation, minimisation, projet
13
juin
2003
# Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 2.
(sur les navigateurs qui supportent les feuilles de styles alternatives (moz, firebird, opera...))
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par blackshack . Évalué à 3.
Pourquoi il y ait pas??
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 1.
mais effectivement faut rajouter le lien
Je le rajoute.
http://www.fefe.de/fnord/(...)
Merci
# Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 3.
ca veut dire quoi, quel que soit le prix?
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 1.
Avez-vous les meilleurs outils de developpement, sans consideration de prix ?
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 2.
# Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 2.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 1.
je ne connais pas les effets sur l'optimisation.
Dis-m'en plus !
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 3.
for(i=0;i<max;++i){...}
que
for(i=0;i<max;i++){...}
car dans le premier cas, il n'utilise pas de variable temporaire pour stocker le résultat de l'incrémentation... je l'avais déjà lu autre part, mais je ne connais pas le fondement exact. Faudrait rechercher...
Le premier lien correcpondant sur google (recherche: "++i plutot que i++") c'est
http://www.cppfrance.com/article.aspx?Val=1073(...)
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 1.
Bien que je suspecte fortement ce genre d'optimisation risque d'etre effectue par le compilateur.
Tres interressant, merci.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 1.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 1.
C'est toujours mieux de le savoir plutot que de demander au compilos...
En tout cas Merci !!
(Je ferais les greeting a la fin, je mettrais les pseudos, a moins d'informations contraires...)
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 1.
Je suis étudiant en mathématiques et informatique, et j'ai vu que tu avais participé à une conférence consacrée à MathML. C'est comment, à utiliser (je connais juste LaTeX et HTML/XML/PHP, mais utiliser les deux en même temps, ça me tente de + en +).
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 1.
Le plus facile, c'est avec amaya, mais faut apprendre les raccourcis clavier.
Mais ca te permet d'avoir des documents tres flexibles (XML oblige).
Le seul probleme vient que TRES PEU de conference te permettent de proposer des papiers avec du MathML dedans.
Mais en comparaison, c'est la maniere la plus puissante d'ecrire des maths dans un doc.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jmfayard . Évalué à 1.
Ce qui serait bien, ce serait un convertisseur \LaTeX{} ==> MathML
(uniquement pour les formules de math, évidemment)
</rêve>
Les formules de math, c'est quand même vraiment agréable à taper
en \LaTeX{} et beaucoup de mathématiciens savent le faire.
OK, je sais, latex c'est un format de présentation et pas de structure comme
XML, ce qui rend la chose difficile, mais un convertisseur intelligent doit
pouvoir arriver à le faire, non ?
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par Vincent P (site web personnel) . Évalué à 1.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par PegaseYa . Évalué à 1.
Ensuite, l'économie réalisée est parfaitement négligeable par rapport à une mauvaise utilisation des printf par exemple.
Enfin, pour permettre une bonne relecture, il vaut mieux respecter certaines règles d'écriture, et toujours écrire i++ en fait partie. Un truc du genre: tableau[i++] n'est pas joli du tout, parce qu'il va falloir toujours se reposer la question, la variable est-elle incrémentée avant ou après ?
Bref, dans la majorité des projets, il vaut mieux d'abord faire un code lisible lorsque l'on parle de petites optimisations, et savoir que certaines opérations sont très couteuses, plutôt que d'obscurcir le code pour des gains négligeables.
PS: j'ai eu aussi un prof qui m'avait donné le conseil d'écrire ++i dans les boucles, mais un autre m'a par la suite convaincu du contraire.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par daggett . Évalué à 1.
$ cat postinc.c
#include <stdio.h>
int main(int argc, char **argv){
int a,i;
a = 0;
for (i=0; i<100000; i++)
a+=i;
printf(" a = %d\n", a);
return 0;
}
$ diff postinc.c preinc.c
6c6
< for (i=0; i<100000; i++)
---
> for (i=0; i<100000; ++i)
$ gcc -Wall -O0 -S postinc.c preinc.c
$ diff postinc.s preinc.s
1c1
< .file "postinc.c"
---
> .file "preinc.c"
Voila, meme en optimisation 0, aucune différence dans le code assembleur généré.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par ckyl . Évalué à 1.
--> [-1]
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 1.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 1.
peut-etre dans une section, mais en l'absence de preference en la matiere je sais pas trop...
J'ai toujours trouve ca trop verbeux, la notation polonaise...
j'aime bien les concepts a la java (minuscules - majuscule) mais ca m'a jamais vraiment gene...
En fait, en matiere de doc, a part les specifs technique et les docs de l'analyse (genre graph heritage) le reste ne m'a jamais servi a rien....
Je vais reflechir a une section documentation -
nom de variables, Code style, documentation automatique...
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 2.
On a presque le même id d'utilisateur (#5629 <-> #5613), on a du créer notre compte presque au même moment!!! :-)))
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par huhuhu . Évalué à 2.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 2.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par Nicolas Roard (site web personnel) . Évalué à 1.
Actuellement j'essaie de me tenir au moins à la notation suivante :
- paramètres de fonctions préfixés par "a" ou "an"
- données membres préfixés par "the"
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par ckyl . Évalué à 1.
=========== i++ VS ++i ==================
$diff test1.c test2.c
7c7
< for(i=0; i<12000; i++)
---
> for(i=0; i<12000; ++i)
[13:39:45] cykl ~/test ¤ gcc -S test1.c
[13:39:52] cykl ~/test ¤ gcc -S test2.c
[13:39:55] cykl ~/test ¤ diff test1.s test2.s
1c1
< .file "test1.c"
---
> .file "test2.c"
Quelqu'un peu me presenter un exemple concret ???
notez qu'il n'y a meme pas d'O.
============== x*2 VS x + x ================
[13:47:03] cykl ~/test ¤ diff test3.c test4.c
7c7
< x = x * 2;
---
> x = x + x;
[13:48:03] cykl ~/test ¤ gcc -S test3.c
[13:48:10] cykl ~/test ¤ gcc -S test4.c
[13:48:12] cykl ~/test ¤ diff test3.s test4.s
1c1
< .file "test3.c"
---
> .file "test4.c"
21,23c21,23
< movl -4(%ebp), %eax
< sall $1, %eax
< movl %eax, -4(%ebp)
---
> movl -4(%ebp), %edx
> leal -4(%ebp), %eax
> addl %edx, (%eax)
[13:48:15] cykl ~/test ¤ gcc -O3 -S test4.c
[13:48:20] cykl ~/test ¤ gcc -O3 -S test3.c
[13:48:22] cykl ~/test ¤ diff test3.s test4.s
1c1
< .file "test3.c"
---
> .file "test4.c"
==================== x / 2 VS x * 0.5 ====================
[13:49:54] cykl ~/test ¤ diff test3.c test4.c
7c7
< x = x / 2;
---
> x = x * 0.5;
[13:49:33] cykl ~/test ¤ gcc -S test3.c
[13:49:39] cykl ~/test ¤ gcc -S test4.c
[13:49:42] cykl ~/test ¤ diff test3.s test4.s
1c1
< .file "test3.c"
---
> .file "test4.c"
4a5,8
> .align 8
> .LC1:
> .long 0
> .long 1071644672
21,27c25,34
< movl -4(%ebp), %edx
< movl %edx, %eax
< sarl $31, %eax
< shrl $31, %eax
< leal (%eax,%edx), %eax
< sarl $1, %eax
< movl %eax, -4(%ebp)
---
> fildl -4(%ebp)
> fldl .LC1
> fmulp %st, %st(1)
> fnstcw -6(%ebp)
> movw -6(%ebp), %ax
> movb $12, %ah
> movw %ax, -8(%ebp)
> fldcw -8(%ebp)
> fistpl -4(%ebp)
> fldcw -6(%ebp)
[13:49:45] cykl ~/test ¤ gcc -O3 -S test4.c
[13:49:50] cykl ~/test ¤ gcc -O3 -S test3.c
[13:49:52] cykl ~/test ¤ diff test3.s test4.s
1c1
< .file "test3.c"
---
> .file "test4.c"
=============================================
Toutes ces astuces me paraisse etre un peu de l'enculage de mouche puisque a premiere vu le compilateur peut tres bien le faire tout seul. C'est un peu la meme chose que les multiplications par un multiple de 2 qui sont transformée en decallage de bit. A priori le compilateur le fait et l'ecrire en dur sert juste a rendre le code illisible.
S'amuser a lire les sorties assembleurs de l'ami gcc est parfois tres interessant meme si ce n'est faisable que sur de petits codes.
Donc je suis _VRAIMENT_ interessr pour qu'on me montre du code ou de telles optimisations _DOIVENT_ etre faites a la main et pourquoi le compilateur ne le fait pas lui meme. Il y'a d'autres optimisations (voir le lien que je donne plus bas) qui elles ont vraiment un impacte sur la vitesse d'execution en tenant compte des caracteristiques des processeurs (dependances des variables etc...). Mais bien entendu il est tres difficile d'ecrire du code comme ca :-)
De plus tes optimisations des operateurs binaires sont vraiment attroces. Et permettrons a ton programme de ne jamais etre portable. On pourrait aussi faire les syscalls en assembleur :-)
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 1.
Essaye de comparer ces 3 fonctions en temps d'executions, et imagine toi 5000 appels de cette fonction par secondes... la difference est visible.
Si t'arrives a genere un code aussi rapide sans optimisations juste avec les optimisations compilo, ca m'interresse !!!!
Prb :
Recherche de la plus proche puissance de 2 superieure.
/*sans optimisation*/
int p2(p)
{
return 1 << (int) ceilf(logf((float) p) / M_LN2);
}
===========================
/*avec*/
#define lowest_bit(x) (x & -x)
#define is_pow2(x) (x != 0 && x == lowest_bit(x))
static int ceil_pow2_minus_1(unsigned int x)
{
unsigned int i;
for (i=1; i; i <<= 1)
x |= x >> i;
return x;
}
#define p2(p) (is_pow2(p)?p:ceil_pow2_minus_1((unsigned int) p) + 1)
====================
/* pareil*/
int p2(p){
p -= 1;
p |= p >> 16;
p |= p >> 8;
p |= p >> 4;
p |= p >> 2;
p |= p >> 1;
return p + 1;
}
=========================
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par ckyl . Évalué à 1.
J'ai trouve dans le noyau une telle fonction et j'ai benchmarke rapidos et salement sur 1000000 de passage (les fonctions traite un tableau d'entier remplis aleatoirement qui reste le meme pour les 3 fonctions).
[14:51:05] cykl ~/test ¤ gcc test5.c -Wall -lm
[14:51:24] cykl ~/test ¤ ./a.out
Temps pris par la version de base : 567250
Temps pris par la version de optimisee : 414988
Temps pris par la version noyau : 275745
[14:51:26] cykl ~/test ¤ gcc test5.c -Wall -lm -O3
[14:53:16] cykl ~/test ¤ ./a.out
Temps pris par la version de base : 393512
Temps pris par la version de optimisee : 199696
Temps pris par la version noyau : 185453
Ca vaut ce que ca vaut....
Comme tout benchmark hors contexte. Je colle pas l'horible .c qui ma servit au test :-)
Je dois par contre avoue que la fonction est pas vraiment mieux ce qui repond pas vraiment a la question! elle se trouve dans pci_st40.c nommee r2p2().
Je suis tout a fait d'accord que dans certains cas particuliers cela vaut le cout, il s'agit simplement de ne pas croire qu'il faut bousillier le code de partout avec des bizarries que meme les Perlistes comprennent pas.
On pourrait se faire des Golfs en plus pour vraiment plus rien comprendre
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 1.
Evidemment, ces optimisations sont négligeables par rapport à une optimisation du genre:
transformée de fourier discrète o(n^2) => transformée de fourier rapide o(nln(n)).
Mais les optimisations décrites ci-dessus sont intéressantes si tu doit écrire le compilateur... Evidemment, ca n'arrive pas souvent, mais une nouvelle archi (type embarqué) a souvent besoin d'un compilo léger, et faut parfois mettre la main à la pâte...
Mais je le reconnais, et c'est con pour les mouches, qui vont avoir mal au c*, ça ne vole pas haut...
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par Schwarzy . Évalué à 3.
Je crois que bien des gens ici ne se rende pas compte que des outils de compilations comme gcc, icc ou MCVS sont d'une qualité rare et le fruit d'années de travail par des gens de qualité.
Programmer certains chip proprio demande à la fois de bien choisir les algo mais aussi de veiller à une implementation qui fait aussi de l'optimisation. Ne pas faire confiance au compilo est souvent de règle (sauf si c'est gcc, pas mal présent dans l'embarquée mais encore assez à mon goût).
# Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 2.
Il en manque quand même:
- L'article de Huffman (de 1952) "A method for the construction of minimum redundancy codes" (?) consacré à la compression (de Huffman), utilisé par bzip2, JPEG, ...
- Le papier de Laurent Schwartz sur les distributions qui a révolutionné les calculs d'EDP et validé le point de vue physique des calculs d'EDP(http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Schwartz.ht(...))
- Et Turing dans tout ça?
... y'en a pas mal d'autres, mais déjà, avec ça... Faut vraiment pas oublier Schwartz, notre génie des mathématiques décédé l'été dernier...
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 1.
Peut-etre une section meilleurs papiers informatique ?
Pour turing, dans cette meme nouvelle categorie, c'est difficile de sortir un papier ou de composer un titre... Si t'as un titre ou une reference, je suis preneur ?
je vais quand meme pas mettre : Turing on computer ?
Pour Swartchz, il me faudrait un titre de papiers ou d'oeuvre, sinon, je mets
Laurent Schwartz on partial differential equations
C'est un peu juste, non ?
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par jm trivial (site web personnel) . Évalué à 1.
"Généralisation de la notion de fonction, de dérivation, de transformation de Fourier et applications mathématique et physiques" (en 1948)
Bien sûr, la réédition de 195? est plus complète, et le point de vue un petit peu plus moderne (les distr. on évolué depuis), mais le texte fondateur est celui-ci.
Pour Turing:
"The Turing machine, computability, universal machine" (cf http://home.manyrivers.aunz.com/kathleen/computing_alan_turing.htm(...) ou http://www.turing.org.uk/turing/(...))
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par Kriek . Évalué à 1.
"Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme"
traduit en anglais dans "From Frege to Gödel" de J. van Heijenoort (truffé d'articles repères pour l'informatique et les maths
# Re: Informatique : Optimisation, minimisation, projet
Posté par peyo (site web personnel) . Évalué à 3.
- l'optimisation du code : TRUST the compiler !!!
J'ai vite préféré user du temps à écrire des algorithmes déjà optimisés (méthodes de recherche opérationnelle, algo génétiques ...) que de me demander si je devais utiliser i++ plutot que i=i+1 dans mon code.
- Utiliser les principes de la programmation structurée :
Citation :
[...]Programmation dans laquelle on utilise des structures de contrôle (boucles do, for, while...) standardisées qui permettent d'écrire un code plus clair et plus simple à maintenir. [...] La programmation structurée est un nom générique qui couvre un courant de pensée. Ce courant de pensée s'est développé entre les années 1965 et 1975. La programmation structurée a pour but de faciliter le travail de relecture des programmes et de minimiser le travail de maintenance[...]
un bon exemple sur ces principes ici :
http://etna.int-evry.fr/COURS/COURSC/node88.html(...)
le même algo est écrit de plusieurs manières différentes, dont certaines à privilégier. (ici, calcul de la plus grande valeur absolue de deux nombres)
++ et bon code à tous
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par tuan kuranes (site web personnel) . Évalué à 2.
=> Il faut differencer les applications qui necessite des optimisations qui defigure le code qt (exemple : jeux, edition graphiquem, animations) des applis numeriques, scientifiques ou souvent les algorithmes, la structure et la clarte du code priment, pour sa diffusion. Ainsi, il convient avant d'optimiser de choisir sa voie : optmisation algorithmique ou d'ecriture de code.
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par Quzqo . Évalué à 1.
Sans avoir lu les liens (cause que le proxy n'M pas), on peut aussi favoriser :
- les tests les plus probables afin d'optimiser les branchements prédictifs des processeurs de nouvelle génération (mais c'est parfois au détriment de la lisibilité) et éviter les sauts (goto, jump...)
- l'alignement des données sur des multiples de l'octet, voire du mot du processeur (mais bien peu portable dans le second cas)
- les appels Pascal/C selon les arguments en entrée / sortie / mise à jour d'une méthode/procédure
- les comparaisons binaires
- les allocations statiques
- la non utilisation de concepts objets comme les héritages, les classes abstraites, virtuelles, les exceptions
- define & inline
- d'autres trucs encore...
# Re: Informatique : Optimisation, minimisation, projet
Posté par ckyl . Évalué à 3.
http://www.madchat.org/coding/c/hack_processeur_en_C.html(...)
tout ca pour gagner 3 cycles CPU alors que le choix du bon algorithme en log(n) au lieu de n t'aurais fait gagne quelques annees CPU :-)
Enfin je pense que quand les programmeurs sauront deja vraiment choisir le bon algo alors il sera temps de s'amuser avec ++i et i++
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par ckyl . Évalué à 2.
http://www.freebsd.org/cgi/getmsg.cgi?fetch=331177+334627+/usr/loca(...)
Petite discution sur FreeBSD-Hacker concernant les micros optimisations dans le noyau. Au final ca donne quelque chose comme ca :
1/ Si tu veux gamins amuse toi sur ta branche a toi mais viens pas nous moisir notre code
2/ Tu ferais mieux d'aller aider la team de gcc plutot que de faire mumuse sur notre code a nous....
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par Nicolas Boulay (site web personnel) . Évalué à 1.
Il existe un algo en log(n) pour la multiplication de matrices pleines ?
"La première sécurité est la liberté"
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par ckyl . Évalué à 1.
Comme quoi il vaut mieux choisir le bon algo et seulement ensuite on regarde ce qu'on peut optimiser et que ca reste maintenable.
Aller je met 4 cycles pour te faire plaisir :-þ
Pour la matrice : oui si elle est pleine de 0
[^] # Re: Informatique : Optimisation, minimisation, projet
Posté par Nicolas Boulay (site web personnel) . Évalué à 1.
Nan, parce que c'est moi qui écrit l'article que tu pointes (cela fait d'ailleurs toujours plaisir d'être cité), et que j'étais assez fière des différences de perf entre l'implementation de base et celle optimisé (genre x4 minimum, et x25 dans le cas extrème d'une matrice 512*512).
La différence n'est donc pas négligeable.
"La première sécurité est la liberté"
# break, goto...
Posté par PegaseYa . Évalué à 1.
Peut-être que je ne travaille pas sur un logiciel à fortes contraintes, mais il me semble, comme dit plus haut, qu'il est bien plus intéressant de respecter des conventions d'écriture et de choisir les bons algorithmes plutôt que de tenter de faire des économies de bouts de chandelles...
[^] # Re: break, goto...
Posté par tuan kuranes (site web personnel) . Évalué à 1.
Le temps reel dans des applis.
Enfin, n'empeche que je ne suis on ne peut plus d'accord, et je pensais l'avoir fait passer dans mon "Quand optimiser"... mais cela n' pas l'air d'tre le cas...
Je vais donc rajouter :
Avant de defigurer du code par des optimisations barbares et dependante de l'architecture de la machine, Il faut absolument etre sur d'utiliser le meilleur algo. Au besoin, il faut pouvoir prouver son choix. Verifier son analyse du probleme et l'adequation de sa solution.
Alors, apres tout cela, si vous n'arrivez pas a obtenir un code assez rapide, vous pouvez essayer d'optimiser de facon barbare.
Et je vais diviser en deux :
Optimisation propre
Optimisation barbare
Mieux ?
[^] # Re: break, goto...
Posté par Nicolas Boulay (site web personnel) . Évalué à 3.
"La première sécurité est la liberté"
[^] # Re: break, goto...
Posté par tuan kuranes (site web personnel) . Évalué à 1.
[^] # Re: break, goto...
Posté par Schwarzy . Évalué à 1.
1/ la complexité des algos (bref bien choisir les algo).
2/ les structures de données.
3/ le code en lui-même.
Avec les années et la maturité de compilos sur les machines de bureau et les serveurs, la dernière étape (3/) n'a presque plus de sens. Presque, parce que pour le multimédia et les instructions spécialisées (niveau 3/), il faut faire la 2/ pour ensuite avoir la 3/. Il arrive aussi que la 2/ et la 1/ se retrouve liées.
Mais je trouve finalement que l'importance du cache dans les perfs en calcul renforce le niveau 2/ dans les optimisations. Un bon exemple se trouve avec les calculs sur les matrices, il est possible de multiplier les perfs par 4 en arrangeant différemment les éléments.
[^] # Re: break, goto...
Posté par Nicolas Boulay (site web personnel) . Évalué à 1.
La structure des données impact sur l'algorithme à choisir. Une structure simple peut faire en sorte qu'un algo n² soit plus rapide qu'un log(n). (le cas typique est le trie à bulle d'une liste déjà "bien" trié) : genre un bète tableau indexé par un entier peut être bien plus rapide qu'un hash ou qu'un arbre binaire, si la structure est à haute densité on ne perd pas trop de place.
En général, les études d'algorithmes que l'on lit dans les livres considèrent que tout acces mémoire est à cout constant. Or un caches miss c'est de 20 à 200 cycles de perdu.
La structure de donné permet d'augmenter un peu la localité statique des données (genre écrire tab[100][3] et non tab[3][100] si on utilise les 3 élèments de suite à chaque fois)
un autre conceil : ne jamais utiliser de pointeur !! il faut utiliser un tableau. Les const aident aussi le compilo.
"La première sécurité est la liberté"
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.