“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 154 — #164
i
i
i
i
i
i
i
i
154
3
• Techniques de programmation déclarative
Nous concluons que T (n) = O(n log n). Pour des valeurs de n qui ne sont pas des puissances de 2, nous utilisons le fait, qui est facile à prouver, que n m ⇒ T (n) T (m)
pour montrer que la borne grand O est toujours valable. Cette borne est indépendante
du contenu de la liste d’entrée. La borne O(n log n) est donc aussi une borne pour le
pire cas.
3.6.2 L’utilisation de mémoire
L’utilisation de mémoire n’est pas un seul nombre comme le temps d’exécution. Il y a
deux concepts très différents :
– La taille instantanée de mémoire active m a (t), en mots. Ce nombre indique la
quantité de mémoire nécessaire par le programme pour continuer son exécution. Un nombre apparenté est la taille maximale de la mémoire active, M a (t)
= max 0ut m a (u). Ce nombre est utile pour calculer la quantité de mémoire
physique nécessaire dans l’ordinateur pour exécuter le programme.
– La consommation instantanée de mémoire m c (t), en mots par seconde. Ce
nombre indique le taux d’allocation de mémoire du programme pendant son
exécution. Une grande valeur veut dire qu’il y a plus de travail en gestion de
mémoire : le ramasse-miettes sera exécuté plus souvent, ce qui augmentera le
temps d’exécution. Un nombre apparenté est la consommation totale de mémoire,
M c (t) =
t
0
m c (u)du, qui est une mesure de la quantité totale de travail qui doit
être faite en gestion de mémoire pour exécuter le programme.
Il ne faut pas confondre ces deux nombres. Le premier est bien plus important. Un
programme peut allouer de la mémoire très lentement (1 Ko/s) et avoir tout de même
une grande mémoire active (100 Mo) ; par exemple une grande base de données qui
est gardée en mémoire vive et qui traite des requêtes simples. Le contraire est possible
aussi. Un programme peut consommer de la mémoire à un taux élevé (100 Mo/s) mais
avoir une petite mémoire active (10 Ko) ; par exemple un algorithme de simulation qui
s’exécute dans le modèle déclaratif.
10
La taille instantanée de mémoire active
La taille de mémoire active peut être calculée à tout moment pendant l’exécution en
suivant toutes les références de la pile sémantique en mémoire et en faisant la somme
des tailles de toutes les valeurs partielles accessibles. Elle est approximativement égale
à la taille de toutes les structures de données dont le programme a besoin pendant son
exécution.
10. À cause de ce comportement, le modèle déclaratif n’est pas conseillé pour l’exécution des simulations
sauf si son ramasse-miettes est excellent !
i
i
i
i
i
i
i
i
154
3
• Techniques de programmation déclarative
Nous concluons que T (n) = O(n log n). Pour des valeurs de n qui ne sont pas des puissances de 2, nous utilisons le fait, qui est facile à prouver, que n m ⇒ T (n) T (m)
pour montrer que la borne grand O est toujours valable. Cette borne est indépendante
du contenu de la liste d’entrée. La borne O(n log n) est donc aussi une borne pour le
pire cas.
3.6.2 L’utilisation de mémoire
L’utilisation de mémoire n’est pas un seul nombre comme le temps d’exécution. Il y a
deux concepts très différents :
– La taille instantanée de mémoire active m a (t), en mots. Ce nombre indique la
quantité de mémoire nécessaire par le programme pour continuer son exécution. Un nombre apparenté est la taille maximale de la mémoire active, M a (t)
= max 0ut m a (u). Ce nombre est utile pour calculer la quantité de mémoire
physique nécessaire dans l’ordinateur pour exécuter le programme.
– La consommation instantanée de mémoire m c (t), en mots par seconde. Ce
nombre indique le taux d’allocation de mémoire du programme pendant son
exécution. Une grande valeur veut dire qu’il y a plus de travail en gestion de
mémoire : le ramasse-miettes sera exécuté plus souvent, ce qui augmentera le
temps d’exécution. Un nombre apparenté est la consommation totale de mémoire,
M c (t) =
t
0
m c (u)du, qui est une mesure de la quantité totale de travail qui doit
être faite en gestion de mémoire pour exécuter le programme.
Il ne faut pas confondre ces deux nombres. Le premier est bien plus important. Un
programme peut allouer de la mémoire très lentement (1 Ko/s) et avoir tout de même
une grande mémoire active (100 Mo) ; par exemple une grande base de données qui
est gardée en mémoire vive et qui traite des requêtes simples. Le contraire est possible
aussi. Un programme peut consommer de la mémoire à un taux élevé (100 Mo/s) mais
avoir une petite mémoire active (10 Ko) ; par exemple un algorithme de simulation qui
s’exécute dans le modèle déclaratif.
10
La taille instantanée de mémoire active
La taille de mémoire active peut être calculée à tout moment pendant l’exécution en
suivant toutes les références de la pile sémantique en mémoire et en faisant la somme
des tailles de toutes les valeurs partielles accessibles. Elle est approximativement égale
à la taille de toutes les structures de données dont le programme a besoin pendant son
exécution.
10. À cause de ce comportement, le modèle déclaratif n’est pas conseillé pour l’exécution des simulations
sauf si son ramasse-miettes est excellent !