Note : J'ai peut-être choisi le mauvais mot dans le titre ; peut-être que je parle en fait de polynomial croissance ici. Voir le résultat du benchmark à la fin de cette question.
Commençons par ces trois interfaces génériques récursives † qui représentent des piles immuables :
interface IStack<T>
{
INonEmptyStack<T, IStack<T>> Push(T x);
}
interface IEmptyStack<T> : IStack<T>
{
new INonEmptyStack<T, IEmptyStack<T>> Push(T x);
}
interface INonEmptyStack<T, out TStackBeneath> : IStack<T>
where TStackBeneath : IStack<T>
{
T Top { get; }
TStackBeneath Pop();
new INonEmptyStack<T, INonEmptyStack<T, TStackBeneath>> Push(T x);
}J'ai créé des implémentations simples EmptyStack<T> , NonEmptyStack<T,TStackBeneath> .
Mise à jour n° 1 : Voir le code ci-dessous.
J'ai remarqué les choses suivantes concernant leurs performances d'exécution :
- Pousser 1 000 articles sur un
EmptyStack<int>pour la première fois prend plus de 7 secondes. - Pousser 1 000 articles sur un
EmptyStack<int>ne prend pratiquement pas de temps par la suite. - Les performances se dégradent de façon exponentielle au fur et à mesure que l'on ajoute des éléments à la pile.
Mise à jour n°2 :
J'ai enfin effectué une mesure plus précise. Voir le code du benchmark et les résultats ci-dessous.
J'ai seulement découvert pendant ces tests que .NET 3.5 ne semble pas autoriser les types génériques avec une profondeur de récursion ≥ 100. .NET 4 ne semble pas avoir cette restriction.
Les deux premiers faits me font penser que la lenteur des performances n'est pas due à mon implémentation, mais plutôt au système de types : .NET doit instancier 1 000 génériques fermés distincts. types , ie. :
EmptyStack<int>NonEmptyStack<int, EmptyStack<int>>NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>NonEmptyStack<int, NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>>- etc.
Questions :
- Mon évaluation ci-dessus est-elle correcte ?
- Si c'est le cas, pourquoi l'instanciation de types génériques comme le
T<U>,T<T<U>>,T<T<T<U>>>et ainsi de suite. exponentiellement plus ils sont imbriqués profondément ? - Les implémentations CLR autres que .NET (Mono, Silverlight, .NET Compact, etc.) présentent-elles les mêmes caractéristiques ?
† ) Note de bas de page hors sujet : Ces types sont assez intéressants btw. parce qu'ils permettent au compilateur d'attraper certaines erreurs telles que :
stack.Push(item).Pop().Pop(); // ^^^^^^ // causes compile-time error if 'stack' is not known to be non-empty.Ou vous pouvez exprimer des exigences pour certaines opérations de la pile :
TStackBeneath PopTwoItems<T, TStackBeneath> (INonEmptyStack<T, INonEmptyStack<T, TStackBeneath> stack)
Mise à jour #1 : Implémentation des interfaces ci-dessus
internal class EmptyStack<T> : IEmptyStack<T>
{
public INonEmptyStack<T, IEmptyStack<T>> Push(T x)
{
return new NonEmptyStack<T, IEmptyStack<T>>(x, this);
}
INonEmptyStack<T, IStack<T>> IStack<T>.Push(T x)
{
return Push(x);
}
}
// ^ this could be made into a singleton per type T
internal class NonEmptyStack<T, TStackBeneath> : INonEmptyStack<T, TStackBeneath>
where TStackBeneath : IStack<T>
{
private readonly T top;
private readonly TStackBeneath stackBeneathTop;
public NonEmptyStack(T top, TStackBeneath stackBeneathTop)
{
this.top = top;
this.stackBeneathTop = stackBeneathTop;
}
public T Top { get { return top; } }
public TStackBeneath Pop()
{
return stackBeneathTop;
}
public INonEmptyStack<T, INonEmptyStack<T, TStackBeneath>> Push(T x)
{
return new NonEmptyStack<T, INonEmptyStack<T, TStackBeneath>>(x, this);
}
INonEmptyStack<T, IStack<T>> IStack<T>.Push(T x)
{
return Push(x);
}
}Mise à jour n°2 : code de benchmark et résultats
J'ai utilisé le code suivant pour mesurer les temps d'instanciation des types génériques récursifs pour .NET 4 sur un ordinateur portable Windows 7 SP 1 x64 (Intel U4100 @ 1.3 GHz, 4 GB RAM). Il s'agit d'une machine différente et plus rapide que celle que j'ai utilisée à l'origine, donc les résultats ne correspondent pas aux déclarations ci-dessus.
Console.WriteLine("N, t [ms]");
int outerN = 0;
while (true)
{
outerN++;
var appDomain = AppDomain.CreateDomain(outerN.ToString());
appDomain.SetData("n", outerN);
appDomain.DoCallBack(delegate {
int n = (int)AppDomain.CurrentDomain.GetData("n");
var stopwatch = new Stopwatch();
stopwatch.Start();
IStack<int> s = new EmptyStack<int>();
for (int i = 0; i < n; ++i)
{
s = s.Push(i); // <-- this "creates" a new type
}
stopwatch.Stop();
long ms = stopwatch.ElapsedMilliseconds;
Console.WriteLine("{0}, {1}", n, ms);
});
AppDomain.Unload(appDomain);
}(Chaque mesure est effectuée dans un domaine d'application distinct, car cela garantit que tous les types d'exécution devront être recréés à chaque itération de la boucle).
Voici un graphique X-Y de la sortie :
-
Axe horizontal : N dénote la profondeur de la récursion de type, c'est-à-dire :
-
N \= 1 indique un
NonEmptyStack<EmptyStack<T>> -
N \= 2 indique un
NonEmptyStack<NonEmptyStack<EmptyStack<T>>> - etc.
-
N \= 1 indique un
- Axe vertical : t est le temps (en millisecondes) nécessaire pour pousser N entiers sur une pile. (Le temps nécessaire à la création des types d'exécution, si cela se produit réellement, est inclus dans cette mesure).
