Pourquoi les tableaux de longueur variable ne font-ils pas partie de la norme C ++?

326

Je n'ai pas beaucoup utilisé C au cours des dernières années. Quand j'ai lu cette question aujourd'hui, je suis tombé sur une syntaxe C que je ne connaissais pas.

Apparemment, en C99, la syntaxe suivante est valide:

void foo(int n) {
    int values[n]; //Declare a variable length array
}

Cela semble être une fonctionnalité assez utile. Y a-t-il déjà eu une discussion sur l'ajout à la norme C ++, et si oui, pourquoi a-t-il été omis?

Quelques raisons potentielles:

  • Poilu pour les éditeurs de compilateurs à implémenter
  • Incompatible avec une autre partie de la norme
  • La fonctionnalité peut être émulée avec d'autres constructions C ++

La norme C ++ stipule que la taille du tableau doit être une expression constante (8.3.4.1).

Oui, bien sûr, je me rends compte que dans l'exemple de jouet on pourrait utiliser std::vector<int> values(m);, mais cela alloue de la mémoire à partir du tas et non de la pile. Et si je veux un tableau multidimensionnel comme:

void foo(int x, int y, int z) {
    int values[x][y][z]; // Declare a variable length array
}

la vectorversion devient assez maladroite:

void foo(int x, int y, int z) {
    vector< vector< vector<int> > > values( /* Really painful expression here. */);
}

Les tranches, les lignes et les colonnes seront également potentiellement réparties sur toute la mémoire.

En regardant la discussion, comp.std.c++il est clair que cette question est assez controversée avec des noms très lourds des deux côtés de l'argument. Il n'est certainement pas évident que a std::vectorsoit toujours une meilleure solution.

Andreas Brinck
la source
3
Par curiosité, pourquoi doit-il être alloué sur la pile? Avez-vous peur des problèmes de performances d'allocation de tas?
Dimitri C.
32
@Dimitri Pas vraiment, mais on ne peut nier que l'allocation de pile sera plus rapide que l'allocation de tas. Et dans certains cas, cela peut être important.
Andreas Brinck
11
Le principal avantage des tableaux de longueur variable est que toutes les données sont rapprochées, donc lorsque vous parcourez ce tableau, vous lisez et écrivez des octets les uns à côté des autres. Vos données sont récupérées dans le cache et le processeur peut y travailler sans récupérer et envoyer les octets vers / depuis la mémoire.
Calmarius
4
Des tableaux de longueur variable peuvent également être utilisés pour remplacer les constantes du préprocesseur par des variables const statiques. De plus, en C, vous n'avez pas d'autre option pour VLA, et il est parfois nécessaire d'écrire du code C / C ++ portable (compatible avec les deux compilateurs).
Yury
2
en passant, il semble que clang ++ autorise les VLA.
user3426763

Réponses:

204

Il y a eu récemment une discussion à ce sujet dans usenet: Pourquoi aucun VLA en C ++ 0x .

Je suis d'accord avec ces gens qui semblent être d'accord pour dire que devoir créer un grand tableau potentiel sur la pile, qui n'a généralement que peu d'espace disponible, n'est pas bon. L'argument est que si vous connaissez la taille au préalable, vous pouvez utiliser un tableau statique. Et si vous ne connaissez pas la taille à l'avance, vous écrirez du code dangereux.

Les VLA C99 pourraient offrir un petit avantage de pouvoir créer de petits tableaux sans gaspiller d'espace ni appeler des constructeurs pour les éléments inutilisés, mais ils introduiront des changements assez importants dans le système de types (vous devez être en mesure de spécifier des types en fonction des valeurs d'exécution - cela n'existe pas encore dans le C ++ actuel, à l'exception des newspécificateurs de type d'opérateur, mais ils sont traités spécialement, de sorte que le runtime-ness n'échappe pas à la portée de l' newopérateur).

