Piste d'amélioration d'une chaînes d'objets

Gégé a écrit :

Effectivement ce genre d'outils peut m'être très utile ! Merci.
Malheureusement, j'utilise VC2005, tu connais un équivalent ?

Pas que je sache mais la programmation Windows c'est pas mon domaine. En
faisant un peu de google, j'ai trouvé une version d'évaluation 180 jours
(VC2005 Team edition qui l'inclut).
Est ce que VC6 n'avait pas un profiler intégré en standard ?

Sinon:
- si tu travailles sur AMD: AMD Code Analyst; j'ai aussi vu qu'il
fonctionnait sur Intel de façon limitée.
- Sur intel: Vtune (en évaluation)
- AQTime (en évaluation)

Maintenant sans un outil comme ça, il faut revenir à la méthode "huile
de coude". Il doit avoir des classes de profiling quelque part sur le
net pour mesurer les temps d'exécution. Au pire, c'est pas très dur d'en
faire une maison.

--
Michael

Gégé a écrit :

J'ai réduit les calculs des nœuds au plus simple : évaluation du nœud
fils et assignation d'une valeur constante.
Voici 2 tests caractéristiques :

* 14610 created nodes : 1285.68 Ko => exec_time = 4.718 sec ( 20000
itérations )
* 7310 created nodes : 643.28 Ko => exec_time = 1.61 sec ( 20000
itérations )

Quand je double ma structure, mon temps d exécution triple ....

ce qui (dé)montre ton impression, donc un autre /truc/ que
le temps de calcul intervient non linéairement.

dans un autre post, tu évoquais le possible impact du temps
d'accès à une "mémoire distante" (ce ne sont pas tes termes),
un adressage mémoire est quasi constant quelque soit l'adresse
utilisée ... s'il s'agit d'un espace mémoire effectivement
présent, par contre le swap de la mémoire est non constant,
non linéaire et couteux.

est-ce que les chiffres ci-avant (1286Ko pour 14610 noeuds
et 643Ko pour 7310 noeuds) représentent l'espace mémoire
requis pour les seuls noeuds du calcul ?

quel est ton modèle mémoire (32 ou 64 bits) et quelles sont
les tailles de mémoire physique installée sur la machine et
logique allouée à l'application ?
(s'il y a moins d'1 Mo dispo pour l'appli., le swap est
évident et le ralentissement simple à expliquer).

as-tu estimé (par dichotomie) à partir de quand le temps
de calcul n'est plus linéaire avec le nb de noeud ?
il devrait l'être jusqu'à une certaine limite puis croitre
en puissance après cette limite.

Sylvain.

On 2008-11-02, valasg@gmail.com <valasg@gmail.com> wrote:

Salut

J'ai cr?? un syst?me de n?uds (une sorte d'arbre), ou chacun peut
avoir entre 1 et 4 fils via des pointeurs. Pour s'?valuer le n?ud
racine appelle classiquement ses fils tours ? tours qui renvoient une
valeur (tout est fait en chaine).

Malheureusement, le temps d'exploration de l'arbre est de plus en plus
long ( > lin?aire ) lorsque sa taille grandit.

Avant d'aller chercher à optimiser des accès mémoires, tu peux déja
regarder si ton algo est linéaire, comme tu semble le croire, ou non.

Dans un autre post, tu dis ne pas pouvoir utiliser gprof car tu es
sous VC++. En quelques heures, tu peux installer GCC+gprof sur ta
machine, soit avec Cygwin, soit avec VirtualBox.
Quand on a déjà perdu plusieurs heures à la recherche d'un bug,
il est parfois utile de changer de méthode.

Sinon, tu peux aussi tracer les appels "à la main", en ajoutant
un compteur d'appel dans les principales fonctions de ton algo,
et en regardant le nombre d'appel pour différentes valeurs d'entrées.

Notamment, je me demandait si les cr?er dans des zones contigu?s de la
m?moire pouvait am?liorer leur temps de recherche.

