Y a-t-il une limite au nombre de boucles "for" imbriquées ?

Question

Comme tout a une limite, je me demandais s'il y avait une limite au nombre d'éléments imbriqués. for boucles ou tant que j'ai de la mémoire, je peux les ajouter, le compilateur Visual Studio peut-il créer un tel programme ?

Bien sûr, 64 ou plus d'éléments imbriqués for Les boucles ne seraient pas pratiques à déboguer, mais est-ce faisable ?

private void TestForLoop()
{
  for (int a = 0; a < 4; a++)
  {
    for (int b = 0; b < 56; b++)
    {
      for (int c = 0; c < 196; c++)
      {
        //etc....
      }
    }
  }
}

Answer 1

Je vais prendre des risques en postant ça, mais je pense que la réponse est.. :

Entre 550 et 575

avec les paramètres par défaut dans Visual Studio 2015

J'ai créé un petit programme qui génère des for des boucles...

for (int i0=0; i0<10; i0++)
{
    for (int i1=0; i1<10; i1++)
    {
        ...
        ...
        for (int i573=0; i573<10; i573++)
        {
            for (int i574=0; i574<10; i574++)
            {
                Console.WriteLine(i574);
            }
        }
        ...
        ...
    }
}

Pour 500 boucles imbriquées, le programme peut encore être compilé. Avec 575 boucles, le compilateur s'arrête :

Warning AD0001 L'analyseur 'Microsoft.CodeAnalysis.CSharp.Diagnostics.SimplifyTypeNames.CSharpSimplifyTypeNamesDiagnosticAnalyzer' a généré une exception de type 'System.InsufficientExecutionStackException' avec le message 'Pile insuffisante pour continuer à exécuter le programme en toute sécurité. Cela peut être dû au fait qu'il y a trop de fonctions sur la pile d'appel ou que la fonction sur la pile utilise trop d'espace sur la pile".

avec le message du compilateur sous-jacent

erreur CS8078 : une expression est trop longue ou complexe pour être compilée

Bien sûr, c'est un purement hypothétique résultat. Si la boucle la plus intérieure fait plus qu'une Console.WriteLine Dans ce cas, moins de boucles imbriquées sont possibles avant que la taille de la pile ne soit dépassée. En outre, il peut ne pas s'agir d'une limite strictement technique, dans le sens où il peut y avoir des paramètres cachés pour augmenter la taille maximale de la pile pour l'"Analyseur" qui est mentionné dans le message d'erreur, ou (si nécessaire) pour l'exécutable résultant. Cette partie de la réponse, cependant, est laissée aux personnes qui connaissent le C# en profondeur.

---

Mise à jour

En réponse à la question dans les commentaires :

Je serais intéressé de voir cette réponse étendue pour "prouver" expérimentalement si vous pouvez mettre 575 variables locales sur la pile si elles sont pas utilisés dans les boucles for, et/ou si vous pouvez mettre 575 non imbriqué des boucles for dans une seule fonction

Dans les deux cas, la réponse est : Oui, c'est possible. Lorsque l'on remplit la méthode avec 575 déclarations auto-générées

int i0=0;
Console.WriteLine(i0);
int i1=0;
Console.WriteLine(i1);
...
int i574=0;
Console.WriteLine(i574);

il peut toujours être compilé. Tout le reste m'aurait surpris. La taille de la pile nécessaire pour le int Les variables ne font que 2,3 KB. Mais j'étais curieux, et afin de tester d'autres limites, j'ai augmenté ce nombre. Finalement, cela a fait pas compiler, provoquant l'erreur

erreur CS0204 : Seuls 65534 locaux, y compris ceux générés par le compilateur, sont autorisés.

ce qui est un point intéressant, mais qui a déjà été observé ailleurs : Nombre maximal de variables dans la méthode

De même, 575 non imbriqué for -des boucles, comme dans