Vous pouvez utiliser std::vector, mais ce n'est pas tout à fait la même chose, car il utilise la mémoire dynamique, et le faire utiliser son propre allocateur de pile n'est pas exactement facile (l'alignement est également un problème). Cela ne résout pas non plus le même problème, car un vecteur est un conteneur redimensionnable, alors que les VLA sont de taille fixe. La proposition de matrice dynamique C ++ vise à introduire une solution basée sur une bibliothèque, comme alternative à un VLA basé sur un langage. Cependant, cela ne fera pas partie de C ++ 0x, pour autant que je sache.

Johannes Schaub - litb
la source
22
+1 et accepté. Un commentaire cependant, je pense que l'argument de la sécurité est un peu faible car il existe de nombreuses autres façons de provoquer des débordements de pile. L'argument de sécurité peut être utilisé pour prendre en charge la position selon laquelle vous ne devez jamais utiliser la récursivité et que vous devez allouer tous les objets du tas.
Andreas Brinck
17
Vous dites donc que parce qu'il existe d'autres façons de provoquer des débordements de pile, nous pourrions aussi bien en encourager davantage?
jalf
3
@Andreas, a convenu de la faiblesse. Mais pour la récursivité, il faut un grand nombre d'appels jusqu'à ce que la pile soit consommée, et si cela peut être le cas, les gens utiliseraient l'itération. Comme le disent certaines personnes sur le fil Usenet, ce n'est pas un argument contre les VLA dans tous les cas, car parfois vous pouvez certainement connaître une limite supérieure. Mais dans ces cas, d'après ce que je vois, un tableau statique peut également être suffisant, car il ne gaspillerait pas beaucoup d'espace de toute façon (si c'était le cas , vous devriez en fait vous demander si la zone de la pile est à nouveau suffisamment grande).
Johannes Schaub - litb
10
Regardez également la réponse de Matt Austern dans ce fil: La spécification du langage des VLA serait probablement beaucoup plus complexe pour C ++, en raison des correspondances de type plus strictes en C ++ (exemple: C permet d'assigner un T(*)[]à un T(*)[N]- en C ++, cela n'est pas autorisé, car C ++ ne connaît pas la "compatibilité de type" - elle nécessite des correspondances exactes), les paramètres de type, les exceptions, les destructeurs et les éléments de type. Je ne suis pas sûr que les avantages des VLA rapportent vraiment tout ce travail. Mais alors, je n'ai jamais utilisé de VLA dans la vraie vie, donc je ne connais probablement pas de bons cas d'utilisation pour eux.
Johannes Schaub - litb
1
@AHelps: ce qui serait peut-être le mieux serait un type qui se comporte un peu comme vectormais nécessite un modèle d'utilisation LIFO fixe et conserve un ou plusieurs tampons alloués statiquement par thread qui sont généralement dimensionnés en fonction de la plus grande allocation totale du thread. jamais utilisé, mais qui pourrait être explicitement coupé. Dans le cas courant, une "allocation" normale ne nécessiterait rien de plus qu'une copie de pointeur, une soustraction pointeur-de-pointeur, une comparaison entière et une addition de pointeur; la désallocation nécessiterait simplement une copie du pointeur. Pas beaucoup plus lent qu'un VLA.
supercat
217

(Contexte: J'ai une certaine expérience de la mise en œuvre des compilateurs C et C ++.)

Les tableaux de longueur variable en C99 étaient fondamentalement un faux pas. Afin de soutenir les VLA, C99 a dû faire les concessions suivantes au bon sens:

  • sizeof xn'est plus toujours une constante de compilation; le compilateur doit parfois générer du code pour évaluer une sizeofexpression au moment de l'exécution.

  • Permettre à deux dimensions VLA ( int A[x][y]) nécessaire une nouvelle syntaxe pour déclarer des fonctions qui prennent 2D VLA comme paramètres: void foo(int n, int A[][*]).

  • Moins important dans le monde C ++, mais extrêmement important pour le public cible de C des programmeurs de systèmes embarqués, déclarer un VLA signifie chomping un arbitrairement grand morceau de votre pile. Il s'agit d'un débordement de pile et d'un plantage garantis . (Chaque fois que vous déclarez int A[n], vous affirmez implicitement que vous avez 2 Go de pile à épargner. Après tout, si vous savez " nest certainement inférieur à 1000 ici", alors vous déclareriez simplement int A[1000]. La substitution de l'entier 32 bits npour 1000est une admission que vous n'avez aucune idée du comportement de votre programme.)

Bon, passons maintenant à parler de C ++ maintenant. En C ++, nous avons la même distinction forte entre "système de types" et "système de valeurs" que C89… mais nous avons vraiment commencé à nous y fier d'une manière que C n'a pas. Par exemple:

template<typename T> struct S { ... };
int A[n];
S<decltype(A)> s;  // equivalently, S<int[n]> s;

Si n n'était pas une constante de temps de compilation (c.-à-d., Si elle Aétait de type modifié de façon variable), alors quel serait le type de ce type S? Would Stype de » également être déterminée que lors de l' exécution?

Et ça:

template<typename T> bool myfunc(T& t1, T& t2) { ... };
int A1[n1], A2[n2];
myfunc(A1, A2);

Le compilateur doit générer du code pour une certaine instanciation de myfunc. À quoi devrait ressembler ce code? Comment pouvons-nous générer statiquement ce code, si nous ne connaissons pas le type A1au moment de la compilation?

Pire encore, que se passe-t-il s'il s'avère au moment de l'exécution que n1 != n2 , alors !std::is_same<decltype(A1), decltype(A2)>()? Dans ce cas, l'appel à myfunc ne devrait même pas être compilé , car la déduction du type de modèle devrait échouer! Comment pourrions-nous éventuellement émuler ce comportement lors de l'exécution?

Fondamentalement, C ++ évolue dans le sens de pousser de plus en plus de décisions au moment de la compilation : génération de code de modèle, constexprévaluation de fonction, etc. Pendant ce temps, C99 était occupé à pousser les décisions traditionnelles de compilation (par exemple sizeof) dans le runtime . Dans cet esprit, est-il vraiment logique de consacrer des efforts à essayer d'intégrer des VLA de style C99 dans C ++?

Comme tous les autres répondeurs l'ont déjà souligné, C ++ fournit de nombreux mécanismes d'allocation de tas ( std::unique_ptr<int[]> A = new int[n];ou std::vector<int> A(n);étant les plus évidents) lorsque vous voulez vraiment transmettre l'idée "Je n'ai aucune idée de la quantité de RAM dont j'ai besoin". Et C ++ fournit un modèle astucieux de gestion des exceptions pour faire face à la situation inévitable où la quantité de RAM dont vous avez besoin est supérieure à la quantité de RAM dont vous disposez. Mais j'espère que cela réponse vous donne une bonne idée de pourquoi les VLA de style C99 n'étaient pas un bon ajustement pour C ++ - et pas vraiment même un bon ajustement pour C99. ;)


Pour plus d'informations sur le sujet, consultez N3810 «Alternatives pour les extensions de baie» , article d'octobre 2013 de Bjarne Stroustrup sur les VLA. Le POV de Bjarne est très différent du mien; N3810 se concentre davantage sur la recherche d'une bonne syntaxe ish C ++ pour les choses, et sur le découragement de l'utilisation de tableaux bruts en C ++, tandis que je me concentrais davantage sur les implications pour la métaprogrammation et le système de types. Je ne sais pas s'il considère que les implications de la métaprogrammation / système de types sont résolues, résolubles ou simplement sans intérêt.


Un bon article de blog qui touche bon nombre de ces mêmes points est "Utilisation légitime des tableaux à longueur variable" (Chris Wellons, 27/10/2019).

Quuxplusone
la source
15
Je suis d'accord que les VLA étaient tout simplement faux. Le logiciel beaucoup plus largement implémenté et beaucoup plus utile alloca()aurait dû être normalisé en C99 à la place. Les VLA sont ce qui se passe lorsqu'un comité de normalisation saute le pas sur les implémentations, et non l'inverse.
MadScientist
10
Le système de type à modification variable est un excellent ajout à l'OMI, et aucun de vos points de balle ne viole le bon sens. (1) la norme C ne fait pas de distinction entre "au moment de la compilation" et "au moment de l'exécution", ce n'est donc pas un problème; (2) Le *est facultatif, vous pouvez (et devez) écrire int A[][n]; (3) Vous pouvez utiliser le système de type sans déclarer réellement de VLA. Par exemple, une fonction peut accepter un tableau de type modifié de manière variable et peut être appelée avec des tableaux 2D non VLA de dimensions différentes. Cependant, vous marquez des points valides dans la dernière partie de votre message.
MM
3
"déclarer un VLA signifie couper un morceau arbitrairement grand de votre pile. C'est un débordement de pile garanti et un plantage. (Chaque fois que vous déclarez int A [n], vous affirmez implicitement que vous avez 2 Go de pile à revendre" est empiriquement false. Je viens de lancer un programme VLA avec une pile bien inférieure à 2 Go sans débordement de pile.
Jeff
3
@Jeff: Quelle était la valeur maximale de ndans votre scénario de test et quelle était la taille de votre pile? Je vous suggère d'essayer de saisir une valeur nau moins aussi grande que la taille de votre pile. (Et s'il n'y a aucun moyen pour l'utilisateur de contrôler la valeur de ndans votre programme, alors je vous suggère de propager la valeur maximale de ndirectement dans la déclaration: déclarer int A[1000]ou tout ce dont vous avez besoin. Les VLA sont uniquement nécessaires et dangereux, lorsque la valeur maximale de nn'est pas limitée par une petite constante de temps de compilation.)
Quuxplusone
2
Puisque alloca () peut être implémenté en utilisant de tels intrinsèques, il est par définition vrai que alloca () peut être implémenté sur n'importe quelle plate-forme, en tant que fonction standard du compilateur. Il n'y a aucune raison que le compilateur ne puisse pas détecter la première instance d'alloca () et organiser les types de marques et de versions à incorporer dans le code, et il n'y a aucune raison pour qu'un compilateur ne puisse pas implémenter alloca () en utilisant le tas si cela ne peut pas être fait avec la pile. Ce qui est dur / non portable est d'avoir alloca () implémenté au-dessus d' un compilateur C, de sorte qu'il fonctionne sur un large éventail de compilateurs et de systèmes d'exploitation.
MadScientist
26

Vous pouvez toujours utiliser alloca () pour allouer de la mémoire sur la pile au moment de l'exécution, si vous le souhaitez:

void foo (int n)
{
    int *values = (int *)alloca(sizeof(int) * n);
}

L'allocation sur la pile implique qu'elle sera automatiquement libérée lors du déroulement de la pile.

Remarque rapide: comme mentionné dans la page de manuel Mac OS X pour alloca (3), "La fonction alloca () dépend de la machine et du compilateur; son utilisation est déconseillée." Juste pour que tu saches.

PfhorSlayer
la source
4
En outre, la portée de alloca () est la fonction entière, pas seulement le bloc de code contenant la variable. Donc, en l'utilisant à l'intérieur d'une boucle, cela augmentera continuellement la pile. Un VLA n'a pas ce problème.
sashoalm
3
Cependant, les VLA ayant la portée du bloc englobant signifient qu'ils sont nettement moins utiles que alloca () avec la portée de la fonction entière. Considérez: if (!p) { p = alloca(strlen(foo)+1); strcpy(p, foo); } Cela ne peut pas être fait avec les VLA, précisément en raison de leur portée de bloc.
MadScientist
1
Cela ne répond pas à la question de savoir pourquoi OP . De plus, il s'agit d'une Csolution semblable à celle du présent , et pas vraiment de celle-ci C++.
Adrian W
13

Dans mon propre travail, j'ai réalisé que chaque fois que je voulais quelque chose comme des tableaux automatiques de longueur variable ou alloca (), je me fichais vraiment que la mémoire soit physiquement située sur la pile cpu, juste qu'elle provenait de un allocateur de pile qui n'a pas subi de déplacements lents vers le tas général. J'ai donc un objet par thread qui possède de la mémoire à partir de laquelle il peut pousser / pop des tampons de taille variable. Sur certaines plates-formes, je laisse cela se développer via mmu. D'autres plates-formes ont une taille fixe (généralement accompagnée d'une pile de processeurs de taille fixe également car aucun mmu). Une plate-forme avec laquelle je travaille (une console de jeu portable) possède de toute façon une petite pile de processeurs précieuse car elle réside dans une mémoire rapide et rare.

Je ne dis pas que pousser des tampons de taille variable sur la pile cpu n'est jamais nécessaire. Honnêtement, j'ai été surpris lorsque j'ai découvert que ce n'était pas standard, car il semble certainement que le concept s'intègre assez bien dans le langage. Pour moi cependant, les exigences "taille variable" et "doivent être physiquement situées sur la pile cpu" ne se sont jamais réunies. Il s'agissait de vitesse, donc j'ai créé ma propre sorte de "pile parallèle pour les tampons de données".

Eric
la source
12

Il existe des situations où l'allocation de mémoire de tas est très coûteuse par rapport aux opérations effectuées. Un exemple est les mathématiques matricielles. Si vous travaillez avec de petites matrices, dites 5 à 10 éléments et faites beaucoup d'arithmétiques, les frais généraux du malloc seront vraiment importants. En même temps, faire de la taille une constante de temps de compilation semble très gaspilleur et rigide.

Je pense que C ++ est si dangereux en soi que l'argument pour "essayer de ne pas ajouter plus de fonctionnalités dangereuses" n'est pas très fort. En revanche, comme C ++ est sans doute le langage de programmation le plus efficace, ce qui le rend encore plus utile est toujours utile: les personnes qui écrivent des programmes critiques en termes de performances utiliseront dans une large mesure C ++, et elles auront besoin d'autant de performances que possible. Le déplacement de trucs du tas vers la pile est une de ces possibilités. La réduction du nombre de blocs de tas en est une autre. Autoriser les VLA en tant que membres d'objets serait un moyen d'y parvenir. Je travaille sur une telle suggestion. C'est un peu compliqué à mettre en œuvre, certes, mais cela semble tout à fait faisable.

Bengt Gustafsson
la source
12

Semble qu'il sera disponible en C ++ 14:

https://en.wikipedia.org/wiki/C%2B%2B14#Runtime-sized_one_dimensional_arrays

Mise à jour: il n'est pas entré en C ++ 14.

Viktor Sehr
la source
intéressant. Herb Sutter en parle ici sous Dynamic Arrays : isocpp.org/blog/2013/04/trip-report-iso-c-spring-2013-meeting (c'est la référence pour les informations wikipedia)
Default
1
"Les tableaux et les tableaux dynamiques de taille d'exécution ont été déplacés vers la spécification technique des extensions de tableau", a écrit 78.86.152.103 sur Wikipédia le 18 janvier 2014: en.wikipedia.org/w/…
strager
10
Wikipedia n'est pas une référence normative :) Cette proposition n'est pas entrée en C ++ 14.
MM
2
@ViktorSehr: Quel est le statut de ce wrt C ++ 17?
einpoklum
@einpoklum Aucune idée, utilisez boost :: container :: static_vector
Viktor Sehr
7

Cela a été envisagé pour inclusion dans C ++ / 1x, mais a été abandonné (c'est une correction à ce que j'ai dit plus tôt).

Ce serait de toute façon moins utile en C ++ puisque nous devons déjà std::vectorremplir ce rôle.

philsquared
la source
42
Non, nous ne le faisons pas, std :: vector n'alloue pas de données sur la pile. :)
Kos
7
"la pile" est un détail d'implémentation; le compilateur peut allouer de la mémoire de n'importe où tant que les garanties sur la durée de vie de l'objet sont réunies.
MM
1
@MM: Très bien, mais dans la pratique , on ne peut pas encore utiliser au std::vectorlieu de, disons, alloca().
einpoklum
@einpoklum pour obtenir une sortie correcte pour votre programme, vous le pouvez. La performance est un problème de qualité de mise en œuvre
MM
1
La qualité d'implémentation @MM n'est pas portable. et si vous n'avez pas besoin de performances, vous n'utilisez pas c ++ en premier lieu
pal
3

Utilisez std :: vector pour cela. Par exemple:

std::vector<int> values;
values.resize(n);

La mémoire sera allouée sur le tas, mais cela ne présente qu'un petit inconvénient de performances. De plus, il est sage de ne pas allouer de gros blocs de données sur la pile, car sa taille est plutôt limitée.

Dimitri C.
la source
4
Une application majeure des tableaux de longueur variable est l'évaluation des polynômes à degrés arbitraires. Dans ce cas, votre "petit inconvénient de performances" signifie "le code s'exécute cinq fois plus lentement dans les cas typiques". Ce n'est pas petit.
AHelps
1
Pourquoi n'utilisez-vous pas simplement std::vector<int> values(n);? En utilisant resizeaprès la construction, vous interdisez les types non mobiles.
LF
1

C99 autorise VLA. Et cela impose des restrictions sur la façon de déclarer VLA. Pour plus de détails, reportez-vous au 6.7.5.2 de la norme. C ++ interdit VLA. Mais g ++ le permet.

Jingguo Yao
la source
Pouvez-vous fournir un lien vers le paragraphe standard que vous pointez?
Vincent
0

Des tableaux comme celui-ci font partie de C99, mais ne font pas partie de C ++ standard. comme d'autres l'ont dit, un vecteur est toujours une bien meilleure solution, c'est probablement pourquoi les tableaux de taille variable ne sont pas dans la norme C ++ (ou dans la norme C ++ 0x proposée).

BTW, pour des questions sur "pourquoi" la norme C ++ est la façon dont elle est, le groupe de discussion Usenet modéré comp.std.c ++ est l'endroit où aller.


la source
6
-1 Le vecteur n'est pas toujours meilleur. Souvent, oui. Toujours non. Si vous n'avez besoin que d'un petit tableau, que vous êtes sur une plate-forme où l'espace de stockage est lent et que l'implémentation de votre bibliothèque de vecteur utilise l'espace de stockage, cette fonctionnalité pourrait très bien être meilleure si elle existait.
Patrick M
-1

Si vous connaissez la valeur au moment de la compilation, vous pouvez effectuer les opérations suivantes:

template <int X>
void foo(void)
{
   int values[X];

}

Modifier: vous pouvez créer un vecteur qui utilise un allocateur de pile (alloca), car l'allocateur est un paramètre de modèle.

Edouard A.
la source
18
Si vous connaissez la valeur au moment de la compilation, vous n'avez pas du tout besoin d'un modèle. Utilisez simplement X directement dans votre fonction non-modèle.
Rob Kennedy
3
Parfois, l'appelant sait au moment de la compilation et l'appelé ne le sait pas, c'est à cela que servent les modèles. Bien sûr, dans le cas général, personne ne connaît X jusqu'à l'exécution.
Qwertie
Vous ne pouvez pas utiliser alloca dans un allocateur STL - la mémoire allouée par alloca sera libérée lorsque le cadre de pile est détruit - c'est à ce moment que la méthode qui doit allouer la mémoire revient.
Oliver
-5

J'ai une solution qui a vraiment fonctionné pour moi. Je ne voulais pas allouer de mémoire en raison de la fragmentation d'une routine qui devait s'exécuter plusieurs fois. La réponse est extrêmement dangereuse, alors utilisez-la à vos risques et périls, mais elle profite de l'assemblage pour réserver de l'espace sur la pile. Mon exemple ci-dessous utilise un tableau de caractères (évidemment, une autre variable de taille nécessiterait plus de mémoire).

void varTest(int iSz)
{
    char *varArray;
    __asm {
        sub esp, iSz       // Create space on the stack for the variable array here
        mov varArray, esp  // save the end of it to our pointer
    }

    // Use the array called varArray here...  

    __asm {
        add esp, iSz       // Variable array is no longer accessible after this point
    } 
}

Les dangers ici sont nombreux mais j'expliquerai quelques-uns: 1. Changer la taille de la variable à mi-chemin tuerait la position de la pile 2. Le dépassement des limites du tableau détruirait les autres variables et le code possible 3. Cela ne fonctionne pas en 64 bits build ... nécessite un assemblage différent pour celui-ci (mais une macro pourrait résoudre ce problème). 4. Spécifique au compilateur (peut avoir du mal à se déplacer entre les compilateurs). Je n'ai pas essayé donc je ne sais vraiment pas.

Alan
la source
... et si vous voulez rouler vous-même, utilisez peut-être une classe RAII?
einpoklum
Vous pouvez simplement utiliser boost :: container :: static_vector thou.
Viktor Sehr
Cela n'a pas d'équivalents pour les autres compilateurs qui ont plus d'assemblage brut que MSVC. VC comprendra probablement que cela a espchangé et ajustera ses accès à la pile, mais par exemple dans GCC, vous le casserez complètement - du moins si vous utilisez des optimisations et -fomit-frame-pointeren particulier.
Ruslan