En C ++, ¿sigue siendo una mala práctica devolver un vector de una función?

Versión corta: es común devolver objetos grandes, como vectores / matrices, en muchos lenguajes de progtwigción. ¿Este estilo ahora es aceptable en C ++ 0x si la clase tiene un constructor de movimiento, o los progtwigdores de C ++ lo consideran extraño / feo / abominable?

Versión larga: ¿ en C ++ 0x esto todavía se considera mala forma?

std::vector BuildLargeVector(); ... std::vector v = BuildLargeVector(); 

La versión tradicional se vería así:

 void BuildLargeVector(std::vector& result); ... std::vector v; BuildLargeVector(v); 

En la versión más reciente, el valor devuelto por BuildLargeVector es un valor r, por lo que v se construiría usando el constructor de movimiento de std::vector , suponiendo que (R) no se lleve a cabo.

Incluso antes de C ++ 0x, la primera forma a menudo sería “eficiente” debido a (N) RVO. Sin embargo, (N) RVO queda a criterio del comstackdor. Ahora que tenemos referencias de valor real, se garantiza que no se realizará ninguna copia en profundidad.

Editar : La pregunta realmente no es sobre la optimización. Ambas formas mostradas tienen un rendimiento casi idéntico en los progtwigs del mundo real. Mientras que, en el pasado, la primera forma podría haber tenido peor orden de magnitud de rendimiento. Como resultado, la primera forma fue un gran olor a código en la progtwigción de C ++ durante mucho tiempo. Ya no, espero?

Dave Abrahams tiene un análisis bastante completo de la velocidad de los valores de aprobación / devolución .

Respuesta corta, si necesita devolver un valor, regrese un valor. No use referencias de salida porque el comstackdor lo hace de todos modos. Por supuesto, hay advertencias, por lo que debe leer ese artículo.

Al menos IMO, generalmente es una idea pobre, pero no por razones de eficiencia. Es una idea pobre porque la función en cuestión normalmente debe escribirse como un algoritmo genérico que produce su salida a través de un iterador. Casi cualquier código que acepte o devuelva un contenedor en lugar de operar en iteradores se debe considerar sospechoso.

No me malinterpreten: a veces tiene sentido pasar por objetos similares a colecciones (por ejemplo, cadenas), pero para el ejemplo citado, consideraría pasar o devolver al vector una mala idea.

La esencia es:

Copiar Elision y RVO pueden evitar las “copias de miedo” (el comstackdor no está obligado a implementar estas optimizaciones, y en algunas situaciones no se puede aplicar)

Las referencias C ++ 0x RValue permiten una implementación de cadena / vector que garantiza eso.

Si puede abandonar implementaciones de comstackdores / STL más antiguas, devuelva los vectores libremente (y asegúrese de que sus propios objetos también lo admitan). Si su base de código necesita admitir comstackdores “menores”, manténgase en el viejo estilo.

Desafortunadamente, eso tiene una gran influencia en sus interfaces. Si C ++ 0x no es una opción, y necesita garantías, puede utilizar objetos en lugar de referencia contados o de escritura en algunos escenarios. Sin embargo, tienen inconvenientes con el multihilo.

(Deseo que una sola respuesta en C ++ sea simple y directa y sin condiciones).

Todavía creo que es una mala práctica, pero vale la pena señalar que mi equipo usa MSVC 2008 y GCC 4.1, por lo que no estamos utilizando los últimos comstackdores.

Anteriormente, muchos de los hotspots mostrados en vtune con MSVC 2008 se reducían a la copia de cadenas. Teníamos un código como este:

 String Something::id() const { return valid() ? m_id: ""; } 

… tenga en cuenta que utilizamos nuestro propio tipo String (esto fue necesario porque proporcionamos un kit de desarrollo de software donde los escritores de plugins podrían usar diferentes comstackdores y, por lo tanto, implementaciones diferentes e incompatibles de std :: string / std :: wstring).

Realicé un cambio simple en respuesta a la sesión de generación de perfiles de muestreo del gráfico de llamadas que muestra String :: String (const String &) que ocupará una cantidad significativa de tiempo. Los métodos como en el ejemplo anterior fueron los que más contribuyeron (en realidad, la sesión de generación de perfiles mostró que la asignación de memoria y la desasignación eran uno de los puntos de acceso más importantes, y que el constructor de copias String era el principal contribuyente para las asignaciones).

