les arbres binaires - Page 2

Ethaniel :
En Asm, comme il n'y a pas de variables locales, on est oblige pour faire du recursif de passer par la pile et le pointeur (E)BP, mais la pile est d'une lenteur affligeante ...
Enfin du moins, ca c'est pour les programmes a flux direct (*.com) ; pour les autres (*.exe, ...), je n'en sais rien ...

@++

Et c'est pas la même pile qu'utilise le compilateur C lorsqu'il stack les appels de fonction ? Les variables locales sont allouées sur la pile également si je ne me trompe pas.

Lionel Debroux :
C'est con de vouloir faire de l'itératif à tout prix quand la solution récursive est efficace, facile à écrire et à comprendre.

Ça a toujours été mon point : j'aime le récursif parce que c'est efficace, facile à écrire et à comprendre, pas parce que c'est plus performant (puisque ce n'est pas le cas).

Quesoft a écrit :

Ethaniel :
En Asm, comme il n'y a pas de variables locales, on est oblige pour faire du recursif de passer par la pile et le pointeur (E)BP, mais la pile est d'une lenteur affligeante ...
Enfin du moins, ca c'est pour les programmes a flux direct (*.com) ; pour les autres (*.exe, ...), je n'en sais rien ...

@++

Et c'est pas la même pile qu'utilise le compilateur C lorsqu'il stack les appels de fonction ? Les variables locales sont allouées sur la pile également si je ne me trompe pas.

Il me semble que c'est bien le cas, mais je n'en connais pas assez sur l'assemblage d'un programme C pour l'affirmer ...
Cependant, la difference, c'est que l'utilisation des variables locales est hyper-simple en C, alors qu'en Asm, il faut bien connaitre le remplissage de la pile pour que (E)BP ne pointe pas a cote de ce que l'on voulait (savoir si c'est IP ou EIP qui est pushe, savoir si (E)CS l'est egalement, ...).
De plus, en C, le fait que la pile est utilisee pour les variables locales n'est pas grave, puisque ce n'est pas la vitesse que l'on cherche, alors qu'en Asm, on utilise la pile en extreme recours, lorsqu'il n'y a absolument aucun moyen de faire autrement (et il y a toujours moyen de faire autrement ...).

@++

et il y a toujours moyen de faire autrement ...

Meme pour une fonction recursive ?

Ethaniel
:

Quesoft a écrit :

Ethaniel :
En Asm, comme il n'y a pas de variables locales, on est oblige pour faire du recursif de passer par la pile et le pointeur (E)BP, mais la pile est d'une lenteur affligeante ...
Enfin du moins, ca c'est pour les programmes a flux direct (*.com) ; pour les autres (*.exe, ...), je n'en sais rien ...

@++

Et c'est pas la même pile qu'utilise le compilateur C lorsqu'il stack les appels de fonction ? Les variables locales sont allouées sur la pile également si je ne me trompe pas.

Il me semble que c'est bien le cas, mais je n'en connais pas assez sur l'assemblage d'un programme C pour l'affirmer ...
Cependant, la difference, c'est que l'utilisation des variables locales est hyper-simple en C, alors qu'en Asm, il faut bien connaitre le remplissage de la pile pour que (E)BP ne pointe pas a cote de ce que l'on voulait (savoir si c'est IP ou EIP qui est pushe, savoir si (E)CS l'est egalement, ...).
De plus, en C, le fait que la pile est utilisee pour les variables locales n'est pas grave, puisque ce n'est pas la vitesse que l'on cherche, alors qu'en Asm, on utilise la pile en extreme recours, lorsqu'il n'y a absolument aucun moyen de faire autrement (et il y a toujours moyen de faire autrement ...).

@++

et tout le monde ne fais pas de l'asm x86 (qui vaux rien du tout)

Ethaniel :
alors qu'en Asm, on utilise la pile en extreme recours, lorsqu'il n'y a absolument aucun moyen de faire autrement (et il y a toujours moyen de faire autrement ...).

@++

Avec 4 GPR, je me souviens l'avoir utilisé courrament... Mais c'est sûr qu'éviter le plus possible de faire des push/pop, c'est bien.

Godzil :
et tout le monde ne fais pas de l'asm x86 (qui vaux rien du tout)

Comme beaucoup de gens ont un PC, c'est normal qu'ils commencent par le x86 lorsqu'ils veullent apprendre l'ASM...

