Un bon exemple de tableau de longueur variable C [fermé]

9

Cette question a plutôt été gelée à SO, j'ai donc décidé de la supprimer ici et d'essayer ici à la place. Si vous pensez que cela ne convient pas non plus, veuillez au moins laisser un commentaire sur la suggestion pour trouver un exemple que je recherche ...

Pouvez-vous donner un exemple , où l'utilisation des VLA C99 offre un réel avantage sur quelque chose comme les mécanismes C ++ RAII standard utilisant des segments de mémoire?

L'exemple que je recherche devrait:

  1. Obtenez un avantage de performance facilement mesurable (10% peut-être) par rapport à l'utilisation du tas.
  2. Ne pas avoir une bonne solution de contournement, qui n'aurait pas besoin du tout du tableau.
  3. Bénéficiez réellement de l'utilisation de la taille dynamique, au lieu d'une taille maximale fixe.
  4. Il est peu probable de provoquer un débordement de pile dans un scénario d'utilisation normale.
  5. Soyez suffisamment fort pour tenter un développeur ayant besoin des performances d'inclure un fichier source C99 dans un projet C ++.

Ajout de quelques précisions sur le contexte: je veux dire VLA tel que signifié par C99 et non inclus dans la norme C ++: int array[n]nest une variable. Et je suis après un exemple de cas d'utilisation où il l'emporte sur les alternatives proposées par d'autres normes (C90, C ++ 11):

int array[MAXSIZE]; // C stack array with compile time constant size
int *array = calloc(n, sizeof int); // C heap array with manual free
int *array = new int[n]; // C++ heap array with manual delete
std::unique_ptr<int[]> array(new int[n]); // C++ heap array with RAII
std::vector<int> array(n); // STL container with preallocated size

Quelques idées:

  • Fonctions prenant des varargs, ce qui limite naturellement le nombre d'éléments à quelque chose de raisonnable, mais sans limite supérieure utile au niveau de l'API.
  • Fonctions récursives, où la pile perdue n'est pas souhaitable
  • Beaucoup de petites allocations et versions, où les frais généraux du tas seraient mauvais.
  • Manipuler des tableaux multidimensionnels (comme des matrices de taille arbitraire), où les performances sont critiques et où les petites fonctions devraient beaucoup s'aligner.
  • Extrait du commentaire: algorithme simultané, où l' allocation de segment a une surcharge de synchronisation .

Wikipédia a un exemple qui ne répond pas à mes critères , car la différence pratique avec l'utilisation du tas semble hors de propos, du moins sans contexte. Il n'est pas non plus idéal, car sans plus de contexte, il semble que le nombre d'éléments pourrait très bien provoquer un débordement de pile.

Remarque: je suis spécifiquement après un exemple de code, ou la suggestion d'un algorithme qui en bénéficierait, pour moi d'implémenter l'exemple moi-même.

hyde
la source
1
Un peu spéculatif (car il s'agit d'un marteau à la recherche d'un clou), mais cela alloca()pourrait peut - être vraiment éclipser malloc()dans un environnement multithread en raison de la contention de verrouillage dans ce dernier . Mais c'est un véritable tronçon car les petits tableaux doivent simplement utiliser une taille fixe, et les grands tableaux auront probablement besoin du tas de toute façon.
chrisaycock
1
@chrisaycock Oui, beaucoup de marteau à la recherche d'un clou, mais un marteau qui existe réellement (que ce soit le C99 VLA ou le non-réellement-dans-n'importe-quelle norme alloca, qui je pense sont fondamentalement la même chose). Mais cette chose multithread est bonne, question d'édition pour l'inclure!
hyde
Un inconvénient des VLA est qu'il n'y a pas de mécanisme pour détecter un échec d'allocation; s'il n'y a pas assez de mémoire, le comportement n'est pas défini. (Il en va de même pour les tableaux de taille fixe - et pour alloca ().)
Keith Thompson
@KeithThompson Eh bien, rien ne garantit non plus que malloc / new détecte un échec d'allocation, voir par exemple la page de manuel Notes pour Linux malloc ( linux.die.net/man/3/malloc ).
hyde
@hyde: Et on peut se demander si le malloccomportement de Linux est conforme à la norme C.
Keith Thompson

Réponses:

9

Je viens de pirater un petit programme qui génère un ensemble de nombres aléatoires redémarrant à la même graine à chaque fois, pour s'assurer qu'il est "juste" et "comparable". Au fur et à mesure, il détermine les valeurs min et max de ces valeurs. Et quand il a généré l'ensemble des nombres, il compte combien sont supérieurs à la moyenne de minet max.

Pour les TRÈS petites baies, cela montre un net avantage avec les VLA terminés std::vector<>.

Ce n'est pas un vrai problème, mais nous pouvons facilement imaginer quelque chose où nous lirions les valeurs d'un petit fichier au lieu d'utiliser des nombres aléatoires et de faire d'autres calculs de comptage / min / max plus significatifs avec le même type de code .

Pour les TRÈS petites valeurs du "nombre de nombres aléatoires" (x) dans les fonctions concernées, la vlasolution gagne par une énorme marge. Au fur et à mesure que la taille augmente, le «gagnant» devient plus petit et, avec une taille suffisante, la solution vectorielle semble être PLUS efficace - n'a pas trop étudié cette variante, car lorsque nous commençons à avoir des milliers d'éléments dans un VLA, ce n'est pas vraiment ce qu'ils étaient censés faire ...

Et je suis sûr que quelqu'un me dira qu'il existe un moyen d'écrire tout ce code avec un tas de modèles et de le faire sans exécuter plus que le RDTSC et les coutbits à l'exécution ... Mais je ne pense pas que ce soit vraiment le point.

Lors de l'exécution de cette variante particulière, j'obtiens une différence d'environ 10% entre le func1(VLA) et le func2(std :: vector).

count = 9884
func1 time in clocks per iteration 7048685
count = 9884
func2 time in clocks per iteration 7661067
count = 9884
func3 time in clocks per iteration 8971878

Ceci est compilé avec: g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp

Voici le code:

#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>

using namespace std;

const int SIZE = 1000000;

uint64_t g_val[SIZE];


static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}


int func1(int x)
{
    int v[x];

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}

int func2(int x)
{
    vector<int> v;
    v.resize(x); 

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v[i] = rand() % x;
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

int func3(int x)
{
    vector<int> v;

    int vmax = 0;
    int vmin = x;
    for(int i = 0; i < x; i++)
    {
        v.push_back(rand() % x);
        if (v[i] > vmax) 
            vmax = v[i];
        if (v[i] < vmin) 
            vmin = v[i];
    }
    int avg = (vmax + vmin) / 2;
    int count = 0;
    for(int i = 0; i < x; i++)
    {
        if (v[i] > avg)
        {
            count++;
        }
    }
    return count;
}    

void runbench(int (*f)(int), const char *name)
{
    srand(41711211);
    uint64_t long t = rdtsc();
    int count = 0;
    for(int i = 20; i < 200; i++)
    {
        count += f(i);
    }
    t = rdtsc() - t;
    cout << "count = " << count << endl;
    cout << name << " time in clocks per iteration " << dec << t << endl;
}

struct function
{
    int (*func)(int);
    const char *name;
};


#define FUNC(f) { f, #f }

function funcs[] = 
{
    FUNC(func1),
    FUNC(func2),
    FUNC(func3),
}; 


int main()
{
    for(size_t i = 0; i < sizeof(funcs)/sizeof(funcs[0]); i++)
    {
        runbench(funcs[i].func, funcs[i].name);
    }
}
Mats Petersson
la source
Wow, mon système montre une amélioration de 30% par rapport à la version VLA std::vector.
chrisaycock
1
Eh bien, essayez avec une plage de tailles d'environ 5-15 au lieu de 20-200, et vous aurez probablement une amélioration de 1000% ou plus. [Dépend également des options du compilateur - je modifierai le code ci-dessus pour afficher mes options du compilateur sur gcc]
Mats Petersson
Je viens d'ajouter un func3qui utilise v.push_back(rand())au lieu de v[i] = rand();et supprime le besoin de resize(). Cela prend environ 10% de plus par rapport à celui qui utilise resize(). [Bien sûr, au cours du processus, j'ai trouvé que l'utilisation de v[i]est un contributeur majeur au temps nécessaire à la fonction - je suis un peu surpris à ce sujet].
Mats Petersson
1
@MikeBrown Connaissez-vous une std::vectorimplémentation réelle qui utiliserait VLA / alloca, ou est-ce juste une spéculation?
hyde
3
Le vecteur utilise en effet un tableau en interne, mais pour autant que je sache, il n'a aucun moyen d'utiliser un VLA. Je crois que mon exemple montre que les VLA sont utiles dans certains (peut-être même de nombreux) cas où la quantité de données est faible. Même si le vecteur utilise des VLA, ce serait après un effort supplémentaire à l'intérieur de l' vectorimplémentation.
Mats Petersson
0

Concernant les VLA par rapport à un vecteur

Avez-vous considéré qu'un vecteur peut tirer parti des VLA lui-même. Sans VLA, le vecteur doit spécifier certaines «échelles» de tableaux, par exemple 10, 100, 10000 pour le stockage, de sorte que vous finissez par allouer un tableau de 10000 éléments pour contenir 101 éléments. Avec les VLA, si vous redimensionnez à 200, l'algorithme peut supposer que vous n'aurez besoin que de 200 et pouvez allouer un tableau de 200 éléments. Ou il peut allouer un tampon de disons n * 1,5.

Quoi qu'il en soit, je dirais que si vous savez de combien d'éléments vous aurez besoin au moment de l'exécution, un VLA est plus performant (comme l'a montré le benchmark de Mats). Ce qu'il a démontré était une simple itération en deux passes. Pensez aux simulations de monte carlo où des échantillons aléatoires sont prélevés à plusieurs reprises, ou à la manipulation d'images (comme les filtres Photoshop) où les calculs sont effectués plusieurs fois sur chaque élément et très probablement chaque calcul sur chaque élément implique de regarder les voisins.

Ce saut de pointeur supplémentaire du vecteur à son tableau interne s'additionne.

Répondre à la question principale

Mais lorsque vous parlez d'utiliser une structure allouée dynamiquement comme une LinkedList, il n'y a pas de comparaison. Un tableau fournit un accès direct en utilisant l'arithmétique des pointeurs à ses éléments. À l'aide d'une liste chaînée, vous devez parcourir les nœuds pour accéder à un élément spécifique. Le VLA gagne donc haut la main dans ce scénario.

Selon cette réponse , elle dépend de l'architecture, mais dans certains cas, l'accès à la mémoire sur la pile sera plus rapide car la pile est disponible sur le cache. Avec un grand nombre d'éléments, cela peut être annulé (potentiellement la cause des rendements décroissants observés par Mats dans ses références). Cependant, il convient de noter que les tailles de cache augmentent considérablement et que vous verrez potentiellement plus ce nombre augmenter en conséquence.

Michael Brown
la source
Je ne suis pas sûr de comprendre votre référence aux listes chaînées, j'ai donc ajouté une section à la question, expliquant un peu plus le contexte et en ajoutant des exemples d'alternatives auxquelles je pense.
hyde
Pourquoi aurait-on std::vectorbesoin d'échelles de tableaux? Pourquoi aurait-il besoin d'espace pour les éléments 10K alors qu'il n'en a besoin que de 101? De plus, la question ne mentionne jamais de listes liées, donc je ne sais pas d'où vous tenez cela. Enfin, les VLA en C99 sont alloués par pile; ils sont une forme standard de alloca(). Tout ce qui nécessite un stockage en tas (il realloc()existe après le retour de la fonction) ou un (le tableau se redimensionne) interdirait de toute façon les VLA.
chrisaycock
@chrisaycock C ++ n'a pas de fonction realloc () pour une raison quelconque, en supposant que la mémoire est allouée avec new []. N'est-ce pas la raison principale pour laquelle std :: vector doit utiliser des échelles?
@Lundin Le C ++ met-il le vecteur à l'échelle par des puissances de dix? J'ai juste l'impression que Mike Brown était vraiment confus par la question, étant donné la référence de la liste chaînée. (Il a également fait une affirmation antérieure qui impliquait que les VLA C99 vivent sur le tas.)
chrisaycock
@hyde Je ne savais pas que c'était de ça que tu parlais. Je pensais que vous vouliez dire d'autres structures de données basées sur le tas. Intéressant maintenant que vous avez ajouté cette précision. Je ne suis pas assez un geek C ++ pour vous dire la différence entre ceux-ci.
Michael Brown
0

