Faster way to convert a vector of vectors to a single contiguous vector with opposite storage order : <p>I have a <code>std::vector&lt;std::vector&lt;double&gt;&gt;</code> that I am trying to convert to a single contiguous vector as fast as possible. My vector has a shape of roughly <code>4000 x 50</code>. </p>

<p>The problem is, sometimes I need my output vector in column-major contiguous order (just concatenating the interior vectors of my 2d input vector), and sometimes I need my output vector in row-major contiguous order, effectively requiring a transpose. </p>

<p>I have found that a naive for loop is quite fast for conversion to a column-major vector:</p>

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

<p>But obviously a similar approach is very slow for row-wise conversion, because of all of the cache misses. So for row-wise conversion, I thought a blocking strategy to promote cache locality might be my best bet:</p>

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

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

<p>This is considerably faster than a naive loop for row-major conversion, but still almost an order of magnitude slower than naive column-major looping on my input size. </p>

<p><a href="https://i.stack.imgur.com/YfgCj.png" rel="noreferrer"><img src="https://i.stack.imgur.com/YfgCj.png" alt="enter image description here"></a></p>

<p><strong>My question is</strong>, is there a faster approach to converting a (column-major) vector of vectors of doubles to a single contiguous row-major vector? I am struggling to reason about what the limit of speed of this code should be, and am thus questioning whether I'm missing something obvious. My assumption was that blocking would give me a <em>much</em> larger speedup then it appears to actually give. </p>

<hr>

<p>The chart was generated using QuickBench  (and somewhat verified with GBench locally on my machine) with this code: (Clang 7, C++20, -O3)</p>

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

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

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

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

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

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

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

static void NaiveColumnMajor(benchmark::State&amp; 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&amp; 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&amp; 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&amp; 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);
</code></pre>
