快速复制`std :: vector <std :: uint8_t>`

Question

我有一个std::vector<std::uint8_t>,需要重复.只需调用复制构造函数即可完成此操作.

我的分析结果显示,Microsoft Visual C++(msvc100)实现在std::uninitialized_copy内部使用.这将逐个复制每个元素.在这种情况下,可以通过一次复制整个存储块来完成更优化的复制(就像memcpy可能一样).

换句话说,这可能是一个重要的优化.有没有办法强制矢量使用这种优化方法？

注意:我尝试过使用std::basic_string<std::uint8_t>它确实表现更好,但它有其他问题.

Answer 1

这个答案并非特定于msvc100.

如果您使用像中的复制构造函数

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

另外,必须复制(和使用)otherVect的allocator对象,这需要更多的努力才能在STL实现中实现它.

如果您只想复制otherVect 的内容,请使用

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

它使用newVect的默认分配器.

另一种可能性是

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

在这种情况下,所有这些(包括otherVect使用默认分配器时的复制构造函数)应归结为良好STL实现中的memmove/memcpy.请注意,otherVect与newVect具有完全相同的元素类型(不是'char'或'int8_t').

使用容器的方法通常比使用通用算法更高效,因此如果供应商没有,那么vector :: resize()和std :: copy()甚至memmove()/ memcpy()的组合将是一种解决方法.不要充分优化容器.

Answer 2

根据建议的解决方案，我决定整理一个小型基准。

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

在我的 PC 上，使用 msvc100 编译为 x64，经过完全优化，会产生以下输出：

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

结果非常清楚：std::copy执行得和 一样std::memcpy，而构造函数 和assign都慢了一个数量级。当然，确切的数字和比率取决于向量大小，但 msvc100 的结论是显而易见的：按照Rapptz 的建议，使用std::copy。

编辑：对于其他编译器来说结论并不明显。我也在 64 位 Linux 上进行了测试，Clang 3.2 的结果如下

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

GCC 4.8 给出了类似的输出。对于 Windows 上的 GCC，memcpy和copy比构造函数 和 稍慢assign，尽管差异较小。然而，我的经验是 GCC 在 Windows 上优化得不是很好。我也测试了msvc110，结果和msvc100类似。