c++ - 将 vector vector 转换为具有相反存储顺序的单个连续 vector 的更快方法

Question

我有一个 std::vector<std::vector<double>>我试图尽快转换为单个连续 vector 。我的 vector 的形状大约为 4000 x 50 .

问题是，有时我需要以列为主连续顺序的输出 vector (只是连接我的 2d 输入 vector 的内部 vector )，有时我需要以行为主连续顺序的输出 vector ，实际上需要转置。

我发现一个简单的 for 循环转换为列主 vector 的速度非常快:

auto to_dense_column_major_naive(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    for (size_t i = 0; i < n_col; ++i)
        for (size_t j = 0; j < n_row; ++j)
            out_vec[i * n_row + j] = vec[i][j];
    return out_vec;
}

但显然，由于所有缓存未命中，类似的方法对于逐行转换来说非常慢。因此，对于逐行转换，我认为促进缓存局部性的阻塞策略可能是我最好的选择:

auto to_dense_row_major_blocking(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    size_t block_side = 8;

    for (size_t l = 0; l < n_col; l += block_side) {
        for (size_t k = 0; k < n_row; k += block_side) {
            for (size_t j = l; j < l + block_side && j < n_col; ++j) {
                auto const &column = vec[j];
                for (size_t i = k; i < k + block_side && i < n_row; ++i)
                    out_vec[i * n_col + j] = column[i];
            }
        }
    }
    return out_vec;
}

这比行优先转换的朴素循环快得多，但仍然比输入大小的朴素列优先循环慢几乎一个数量级。



我的问题是 ，是否有更快的方法将 double vector 的(列主) vector 转换为单个连续的行主 vector ？我正在努力推理这段代码的速度限制应该是多少，因此我怀疑我是否遗漏了一些明显的东西。我的假设是阻塞会给我一个比它实际提供的更大的加速。

该图表是使用 QuickBench 生成的(并在我的机器上本地使用 GBench 进行了一些验证)，代码如下:(Clang 7、C++20、-O3)

auto to_dense_column_major_naive(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    for (size_t i = 0; i < n_col; ++i)
        for (size_t j = 0; j < n_row; ++j)
            out_vec[i * n_row + j] = vec[i][j];
    return out_vec;
}

auto to_dense_row_major_naive(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    for (size_t i = 0; i < n_col; ++i)
        for (size_t j = 0; j < n_row; ++j)
            out_vec[j * n_col + i] = vec[i][j];
    return out_vec;
}

auto to_dense_row_major_blocking(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    size_t block_side = 8;

    for (size_t l = 0; l < n_col; l += block_side) {
        for (size_t k = 0; k < n_row; k += block_side) {
            for (size_t j = l; j < l + block_side && j < n_col; ++j) {
                auto const &column = vec[j];
                for (size_t i = k; i < k + block_side && i < n_row; ++i)
                    out_vec[i * n_col + j] = column[i];
            }
        }
    }
    return out_vec;
}

auto to_dense_column_major_blocking(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    size_t block_side = 8;

    for (size_t l = 0; l < n_col; l += block_side) {
        for (size_t k = 0; k < n_row; k += block_side) {
            for (size_t j = l; j < l + block_side && j < n_col; ++j) {
                auto const &column = vec[j];
                for (size_t i = k; i < k + block_side && i < n_row; ++i)
                    out_vec[j * n_row + i] = column[i];
            }
        }
    }
    return out_vec;
}

auto make_vecvec() -> std::vector<std::vector<double>>
{
  std::vector<std::vector<double>> vecvec(50, std::vector<double>(4000));
  std::mt19937 mersenne {2019};
  std::uniform_real_distribution<double> dist(-1000, 1000);
  for (auto &vec: vecvec)
   for (auto &val: vec)
       val = dist(mersenne);
  return vecvec;
}

static void NaiveColumnMajor(benchmark::State& state) {
  // Code before the loop is not measured

  auto vecvec = make_vecvec();
  for (auto _ : state) {
    benchmark::DoNotOptimize(to_dense_column_major_naive(vecvec));
  }
}
BENCHMARK(NaiveColumnMajor);

static void NaiveRowMajor(benchmark::State& state) {
  // Code before the loop is not measured

  auto vecvec = make_vecvec();
  for (auto _ : state) {
    benchmark::DoNotOptimize(to_dense_row_major_naive(vecvec));
  }
}
BENCHMARK(NaiveRowMajor);

static void BlockingRowMajor(benchmark::State& state) {
  // Code before the loop is not measured

  auto vecvec = make_vecvec();
  for (auto _ : state) {
    benchmark::DoNotOptimize(to_dense_row_major_blocking(vecvec));
  }
}
BENCHMARK(BlockingRowMajor);

