Un doute existenciel a propos du parcours de liste dans une boucle 'for'

kanze wrote on 26/09/2006 17:03:

Mais justement, une bonne VM analyse le code, fait des
suppositions, et...

(comme indiqué par Alain) tu parles partout ici de compilateur JIT pas
de la VM. une VM se caractérise ""seulement"" par sa pile et son byte-code.

cette distinction faite, en effet, il y a de grosses différences d'un
JIT à un autre, d'un système hôte à un autre.

De même, s'ils l'ont fait bien, la VM doit
pouvoir « découvrir » que tous les objets qui sont mis dans le
Object[] (qui se trouve à la base de l'implémentation de la
collection) sont en fait des MaClasse, et remplacer le
transtypage dynamique à MaClasse en sortie par un transtypage
statique.

non génériquement, tu peux écrire:

Vector<Integer> numbers = new Vector<Integer>(10, 10);
Object object = new String("toto");
numbers.add((Integer) object);

qui levera un CastClassException à l'exécution, parce qu'il y a bien
vérification dynamique.

mais oui, spécifiquement, le code

numbers.add(1);
numbers.add(3);
numbers.add(5);

peut être réécrit - avant exécution - par le JIT pour ne pas tester que
les Integer explicites sont bien des Integer.

Ben non, toujours pas. D'ailleurs soit dit en passant les tableaux ne
fonctionnent pas avec les génériques.

"primitifs" non ?

Sauf qu'une bonne VM va plus loin ici. [...]

assumption sur une implémentation particulière de JIT, ce ne sont pas
ici les règles d'une VM.

[...]

Bref les génériques en java c'est plus de l'ordre du sucre
syntaxique qu'autre chose et on est bien loin de C++

Certes, mais pour d'autres raisons -- je ne crois pas qu'il y a
des paramètres non-type, ni des spécialisations explicites, par
exemple.

"spécialisation explicite" est un concept, paradigme, ..., C++ donc en
effet on le rencontre en C++

un 'template' C++ est principalement une définition paramétrée, il
n'existe vraiment qu'au travers son instantiation pour un (des) type(s)
paramètre(s) donné(s) - le code concret n'existe pas indépendamment de
ce(s) paramètre(s).

une "classe paramétrée" Java existe bien indépendamment de toute
instantiation, une fois déclarée (et visible dans le contexte), elle ne
peut bien sur pas être redéfinie, donc une "spécialisation à la C++"
résulterait forcément en une redéfinition invalide.

