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:
- Logre una ventaja de rendimiento fácilmente medible (10% tal vez) sobre el uso del montón.
- No tiene una buena solución, que no necesitaría toda la matriz.
- En realidad, se beneficia del uso del tamaño dinámico, en lugar del tamaño máximo fijo.
- Es poco probable que cause un desbordamiento de la pila en el escenario de uso normal.
- 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 n
es 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.
alloca()
realmente eclipsaríamalloc()
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.alloca
, que creo que son básicamente lo mismo). Pero esa cosa multiproceso es buena, ¡edición de preguntas para incluirla!malloc
comportamiento de Linux se ajusta al estándar C.Respuestas:
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
min
ymax
.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
vla
solució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
cout
bits 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) yfunc2
(std :: vector).Esto se compila con:
g++ -O3 -Wall -Wextra -std=gnu++0x -o vla vla.cpp
Aquí está el código:
fuente
std::vector
.func3
que usa env.push_back(rand())
lugar dev[i] = rand();
y elimina la necesidad deresize()
. Tarda aproximadamente un 10% más en comparación con el que usaresize()
. [Por supuesto, en el proceso, descubrí que el uso dev[i]
es un importante contribuyente al tiempo que lleva la función, estoy un poco sorprendido por eso].std::vector
implementación real que usaría VLA /alloca
, o es solo especulación?vector
implementación.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.
fuente
std::vector
necesitarí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 dealloca()
. Cualquier cosa que requiera almacenamiento de almacenamiento dinámico (vive después de que la función regrese) o arealloc()
(la matriz cambia de tamaño) prohibiría los VLA de todos modos.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_val
habí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:
Lo que pasa con cualquier declaración local es que es extremadamente rápido. La línea
float vals[n]
generalmente solo requiere un par de instrucciones del procesador (quizás solo una). Simplemente agrega el valorn
al 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
n
en 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 quemalloc
fuera 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 lamalloc
llamada.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.
fuente
int vla[n]; if(test()) { struct LargeStruct s; int i; }
desplazamiento de la pilas
no se conocerá en el momento de la compilación, y también es dudoso que el compilador mueva el almacenamientoi
fuera 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;)s
yi
cuando se ingresa la función, antes de quetest
se llame ovla
se asigne, como las asignaciones paras
yi
no tienen efectos secundarios. (Y, de hecho,i
incluso 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.