There is a task to write a quick sort algorithm using coroutines from the boost library. It seems to have written, but it turns out that he sorts by time longer than without using coroutines. Although in theory should be faster. Tell me what I'm doing wrong?

template <class T> using vector_t = std::vector<T>; using coro_t = boost::coroutines2::coroutine<int32_t>; template <class T> void partition(coro_t::push_type& sink, vector_t<T>& v, int32_t left, int32_t right) { int32_t pivot = v[right]; int32_t i = (left - 1); for (int32_t j = left; j <= right - 1; j++) { if (v[j] <= pivot) { i++; std::swap(v[i], v[j]); } } std::swap(v[i + 1], v[right]); sink(i + 1); } template <class T> void quickSort(vector_t<T>& v, int32_t left, int32_t right) { if (left <= right) { coro_t::pull_type source{[&](auto &&arg1) { partition(arg1, v, left, right); quickSort(v, left, source.get() - 1); quickSort(v, source.get() + 1, right); }}; source(); } } int main() { vector_t<int32_t> v(10); std::cin >> v; std::cout <<"Vector before:\n" << v << std::endl; clock_t t = clock(); quickSort(v, 0, v.size() - 1); t = clock() - t; std::cout << std::fixed << ((double) t) / CLOCKS_PER_SEC << std::endl; std::cout << "Vector after:\n" << v << std::endl; }
  • firstly, the vector is too small to estimate the time ... and secondly, I don’t understand something, how coroutines can help make sorting faster? - Fat-Zer 1:58 pm
  • To estimate the time, the vector was taken in different sizes. And at the expense of speeding up the sorting, this is only my, possibly erroneous, assumption based on my previous coroutine experiments. - agrmv 2:23 pm

1 answer 1

Korutin work in the same thread, in any case, they will work more slowly (time is spent on their creation). They provide an advantage only for asynchronous operations.

For acceleration, you need either multi-threaded corutines (in boost, it seems, there is something similar), or a banal pool of threads. If you want to achieve acceleration - I would recommend first to implement a quick sort using std::async and see if the acceleration will work out at all when parallelizing. For small vectors, it will not work out exactly, the results should be visible when sorting about a thousand small lines (sorting lines better demonstrates applicability in real programs, for sorting int it is unlikely to need multithreading).