Pollux
:

et il y a toujours moyen de faire autrement ...

Meme pour une fonction recursive ?

Il n'y a pas toujours moyen de faire autrement en effet (bon, il y a moyen de se gosser une pile avec le storage local, mais ça reviens un peu au même si je ne fais pas erreur).

Pollux a écrit :

et il y a toujours moyen de faire autrement ...

Meme pour une fonction recursive ?

Oui : en creant sa propre pile indexee par (E)SI ou (E)DI dans la zone des donnees non initialisees, ce qui est un chouia plus rapide puisqu'il n'y a pas besoin de desentrelacer les variables avec (E)IP et (E)CS ...
Fondamentalement, dans l'esprit, c'est un peu la meme chose, mais bon ...

Et l'Asm x86, sp00tramort !!!

@++

Ethaniel
:

Pollux a écrit :

et il y a toujours moyen de faire autrement ...

Meme pour une fonction recursive ?

Oui : en creant sa propre pile indexee par (E)SI ou (E)DI dans la zone des donnees non initialisees, ce qui est un chouia plus rapide puisqu'il n'y a pas besoin de desentrelacer les variables avec (E)IP et (E)CS ...
Fondamentalement, dans l'esprit, c'est un peu la meme chose, mais bon ...

Et l'Asm x86, sp00tramort !!!

@++

J'ai pas eu le temps de compléter mon précédent post. Ce que l'on voullait dire c'était 'sans pile' : je pense pas qu'une pile 'à bras' soit plus efficace que la pile manipulé par les instructions push et pop.

Comme beaucoup de gens ont un PC, c'est normal qu'ils commencent par le x86 lorsqu'ils veullent apprendre l'ASM...

Je déconseille a quiqu'on qui veux apprend un asm propre (et meme comment penser/code en asm de débuter par du 8086 et dérivé, cet asm est completement pourri jusqu'a la moelle par les ajouts dans tout les sens lié a l'évolution du coeur x86 (d'ailleur la facon dont a évolué l'asm prouve qu'il etait plus que mal concu a la base, l'asm 68k a tres bien supporté l'évolution jusqu'au 68060, il en est de meme avec les ARM et auters PowerPC, l'évolution de l'asm n'est pas du bidouillage)

Si si, c'est plus efficace, puisque si tu fais push - call - pop ou push - return - pop, bam, game over (a cause de l'entrelacement) il ne faut pas poper, mais jouer avec (E)BP et return N, ce qui demande beaucoup d'attention et des cycles supplementaires pour la manipulation de (E)BP.
En plus, pour une pile maison, toutes les variables sont accollees, donc la mise en cache L2 est plus efficace, puisqu'elle se fait moins souvent.
Mais comme je le disais, dans l'esprit, c'est en effet un peu la meme chose ...

@++

Godzil
:

Comme beaucoup de gens ont un PC, c'est normal qu'ils commencent par le x86 lorsqu'ils veullent apprendre l'ASM...

Je déconseille a quiqu'on qui veux apprend un asm propre (et meme comment penser/code en asm de débuter par du 8086 et dérivé, cet asm est completement pourri jusqu'a la moelle par les ajouts dans tout les sens lié a l'évolution du coeur x86 (d'ailleur la facon dont a évolué l'asm prouve qu'il etait plus que mal concu a la base, l'asm 68k a tres bien supporté l'évolution jusqu'au 68060, il en est de meme avec les ARM et auters PowerPC, l'évolution de l'asm n'est pas du bidouillage)

Je suis d'accord. Le premier que j'ai appris était le S/390 (mainframe). L'avantage, c'est qu'il est très simple : 2 premiers bytes de l'instruction sont le opcode, toujours et un mnémonique -> un instruction, etc. Passer du code machine à l'asm est donc très simple dans c'est cas là et c'est une bonne chose.

Ethaniel :
Si si, c'est plus efficace, puisque si tu fais push - call - pop ou push - return - pop, bam, game over (a cause de l'entrelacement) il ne faut pas poper, mais jouer avec (E)BP et return N, ce qui demande beaucoup d'attention et des cycles supplementaires pour la manipulation de (E)BP.
En plus, pour une pile maison, toutes les variables sont accollees, donc la mise en cache L2 est plus efficace, puisqu'elle se fait moins souvent.
Mais comme je le disais, dans l'esprit, c'est en effet un peu la meme chose ...