El cambio que hice fue simple:

 static String null_string; const String& Something::id() const { return valid() ? m_id: null_string; } 

Sin embargo, esto hizo un mundo de diferencia! El punto de conexión desapareció en las siguientes sesiones de perfiladores, y además de esto, realizamos muchas pruebas unitarias para realizar un seguimiento del rendimiento de nuestra aplicación. Todos los tipos de tiempos de prueba de rendimiento disminuyeron significativamente después de estos cambios simples.

Conclusión: no estamos utilizando los últimos comstackdores absolutos, pero todavía no podemos depender del comstackdor que optimice la copia para devolver el valor de forma confiable (al menos no en todos los casos). Ese puede no ser el caso para aquellos que usan comstackdores más nuevos como MSVC 2010. Espero con ansias cuándo podemos usar C ++ 0x y simplemente usar referencias rvalue y no tener que preocuparnos de que estamos pesimizando nuestro código volviendo complejo clases por valor

[Editar] Como Nate señaló, RVO se aplica a devolver los temporales creados dentro de una función. En mi caso, no existían tales temporales (a excepción de la twig inválida donde construimos una cadena vacía) y, por lo tanto, RVO no habría sido aplicable.

De hecho, desde C ++ 11, el costo de copiar el std::vector se ha ido en la mayoría de los casos.

Sin embargo, se debe tener en cuenta que el costo de construir el nuevo vector (luego destruirlo ) aún existe, y usar parámetros de salida en lugar de devolver por valor sigue siendo útil cuando se desea reutilizar la capacidad del vector. Esto está documentado como una excepción en F.20 de las Directrices básicas de C ++.

Comparemos:

 std::vector BuildLargeVector1(size_t vecSize) { return std::vector(vecSize, 1); } 

con:

 void BuildLargeVector2(/*out*/ std::vector& v, size_t vecSize) { v.assign(vecSize, 1); } 

Ahora, supongamos que necesitamos llamar a estos métodos numIter veces en un ciclo cerrado, y realizar alguna acción. Por ejemplo, calculemos la sum de todos los elementos.

Usando BuildLargeVector1 , harías:

 size_t sum1 = 0; for (int i = 0; i < numIter; ++i) { std::vector v = BuildLargeVector1(vecSize); sum1 = std::accumulate(v.begin(), v.end(), sum1); } 

Usando BuildLargeVector2 , harías:

 size_t sum2 = 0; std::vector v; for (int i = 0; i < numIter; ++i) { BuildLargeVector2(/*out*/ v, vecSize); sum2 = std::accumulate(v.begin(), v.end(), sum2); } 

En el primer ejemplo, hay muchas asignaciones / desasignaciones dinámicas innecesarias que suceden, que se evitan en el segundo ejemplo al usar un parámetro de salida de la vieja manera, reutilizando la memoria ya asignada. Si esta optimización vale la pena o no depende del costo relativo de la asignación / desasignación en comparación con el costo de computar / mutar los valores.

Punto de referencia

Juguemos con los valores de vecSize y numIter . Mantendremos constante el vecSize * numIter para que "en teoría", tome el mismo tiempo (= hay el mismo número de asignaciones y adiciones, con los mismos valores exactos), y la diferencia de tiempo solo puede venir del costo de asignaciones, desasignaciones y mejor uso de la memoria caché.

Más específicamente, use vecSize * numIter = 2 ^ 31 = 2147483648, porque tengo 16 GB de RAM y este número asegura que no se asignan más de 8 GB (sizeof (int) = 4), asegurando que no estoy intercambiando en el disco ( todos los demás progtwigs se cerraron, tenía ~ 15GB disponibles cuando ejecuté la prueba).

