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

https://stackoverflow.com/questions/3134831

01-10-2019
|

Pregunta

versión corta: Es común para volver objetos grandes, tales como vectores / matrices en muchos lenguajes de programación. Este estilo es ahora aceptable en C ++ 0x si la clase tiene un constructor mover o hacer los programadores de C ++ consideran / feo / abominación raro?

Versión larga:? En C ++ 0x esta forma es mala todavía se considera

std::vector<std::string> BuildLargeVector();
...
std::vector<std::string> v = BuildLargeVector();

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

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

En la versión más reciente, el valor devuelto por BuildLargeVector es un valor p, de modo v se construyó usando el constructor movimiento de std::vector, asumiendo (N) RVO no tiene lugar.

Incluso antes de C ++ 0x la primera forma a menudo sería "eficiente" a causa de RVO (N). Sin embargo, (N) RVO es a discreción del compilador. Ahora que tenemos referencias rvalue es garantizada que ninguna copia profunda se llevará a cabo.

Editar : Pregunta no es realmente acerca de la optimización. Ambas formas mostradas tienen un rendimiento casi idéntico en los programas del mundo real. Considerando que, en el pasado, la primera forma podría haber tenido un orden de magnitud peor rendimiento. Como resultado, la primera forma era un importante olor código en la programación C ++ por un largo tiempo. Ya no es así, espero?

Solución

David Abrahams tiene un análisis muy exhaustivo de la velocidad de paso / valores que regresan .

respuesta corta, si es necesario devolver un valor a continuación, devuelve un valor. No utilice referencias de salida ya que el compilador hace de todos modos. Por supuesto hay advertencias, por lo que debe leer este artículo.

Otros consejos

Al menos OMI, por lo general es una mala idea, pero no por razones de eficiencia. Es una mala idea porque la función de que se trata por lo general debe ser escrito como un algoritmo genérico que se produce su salida a través de un repetidor. Casi cualquier código que acepta o devuelve un contenedor en vez de operar en iteradores debe ser considerado sospechoso.

No me malinterpreten:. Hay veces que tiene sentido para pasar alrededor de colección como objetos (por ejemplo, cadenas), pero para el ejemplo citado, me gustaría considerar pasar o devolver el vector de una mala idea

Lo esencial es:

Copiar Elision y OVR puede evitar las copias "de miedo" (el compilador no está obligado a poner en práctica estas optimizaciones, y en algunos casos no se puede aplicar)

referencias C ++ 0x RValue permitir una cadena / implementaciones vector que garantías que.

Si puede abandonar compiladores anteriores implementaciones / STL, vectores de retorno libremente (y asegurarse de que sus propios objetos apoyan, también). Si sus necesidades de base de código para apoyar los compiladores "menores", se adhieren a la antigua usanza.

Por desgracia, que tiene gran influencia en sus interfaces. Si C ++ 0x no es una opción, y que necesita garantías, es posible utilizar en lugar de referencia contado o una copia en escritura objetos en algunos escenarios. Ellos tienen inconvenientes con múltiples hilos, sin embargo.

(deseo una sola respuesta en C ++ sería simple y directo y sin condiciones).

De hecho, puesto que C ++ 11, el costo de copiar el std::vector ha desaparecido en la mayoría de los casos.

Sin embargo, uno debe tener en cuenta que el costo de construcción el nuevo vector (entonces destructing es) todavía existe, y el uso de los parámetros de salida en lugar de regresar por el valor es siendo útil cuando se desea volver a utilizar la capacidad del vector. Esto está documentado como una excepción en F.20 de las Directrices Core C ++.

Vamos a comparar:

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

por:

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

Ahora, supongamos que tenemos que llamar a estos métodos tiempos numIter en un bucle estrecho, y realizar alguna acción. Por ejemplo, vamos a calcular la suma de todos los elementos.

El uso de BuildLargeVector1, que haría:

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

El uso de BuildLargeVector2, que haría:

size_t sum2 = 0;
std::vector<int> 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 muchos innecesarios asignaciones dinámicas / cancelaciones de asignación que suceden, lo cual se impide en el segundo ejemplo usando un parámetro de salida la manera antigua, reutilizando de memoria ya asignada. Sea o no esta optimización es digno de hacer depende del coste relativo de la asignación / desasignación en comparación con el costo de la computación / mutación de los valores.