La raison d'utiliser un VLA est principalement la performance. C'est une erreur de ne pas tenir compte de l'exemple du wiki comme n'ayant qu'une différence "non pertinente". Je peux facilement voir des cas où exactement ce code pourrait avoir une énorme différence, par exemple, si cette fonction était appelée dans une boucle étroite, où read_valétait une fonction IO qui revenait très rapidement sur une sorte de système où la vitesse était critique.

En fait, dans la plupart des endroits où les VLA sont utilisés de cette manière, ils ne remplacent pas les appels de segment mais remplacent plutôt quelque chose comme:

float vals[256]; /* I hope we never get more! */

La chose à propos de toute déclaration locale est qu'elle est extrêmement rapide. La ligne float vals[n]ne nécessite généralement que quelques instructions de processeur (peut-être une seule). Elle ajoute simplement la valeur au npointeur de pile.

D'un autre côté, une allocation de tas nécessite de parcourir une structure de données pour trouver une zone libre. Le temps est probablement un ordre de grandeur plus long, même dans le cas le plus chanceux. (C'est-à-dire que l'acte de placer nsur la pile et d'appeler mallocest probablement de 5 à 10 instructions.) Probablement bien pire s'il y a une quantité raisonnable de données dans le tas. Cela ne m'étonnerait pas du tout de voir un cas où la mallocvitesse était 100x à 1000x plus lente dans un vrai programme.

Bien sûr, vous avez également un certain impact sur les performances avec la correspondance free, probablement d'une ampleur similaire à l' mallocappel.

De plus, il y a le problème de la fragmentation de la mémoire. Beaucoup de petites allocations ont tendance à fragmenter le tas. Des tas fragmentés gaspillent de la mémoire et augmentent le temps nécessaire pour allouer de la mémoire.

Gort le robot
la source
À propos de l'exemple de Wikipedia: cela pourrait faire partie d'un bon exemple, mais sans contexte, plus de code autour, il ne montre vraiment aucune des 5 choses énumérées dans ma question. Sinon oui, je suis d'accord avec votre explication. Bien qu'une chose à garder à l'esprit: l'utilisation des VLA peut avoir un coût d'accès aux variables locales, avec eux les décalages de toutes les variables locales ne sont pas nécessairement connus au moment de la compilation, donc il faut faire attention de ne pas remplacer un coût de tas unique par un pénalité de boucle intérieure pour chaque itération.
hyde
Hum ... je ne sais pas ce que tu veux dire. Les déclarations de variables locales sont une opération unique et tout compilateur légèrement optimisé extraira l'allocation d'une boucle interne. Il n'y a pas de "coût" particulier pour accéder aux variables locales, certainement pas celles qu'un VLA augmentera.
Gort le robot
Exemple concret:: le int vla[n]; if(test()) { struct LargeStruct s; int i; }décalage de pile de sne sera pas connu au moment de la compilation, et il est également douteux que le compilateur déplace le stockage de ihors de la portée interne vers un décalage de pile fixe. Un code machine supplémentaire est donc nécessaire car l'indirection, et cela peut également consommer des registres, importants sur le matériel PC. Si vous voulez un exemple de code avec la sortie de l'assembly du compilateur inclus, veuillez poser une question distincte;)
hyde
Le compilateur n'a pas à allouer dans l'ordre rencontré dans le code, et peu importe si l'espace est alloué et non utilisé. Un optimiseur intelligent allouerait de l'espace pour set ilorsque la fonction est entrée, avant testest appelé ou vlaest alloué, comme les allocations pour set in'ont aucun effet secondaire. (Et, en fait, ipeut même être placé dans un registre, ce qui signifie qu'il n'y a aucune "allocation" du tout.)
Gort the Robot
(supprimé un commentaire qui était faux en raison d'une erreur stupide)
hyde