Un buen ejemplo de matriz de longitud variable en C [cerrado]

9

Esta pregunta tuvo una recepción bastante fría en SO, así que decidí eliminarla allí e intentarlo aquí. Si cree que tampoco encaja aquí, al menos deje un comentario sobre la sugerencia de cómo encontrar un ejemplo que estoy buscando ...

¿Puede dar un ejemplo en el que el uso de C99 VLAs ofrezca una ventaja real sobre algo como los mecanismos C ++ RAII de uso de montón estándar actuales?

El ejemplo que busco debería:

  1. Logre una ventaja de rendimiento fácilmente medible (10% tal vez) sobre el uso del montón.
  2. No tiene una buena solución, que no necesitaría toda la matriz.
  3. En realidad, se beneficia del uso del tamaño dinámico, en lugar del tamaño máximo fijo.
  4. Es poco probable que cause un desbordamiento de la pila en el escenario de uso normal.
  5. Sea lo suficientemente fuerte como para tentar a un desarrollador que necesita el rendimiento para incluir un archivo fuente C99 en un proyecto C ++.

Agregando algunas aclaraciones sobre el contexto: me refiero a VLA como lo entiende C99 y no está incluido en C ++ estándar: int array[n]donde nes una variable. Y busco un ejemplo de caso de uso en el que supera las alternativas ofrecidas por otros estándares (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

Algunas ideas:

  • Funciones que toman varargs, que naturalmente limitan el recuento de elementos a algo razonable, pero no tienen ningún límite superior útil de nivel API.
  • Funciones recursivas, donde la pila desperdiciada no es deseable
  • Muchas asignaciones y lanzamientos pequeños, donde la sobrecarga del montón sería mala.
  • Manejo de matrices multidimensionales (como matrices de tamaño arbitrario), donde el rendimiento es crítico, y se espera que las pequeñas funciones se alineen mucho.
  • Del comentario: algoritmo concurrente, donde la asignación del montón tiene sobrecarga de sincronización .

Wikipedia tiene un ejemplo que no cumple con mis criterios , porque la diferencia práctica de usar el montón parece irrelevante, al menos sin contexto. Tampoco es ideal, porque sin más contexto, parece que el recuento de elementos podría causar un desbordamiento de la pila.

Nota: Estoy específicamente después de un código de ejemplo, o sugerencia de un algoritmo que se beneficiaría de esto, para que yo mismo implemente el ejemplo.

Hyde
fuente
1
Un poco especulativo (ya que este es un martillo en busca de un clavo), pero tal vez alloca()realmente eclipsaría malloc()en un entorno multiproceso debido a la contención de bloqueo en este último . Pero esto es una verdadera exageración ya que las matrices pequeñas solo deberían usar un tamaño fijo, y las matrices grandes probablemente necesitarán el montón de todos modos.
chrisaycock
1
@chrisaycock Sí, mucho martillo buscando un clavo, pero un martillo que realmente existe (ya sea C99 VLA o el no-en-ningún-estándar alloca, que creo que son básicamente lo mismo). Pero esa cosa multiproceso es buena, ¡edición de preguntas para incluirla!
hyde
Una desventaja de los VLA es que no existe un mecanismo para detectar una falla de asignación; Si no hay suficiente memoria, el comportamiento es indefinido. (Lo mismo es cierto para las matrices de tamaño fijo, y para alloca ().)
Keith Thompson
@KeithThompson Bueno, tampoco hay garantía de que malloc / new detecte fallas de asignación, por ejemplo, vea la página de manual de notas para Linux malloc ( linux.die.net/man/3/malloc ).
hyde
@hyde: Y es discutible si el malloccomportamiento de Linux se ajusta al estándar C.
Keith Thompson el

Respuestas:

9

Acabo de piratear un pequeño programa que genera un conjunto de números aleatorios que se reinician en la misma semilla cada vez, para garantizar que sea "justo" y "comparable". A medida que avanza, calcula el mínimo y el máximo de estos valores. Y cuando ha generado el conjunto de números, cuenta cuántos están por encima del promedio de miny max.

Para matrices MUY pequeñas, muestra un claro beneficio con el VLA terminado std::vector<>.

No es un problema real, pero podemos imaginar fácilmente algo donde estaríamos leyendo los valores de un archivo pequeño en lugar de usar números aleatorios, y haciendo otros cálculos de conteo / min / max más significativos con el mismo tipo de código .

Para valores MUY pequeños del "número de números aleatorios" (x) en las funciones relevantes, la vlasolución gana por un margen enorme. A medida que el tamaño aumenta, la "ganancia" se reduce y, dado el tamaño suficiente, la solución vectorial parece ser MÁS eficiente: no estudió esa variante demasiado, ya que cuando comenzamos a tener miles de elementos en un VLA, no realmente lo que estaban destinados a hacer ...

Y estoy seguro de que alguien me dirá que hay alguna forma de escribir todo este código con un montón de plantillas y lograr que haga esto sin ejecutar más que el RDTSC y los coutbits en tiempo de ejecución ... Pero no creo que sea realmente el punto.

Cuando ejecuto esta variante en particular, obtengo aproximadamente un 10% de diferencia entre func1(VLA) y 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

Esto se compila con: g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp

Aquí está el código:

#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
fuente
Wow, mi sistema muestra una mejora del 30% en la versión VLA std::vector.
chrisaycock
1
Bueno, intente con un rango de tamaño de aproximadamente 5-15 en lugar de 20-200, y probablemente obtendrá una mejora del 1000% o más. [También depende de las opciones del compilador: editaré el código anterior para mostrar las opciones del compilador en gcc]
Mats Petersson
Acabo de agregar un func3que usa en v.push_back(rand())lugar de v[i] = rand();y elimina la necesidad de resize(). Tarda aproximadamente un 10% más en comparación con el que usa resize(). [Por supuesto, en el proceso, descubrí que el uso de v[i]es un importante contribuyente al tiempo que lleva la función, estoy un poco sorprendido por eso].
Mats Petersson
1
@MikeBrown ¿Conoces una std::vectorimplementación real que usaría VLA / alloca, o es solo especulación?
hyde
3
El vector de hecho usa una matriz internamente, pero por lo que entiendo, no tiene forma de usar un VLA. Creo que mi ejemplo muestra que los VLA son útiles en algunos (quizás incluso muchos) casos en los que la cantidad de datos es pequeña. Incluso si el vector usa VLA, sería después de un esfuerzo adicional dentro de la vectorimplementación.
Mats Petersson
0

Con respecto a los VLA versus un vector

¿Consideró que un Vector puede aprovechar los VLA en sí mismos? Sin los VLA, el Vector tiene que especificar ciertas "escalas" de matrices, por ejemplo, 10, 100, 10000 para el almacenamiento, de modo que termine asignando una matriz de 10000 elementos para contener 101 elementos. Con los VLA, si cambia el tamaño a 200, el algoritmo puede suponer que solo necesitará 200 y puede asignar una matriz de 200 elementos. O puede asignar un búfer de decir n * 1.5.

De todos modos, diría que si sabes cuántos elementos necesitarás en tiempo de ejecución, un VLA es más eficiente (como lo demostró el punto de referencia de Mats). Lo que demostró fue una simple iteración de dos pasos. Piense en las simulaciones de Monte Carlo donde se toman muestras aleatorias repetidamente, o la manipulación de imágenes (como los filtros de Photoshop) donde los cálculos se realizan en cada elemento varias veces y posiblemente cada cálculo en cada elemento implica mirar a los vecinos.

Se suma ese salto adicional del puntero del vector a su matriz interna.

Respondiendo la pregunta principal

Pero cuando habla sobre el uso de una estructura asignada dinámicamente como LinkedList, no hay comparación. Una matriz proporciona acceso directo mediante aritmética de puntero a sus elementos. Usando una lista vinculada, debe recorrer los nodos para llegar a un elemento específico. Entonces, el VLA gana manos abajo en este escenario.

Según esta respuesta , depende de la arquitectura, pero en algunos casos el acceso a la memoria en la pila será más rápido debido a que la pila está disponible en la caché. Con una gran cantidad de elementos, esto puede negarse (potencialmente la causa de los rendimientos decrecientes que Mats vio en sus puntos de referencia). Sin embargo, vale la pena señalar que los tamaños de caché están creciendo significativamente y potencialmente verás crecer ese número en consecuencia.

Michael Brown
fuente
No estoy seguro de entender su referencia a las listas vinculadas, así que agregué una sección a la pregunta, explicando un poco más el contexto y agregando ejemplos de alternativas en las que estoy pensando.
hyde
¿Por qué std::vectornecesitaría escalas de matrices? ¿Por qué necesitaría espacio para elementos de 10K cuando solo necesita 101? Además, la pregunta nunca menciona listas vinculadas, por lo que no estoy seguro de dónde las obtuvo. Finalmente, los VLA en C99 se asignan en pila; que son una forma estándar de alloca(). Cualquier cosa que requiera almacenamiento de almacenamiento dinámico (vive después de que la función regrese) o a realloc()(la matriz cambia de tamaño) prohibiría los VLA de todos modos.
chrisaycock
@chrisaycock C ++ carece de una función realloc () por alguna razón, suponiendo que la memoria se asigne con new []. ¿No es esa la razón principal por la cual std :: vector debe usar escalas?
@Lundin ¿C ++ escala el vector en potencias de diez? Acabo de tener la impresión de que Mike Brown estaba realmente confundido por la pregunta, dada la referencia de la lista vinculada. (También hizo una afirmación anterior de que implicaba C99 VLA viven en el montón.)
chrisaycock
@hyde No me di cuenta de eso es de lo que estabas hablando. Pensé que te referías a otras estructuras de datos basadas en el montón. Interesante ahora que ha agregado esta aclaración. No soy lo suficientemente geek de C ++ como para decirte la diferencia entre ellos.
Michael Brown
0

La razón para usar un VLA es principalmente el rendimiento. Es un error ignorar el ejemplo de wiki porque solo tiene una diferencia "irrelevante". Puedo ver fácilmente casos en los que exactamente ese código podría tener una gran diferencia, por ejemplo, si esa función se llamaba en un bucle cerrado, donde read_valhabía una función IO que regresaba muy rápidamente en algún tipo de sistema donde la velocidad era crítica.

De hecho, en la mayoría de los lugares donde se usan VLA de esta manera, no reemplazan las llamadas de montón sino que reemplazan algo como:

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

Lo que pasa con cualquier declaración local es que es extremadamente rápido. La líneafloat vals[n] generalmente solo requiere un par de instrucciones del procesador (quizás solo una). Simplemente agrega el valor nal puntero de la pila.

Por otro lado, una asignación de montón requiere recorrer una estructura de datos para encontrar un área libre. El tiempo es probablemente un orden de magnitud más largo incluso en el caso más afortunado. (Es decir, el acto de colocar nen la pila y llamarmalloc es probablemente de 5 a 10 instrucciones). Probablemente mucho peor si hay una cantidad razonable de datos en el montón. No me sorprendería en absoluto ver un caso en el que mallocfuera 100x a 1000x más lento en un programa real.

Por supuesto, también tiene un impacto en el rendimiento con la coincidencia free , probablemente de magnitud similar a la mallocllamada.

Además, está el problema de la fragmentación de la memoria. Muchas pequeñas asignaciones tienden a fragmentar el montón. Los montones fragmentados desperdician memoria y aumentan el tiempo requerido para asignar memoria.

Gort the Robot
fuente
Sobre el ejemplo de Wikipedia: podría ser parte de un buen ejemplo, pero sin contexto, más código a su alrededor, realmente no muestra ninguna de las 5 cosas enumeradas en mi pregunta. De lo contrario, sí, estoy de acuerdo con su explicación. Aunque hay una cosa a tener en cuenta: el uso de VLA puede tener un costo de acceso a las variables locales, con ellas las compensaciones de todas las variables locales no se conocen necesariamente en el momento de la compilación, por lo que se debe tener cuidado de no reemplazar un costo de almacenamiento único por un penalización de bucle interno para cada iteración.
hyde
Um ... no estoy seguro de lo que quieres decir. Las declaraciones de variables locales son una operación única y cualquier compilador ligeramente optimizado sacará la asignación de un bucle interno. No hay un "costo" particular en el acceso a variables locales, ciertamente no uno que aumente un VLA.
Gort the Robot
Ejemplo concreto:: el int vla[n]; if(test()) { struct LargeStruct s; int i; }desplazamiento de la pila sno se conocerá en el momento de la compilación, y también es dudoso que el compilador mueva el almacenamiento ifuera del alcance interno al desplazamiento fijo de la pila. Por lo tanto, se necesita un código de máquina adicional debido a la indirección, y esto también puede consumir registros, importantes en el hardware de la PC. Si desea un código de ejemplo con salida de ensamblaje del compilador incluida, haga una pregunta por separado;)
hyde
El compilador no tiene que asignar en el orden encontrado en el código, y no importa si el espacio se asigna y no se usa. Un optimizador inteligente asignaría espacio para sy icuando se ingresa la función, antes de que testse llame o vlase asigne, como las asignaciones para sy ino tienen efectos secundarios. (Y, de hecho, iincluso podría colocarse en un registro, lo que significa que no hay "asignación" en absoluto). No hay garantías de compilación para el orden de asignaciones en la pila, o incluso que la pila se utiliza.
Gort the Robot
(eliminó un comentario que estaba mal debido a un error estúpido)
hyde