Benchmark

Juguemos con los valores de vecSize y numIter. Vamos a mantener constante vecSize * numIter por lo que "en teoría", se debe tomar al mismo tiempo (= existe el mismo número de misiones y adiciones, con exactamente los mismos valores), y la diferencia de tiempo sólo puede venir de los costes de asignaciones, cancelaciones de asignación, y un mejor uso de la memoria caché.

Más específicamente, vamos a usar vecSize * numIter = 2 ^ 31 = 2147483648, porque tengo 16 GB de RAM y este número asegura que no más de 8 GB se asigna (sizeof (int) = 4), asegurándose de que no estoy intercambiando en el disco (todos los demás programas estaban cerrados, tenía ~ 15 GB disponibles cuando se ejecuta la prueba).

Este es el código:

#include <chrono>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

class Timer {
    using clock = std::chrono::steady_clock;
    using seconds = std::chrono::duration<double>;
    clock::time_point t_;

public:
    void tic() { t_ = clock::now(); }
    double toc() const { return seconds(clock::now() - t_).count(); }
};

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

void BuildLargeVector2(/*out*/ std::vector<int>& 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<int> v = BuildLargeVector1(vecSize);
                sum1 = std::accumulate(v.begin(), v.end(), sum1);
            }
        }
        double time1 = t.toc();

        t.tic();
        size_t sum2 = 0;
        {
            std::vector<int> 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 aquí está 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

(Intel i7-7700K @ 4.20GHz; 16GB 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) = 8 GB), los tiempos son perfectamente idénticos. De hecho, en ambos casos sólo estamos asignando una vez a la gran vector de 8 GB en la memoria. Esto también demuestra que ninguna copia sucedió cuando se utiliza BuildLargeVector1 (): no tener suficiente memoria RAM para hacer la copia

Cuando numIter = 2, la reutilización de la capacidad vectorial en lugar de re-asignación de un segundo vector es 1.37x más rápido.

Cuando numIter = 256, la reutilización de la capacidad vectorial (en lugar de asignar / desasignar un vector una y otra vez 256 veces ...) es 2.45x más rápido :)

Se puede notar que tiempo1 es más o menos constante desde numIter = 1 a numIter = 256, lo que significa que la asignación de una gran vector de 8 GB es casi tan costosa como la asignación de 256 vectores de 32MB. Sin embargo, la asignación de una gran vector de 8 GB es definitivamente más caro que la asignación de un vector de 32 MB, por lo que la reutilización de la capacidad del vector proporciona mejoras de rendimiento.

De numIter = 512 (MEM (v) = 16 MB) a numIter = 8M (MEM (v) = 1kB) es el punto dulce: ambos métodos son exactamente tan rápido, y más rápido que todas las otras combinaciones de numIter y vecSize. Esto probablemente tiene que ver con el hecho de que el tamaño de caché L3 de mi procesador es de 8 MB, de modo que el vector más o menos encaja completamente en la memoria caché. Realmente no me explico por qué el repentino salto de time1 es para mem (v) = 16MB, parecería más lógico que suceda justo después, cuando mem (v) = 8 MB. Tenga en cuenta que surprendentemente, en este punto dulce, no se vuelve a utilizar la capacidad es de hecho un poco más rápido! Realmente no me explico esto.

Cuando las cosas empiezan a ponerse numIter > 8M feo. Ambos métodos consiguen más lenta pero volviendo el vector de valor es aún más lenta. En el peor de los casos, con un vector que contiene solamente un único int, la reutilización de la capacidad en vez de volver por valor es 3.3x más rápido. Presumiblemente, esto es debido a los costos fijos de malloc () que comienzan a dominar.

Nota cómo la curva durante el tiempo 2 es más suave que la curva de tiempo 1:. No sólo la reutilización de la capacidad del vector es generalmente más rápido, pero quizás lo más importante, es más predecible

