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

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

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 BuildLargeVectores un rvalue, por lo que v se construiría usando el constructor de movimiento de std::vector, asumiendo que (N) RVO no se lleva 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 discreción del compilador. Ahora que tenemos referencias de rvalue, se garantiza que no se realizará ninguna copia profunda.

Editar : La pregunta no se trata realmente de optimización. Ambas formas mostradas tienen un rendimiento casi idéntico en programas del mundo real. Mientras que, en el pasado, la primera forma podría haber tenido un peor desempeño en un orden de magnitud. Como resultado, la primera forma fue un importante olor a código en la programación C ++ durante mucho tiempo. ¿Ya no, espero?

Dave Abrahams tiene un análisis bastante completo de la velocidad de pasar / devolver valores .

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

Al menos en mi opinión, suele ser una mala idea, pero no por razones de eficiencia. Es una mala idea porque la función en cuestión generalmente 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 debe considerarse sospechoso.

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

La esencia es:

Copy Elision y RVO pueden evitar las "copias aterradoras" (el compilador no está obligado a implementar estas optimizaciones y, en algunas situaciones, no se puede aplicar)

Las referencias de C ++ 0x RValue permiten implementaciones de cadena / vector que garantizan eso.

Si puede abandonar las implementaciones de STL / compiladores más antiguos, devuelva los vectores libremente (y asegúrese de que sus propios objetos también lo admitan). Si su base de código necesita ser compatible con compiladores "menores", siga el estilo antiguo.

Desafortunadamente, eso tiene una gran influencia en sus interfaces. Si C ++ 0x no es una opción y necesita garantías, puede usar en su lugar objetos contados por referencias o copia en escritura en algunos escenarios. Sin embargo, tienen desventajas con el subproceso múltiple.

(Ojalá solo una respuesta en C ++ fuera simple y directa y sin condiciones).

En efecto, puesto que C ++ 11, el costo de la copia de la std::vectorha desaparecido en la mayoría de los casos.

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

Comparemos:

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

con:

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

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

Usando BuildLargeVector1, harías:

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);
}

Usando BuildLargeVector2, harías:

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, se producen muchas asignaciones / desasignaciones dinámicas innecesarias, que se evitan en el segundo ejemplo mediante el uso de un parámetro de salida de la forma anterior, reutilizando la memoria ya asignada. Si vale la pena realizar esta optimización o no, depende del costo relativo de la asignación / desasignación en comparación con el costo de calcular / mutar los valores.

Punto de referencia

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

Más específicamente, usemos vecSize * numIter = 2 ^ 31 = 2147483648, porque tengo 16 GB de RAM y este número garantiza que no se asignen más de 8 GB (tamaño de (int) = 4), lo que garantiza que no estoy intercambiando al disco ( todos los demás programas estaban cerrados, tenía ~ 15 GB disponibles cuando ejecuté la prueba).

Aquí está 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 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

(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) = 8GB), los tiempos sean perfectamente idénticos. De hecho, en ambos casos solo asignamos una vez un enorme vector de 8GB en memoria. Esto también demuestra 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,37 veces 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,45 veces más rápido :)

Podemos notar que el tiempo1 es bastante constante de numIter = 1a numIter = 256, lo que significa que asignar un vector enorme de 8GB es tan costoso como asignar 256 vectores de 32MB. Sin embargo, asignar un vector enorme de 8 GB es definitivamente más caro que asignar un vector de 32 MB, por lo que reutilizar la capacidad del vector proporciona ganancias de rendimiento.

De numIter = 512(mem (v) = 16MB) a 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. Esto probablemente tenga que ver con el hecho de que el tamaño de la caché L3 de mi procesador es de 8 MB, por lo que el vector encaja casi por completo en la caché. Realmente no explico por qué el salto repentino de time1es para mem (v) = 16 MB, parecería más lógico que suceda justo después, cuando mem (v) = 8 MB. Tenga en cuenta que, sorprendentemente, en este punto óptimo, ¡no reutilizar la capacidad es de hecho un poco más rápido! Realmente no explico esto.

Cuando las numIter > 8Mcosas se ponen feas. Ambos métodos se vuelven más lentos, pero devolver el vector por valor se vuelve aún más lento. En el peor de los casos, con un vector que contiene solo uno int, reutilizar la capacidad 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 reutilizar la capacidad vectorial es generalmente más rápido, sino que 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 enteros de 64 bits en ~ 0.5s, lo cual es bastante óptimo en un procesador de 4.2Ghz 64bit. 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, lo cual he verificado al volver a ejecutar la prueba mientras monitoreaba el uso de la CPU). El mejor rendimiento se logra cuando mem (v) = 16kB, que es el orden de magnitud de la caché L1 (la caché de datos L1 para el i7-7700K es 4x32kB).

Por supuesto, las diferencias se vuelven cada vez menos relevantes cuanto más cálculo tiene que hacer en 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);:

Conclusiones

1. El uso de parámetros de salida en lugar de la devolución por valor puede proporcionar ganancias de rendimiento al reutilizar la capacidad.
2. En una computadora de escritorio moderna, esto parece solo aplicable a vectores grandes (> 16 MB) y vectores pequeños (<1kB).
3. Evite la asignación de millones o miles de millones de vectores pequeños (<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.

Sigo pensando 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 usando los últimos compiladores.

Anteriormente, muchos de los puntos de acceso que se mostraban 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 usamos nuestro propio tipo de cadena (esto era necesario porque proporcionamos un kit de desarrollo de software donde los escritores de complementos podrían estar usando diferentes compiladores y, por lo tanto, diferentes implementaciones incompatibles de std :: string / std :: wstring).

Hice un cambio simple en respuesta a la sesión de creación de perfiles de muestreo del gráfico de llamadas que mostraba que String :: String (const String &) estaba ocupando 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 creación de perfiles mostró que la asignación y desasignación de memoria es uno de los puntos de acceso más importantes, siendo el constructor de copia de cadena 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 marcó una gran diferencia! El hotspot desapareció en las siguientes sesiones del generador de perfiles y, además, realizamos muchas pruebas unitarias exhaustivas para realizar un seguimiento del rendimiento de nuestra aplicación. Todo tipo de tiempos de prueba de rendimiento disminuyeron significativamente después de estos simples cambios.

Conclusión: no estamos usando los últimos compiladores absolutos, pero todavía parece que no podemos depender de que el compilador optimice la copia para devolver el valor de manera confiable (al menos no en todos los casos). Ese puede no ser el caso para aquellos que usan compiladores más nuevos como MSVC 2010. Estoy deseando que podamos usar C ++ 0x y simplemente usar referencias de rvalue y no tener que preocuparnos nunca de que estemos pesimizando nuestro código al devolver complejos clases por valor.

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

Solo para puntualizar un poco: no es común en muchos lenguajes de programació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 regresarboost::shared_array

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