le paradigme est donc différent pour autant le même objectif peut être
réalisé, mais à la Java, en spécialisant par surcharge ce qui doit être
spécialisé, par exemple (ici je joue sur la valeur retournée, on ferait
de même pour un traitement spécifique à la classe de l'argument):

Vector<Integer> numbers = new Vector<Integer>(10, 10);
numbers.add(1);
numbers.add(3);
numbers.add(5);

for (Integer nb: numbers)
System.out.println(nb);

out: 1 3 5
[btw, exemple on-topic et sans interrogation métaphysique sur le end()]

Vector<Integer> squares = new Vector<Integer>(10, 10){
public synchronized Integer get(int index) {
int value = super.get(index).intValue();
return new Integer(value * value);
}
};
squares.add(1);
squares.add(3);
squares.add(5);

for (Integer nb: squares)
System.out.println(nb);

out: 1 9 25

je considère même que cette forme de spécialisation est plus avantageuse
du fait même qu'elle tire parti de l'héritage.

Sylvain.

Alain Gaillard wrote:

[...]

Mais justement, une bonne VM analyse le code, fait des
suppositions, et...

Franchement je ne sais pas d'où tu sort ça. Si tu as des infos
ça m'intéresse d'ailleurs.

C'est surtout des discussions personnelles avec des gens qui
travaillent sur des compilateurs.

A moins que tu ne parle du JIT ?

Je parle des VM concrètes, non la machine abstraite. C-à-d un
programme qui, donné une suite de byte codes, s'arrange pour
effectuer leur sémantique. Le JIT et HotSpot en font partie.

Voici le byte code pour la fin du code ci-dessus:

63: new #2; //class java/util/Vector
66: dup
67: invokespecial #3; //Method java/util/Vector."<init>":()V
70: astore 5
72: aload 5
74: new #17; //class testgeneric/Generic

Donc, type connu...

En effet

77: dup
78: iload_1
79: invokespecial #18; //Method "<init>":(I)V
82: invokevirtual #5; //Method
java/util/Vector.add:(Ljava/lang/Object;)Z

Sauf qu'une bonne VM va plus loin ici. Elle entre dans la
fonction, voit ce qu'elle fait, etc. Et note quelque part,
optimistiquement, que le tableut que contient l'objet ne
contient en fait que des type #17. Chaque fois qu'elle
compile un bout de code, elle vérifie (ou essaie) que cette
post-condition tient avec le bout du code qu'elle a
compilée.

"Qu'elle compile un bout de code" dit tu, donc tu me parle
bien du JIT là, si je te suis bien. Parce que au niveau du
compilateur proprement dit, je n'en ai jamais vu un qui fait
ça.

Je ne sais pas. Il y a des parties de la VM de JDK qui sont
assez intelligentes. Et d'autres, dont il vaut mieux ne pas en
parler. Et beaucoup de points dont je ne sais rien : est-ce
qu'ils prenent en compte l'encapsulation, par exemple ? Et dans
quelle mesure c'est même possible. Analyser toute une classe
pour régarder d'où viennent les valeurs affectées à des membres
privés est bien à la portée des systèmes modernes. Je sais aussi
que la JIT, il y a cinq ans, régardait une fonction complète, et
même des fonctions qu'elle appelait, si elles n'était pas trop
grosses. Dans un exemple simple comme le tien, elle commencerait
prèsque certainement par inliner les fonctions de Vector.

Le problème ici, c'est ce qui pourrait éventuellement se passer
ailleurs. Je sais que la JIT d'il y a cinq ans faisait des
suppositions optimistes, et générer du code en tête du bloc qui
les vérifier, et déclencher le compilateur de nouveau si elles
s'avérait fausses. Je sais aussi qu'elle travaillait sur des
blocs de plusieurs milliers d'instructions VM à la fois.

Je sais aussi que la propagation des constantes est une
technique très ancienne d'optimisation. Et que quand tu fais un
new, le type dynamique de l'expression est une constante.

Ce que je ne sais pas, c'est d'une part, est-ce qu'ils ont pensé
à tracer les informations de type comme faisant partie de la
valeur, pour qu'elle se propage comme les autres constantes, et
de l'autre, est-ce qu'ils ont essayé à faire quelque chose avec
des tableaux -- dans le temps, on n'essayait pas à tracer des
valeurs constantes à travers un tableau, mais si on considère
les types, c'est certainement pas rare que tout le tableau
contient le même type. Tracer à travers un tableau est assez
délicat, parce que sa modification n'est pas tout ou rien ; une
affectation à un tableau ne signifie pas que je peux ignorer
toutes les affectations précédantes. Mais si on arrive à prendre
en compte l'encapsulation, et faire une analyse au niveau de la
classe, il doit bien être possible de faire des assertations en
ce qui concerne le contenu global du tableau. Un optimisateur
C++ ne le ferait jamais, parce que c'est pas mal du boulot, et
en C++, ça apporterait assez peu. Mais dans un JVM, j'imagine
que ça pourrait être intéressant.

Dans le temps, James Gosling avait une page sur les
modifications nécessaires pour que Java puisse servir au calcul
numérique. Son but, c'était de définir un nombre minimum de
modifications pour que le compilateur pourrait, par exemple,
convertir un tableau de Complex (ou Complex était un type défini
par l'utilisateur, qui comportait deux double) en ce qui
reviendrait à un tableau de struct en C -- le tableau physique
ne contiendrait pas des pointeurs à des objets, chacun alloué
dynamiquement, mais bien les objets. Depuis, je n'arrive plus à
la trouver -- sans doute, une déclaration que Java pourrait
être amélioré, et qu'elle n'était pas parfait déjà, n'a pas plus
à son employeur (sûrtout en venant d'une telle source). Mais je
ne peux pas croire que ses observations était sans effet, et si
une partie n'a pas été implémentée (il disait que le surcharge
des opérateurs était une nécessité, par exemple), ce n'est pas
exclu que ses idées sur la gestion de boxing soient prises en
compte, que la boxing soit conceptuellement présente dans tous
les cas, mais que la VM arrive à s'en passer, et à utiliser un
tableau des types de base ou des « struct » la plupart du
temps.

À la fin : la spécification de la JVM joue à peu près la même
rôle dans Java que la spécification de la machine abstraite dans
la norme joue dans C++. Elle définit la sémantique de
l'exécution des byte codes. Comment l'implémentation y arrive,
c'est son affaire, et on sait assez bien optimiser lors de
l'exécution aujourd'hui.

85: pop
86: aload 5
88: iconst_0
89: invokevirtual #6; //Method
java/util/Vector.get:(I)Ljava/lang/Object;
92: checkcast #17; //class testgeneric/Generic
95: astore 6
97: return

Et quand elle compile ce bout du code, elle entre dans
Vector.get assez pour voir que la valeur de retour vient
bien d'un tableau d'objet, et si le type est effectivement
noté pour ce tableau, et c'est #17, elle remplace le
checkcast par l'équivalent d'un static_cast (en fait, un
no-op si #17 est une classe, et non une interface). Et
évidemment, elle génère une pré-condition pour ce bout du
code qui assure que le type dans le tableau n'a pas changé.

Quand bien même ce que tu me dis serait vrai, (ce n'est pas la
question, je veux bien te croire), tu avoueras que c'est assez
laid tout ça non ?

En soi, non. Au contraire, c'est ce qu'on démande. En C++ aussi,
tu préfèrerais un compilateur capable d'extraire l'appel de
vector<>::end() de la boucle, non ? Idéalement, l'optimisation
doit être le rôle du compilateur, non du programmeur. La
définition des génériques comme le fait Java passe bien à la
reste du langage (où on n'a pas de sémantique de valeur, etc.).

Qu'elle ne correspond qu'à une partie de ce qu'on fait avec des
templates, c'est autre chose. Mais je crois que la philosophie
de Java, c'est plutôt que la génération du code doit toujours se
trouver en dehors du programme, et se faire par un programme à
part. Dans la mesure où ce qu'on génère ne dépend pas des
informations embriquées dans le langage, comme le type d'un
objet, je ne leur donne pas tort : j'utilise beaucoup de petits
scripts (en général en AWK) pour la génération du code. Mais il
y a aussi des cas où on veut bien que la génération dépend des
détails du type, par exemple, ou où on veut que le code généré
soit inséré dans une fonction plus grande. J'aime bien avoir le
choix.

Selon certains experts avec qui j'ai parlé, c'est en
principe plus facile d'optimiser lors de l'exécution dans un
VM que dans un compilateur classique. Parce que dans la VM,
tu as accès réel du profiling du programme en cours,

Je ne suis toujours pas sûr d'avoir bien compris si tu me
parles de la VM proprement dite ou du JIT.

Le JIT fait partie de la VM du Sun. C'est un nom commercial qui
ne veut rien dire, étant donné qu'il décrit la façon que
fonctionne tous les machines virtuelles et les émulateurs,
depuis au moins vingt ans. (Le premier papier que j'ai lu dessus
décrivait du travail chez IBM pour émuler l'architecture 360 sur
un RS 6000. Mi-1980's, si mes souvenirs sont corrects) Le
concept d'utiliser une machine virtuelle pour l'implémentation
d'un langage n'est pas nouveau ; on l'avait déjà dans le Pascal
UCSD, sous CP/M dans les années 1970. C'est l'évolution dans la
technologie des VM qui l'a rendu viable, et qui permet à Java
d'avoir des performances adéquates.

Je sais que Hot Spot fait des optimisations en fonctions des
bouts de code les plus utilisés. Je veux dire que seulement
des bouts pertinents de byte-code sont compilés en des
routines assembleurs et que Hot Spot s'arrange pour éviter de
tout compiler ce qui prendrait trop de temps souvent pour un
gain assez faible.

Hot Spot et JIT sont des noms commerciaux de chez Sun -- si ton
émulateur vient d'IBM, il ferait la même chose (sauf peut-être
en mieux). Ce sont aujourd'hui des techniques devenues standard
d'implémentation d'une machine virtuelle. (Ça ne veut pas dire
qu'on les utilise tout de suite, dans l'épreuve de concept,
avant d'avoir vérifié que les idées de base marchent. Ni,
d'ailleurs, que certains vendent ces épreuves de concept, aussi
immature soient-elles, comme de la technologie mature.)

Au minimum absolu, la VM va découper le code en blocs de flux,
c-à-d en blocs avec une seule entrée, en tête, et une seule
sortie, à la fin. (La première représentation d'un programme
dans un optimisateur, c'est un graphe orienté des tels blocs.)
Et générer l'assembleur pour chaque bloc. En l'occurance, et le
JIT, et Hot Spot vont bien plus loin, mais d'une façon
différente -- le Hot Spot est optimisé pour le type de code
qu'on trouve dans un serveur (des EJB, etc.), et apporte prèsque
rien à une application GUI, JIT est plutôt le contraire (et sans
JIT, même une machine 3 GHz ne suffirait pas pour Swing).

Mais ce que tu me dis semble se passer au niveau de la VM (tu
dis toujours VM) et là franchement je ne sais pas. Moi je
croyais même qu'il y avait toujours transtypages dynamique
même après intervention de Hot Spot, en tous cas au moins
jusqu'à la version Hot Spot 1.4. Peut être qu'avec la 1.5
c'est différent. Si tu as des infos là-dessus, un bon lien, je
suis preneur, parce que tu piques ma curiosité au vif là :-)

Je ne dis pas qu'il n'y en a pas. Je ne me suis plus servi de
Java depuis quelques années maintenant. Mais je sais que c'est
conceptuellement possible, et je sais que Gosling, au moins, s'y
était intéressé.

Je sais aussi qu'il y a des compilateurs C++ qui en font plus ou
moins autant, à partir des informations du profiling. Que dans
un bout du code dans une boucle serrée, où on fait p->f(), et
que p a le type B*, si le profiling indique que 99% des fois, on
exécute en fait D1::f(), le compilateur génère un bout du code
avant la boucle qui teste rapidement si la résolution de f()
pour p serait D1::f() (deux ou trois instructions machine
suffissent), pour choisir entre deux implémentations de la
boucle, et dans celle où on sait qu'on a D1::f(), il le génère
inline.

Comme tu vois c'est un Object qui est mis dans le tableau et
un Object qui en sort.

Mais la VM peut voir plus loins.

Tu sembles en être tellement convaincu que je vais finir par
douter.

Je suis 100% convaincu que c'est possible. Je sais en plus que
James Gosling y a reflechi. Je sais en revanche que ce n'est pas
forcement très simple, et je ne sais pas du tout si le JVM de
JDK ou de Jikes va aussi loin.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

(comme indiqué par Alain) tu parles partout ici de compilateur JIT pas
de la VM. une VM se caractérise ""seulement"" par sa pile et son byte-code.

En effet la JVM pour ce que j'en connais, c'est ça. Mais James a l'air
tellement sûr de lui.

cette distinction faite, en effet, il y a de grosses différences d'un
JIT à un autre, d'un système hôte à un autre.

Ca c'est sûr.

non génériquement, tu peux écrire:

Vector<Integer> numbers = new Vector<Integer>(10, 10);
Object object = new String("toto");
numbers.add((Integer) object);

qui levera un CastClassException à l'exécution, parce qu'il y a bien
vérification dynamique.

Mais quelle horreur un truc pareil...


--
Alain

C'est surtout des discussions personnelles avec des gens qui
travaillent sur des compilateurs.

A moins que tu ne parle du JIT ?

Je parle des VM concrètes, non la machine abstraite. C-à-d un
programme qui, donné une suite de byte codes, s'arrange pour
effectuer leur sémantique. Le JIT et HotSpot en font partie.

Certes. Mais si j'ai tant insisté sur ce point c'est que je vois mal la
VM hors JIT faire de l'optimisation à la volée.

"Qu'elle compile un bout de code" dit tu, donc tu me parle
bien du JIT là, si je te suis bien. Parce que au niveau du
compilateur proprement dit, je n'en ai jamais vu un qui fait
ça.

Je ne sais pas.

Moi je ne connais pas un compilateur Java qui fasse de l'optimisation.
Ils ont tous une options -O comme "optimisation" ... qui ne fait rien.

Il y a des parties de la VM de JDK qui sont
assez intelligentes.

Ah ?

Et d'autres, dont il vaut mieux ne pas en
parler.

:-)

Le problème ici, c'est ce qui pourrait éventuellement se passer
ailleurs. Je sais que la JIT d'il y a cinq ans faisait des
suppositions optimistes, et générer du code en tête du bloc qui
les vérifier, et déclencher le compilateur de nouveau si elles
s'avérait fausses.

En effet. C'est toujours comme ça il me semble. Et, je crois, quand ils
améliorent leur Hot Spot c'est au niveau de la pertinence des
suppositions que se situent les améliorations.

Ce que je ne sais pas, c'est d'une part, est-ce qu'ils ont pensé
à tracer les informations de type comme faisant partie de la
valeur, pour qu'elle se propage comme les autres constantes,

Franchement je ne pense pas. Je me demande même si c'est possible.

Dans le temps, James Gosling avait une page sur les
modifications nécessaires pour que Java puisse servir au calcul
numérique. Son but, c'était de définir un nombre minimum de
modifications pour que le compilateur pourrait, par exemple,
convertir un tableau de Complex (ou Complex était un type défini
par l'utilisateur, qui comportait deux double) en ce qui
reviendrait à un tableau de struct en C -- le tableau physique
ne contiendrait pas des pointeurs à des objets, chacun alloué
dynamiquement, mais bien les objets.
Depuis, je n'arrive plus à
la trouver --

Dommage, j'avour que j'aurais bien aimé la lire.

sans doute, une déclaration que Java pourrait
être amélioré, et qu'elle n'était pas parfait déjà, n'a pas plus
à son employeur (sûrtout en venant d'une telle source).

LOL

Mais je
ne peux pas croire que ses observations était sans effet,

Moi si. Ca semble tellement à l'encontre de ce qui a été fait jusqu'à
maintenant que les modifications pourrait bien ne pas être en "nombre
minimum". AMHA.

En soi, non. Au contraire, c'est ce qu'on démande. En C++ aussi,
tu préfèrerais un compilateur capable d'extraire l'appel de
vector<>::end() de la boucle, non ?

Je ne dis pas quoique...

Idéalement, l'optimisation
doit être le rôle du compilateur, non du programmeur.

On relance le débat ? ;-)
"Non du programmeur", jusqu'à un certain point seulement. Tiens question
fatale, j'itère dans un vector et dans l'itèration j'ajoute un élément
au vector. Si le compilo a sorti end() sans me le dire, mon code ne
marche plus.

Donc l'optimisation c'est aussi un peu le rôle du programmeur, dans le
sens où il doit au moins être conscient de ce qu'il code et de ce que le
compilo peut faire de son code.
Ou bien c'est au compilo de détecter que dans ce cas il ne faut pas
optimiser. Mais je vois mal comment cela pourrait être possible.

Dernière possibilité, on écartèle en place de Grèves le type qui modifie
un vector pendant l'itération, ça simplifie tout ;-)

Le JIT fait partie de la VM du Sun.

Oui c'est une affaire entendue.
Si je fais tant le distinguo c'est parce que j'imagine mal une
optimisation se faire ailleurs que dans le JIT.

Au minimum absolu, la VM va découper le code en blocs de flux,
c-à-d en blocs avec une seule entrée, en tête, et une seule
sortie, à la fin. (La première représentation d'un programme
dans un optimisateur, c'est un graphe orienté des tels blocs.)
Et générer l'assembleur pour chaque bloc. En l'occurance, et le
JIT, et Hot Spot vont bien plus loin, mais d'une façon
différente -- le Hot Spot est optimisé pour le type de code
qu'on trouve dans un serveur (des EJB, etc.),

Oui. C'est même là que l'efficacité de Hot Spot est la plus probante.

Je sais aussi qu'il y a des compilateurs C++ qui en font plus ou
moins autant, à partir des informations du profiling. Que dans
un bout du code dans une boucle serrée, où on fait p->f(), et
que p a le type B*, si le profiling indique que 99% des fois, on
exécute en fait D1::f(), le compilateur génère un bout du code
avant la boucle qui teste rapidement si la résolution de f()
pour p serait D1::f() (deux ou trois instructions machine
suffissent), pour choisir entre deux implémentations de la
boucle, et dans celle où on sait qu'on a D1::f(), il le génère
inline.

Tout ça est passionnant, mais je ne vois pas un compilateur Java faire
de même.

Je suis 100% convaincu que c'est possible. Je sais en plus que
James Gosling y a reflechi. Je sais en revanche que ce n'est pas
forcement très simple, et je ne sais pas du tout si le JVM de
JDK ou de Jikes va aussi loin.

J'ai me suis intéressé Jikes à une époque. Je n'ai pas vu qu'il faisait
la moindre optimisation, pas plus que les autres. J'ai compilé de
nombreux codes avec le compilateur de Sun et Jikes, désassemblé et
comparé. A chaque fois le byte-code généré était exactement le même.
Par contre Jikes compile extrêmement vite. Notamment parce qu'il n'est
pas écrit en Java mais en C. C'est en cela qu'il est optimisé ;-)

Tu as dis beaucoup de choses très intéressantes dans ton long post, ce
dont je te remercie. Faute de temps et aussi de connaissances je n'ai
pas discuté de tout.
Ce qu'il faudrait pour vraiment parler concret c'est regarder les
sources de la JVM et comprendre comment ça marche "dedans". Maintenant
les sources sont ouverts alors "il n'y a qu'à" :-) Mais là aussi
faudrait avoir le temps... et le courage de lire tout ce code.

Maintenant si tu retrouves la page de Gosling, ou des pages
intéressantes, n'hésites pas à m'envoyer les infos en privé, je t'en
serait très reconnaissant.

--
Alain

On relance le débat ? ;-)
"Non du programmeur", jusqu'à un certain point seulement. Tiens question
fatale, j'itère dans un vector et dans l'itèration j'ajoute un élément
au vector. Si le compilo a sorti end() sans me le dire, mon code ne
marche plus.

Un compilateur faisant ce genre d'optim sans avoir validé au préalable
qu'il a le droit, poubelle.

Donc l'optimisation c'est aussi un peu le rôle du programmeur, dans le
sens où il doit au moins être conscient de ce qu'il code et de ce que le
compilo peut faire de son code.
Ou bien c'est au compilo de détecter que dans ce cas il ne faut pas
optimiser. Mais je vois mal comment cela pourrait être possible.

C'est pourtant la noble tâche d'un compilateur. Et je pense que c'est
suite à ça que des options "whole code optimisation" faisant fi de la
compilation séparée ont de l'intérêt.

Dernière possibilité, on écartèle en place de Grèves le type qui modifie
un vector pendant l'itération, ça simplifie tout ;-)

C'est un peu l'optique .NET : Pour itérer, parfois, le seul moyen, c'est
foreach, qui ne supporte pas les modifications. Et c'est très lourd.
C'est aussi peu efficace, puisque ça impose dans certains cas un algo en
O(n²) pour supprimer des éléments répondant à certains critères.

--
Loïc

Donc l'optimisation c'est aussi un peu le rôle du programmeur, dans le
sens où il doit au moins être conscient de ce qu'il code et de ce que
le compilo peut faire de son code.
Ou bien c'est au compilo de détecter que dans ce cas il ne faut pas
optimiser. Mais je vois mal comment cela pourrait être possible.

C'est pourtant la noble tâche d'un compilateur.

Nous sommes nous compris ? "dans ce cas", je voulais dire dans le cas du
end() sorti de la boucle.
Tu penses qu'un compilateur peut voir qu'un itérateur de conteneur
risque d'être invalidé ?

--
Alain

Alain Gaillard <alain_gaillard28@hotmail.fr> writes:

Donc l'optimisation c'est aussi un peu le rôle du programmeur, dans le
sens où il doit au moins être conscient de ce qu'il code et de ce que le
compilo peut faire de son code.
Ou bien c'est au compilo de détecter que dans ce cas il ne faut pas
optimiser. Mais je vois mal comment cela pourrait être possible.
C'est pourtant la noble tâche d'un compilateur.

Nous sommes nous compris ? "dans ce cas", je voulais dire dans le cas du
end() sorti de la boucle.
Tu penses qu'un compilateur peut voir qu'un itérateur de conteneur risque
d'être invalidé ?

Pourquoi pas? Sortir du code invariant des boucles, c'est un grand
classique des algo d'optimisation -- pour tout dire, c'est dans le Dragon
book, pas le livre le plus récent ni le plus porté sur l'optimisation.
C'est exactement ce qu'il faut faire pour sortir le end()... Comme toute
optimisation, le compilateur ne doit la faire qu'après avoir prouvé qu'elle
est sans effet sur le comportement du programme. Donc il ne le fera pas
s'il ne voit pas tout le code de la boucle (soit parce que tout est présent
dans l'unité, soit qu'on compile tous les fichiers pertinents en même temps
avec une option comme -xcrossfile de Sun CC, soit qu'on effectue de
l'optimisation au moment du link -- Sun CC en a, HP en a, pour gcc c'est en
cours; dans aucun des cas je ne sais si la sortie du code invariant des
boucles fait partie de ce qui est effectué).

A+


--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Sylvain wrote:

kanze wrote on 26/09/2006 17:03:

Mais justement, une bonne VM analyse le code, fait des
suppositions, et...

(comme indiqué par Alain) tu parles partout ici de compilateur
JIT pas de la VM. une VM se caractérise ""seulement"" par sa
pile et son byte-code.

La VM, c'est la « virtual machine ». C'est un programme qui
exécute un programme définit par des byte-codes. Comment il
l'exécute, c'est son affaire, pourvu qu'il en respecte la
sémantique.

Le « JIT >>, c'est un nom commercial, publicitaire.
Apparamment, Sun ne l'a pas protégé comme marque déposée, comme
je croyais, mais c'est bien une expression du marketing, qui ne
veut rien dire sur le plan technique.

cette distinction faite, en effet, il y a de grosses
différences d'un JIT à un autre, d'un système hôte à un autre.

De même, s'ils l'ont fait bien, la VM doit
pouvoir « découvrir » que tous les objets qui sont mis dans le
Object[] (qui se trouve à la base de l'implémentation de la
collection) sont en fait des MaClasse, et remplacer le
transtypage dynamique à MaClasse en sortie par un transtypage
statique.

non génériquement, tu peux écrire:

Vector<Integer> numbers = new Vector<Integer>(10, 10);
Object object = new String("toto");
numbers.add((Integer) object);

qui levera un CastClassException à l'exécution, parce qu'il y
a bien vérification dynamique.

C'est peu problable qu'on essaie d'optimiser du code qui lève
des exceptions. Surtout des RuntimeException. (Et ici, aussi,
l'exception a lieu en dehors de l'objet Vector<Integer>.)

Je remarque aussi qu'une fois de plus, ils n'ont pas appris des
erreurs du C++. Ça fait longtemps, par exemple, qu'on sait que
le choit de <...> comme syntaxe n'est pas des plus heureux. Et
que sans le code existant, on le changerait volentiers.

[...]

Bref les génériques en java c'est plus de l'ordre du sucre
syntaxique qu'autre chose et on est bien loin de C++

Certes, mais pour d'autres raisons -- je ne crois pas qu'il
y a des paramètres non-type, ni des spécialisations
explicites, par exemple.

"spécialisation explicite" est un concept, paradigme, ..., C++
donc en effet on le rencontre en C++

C'est un concept qu'on retrouve effectivement en C++. Mais c'est
un concept assez général, qu'on pourrait aussi rétrouver dans
d'autres langages (peut-être sous un autre nom). Ça
m'étonnerait, d'ailleurs, qu'il ne soit pas présent dans
d'autres langages.

un 'template' C++ est principalement une définition
paramétrée, il n'existe vraiment qu'au travers son
instantiation pour un (des) type(s) paramètre(s) donné(s) - le
code concret n'existe pas indépendamment de ce(s)
paramètre(s).

une "classe paramétrée" Java existe bien indépendamment de
toute instantiation, une fois déclarée (et visible dans le
contexte), elle ne peut bien sur pas être redéfinie, donc une
"spécialisation à la C++" résulterait forcément en une
redéfinition invalide.

En effet. Ça, je ne savais pas.

Si j'ai bien compris, ils ont adopté tout ce qui était mauvais
dans les templates C++ : la syntaxe <...> et la convention que
le paramètre soit un seul caractère majuscule, et ont ignoré
tout ce qui était intéressant, comme l'idée que le template
lui-même n'est pas un type, mais n'en devient un que quand il
est instantié.

le paradigme est donc différent pour autant le même objectif
peut être réalisé, mais à la Java, en spécialisant par
surcharge ce qui doit être spécialisé, par exemple (ici je
joue sur la valeur retournée, on ferait de même pour un
traitement spécifique à la classe de l'argument):

Vector<Integer> numbers = new Vector<Integer>(10, 10);
numbers.add(1);
numbers.add(3);
numbers.add(5);

for (Integer nb: numbers)
System.out.println(nb);

out: 1 3 5
[btw, exemple on-topic et sans interrogation métaphysique sur le end()]

Vector<Integer> squares = new Vector<Integer>(10, 10){
public synchronized Integer get(int index) {
int value = super.get(index).intValue();
return new Integer(value * value);
}
};
squares.add(1);
squares.add(3);
squares.add(5);

for (Integer nb: squares)
System.out.println(nb);

out: 1 9 25

je considère même que cette forme de spécialisation est plus
avantageuse du fait même qu'elle tire parti de l'héritage.

Ça ne fait pas la même chose. Quand il convient, on peut faire
la même chose en C++, à condition que la classe de base
l'autorise. (Ici, évidemment, je suppose qu'il s'agit d'un
exemple d'une possibilité, pris un peu au hazard, et non d'un
exemple réel d'une chose qu'on voudrait faire. Parce qu'en ce
qui me concerne, si j'utilise quelque chose qui s'appelle
Vector, j'imagine qu'une post-condition de la fonction get,
c'est que ce qu'il renvoie, c'est la valeur qu'on y a mis. Et
que s'il était possible de vérifier cette post-condition, on le
ferait. Et qu'évidemment, dans une classe Vector bien conçue en
Java, get serait final.)

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Alain Gaillard wrote:

(comme indiqué par Alain) tu parles partout ici de
compilateur JIT pas de la VM. une VM se caractérise
""seulement"" par sa pile et son byte-code.

En effet la JVM pour ce que j'en connais, c'est ça. Mais James
a l'air tellement sûr de lui.

Je me base sur la signification de l'expression « virtual
machine » en anglais, et son utilisation avant Java. La
spécification de la machine virtuelle ne concerne pas son
implémentation, mais son « contrat ». Les byte-code définit la
sémantique, mais comment la VM même y arrive, c'est son affaire.

Ce n'est pas tout à fait pareil, mais on pourrait imaginer la
spécification de la machine virtuelle comme la spécification de
la machine abstraite de C++ dans la norme C++. La spécification
définit un comportement visible (ou un ensemble de comportements
visibles possibles, dans le cas de C++) pour un programme donné.
Ensuite, c'est la responsibilité de l'interpréteur ou du
compilateur pour traduire le programme en code machine
exécutable, soit en interprétant chaque instructions ou chaque
action dans la machine abstraite une par une, soit en faisant
quelque chose de plus astucieux.

Il faut dire que le concept d'une VM n'est pas quelque chose de
nouveau avec Java. Il existait bien avant : le Pascal de UCSD
s'en servait, par exemple, de même que certaines implémentations
de Lisp. C'est un concept assez connu.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Je me base sur la signification de l'expression « virtual
machine » en anglais, et son utilisation avant Java. La
spécification de la machine virtuelle ne concerne pas son
implémentation, mais son « contrat ». Les byte-code définit la
sémantique, mais comment la VM même y arrive, c'est son affaire.

Non sommes bien d'accord sur ce point.

Ce n'est pas tout à fait pareil, mais on pourrait imaginer la
spécification de la machine virtuelle comme la spécification de
la machine abstraite de C++ dans la norme C++. La spécification
définit un comportement visible (ou un ensemble de comportements
visibles possibles, dans le cas de C++) pour un programme donné.
Ensuite, c'est la responsibilité de l'interpréteur ou du
compilateur pour traduire le programme en code machine
exécutable, soit en interprétant chaque instructions ou chaque
action dans la machine abstraite une par une, soit en faisant
quelque chose de plus astucieux.

Il est possible qu'une VM le fasse. Ca je ne dis pas.

Il faut dire que le concept d'une VM n'est pas quelque chose de
nouveau avec Java. Il existait bien avant : le Pascal de UCSD
s'en servait, par exemple, de même que certaines implémentations
de Lisp. C'est un concept assez connu.

Sauf que j'aime bien coder en Lisp :-)

--
Alain