Aquí está el código:

 #include  #include  #include  #include  #include  class Timer { using clock = std::chrono::steady_clock; using seconds = std::chrono::duration; clock::time_point t_; public: void tic() { t_ = clock::now(); } double toc() const { return seconds(clock::now() - t_).count(); } }; std::vector BuildLargeVector1(size_t vecSize) { return std::vector(vecSize, 1); } void BuildLargeVector2(/*out*/ std::vector& v, size_t vecSize) { v.assign(vecSize, 1); } int main() { Timer t; size_t vecSize = size_t(1) < < 31; size_t numIter = 1; std::cout << std::setw(10) << "vecSize" << ", " << std::setw(10) << "numIter" << ", " << std::setw(10) << "time1" << ", " << std::setw(10) << "time2" << ", " << std::setw(10) << "sum1" << ", " << std::setw(10) << "sum2" << "\n"; while (vecSize > 0) { t.tic(); size_t sum1 = 0; { for (int i = 0; i < numIter; ++i) { std::vector v = BuildLargeVector1(vecSize); sum1 = std::accumulate(v.begin(), v.end(), sum1); } } double time1 = t.toc(); t.tic(); size_t sum2 = 0; { std::vector v; for (int i = 0; i < numIter; ++i) { BuildLargeVector2(/*out*/ v, vecSize); sum2 = std::accumulate(v.begin(), v.end(), sum2); } } // deallocate v double time2 = t.toc(); std::cout << std::setw(10) << vecSize << ", " << std::setw(10) << numIter << ", " << std::setw(10) << std::fixed << time1 << ", " << std::setw(10) << std::fixed << time2 << ", " << std::setw(10) << sum1 << ", " << std::setw(10) << sum2 << "\n"; vecSize /= 2; numIter *= 2; } return 0; } 

Y aqui esta el resultado:

 $ g++ -std=c++11 -O3 main.cpp && ./a.out vecSize, numIter, time1, time2, sum1, sum2 2147483648, 1, 2.360384, 2.356355, 2147483648, 2147483648 1073741824, 2, 2.365807, 1.732609, 2147483648, 2147483648 536870912, 4, 2.373231, 1.420104, 2147483648, 2147483648 268435456, 8, 2.383480, 1.261789, 2147483648, 2147483648 134217728, 16, 2.395904, 1.179340, 2147483648, 2147483648 67108864, 32, 2.408513, 1.131662, 2147483648, 2147483648 33554432, 64, 2.416114, 1.097719, 2147483648, 2147483648 16777216, 128, 2.431061, 1.060238, 2147483648, 2147483648 8388608, 256, 2.448200, 0.998743, 2147483648, 2147483648 4194304, 512, 0.884540, 0.875196, 2147483648, 2147483648 2097152, 1024, 0.712911, 0.716124, 2147483648, 2147483648 1048576, 2048, 0.552157, 0.603028, 2147483648, 2147483648 524288, 4096, 0.549749, 0.602881, 2147483648, 2147483648 262144, 8192, 0.547767, 0.604248, 2147483648, 2147483648 131072, 16384, 0.537548, 0.603802, 2147483648, 2147483648 65536, 32768, 0.524037, 0.600768, 2147483648, 2147483648 32768, 65536, 0.526727, 0.598521, 2147483648, 2147483648 16384, 131072, 0.515227, 0.599254, 2147483648, 2147483648 8192, 262144, 0.540541, 0.600642, 2147483648, 2147483648 4096, 524288, 0.495638, 0.603396, 2147483648, 2147483648 2048, 1048576, 0.512905, 0.609594, 2147483648, 2147483648 1024, 2097152, 0.548257, 0.622393, 2147483648, 2147483648 512, 4194304, 0.616906, 0.647442, 2147483648, 2147483648 256, 8388608, 0.571628, 0.629563, 2147483648, 2147483648 128, 16777216, 0.846666, 0.657051, 2147483648, 2147483648 64, 33554432, 0.853286, 0.724897, 2147483648, 2147483648 32, 67108864, 1.232520, 0.851337, 2147483648, 2147483648 16, 134217728, 1.982755, 1.079628, 2147483648, 2147483648 8, 268435456, 3.483588, 1.673199, 2147483648, 2147483648 4, 536870912, 5.724022, 2.150334, 2147483648, 2147483648 2, 1073741824, 10.285453, 3.583777, 2147483648, 2147483648 1, 2147483648, 20.552860, 6.214054, 2147483648, 2147483648 

Resultados de referencia

(Intel i7-7700K @ 4.20GHz; 16 GB DDR4 2400Mhz; Kubuntu 18.04)

Notación: mem (v) = v.size () * sizeof (int) = v.size () * 4 en mi plataforma.

No es sorprendente que cuando numIter = 1 (es decir, mem (v) = 8GB), los tiempos sean perfectamente idénticos. De hecho, en ambos casos, solo estamos asignando una vez un enorme vector de 8GB en memoria. Esto también prueba que no se realizó ninguna copia al usar BuildLargeVector1 (): ¡No tendría suficiente RAM para hacer la copia!

