In C++, sorting a vector of big struct would be slow?

Question

I thought when sorting a vector of structs, the struct elements would be moved around, or the copy-constructor would be called, which will bring in some overhead, so it should be slow.

For example,

struct big_struct_t {
  // with many data members, just to name a few
  int val;
  vector<string> strs;
  ...
};

int main() {
  vector<big_struct_t> V;
  ... // populate V with 10k elements for example

  sort(V.begin(), V.end(), [](const big_struct_t& lhs, const big_struct_t& rhs) {
    return lhs.val < rhs.val;
  });
}

But after testing the above code, seems like no copy-constructor called at all during sorting. So I wonder how the sort actually works? It doesn't need to move the elements around at all inside the vector?

Answer 1

Like the comments said, the performance of std::sort is highly dependent on the elements.

std::vector stores elements contiguously. The only way to change the order of elements is to change their values, by copying, moving or swapping them.

std::sort works by comparing and swapping elements in a random-accessible range (such as a std::vector), which, consequently, must also satisfy ValueSwappable.

In other words, the elements must either have a member function called swap, or be both MoveConstructible and MoveAssignable (in order for std::swap to be used). The compiler will automatically generate both move constructor and move assignment operator, unless you explicitly delete them or a member of your struct causes them to be deleted (such as std::mutex). Although you can use std::is_move_constructible and std::is_move_assignable to check, you don't normally need to worry about that.

SMALL CORRECTION (thanks to @FrançoisAndrieux): an object can still be MoveConstructible and/or MoveAssignable, as long as it has a copy constructor and copy assignment operator (unusual, but possible). See their comment.

Since std::sort will swap elements, the faster instances of your struct can be swapped, the faster the algorithm can run. But, how do you know how complex that is?

If your struct contains only numeric, pointer and other easily swappable members, it should be pretty fast to swap. That also includes most STL containers, such as std::vector, std::deque, std::list, etc..., because they dynamically allocate their elements and simply store pointers to them. Thus, swapping them is as simple as (internally) swapping pointers to the elements.

Therefore, as long as your big_struct_t only contains stuff that can be quickly swapped, std::swap should also work fast.

You may, however, also have members that cannot be quickly swapped, such as C-arrays or std::arrays, or have way too many members. Is this case, you may be better off using another type of container.

Containers such as std::list are able to reorder elements without having to swap their contents, which causes the performance of a sorting operation on one of these containers not to depend on the elements.

To demonstrate, I wrote a quick benchmark. Suppose you have the structs:

struct big_struct_t {
  int val;
  std::vector<std::string> strs;

  bool operator<(const big_struct_t& x) const {
    return val < x.val;
  }
};

struct bigger_struct_t : big_struct_t {
  std::array<std::uint8_t, 1024> kiloByteArray;
};

The first one is pretty trivial to swap. The second one is not. Let's try sorting std::vectors and std::lists of 1000 big_struct_t and bigger_struct_t.

template <typename T>
static T newContainer() {
  int i = 1000;
  T v(i);

  for (auto& struc : v)
  {
    struc.val = i;
    struc.strs.emplace_back(std::to_string(i));
    i--;
  }

  return v;
}

static void SortVectorOfBigStruct(benchmark::State& state) {
  for (auto _ : state) {
    state.PauseTiming();
    auto v = newContainer<std::vector<big_struct_t>>();
    state.ResumeTiming();
    sort(v.begin(), v.end());
    benchmark::DoNotOptimize(v);
  }
}

BENCHMARK(SortVectorOfBigStruct);

static void SortVectorOfBiggerStruct(benchmark::State& state) {
  for (auto _ : state) {
    state.PauseTiming();
    auto v = newContainer<std::vector<bigger_struct_t>>();
    state.ResumeTiming();
    sort(v.begin(), v.end());
    benchmark::DoNotOptimize(v);
  }
}

BENCHMARK(SortVectorOfBiggerStruct);

static void SortListOfBigStruct(benchmark::State& state) {
  for (auto _ : state) {
    state.PauseTiming();
    auto l = newContainer<std::list<big_struct_t>>();
    state.ResumeTiming();
    l.sort();
    benchmark::DoNotOptimize(l);
  }
}

BENCHMARK(SortListOfBigStruct);

static void SortListOfBiggerStruct(benchmark::State& state) {
  for (auto _ : state) {
    state.PauseTiming();
    auto l = newContainer<std::list<bigger_struct_t>>();
    state.ResumeTiming();
    l.sort();
    benchmark::DoNotOptimize(l);
  }
}

BENCHMARK(SortListOfBiggerStruct);

Benchmark on quick-bench.com.

As you can see, sorting a std::vector<bigger_struct_t> is 49x slower than std::vector<big_struct_t>, due to the std::array.

Sorting both std::list<bigger_struct_t> and std::list<big_struct_t> is much faster than std::vector<bigger_struct_t>, since they don't have to deal with the std::array.

Both are also considerably slower than std::vector<big_struct_t>, so avoid using std::list unless you need to.

PS: I'm not sure why std::list<bigger_struct_t> is slower than std::list<big_struct_t>. Maybe a problem with the benchmark? NOTE: See @FrançoisAndrieux's comment about the likely culprit being cache misses.