@++

Un push pop prend moins de cycle qu'un move increment move decrement non ? push et pop ne sont pas de mauvaises instructions je crois.

J'ai pas une tonne d'expérience en ASM x86 par contre, j'en ai fais un peu dans le cadre d'un cours.

Bah le probleme c'est que passer par un seul registre (le pointeur de pile en l'occurrence) augmente les dependances entre instructions, donc ca se pipeline bcp moins bien (le processeur ne peut pas commencer a executer l'instruction B avant que l'instruction A n'ait termine, donc c'est moins efficace) ; si tu passes par un maximum de registres (enfin, dans la limite du nb de registres disponibles, evidemment) tu diminues cet effet.

Quesoft
: Ça a toujours été mon point : j'aime le récursif parce que c'est efficace, facile à écrire et à comprendre, pas parce que c'est plus performant (puisque ce n'est pas le cas).

En même temps c'est pas très étonnant de la part d'un java-fan </troll>

Ah bon, Java est efficace, facile à écrire et à comprendre ? </troll>

Plus que le C, mais moins que Caml, certes.

à la limite, une conversation constructive sur la récursivité, c'est intéressant...
mais une connerie de Troll genre java vs C vs caml et autres, ça gave...

squale92 :
à la limite, une conversation constructive sur la récursivité, c'est intéressant...
mais une connerie de Troll genre java vs C vs caml et autres, ça gave...

pas bien de troller ^^

En effet, l'assembleur x86 est complètement pourri.
Côté CISC au jeu puissant (même si on regrette parfois quelques instructions récentes du x86 ou de certains RISC comme l'ARM), le 68k est très bien.
Côté RISC, l'ARM est intéressant, avec les instructions conditionnelles et le multiplexage généralisé (faire n'importe quelle opération de shift/rotate en moins d'1 clock), même si ça reste un RISC (gaspillage constant de registres pour faire un truc aussi bête que modifier des variables en mémoire, manque de division - il a déjà la multiplication et le shift ultra-rapide, ce qui limite la casse pour les divisions par des facteurs constants).

Pollux> ah, t'as eu le temps de le voir ?
J'ai prévenu squale dès que j'ai posté pourtant

D'une manière générale, je n'aime pas bien le récursif quand l'itératif est simple (et plus efficace: Fibonacci, factorielle, etc. mais pas bubble sort par rapport à mergesort et quicksort), je n'aime pas bien l'itératif quand le récursif est beaucoup plus simple (parsing, tours de Hanoï, parcours en profondeur d'un graphe, 8 reines, etc.).
Il faut savoir connaître et reconnaître les forces et faiblesses de chaque type, et utiliser au mieux.

J'ai vu aussi.

Lionel Debroux :
D'une manière générale, je n'aime pas bien le récursif quand l'itératif est simple (et plus efficace: Fibonacci, factorielle, etc. mais pas bubble sort par rapport à mergesort et quicksort), je n'aime pas bien l'itératif quand le récursif est beaucoup plus simple (parsing, tours de Hanoï, parcours en profondeur d'un graphe, 8 reines, etc.).
Il faut savoir connaître et reconnaître les forces et faiblesses de chaque type, et utiliser au mieux.

C'est une bonne pratique de programmation.

squale92 :
à la limite, une conversation constructive sur la récursivité, c'est intéressant...
mais une connerie de Troll genre java vs C vs caml et autres, ça gave...

C'est sûr qu'un troll sur l'assembleur x86, c'est vachement plus intéressant ...

sauf que celui-là, je l'ai pas vu avant qu'il soit lancé

et les posts sur l'ASM ne sont-ils pas plus "évolués" que, par exempe, ./45 ?

Je peux développer ./45 en un post plus évolué, mais je crois que ce serait encore plus mal vu

Ce qu'on est en train de dire sur l'ASM est nettement plus objectif que le fait d'aimer ou pas Java, C, CamL, etc... L'assembleur x86 est mal fait dès le départ, alors on rajoute des quantités d'instructions pour le rendre mieux. Le x86 est maintenant extrêmement CISC, surtout le x86-64.

pourtant le coeur des athlon et autres pentium 4 est un core risc

ça y'est je sens que ça se barre en live