for (int i0=0; i0<10; i0++)
{
    Console.WriteLine(i0);
}
for (int i1=0; i1<10; i1++)
{
    Console.WriteLine(i1);
}
...
for (int i574=0; i574<10; i574++)
{
    Console.WriteLine(i574);
}

peuvent également être compilés. Ici, j'ai aussi essayé de trouver la limite, et j'ai créé plus de ces boucles. En particulier, je n'étais pas sûr si les variables de la boucle dans ce cas comptent aussi comme "locales", parce qu'elles sont dans leur propre { block } . Mais toujours, plus de 65534 n'est pas possible. Enfin, j'ai ajouté un test consistant en 40000 boucles du motif

for (int i39999 = 0; i39999 < 10; i39999++)
{
    int j = 0;
    Console.WriteLine(j + i39999);
}

qui contenait une variable supplémentaire sur la boucle, mais ceux-ci semblent compter comme des "locaux" également, et il n'a pas été possible de compiler ceci.

---

Donc, pour résumer : La limite de ~550 est en effet causée par la profondeur de nidification des boucles. Cela a également été indiqué par le message d'erreur

erreur CS8078 : une expression est trop longue ou trop complexe pour être compilée

Le site documentation de l'erreur CS1647 ne spécifie malheureusement (mais de manière compréhensible) aucune "mesure" de la complexité, mais donne seulement un conseil pragmatique

Il y a eu un débordement de pile dans le compilateur traitant votre code. Pour résoudre cette erreur, simplifiez votre code.

Pour le souligner à nouveau : Pour le cas particulier de l'imbrication profonde for -Les boucles, tout ceci est plutôt académique et hypothétique. . Mais une recherche sur le Web du message d'erreur CS1647 révèle plusieurs cas où cette erreur est apparue pour un code qui n'était très probablement pas intentionnellement complexe, mais créé dans des scénarios réalistes.

Answer 2

Il n'y a pas de limite stricte dans les spécifications du langage C# ou du CLR. Votre code serait itératif, plutôt que récursif, ce qui pourrait conduire à un débordement de pile assez rapidement.

Il y a quelques éléments qui pourraient compter comme un seuil, par exemple le (généralement) int que vous utiliseriez, qui allouerait un compteur de int en mémoire pour chaque boucle (et avant d'avoir alloué toute votre pile avec des ints...). Notez que l'utilisation de cette int est nécessaire et vous pouvez réutiliser la même variable.

Comme signalé par Marco le seuil actuel se trouve davantage dans le compilateur que dans la spécification du langage ou le runtime. Une fois que cela sera recodé, il se peut que vous ayez à effectuer un certain nombre d'itérations supplémentaires. Si vous utilisez par exemple Ideone qui utilise par défaut l'ancien compilateur, vous pouvez obtenir plus de 1200 for boucles facilement.

Un tel nombre de boucles for est un indicateur de mauvaise conception. J'espère que cette question est purement hypothétique.

Answer 3

Il y a une limite pour tout le C# compilé en MSIL. MSIL ne peut supporter que 65535 variables locales. Si votre for Les boucles sont comme celles que vous avez montrées dans l'exemple, chacune nécessite une variable.

Il est possible que votre compilateur puisse allouer des objets sur le tas pour servir de stockage aux variables locales, contournant ainsi cette limite. Cependant, je ne suis pas sûr des résultats bizarres qui en découleraient. Il se peut que des problèmes liés à la réflexion rendent une telle approche illégale.

Answer 4

Entre 800 et 900 pour le vide for(;;) boucles.

J'ai reflété l'approche de Marco13, sauf que j'ai essayé for(;;) boucles :

for (;;)  // 0
for (;;)  // 1
for (;;)  // 2
// ...
for (;;)  // n_max
{
  // empty body
}

Cela a fonctionné pour 800 imbriqués for(;;) mais il a donné la même erreur que Marco13 a rencontré en essayant 900 boucles.

Lorsqu'il est compilé, le for(;;) semble bloquer le thread sans solliciter au maximum le CPU ; superficiellement, il semble agir comme une Thread.Sleep() .