Vector-transposing function

Question

I profiled a library I'm writing that uses vector transposes and found that I am spending a good bit of time doing the following transpose. I am using a std::vector of std::vector<double>s to represent the column vectors.

What are some ways to optimize this function?

std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) {
  // take a column vector:
  // |x1|
  // |x2|
  // |x3|
  // and return a row vector |x1, x2, x3|
  std::vector<double> row_vector;
  for (auto c : column_vec) {
    for (auto r : c) {
      row_vector.push_back(r);
    }
  }
  return row_vector;
}

Answer 1

Change your column loop to use a reference.

for (const auto &c : column_vec)

Without the reference, a copy will be made of each vector. This will involve a memory allocation. Using the reference you avoid all that, which should save a good deal of time since each c will be a single element vector.

auto r can stay since r will be a double.

Combine this with using reserve on row_vector will eliminate all but one memory allocation.

Answer 2

Is the vector-of-vectors representation imposed on you, or can you change it? It's going to be more efficient to allocate a single vector, and use simple arithmetic to convert row/column representation into a linear index. It's then possible to provide a transpose view without needing to move all the elements, which may be useful in some circumstances (in others, you'll want to actually perform the transpose, to keep rows contiguous in cache).

If you have a square matrix, a simpler way to transpose (which may or may not be faster - but you'll be benchmarking anyway, to confirm) is to take a copy of the input, and then swap() the elements across the leading diagonal. This is likely to be most advantageous when the elements are trivially copyable, such as the double you're using here.

Answer 3

There's not really much here. The only thing I can think of is it may prove faster to pre-allocate the destination vector using reserve. push_back has the potential to cause several re-allocations per call to transpose, which will be slow. Try:

std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) {
  std::vector<double> row_vector;
  row_vector.reserve(total_entries(column_vec)); // Pre-allocate the space we need

  for (auto c : column_vec) {
    for (auto r : c) {
      row_vector.push_back(r);
    }
  }
  return row_vector;
}

Where total_entries is a function that finds how many cells there are in the 2D vector. If each row is the same length, you could use math to figure this out. If it's ragged though, you may need to iterate column_vector summing the row lengths.

Answer 4

Given that you say this is to transpose vectors and not matrices in general, you can initialize the row vector with the inner vector, for gcc and clang compiler explorer shows differing results between using the iterators or just the inner array.

#include <vector>
#include <cassert>

std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) {
  // take a column vector:
  // |x1|
  // |x2|
  // |x3|
  // and return a row vector |x1, x2, x3|
  assert(column_vec.size() == 1);
  return std::vector<double>(column_vec[0].cbegin(), column_vec[0].cend());
}

As @TobySpeight mentioned the question is if you chose this representation yourself or if you were given in. For example you could probably be more flexible if you separated the storage from the dimension of the data being transported.

Answer 5

The most important point is the name and contract.

And your function doesn't really do any transposing, it just flattens a vector of vectors into a vector, creating spurious temporaries on the way.