static void BlockingColumnMajor(benchmark::State& state) {
  // Code before the loop is not measured

  auto vecvec = make_vecvec();
  for (auto _ : state) {
    benchmark::DoNotOptimize(to_dense_column_major_blocking(vecvec));
  }
}
BENCHMARK(BlockingColumnMajor);

Answer 1

首先，每当某些东西被限定为“显然”时，我都会畏缩。这个词经常用来掩盖一个人在推理中的缺点。

But obviously a similar approach is very slow for row-wise conversion, because of all of the cache misses.

我不确定哪个应该是显而易见的:逐行转换会很慢，或者由于缓存未命中而变慢。无论哪种情况，我都觉得这并不明显。毕竟，这里有两个缓存注意事项，不是吗？一读一写？我们从阅读的角度来看代码:
row_major_naive

for (size_t i = 0; i < n_col; ++i)
    for (size_t j = 0; j < n_row; ++j)
        out_vec[j * n_col + i] = vec[i][j];

连续读取来自 vec是连续内存的读取: vec[i][0]其次是 vec[i][1]等，非常适合缓存。所以...缓存未命中？减缓？ :) 也许不那么明显。
尽管如此，还是可以从中得到一些启示。只有声称“显然”是错误的。存在非局部性问题，但它们发生在写入端。 (连续写入被 50 个 double 值的空间所抵消。)经验测试证实了缓慢。所以也许一个解决方案是翻转被认为是“明显”的东西？
行专业翻转

for (size_t j = 0; j < n_row; ++j)
    for (size_t i = 0; i < n_col; ++i)
        out_vec[j * n_col + i] = vec[i][j];

我在这里所做的只是反转循环。从字面上交换这两行代码的顺序，然后调整缩进。现在连续读取可能无处不在，因为它们从不同的 vector 中读取。但是，连续写入现在是对连续的内存块。从某种意义上说，我们的处境和以前一样。但就像以前一样，在假设“快”或“慢”之前应该先衡量性能。
NaiveColumnMajor:3.4 秒
NaiveRowMajor:7.7 秒
翻转行主要:4.2 秒
BlockingRowMajor:4.4 秒
BlockingColumnMajor:3.9 秒
仍然比朴素的列主要转换慢。但是，这种方法不仅比 naive row major 快，而且也比 快。阻塞 行专业。至少在我的电脑上(使用 gcc -O3 显然 :P 迭代数千次)。里程可能会有所不同。我不知道花哨的分析工具会说什么。关键是有时越简单越好。
对于 funsies，我做了一个测试，其中维度交换了(从 4000 个元素的 50 个 vector 更改为 50 个元素的 4000 个 vector )。所有方法都以这种方式受到伤害，但“NaiveRowMajor”受到的打击最大。值得注意的是，“翻转行专业”落后于阻塞版本。因此，正如人们所期望的那样，适合这项工作的最佳工具取决于具体的工作内容。
NaiveColumnMajor:3.7 秒
NaiveRowMajor: 16 秒
翻转行主要:5.6 秒
BlockingRowMajor:4.9 秒
BlockingColumnMajor:4.5 秒
(顺便说一句，我还尝试了阻塞版本的翻转技巧。变化很小 - 大约 0.2 - 与翻转天真的版本相反。也就是说，对于问题的“翻转阻塞”比“阻塞”慢50-of-4000 vector ，但对于我的 4000-of-50 变体更快。微调可能会改善结果。)

更新:我对阻塞版本的翻转技巧进行了更多测试。这个版本有四个循环，所以“翻转”不像只有两个循环那样直接。看起来交换外部两个循环的顺序对性能不利，而交换内部两个循环的顺序是好的。 (最初，我已经完成了这两项工作，但结果喜忧参半。)当我只交换内部循环时，我测量了 。 3.8 秒 (在 4000-of-50 场景中为 4.1 秒)，使其成为我测试中最好的行优先选项。
排大杂种

for (size_t l = 0; l < n_col; l += block_side)
    for (size_t i = 0; i < n_row; ++i)
        for (size_t j = l; j < l + block_side && j < n_col; ++j)
            out_vec[i * n_col + j] = vec[j][i];

(交换内循环后，我合并了中间循环。)
至于这背后的理论，我猜这相当于一次尝试写入一个缓存块。一旦一个块被写入，在它们从缓存中弹出之前尝试重用 vector ( vec[j])。用完这些源 vector 后，转到一组新的源 vector ，再次一次写入完整块。