También se nota que en el punto dulce, hemos sido capaces de realizar adiciones de 2 mil millones de números enteros de 64 bits en ~ 0,5 s, lo cual es bastante óptima en un procesador de 4.2GHz de 64 bits. Podríamos hacerlo mejor mediante la paralelización de la computación con el fin de utilizar los 8 núcleos (la prueba anterior sólo utiliza un núcleo a la vez, que he verificado por volver a ejecutar la prueba, mientras que la supervisión del uso de la CPU). El mejor rendimiento se alcanza cuando mem (v) = 16kB, que es el orden de magnitud de la memoria caché L1 (caché de datos L1 para el i7-7700K es 4x32kB).

Por supuesto, las diferencias se hacen cada vez menos relevante el cálculo más que realmente tiene que ver en los datos. A continuación se presentan los resultados si se sustituye por sum = std::accumulate(v.begin(), v.end(), sum); for (int k : v) sum += std::sqrt(2.0*k);:

Conclusiones

Uso de los parámetros de salida en lugar de regresar por el valor de puede proporcionar mejoras de rendimiento mediante la reutilización de la capacidad.
En una computadora de escritorio moderno, esto parece sólo es aplicable a los vectores de gran tamaño (> 16 MB) y vectores pequeños (<1 kb).
evite la asignación de millones / miles de pequeños vectores (<1 kb). Si la capacidad es posible, la reutilización, o mejor aún, el diseño de su arquitectura diferente.

Los resultados pueden diferir en otras plataformas. Como de costumbre, si los asuntos de rendimiento, los puntos de referencia de escritura para el caso de uso específico.

Todavía pienso que es una mala práctica, pero vale la pena señalar que mi equipo utiliza MSVC 2008 y GCC 4.1, así que no estamos utilizando los últimos compiladores.

Anteriormente una gran cantidad de los puntos que se muestran en VTune con MSVC 2008 descendió a la copia cadena. Tuvimos código como este:

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

... nota que utilizamos nuestro propio tipo String (esto era necesario porque estamos proporcionando un kit de desarrollo de software donde los escritores de plugin podrían estar utilizando diferentes compiladores y, por lo tanto, diferentes implementaciones incompatibles de std :: string / std :: wstring).

Me hizo un simple cambio en respuesta a la gráfica llamada muestreo de perfiles de sesión mostrando Cadena :: string (const string &) para estar tomando una cantidad significativa de tiempo. Métodos como en el ejemplo anterior fueron los mayores contribuyentes (en realidad la sesión de perfiles mostraron asignación de memoria y cancelación de asignación a ser uno de los mayores puntos de acceso, con el constructor de copia de cuerdas siendo el principal contribuyente de 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, este hizo un mundo de diferencia! El punto de acceso se fue en sesiones posteriores de perfil, y además de esto, hacer un montón de pruebas de unidad a fondo para no perder de vista nuestro rendimiento de las aplicaciones. Todos los tipos de tiempos de prueba de rendimiento se redujo significativamente después de estos simples cambios.

Conclusión: no estamos usando las últimas absolutos compiladores, pero todavía parece que no puede depender de la distancia compilador optimizar la copia de la devolución por el valor fiable (al menos no en todos los casos). Eso no puede ser el caso de los que utilizan los nuevos compiladores como MSVC 2010. Estoy deseando que cuando podemos utilizar C ++ 0x y simplemente utilizar referencias rvalue y no siempre tienen que preocuparse de que estamos pessimizing nuestro código devolviendo complejo clases por valor.

[Editar] Como Nate señaló, RVO se aplica a regresar temporales creadas dentro de una función. En mi caso, no había tales temporales (a excepción de la rama nulo, cuando se construye una cadena vacía) y por lo tanto RVO no habría sido aplicable.

Al igual que pequeñez un poco: no es común en muchos lenguajes de programación para volver matrices de funciones. En la mayoría de ellos, se devuelve una referencia a la matriz. En C ++, la analogía más cercana estaría volviendo boost::shared_array

Si el rendimiento es un problema real que debe darse cuenta de que la semántica movimiento no son siempre más rápido que copiar. Por ejemplo, si usted tiene una cadena que utiliza el pequeña cadena optimización a continuación, para las pequeñas cadenas de un constructor movimiento debe hacer exactamente la misma cantidad de trabajo como un constructor de copia normal.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow