c++ - Copia rápida de `std:: vector<std:: uint8_t>`

performance optimization

Question

Tengo un std::vector<std::uint8_t> , que necesita ser duplicado. Esto se hace simplemente llamando al constructor de copia.

Los resultados de mi perfil muestran que la implementación de Microsoft Visual C ++ (msvc100) usa std::uninitialized_copy internamente. Esto copia cada elemento uno por uno. En este caso, se puede hacer una copia más optimizada copiando bloques completos de memoria a la vez (como puede hacer memcpy ).

En otras palabras, esto podría ser una optimización significativa. ¿Hay alguna manera de forzar al vector a usar un método tan optimizado?

Nota: He intentado usar std::basic_string<std::uint8_t> y funciona mejor, pero tiene otros problemas.

Answer 1

Basándome en las soluciones sugeridas, decidí armar un pequeño punto de referencia.

#include <cstdint>
#include <cstring>
#include <ctime>
#include <iostream>
#include <random>
#include <vector>

using namespace std;

int main()
{
  random_device seed;
  mt19937 rnd(seed());
  uniform_int_distribution<uint8_t> random_byte(0x00, 0xff);

  const size_t n = 512 * 512;

  vector<uint8_t> source;
  source.reserve(n);
  for (size_t i = 0; i < n; i++) source.push_back(random_byte(rnd));

  clock_t start;
  clock_t t_constructor1 = 0; uint8_t c_constructor1 = 0;
  clock_t t_constructor2 = 0; uint8_t c_constructor2 = 0;
  clock_t t_assign = 0;       uint8_t c_assign = 0;
  clock_t t_copy = 0;         uint8_t c_copy = 0;
  clock_t t_memcpy = 0;       uint8_t c_memcpy = 0;

  for (size_t k = 0; k < 4; k++)
  {
    start = clock();
    for (size_t i = 0; i < n/32; i++)
    {
      vector<uint8_t> destination(source);
      c_constructor1 += destination[i];
    }
    t_constructor1 += clock() - start;

    start = clock();
    for (size_t i = 0; i < n/32; i++)
    {
      vector<uint8_t> destination(source.begin(), source.end());
      c_constructor2 += destination[i];
    }
    t_constructor2 += clock() - start;

    start = clock();
    for (size_t i = 0; i < n/32; i++)
    {
      vector<uint8_t> destination;
      destination.assign(source.begin(), source.end());
      c_assign += destination[i];
    }
    t_assign += clock() - start;

    start = clock();
    for (size_t i = 0; i < n/32; i++)
    {
      vector<uint8_t> destination(source.size());
      copy(source.begin(), source.end(), destination.begin());
      c_copy += destination[i];
    }
    t_copy += clock() - start;

    start = clock();
    for (size_t i = 0; i < n/32; i++)
    {
      vector<uint8_t> destination(source.size());
      memcpy(&destination[0], &source[0], n);
      c_memcpy += destination[i];
    }
    t_memcpy += clock() - start;
  }

  // Verify that all copies are correct, but also prevent the compiler
  // from optimising away the loops
  uint8_t diff = (c_constructor1 - c_constructor2) +
                 (c_assign - c_copy) +
                 (c_memcpy - c_constructor1);

  if (diff != 0) cout << "one of the methods produces invalid copies" << endl;

  cout << "constructor (1): "    << t_constructor1 << endl;
  cout << "constructor (2): "    << t_constructor2 << endl;
  cout << "assign:          "    << t_assign << endl;
  cout << "copy             "    << t_copy << endl;
  cout << "memcpy           "    << t_memcpy << endl;

  return 0;
}

En mi PC, compilado para x64 con msvc100, totalmente optimizado, esto produce el siguiente resultado:

constructor (1): 22388
constructor (2): 22333
assign:          22381
copy             2142
memcpy           2146

Los resultados son bastante claros: std::copy funciona tan bien como std::memcpy , mientras que tanto los constructores como la assign son un orden de magnitud más lento. Por supuesto, los números exactos y las proporciones dependen del tamaño del vector, pero la conclusión para msvc100 es obvia: como lo sugiere Rapptz , use std::copy .

Edit: la conclusión no es obvia para otros compiladores. También probé en Linux de 64 bits, con el siguiente resultado para Clang 3.2

constructor (1): 530000
constructor (2): 560000
assign:          560000
copy             840000
memcpy           860000

GCC 4.8 da un resultado similar. Para GCC en Windows, memcpy y copy fueron ligeramente más lentos que los constructores y assign , aunque la diferencia fue menor. Sin embargo, mi experiencia es que GCC no se optimiza muy bien en Windows. También probé msvc110 y los resultados fueron similares a los de msvc100.

Answer 2

Esta respuesta no es específica para el msvc100.

Si usas el constructor de copia como en

std::vector<uint8_t> newVect(otherVect);

El objeto del asignador otherVect también debe copiarse (y usarse), lo que requiere más esfuerzos para que funcione en la implementación de STL.

Si solo desea copiar el contenido de otherVect, use

std::vector<uint8_t> newVect(otherVect.begin(), otherVect.end());

que utiliza el asignador predeterminado para newVect.

Otra posibilidad es

std::vector<uint8_t> newVect; nevVect.assign(otherVect.begin(), otherVect.end());

Todos ellos (incluido el agente de copia cuando otherVect usa el asignador predeterminado) deben reducirse a un memmove / memcpy en una buena implementación de STL en este caso. Tenga cuidado, que otherVect tiene exactamente el mismo tipo de elemento (no, por ejemplo, ''char'' o ''int8_t'') que newVect.

El uso del método del contenedor generalmente es más eficaz que el uso de algoritmos genéricos, por lo que una combinación de vector :: resize () y std :: copy () o incluso memmove () / memcpy () sería una solución alternativa, si el proveedor no lo hiciera No optimizar suficientemente el contenedor.