Ca peut peut-être avoir une influence, mais je ne pense pas
que ça puisse donner des perfs polynomiales ou expronnentielles
à un algo linéaire.

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)

Sylvain SF <sylvain@boiteaspam.info> writes:

J'ai réduit les calculs des nœuds au plus simple : évaluation du nœud
fils et assignation d'une valeur constante.
Voici 2 tests caractéristiques :
* 14610 created nodes : 1285.68 Ko => exec_time = 4.718 sec ( 20000
itérations )
* 7310 created nodes : 643.28 Ko => exec_time = 1.61 sec ( 20000
itérations )
Quand je double ma structure, mon temps d exécution triple ....

ce qui (dé)montre ton impression, donc un autre /truc/ que
le temps de calcul intervient non linéairement.

Voici une formule reliant le temps au nombre de noeuds n :
T(n) = (3.108/7310)*n + (1.61-3.108) (en secondes)
C'est parfaitement linéaire. Bien sûr ça na marche pas pour les
petites valeurs de n, mais une complexité c'est toujours asymptotique.
Donc ces chiffres ne démontrent rien du tout.

Le mieux serait de faire plein de mesures pour des valeurs croissantes
du nombre de noeuds et de tracer la courbe. Si l'algo est vraiment
linéaire (ce qu'il a l'air d'être), on verra que la fin de la courbe
est droite. Pour cela, il faut être sûr qu'on ne mesure que le
parcours de l'arbre, et pas, par exemple, malloc (ou new), dont le
temps d'exécution est en général substantiel pour un calcul aussi
simple que celui-là.

dans un autre post, tu évoquais le possible impact du temps
d'accès à une "mémoire distante" (ce ne sont pas tes termes),
un adressage mémoire est quasi constant quelque soit l'adresse
utilisée ...

Ce n'est pas le problème. Le problème c'est l'ordre dans lequel tu
traverses ta mémoire, et en particulier le fait de savoir si le cache
est efficace. Si chaque accès à un objet le trouve dans le cache, tu
seras quelques dizaines de fois plus rapide que si chaque accès est
obligé de rapatrier l'objet depuis un cache plus lointain, voire
depuis la mémoire.

D'après les chiffres, il se pourrait bien que ce soit ce phénomène
qu'on est en train d'observer : dans le petit exemple, tout est dans
le cache ; dans le grand ce n'est plus le cas. (Lire "un cache" au
lieu de "le cache", parce qu'il y a plusieurs étages, mais ça ne
change rien au propos.) Si tu traces effectivement la courbe, tu
trouveras plusieurs phases selon l'utilisation du (des) caches.

(Je ne pense pas que le swap intervienne ici, c'est trop peu de
mémoire).

