“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 155 — #165
i
i
i
i
i
i
i
i
3.6 L’efficacité en temps et en espace
155
La consommation totale de mémoire
La consommation totale de mémoire peut être calculée avec une technique similaire
à celle utilisée pour le temps d’exécution. Chaque opération du langage noyau a une
consommation de mémoire bien définie. Le tableau 3.5 donne la consommation de
mémoire M(s) pour chaque instruction noyau s. Avec ce tableau, on peut établir
des équations de récurrence pour le programme, à partir desquelles la consommation
totale de mémoire du programme peut être calculée en fonction de la taille de l’entrée.
À ce nombre il faut ajouter la consommation de mémoire de la pile sémantique. Pour
l’instruction x=v il y a un cas rare pour lequel la consommation de mémoire est
plus petite que memsize(v), à savoir quand x est partiellement instanciée. Dans ce
cas, il n’y a que la mémoire des nouvelles entités qui doit être comptée. La fonction
memsize(v) est définie selon le type et la valeur de v :
– Pour un entier : 0 pour des petits entiers, sinon proportionnel au nombre de
chiffres de l’entier. Calculez le nombre de bits nécessaire pour représenter l’entier
en complément à 2. Si ce nombre est plus petit que 28, alors 0. Sinon divisez par
32 et faites l’arrondi à l’entier supérieur.
– Pour un flottant : 2.
– Pour une paire de liste : 2.
– Pour un tuple ou un enregistrement : 1 + n, où n = length(arity(v)).
– Pour une valeur procédurale : k + n, où n est le nombre de références externes du
corps de la procédure et k est une constante qui dépend de l’implémentation.
s : :=
skip
0
| |x 1 =x 2
0
| |x=v
memsize(v)
| |s 1 s 2
M(s 1 ) + M(s 2 )
| local x in s end
1 + M(s)
| if x then s 1 else s 2 end max(M(s 1 ), M(s 2 ))
| case x of pattern
max(M(s 1 ), M(s 2 ))
then s 1 else s 2 end
| {x y 1 · · · ·y n }
M x (size x (I x ({y 1 , . . . , y n })))
Tableau 3.5 La consommation de mémoire des instructions noyau.
Tous les nombres sont calculés en multiples d’un mot de 32 bits et sont corrects pour
Mozart 1.3.0. Pour les valeurs imbriquées, prenez la somme de toutes les valeurs. Pour
les enregistrements et valeurs procédurales, il y a un coût supplémentaire qui est payé
une fois. Pour chaque arité distincte le coût supplémentaire est approximativement
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.6 L’efficacité en temps et en espace
155
La consommation totale de mémoire
La consommation totale de mémoire peut être calculée avec une technique similaire
à celle utilisée pour le temps d’exécution. Chaque opération du langage noyau a une
consommation de mémoire bien définie. Le tableau 3.5 donne la consommation de
mémoire M(s) pour chaque instruction noyau s. Avec ce tableau, on peut établir
des équations de récurrence pour le programme, à partir desquelles la consommation
totale de mémoire du programme peut être calculée en fonction de la taille de l’entrée.
À ce nombre il faut ajouter la consommation de mémoire de la pile sémantique. Pour
l’instruction x=v il y a un cas rare pour lequel la consommation de mémoire est
plus petite que memsize(v), à savoir quand x est partiellement instanciée. Dans ce
cas, il n’y a que la mémoire des nouvelles entités qui doit être comptée. La fonction
memsize(v) est définie selon le type et la valeur de v :
– Pour un entier : 0 pour des petits entiers, sinon proportionnel au nombre de
chiffres de l’entier. Calculez le nombre de bits nécessaire pour représenter l’entier
en complément à 2. Si ce nombre est plus petit que 28, alors 0. Sinon divisez par
32 et faites l’arrondi à l’entier supérieur.
– Pour un flottant : 2.
– Pour une paire de liste : 2.
– Pour un tuple ou un enregistrement : 1 + n, où n = length(arity(v)).
– Pour une valeur procédurale : k + n, où n est le nombre de références externes du
corps de la procédure et k est une constante qui dépend de l’implémentation.
s : :=
skip
0
| |x 1 =x 2
0
| |x=v
memsize(v)
| |s 1 s 2
M(s 1 ) + M(s 2 )
| local x in s end
1 + M(s)
| if x then s 1 else s 2 end max(M(s 1 ), M(s 2 ))
| case x of pattern
max(M(s 1 ), M(s 2 ))
then s 1 else s 2 end
| {x y 1 · · · ·y n }
M x (size x (I x ({y 1 , . . . , y n })))
Tableau 3.5 La consommation de mémoire des instructions noyau.
Tous les nombres sont calculés en multiples d’un mot de 32 bits et sont corrects pour
Mozart 1.3.0. Pour les valeurs imbriquées, prenez la somme de toutes les valeurs. Pour
les enregistrements et valeurs procédurales, il y a un coût supplémentaire qui est payé
une fois. Pour chaque arité distincte le coût supplémentaire est approximativement
© Dunod – La photocopie non autorisée est un délit