Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Itération ou récursion en Java ?

5 réponses
Avatar
Wykaaa
Un article assez long mais intéressant (en anglais) qu'il faut lire
jusqu'au bout car il y a une surprise à la fin :
http://www.developer.com/lang/article.php/10924_3816966_1

5 réponses

Avatar
Francois Cartegnie
Wykaaa wrote:
Un article assez long mais intéressant (en anglais) qu'il faut lire
jusqu'au bout car il y a une surprise à la fin :
http://www.developer.com/lang/article.php/10924_3816966_1



Je ne comprends pas ce que tu pointes précisément ici.
La récursivité finale est connue pour être optimisable par les
compilateurs, et ce n'est pas spécifique à java.
Quant aux problèmes dûs à l'empilage de stack en récursivité non-finale,
c'est tout aussi connu... Le stack overflow était courant sur certains
langages si on ne prêtait pas attention à la profondeur de l'appel.

--
Ce message est transmis sur Usenet à titre non commercial.
Toute reprise par un média non conforme à la RFC1036
(suppression partielle ou totale des entetes, non respect des messages
de controle le concernant), dénaturation ou exploitation commerciale
par insertion publicitaire, obfuscation ou changement du groupe ou du
destinataire initial est prohibée et contrevient à mon droit d'auteur.
Avatar
Wykaaa
Francois Cartegnie a écrit :
Wykaaa wrote:
Un article assez long mais intéressant (en anglais) qu'il faut lire
jusqu'au bout car il y a une surprise à la fin :
http://www.developer.com/lang/article.php/10924_3816966_1



Je ne comprends pas ce que tu pointes précisément ici.
La récursivité finale est connue pour être optimisable par les
compilateurs, et ce n'est pas spécifique à java.



Bien sûr et ce n'est pas l'intérêt de l'article. Heureusement qu'on n'en
est plus là !

Quant aux problèmes dûs à l'empilage de stack en récursivité non-finale,
c'est tout aussi connu... Le stack overflow était courant sur certains
langages si on ne prêtait pas attention à la profondeur de l'appel.



Laisse tomber. Je crois que tu es passé à côté de ce que veut dire
l'article ou alors tu l'as vraiment lu trop en diagonale...

La partie intéressante c'est l'autoboxing qui pénalise la récursion à
cause du passage de paramètre pour les types prédéfinis (int, par
exemple, qui est converti en Integer). Ça c'est un problème typiquement
Java...
Je cite l'article :
"There is an extra step of creating an instance of class Integer before
pushing the data onto the stack. Similarly (though not identically the
same), inside JVM, the primitive types will get wrapped into an object
in order to get pushed onto the call stack. Despite using a "simple"
data type, more time is actually being spent internally to prepare the
call then in the case of using an object! "

Peut-être le savais-tu, moi je ne le savait pas...
Avatar
Sylvain SF
Wykaaa a écrit :

La partie intéressante c'est l'autoboxing qui pénalise la récursion à
cause du passage de paramètre pour les types prédéfinis (int, par
exemple, qui est converti en Integer). Ça c'est un problème typiquement
Java...
Je cite l'article :
"There is an extra step of creating an instance of class Integer before
pushing the data onto the stack. Similarly (though not identically the
same), inside JVM, the primitive types will get wrapped into an object
in order to get pushed onto the call stack. Despite using a "simple"
data type, more time is actually being spent internally to prepare the
call then in the case of using an object! "

Peut-être le savais-tu, moi je ne le savait pas...



ou encore, peut-être que l'auteur raconte n'importe quoi, ou tu le
rapportes hors contexte (un contexte où il ferait exprès de devoir
utiliser des instances et non des types primitifs).

selon SUN [1], la seule promotion est le passage en int de tous
types entiers plus petits, en aucun cas le recours à un Integer.

[1]
<http://java.sun.com/docs/books/jvms/second_edition/html/Overview.doc.html#7565&gt;

Sylvain.
Avatar
Wykaaa
Sylvain SF a écrit :
Wykaaa a écrit :

La partie intéressante c'est l'autoboxing qui pénalise la récursion à
cause du passage de paramètre pour les types prédéfinis (int, par
exemple, qui est converti en Integer). Ça c'est un problème
typiquement Java...
Je cite l'article :
"There is an extra step of creating an instance of class Integer
before pushing the data onto the stack. Similarly (though not
identically the same), inside JVM, the primitive types will get
wrapped into an object in order to get pushed onto the call stack.
Despite using a "simple" data type, more time is actually being spent
internally to prepare the call then in the case of using an object! "

Peut-être le savais-tu, moi je ne le savait pas...



ou encore, peut-être que l'auteur raconte n'importe quoi, ou tu le
rapportes hors contexte (un contexte où il ferait exprès de devoir
utiliser des instances et non des types primitifs).

selon SUN [1], la seule promotion est le passage en int de tous
types entiers plus petits, en aucun cas le recours à un Integer.

[1]
<http://java.sun.com/docs/books/jvms/second_edition/html/Overview.doc.html#7565&gt;


Sylvain.


Merci pour la référence.
Il semble donc que l'article que j'avais cité est de mauvaise qualité.
Mea Culpa

Wykaaa
Avatar
Sylvain SF
Wykaaa a écrit :

Il semble donc que l'article que j'avais cité est de mauvaise qualité.



il manque fortement de rigueur.

l'auteur mesure, pour un calcul de factorielle, un rapport 2,59
entre la version récursive et itérative.
il multiplie les exemples n'apportant rien à son point initial
pour finalement tomber sur un rapport de 3,93 avec une fonction
de même prototype et en conclut (sorti de nul part) que des
instances masquées expliqueraient cette différence.

le fait qu'il ne se rendre pas compte qu'il aurait du obtenir
2,59 ou 3,93 dans les 2 cas ne l'effleure même pas.

plus révélateur encore, fort de cette fausse découverte, il enchaîne
sur un calcul de GCD et déclare:

"Running these two implementations in parallel, gets in most cases
"slightly bigger times for the recursive one, however, I did manage
"after the fourth execution to get the following"

une mesure sérieuse de temps d'exécution voudrait qu'il fasse 10,
50 ou 100 fois le calcul et le moyenne (pour s'affranchir des aléas
de charge machine et autres parasites), rien de cela, au contraire
il nous déclare qu'il a réussi au 4ième essai à avoir un chiffre
qui lui plaisait !?!

pour paraphraser François, certains algos peuvent être optimisés
(ici par la VM ou un compilateur JIT, et notons que l'auteur ne
décrit aucun des systèmes utilisés pour ses mesures), d'autres pas,
via qlq portes ouvertes l'auteur a illustré cela, il l'effleure
dans sa conclusion mais ne semble pas vraiment l'avoir compris.

Sylvain.