Pour un parcours d'arbre, typiquement, il faut que les objets soient
alloués dans l'ordre dans lequel ils sont accédés. Ce n'est pas
toujours possible (on peut parcourir l'arbre de plusieurs façons).
Aussi, utiliser une classe abstraite oblige à utiliser de pointeurs
(on ne peux pas placer tous les noeuds dans un tableau, par exemple)
et donc contribue à éparpiller la mémoire (dans cet exemple ça doit
être négligeable).

-- Alain.

Alain Ketterlin a écrit :

Voici une formule reliant le temps au nombre de noeuds n :
T(n) = (3.108/7310)*n + (1.61-3.108) (en secondes)

regression affine sur 2 points ??
quelle est la marge d'erreur selon toi ? 200% ? plus ?
un temps de calcul de -1.5 sec pour 0 point ne te gène pas ?

C'est parfaitement linéaire. Bien sûr ça na marche pas pour les
petites valeurs de n, mais une complexité c'est toujours asymptotique.
Donc ces chiffres ne démontrent rien du tout.

"ces chiffres" ? tu veux dire ta formule t = a.n + b ?
bien sur que cette formule ne démontre rien, les chiffres
du PO *montrent* (tu avais noté les parenthèses) simplement
une tendance qu'il fallait mieux caractériser comme je
l'indiquais.

Le mieux serait de faire plein de mesures pour des valeurs
croissantes du nombre de noeuds et de tracer la courbe.

disais-je.

Si l'algo est vraiment
linéaire (ce qu'il a l'air d'être), on verra que la fin de la courbe
est droite. Pour cela, il faut être sûr qu'on ne mesure que le
parcours de l'arbre, et pas, par exemple, malloc (ou new), dont le
temps d'exécution est en général substantiel pour un calcul aussi
simple que celui-là.

je n'excluerais pas les allocations, dont le temps n'est pas
proportionnel à la taille mémoire alloué, le nombre d'allocations
des noeuds a par contre des chances d'être proportionnel au nombre
de noeuds et ne doit pas créer la rupture de linéarité.

Ce n'est pas le problème. Le problème c'est l'ordre dans lequel tu
traverses ta mémoire, et en particulier le fait de savoir si le cache
est efficace. Si chaque accès à un objet le trouve dans le cache, tu
seras quelques dizaines de fois plus rapide que si chaque accès est
obligé de rapatrier l'objet depuis un cache plus lointain, voire
depuis la mémoire.

un cache de 640Ko ou 1,2Mo ?? tu penses à quel type de proc ?
ou qu'est ce que tu appelles un cache ?

(Je ne pense pas que le swap intervienne ici, c'est trop peu de
mémoire).

je n'ai lu nulle part la quantité de mémoire utilisée, même
les 640Ko et 1,2Mo ne sont que des chiffres au sens interprétés,
peux-tu nous rappeler ces quantités si tu les connais avec
certitude ?

Pour un parcours d'arbre, typiquement, il faut que les objets soient
alloués dans l'ordre dans lequel ils sont accédés. [...]

pour un maillage c'est facile, pour un arbre quelconque c'est
bcp moins évident.

Sylvain.

Sylvain SF <sylvain@boiteaspam.info> writes:

Alain Ketterlin a écrit :

Voici une formule reliant le temps au nombre de noeuds n :
T(n) = (3.108/7310)*n + (1.61-3.108) (en secondes)

regression affine sur 2 points ??
quelle est la marge d'erreur selon toi ? 200% ? plus ?
un temps de calcul de -1.5 sec pour 0 point ne te gène pas ?

J'expliquais tout cela plus bas (y compris pour les valeurs initiales
incohérentes).

Je rappelle que je répondais à quelqu'un qui disait : "on voit bien
avec ces chiffres que ce n'est pas linéaire". On voit rien du tout.

"ces chiffres" ? tu veux dire ta formule t = a.n + b ?

Ceux qui figuraient dans le message initial. Je te les rappelle :

* 14610 created nodes : 1285.68 Ko => exec_time = 4.718 sec ( 20000
itérations )
* 7310 created nodes : 643.28 Ko => exec_time = 1.61 sec ( 20000
itérations )

Je coupe une partie du reste, tu es visiblement de mauvaise foi.

[...]

je n'excluerais pas les allocations, dont le temps n'est pas
proportionnel à la taille mémoire alloué, le nombre d'allocations
des noeuds a par contre des chances d'être proportionnel au nombre
de noeuds et ne doit pas créer la rupture de linéarité.

On ne sait pas comment le posteur initial mesure son temps, et ce que
recouvrent ses mesures. Et oui, bien sûr, "le nombre d'allocations de
noeuds a des chances d'être proportionnel au nombre de noeuds". On a
appris quelque chose là ? La demande initiale indiquait que le temps
ne prenait en compte que le calcul, et je répondais à l'argument du
swap.

Ce n'est pas le problème. Le problème c'est l'ordre dans lequel tu
traverses ta mémoire, et en particulier le fait de savoir si le cache
est efficace. Si chaque accès à un objet le trouve dans le cache, tu
seras quelques dizaines de fois plus rapide que si chaque accès est
obligé de rapatrier l'objet depuis un cache plus lointain, voire
depuis la mémoire.

un cache de 640Ko ou 1,2Mo ?? tu penses à quel type de proc ?
ou qu'est ce que tu appelles un cache ?

C'est 32Ko en L1, mais 2 ou 4 Mo en L2 sur les processeurs actuels.

je n'ai lu nulle part la quantité de mémoire utilisée, même
les 640Ko et 1,2Mo ne sont que des chiffres au sens interprétés,

On n'a que ça. Je fais confiance à celui qui nous les fournit.

Pour un parcours d'arbre, typiquement, il faut que les objets soient
alloués dans l'ordre dans lequel ils sont accédés. [...]

pour un maillage c'est facile, pour un arbre quelconque c'est
bcp moins évident.

C'est trivial de les ranger comme cela. Tu prends n'importe quel
bouquin d'algorithmique, et tu cherches "ordre de parcours en
profondeur", "ordre postfixé" etc. Pour l'accès, tu ranges tes
résultats sur une pile. Rien de subtil.

-- Alain.

Alain Ketterlin a écrit :

Je rappelle que je répondais à quelqu'un qui disait : "on voit bien
avec ces chiffres que ce n'est pas linéaire". On voit rien du tout.

tu y as répondu par "une droite passe par 2 pts", pardon de ne
pas avoir compris l'ironie ;)

On ne sait pas comment le posteur initial mesure son temps, et ce que
recouvrent ses mesures. Et oui, bien sûr, "le nombre d'allocations de
noeuds a des chances d'être proportionnel au nombre de noeuds". On a
appris quelque chose là ? La demande initiale indiquait que le temps
ne prenait en compte que le calcul, et je répondais à l'argument du
swap.

je n'ai pas exactement dit cela, ce n'est pas tant le nb d'alloc.
que le temps de cette alloc. qui devrait être linéaire.

le pb exposé ici (le cout en temps d'exécution) pourrait avoir
sa raison dans la gestion mémoire (si nombreuses alloc. par noeud,
ou si les temps globaux liés à des processus d'alloc/libération
étaient très contributifs du temps total, le PO nous a laissé
entendre que ce n'était pas le cas).

un cache de 640Ko ou 1,2Mo ?? tu penses à quel type de proc ?
ou qu'est ce que tu appelles un cache ?

C'est 32Ko en L1, mais 2 ou 4 Mo en L2 sur les processeurs actuels.

certes, mais seuls le L1 est propre à chaque core, le L2
(même 6Mo sur les 45nm) est partagé entre les différents
cores, ne connaissant pas la charge de la machine hote
(importances des autres process concurentiels) il me
semblait non garanti que le process de calcul puisse
être intégralement caché.

au dela, le PO nous indiquait "faire un monte-carlo",
sans nullement préjuger négativement de son expérience
pour des calculs importants, l'hypothèse d'un sous
dimensionnement RAM (pouvant aller jusqu'à provoquer
du swap) me passerait pouvoir être levée, non pour
enfoncer des portes ouvertes ou insinuer un amateurisme
seulement pour écarter les mauvaises pistes d'explications.

je n'ai lu nulle part la quantité de mémoire utilisée, même
les 640Ko et 1,2Mo ne sont que des chiffres au sens interprétés,

On n'a que ça. Je fais confiance à celui qui nous les fournit.

je suis d'accord, en appelant à plus de détail pour ne pas
que "faire confiance" à la lecture que j'en ai faite.

Sylvain.

Merci pour vos réponses passionnées et très intéressantes. Je pense
que ma façon de parcourir mon arbre n'est pas optimale étant donné mo n
problème et qu'elle n'est effectivement pas linéaire en temps par
rapport au nombre de nœuds (alors qu'elle pourrait l'être si elle
était mieux pensée !!! ). Je vais refaire cette partie en prenant en
compte vos commentaires et en rajouter un objet qui va manager les
nœuds de façon à améliorer les interactions. Je ne manquerai pas de
commenter la post dès que les résultats tomberont. Encore merci.

Voila, donc comme prévu, mes temps de calcul se sont grandement
améliorés.
J'ai utilisé une classe qui orchestre les requêtes entre les nœuds au
lieux que chacun demande à tous ses petits voisins s'il a déjà ét é
évalué.
Merci pour votre aide en tout cas.