Cuando numIter = 2 , reutilizar la capacidad del vector en lugar de reasignar un segundo vector es 1.37x más rápido.

Cuando numIter = 256 , reutilizar la capacidad del vector (en lugar de asignar / desasignar un vector una y otra vez 256 veces ...) es 2.45x más rápido 🙂

Podemos observar que time1 es bastante constante desde numIter = 1 a numIter = 256 , lo que significa que asignar un enorme vector de 8GB es casi tan costoso como asignar 256 vectores de 32MB. Sin embargo, asignar un enorme vector de 8 GB es definitivamente más caro que asignar un vector de 32 MB, por lo que la reutilización de la capacidad del vector proporciona mejoras de rendimiento.

Desde numIter = 512 (mem (v) = 16MB) hasta numIter = 8M (mem (v) = 1kB) es el punto óptimo: ambos métodos son exactamente igual de rápidos y más rápidos que todas las demás combinaciones de numIter y vecSize. El cálculo es que los dos métodos son casi tan rápidos. Esto probablemente tiene que ver con el hecho de que el tamaño de caché L3 de mi procesador es de 8 MB, por lo que el vector se adapta bastante bien a la caché. Realmente no explico por qué el salto repentino del time1 es para mem (v) = 16MB, parece más lógico que ocurra justo después, cuando mem (v) = 8MB. Tenga en cuenta que, sorprendentemente, en este punto óptimo, la capacidad de no volver a utilizar es, de hecho, un poco más rápida. Realmente no explico esto.

Cuando las cosas numIter > 8M empiezan a ponerse feas. Ambos métodos se vuelven más lentos, pero devolver el vector por valor es aún más lento. En el peor de los casos, con un vector que contiene solo un int , la capacidad de reutilización en lugar de devolver por valor es 3,3 veces más rápido. Presumiblemente, esto se debe a los costos fijos de malloc () que comienzan a dominar.

Observe cómo la curva para el tiempo2 es más suave que la curva para el tiempo1: no solo la reutilización de la capacidad del vector es generalmente más rápida, pero quizás lo más importante es que es más predecible .

También tenga en cuenta que, en el punto óptimo, pudimos realizar 2 mil millones de adiciones de 64 bits enteros en ~ 0.5 s, lo cual es bastante óptimo en un procesador de 4,2 Ghz y 64 bits. Podríamos hacerlo mejor paralelizando el cálculo para usar los 8 núcleos (la prueba anterior solo usa un núcleo a la vez, que he verificado al volver a ejecutar la prueba mientras se monitorea el uso de la CPU). El mejor rendimiento se logra cuando mem (v) = 16kB, que es el orden de magnitud de la memoria caché L1 (la memoria caché de datos L1 para i7-7700K es 4x32kB).

Por supuesto, las diferencias se vuelven menos y menos relevantes cuanto más cálculos tiene que hacer sobre los datos. A continuación se muestran los resultados si reemplazamos sum = std::accumulate(v.begin(), v.end(), sum); por for (int k : v) sum += std::sqrt(2.0*k); :

Benchmark 2

Conclusiones

  1. Usar parámetros de salida en lugar de devolver por valor puede proporcionar ganancias de rendimiento al reutilizar la capacidad.
  2. En una computadora de escritorio moderna, esto solo parece aplicable a vectores grandes (> 16 MB) y pequeños vectores (<1 KB).
  3. Evite asignar millones / billones de pequeños vectores (<1kB). Si es posible, reutilice la capacidad, o mejor aún, diseñe su arquitectura de manera diferente.

Los resultados pueden diferir en otras plataformas. Como de costumbre, si el rendimiento importa, escriba puntos de referencia para su caso de uso específico.

Solo para criticar un poco: no es común en muchos lenguajes de progtwigción devolver matrices de funciones. En la mayoría de ellos, se devuelve una referencia a la matriz. En C ++, la analogía más cercana sería regresar boost::shared_array

Si el rendimiento es un problema real, debe tener en cuenta que la semántica de movimiento no siempre es más rápida que la copia. Por ejemplo, si tiene una cadena que utiliza la optimización de cadena pequeña, entonces para cadenas pequeñas, un constructor de movimientos debe hacer la misma cantidad de trabajo que un constructor de copia normal.