Getting a transpose of a matrix of size of n*n where n=2^m using multithreading The following is a c++ source code to get a matrix (std::vector&lt;std::vector&lt;T&gt;&gt;) transpose in parallel.

The span is \$\Theta(\lg^2(n))\$ while the work is \$\Theta(n^2)\$

Any suggestion to improve will be appreciated.

#include&lt;vector&gt;
#include&lt;iostream&gt;
#include&lt;future&gt;
#include&lt;iomanip&gt;
template &lt;typename T&gt;
void parallelForColsTrans(std::vector&lt;std::vector&lt;T&gt;&gt;&amp; A, size_t fCol, size_t lCol, size_t i, size_t n)
{
    if (fCol == lCol)
    {
        T temp = A[i][fCol+n];
        A[i][fCol+n] = A[i+n][fCol];
        A[i+n][fCol] = temp;

        return;
    }

    std::async(parallelForColsTrans&lt;T&gt;, std::ref(A), fCol, (fCol + lCol) / 2, i, n);
    std::async(parallelForColsTrans&lt;T&gt;, std::ref(A), (fCol + lCol) / 2 + 1, lCol, i, n);

}


template &lt;typename T&gt;
void parallelForRowsTrans(std::vector&lt;std::vector&lt;T&gt;&gt;&amp; A, size_t fRow, size_t lRow, size_t fCol, size_t lCol, size_t n)
{
    if (fRow == lRow) {
        parallelForColsTrans(A, fCol, lCol, fRow, n);
        return;
    }

    std::async(parallelForRowsTrans&lt;T&gt;, std::ref(A), fRow, (fRow+lRow) / 2, fCol, lCol, n);
    std::async(parallelForRowsTrans&lt;T&gt;, std::ref(A), (fRow + lRow) / 2 + 1, lRow, fCol, lCol, n);
}

template &lt;typename T&gt;
void pMatTransposeRecursive(std::vector&lt;std::vector&lt;T&gt;&gt;&amp; A, size_t firstRow, size_t lastRow, size_t firstColumn, size_t lastColumn)
{
    if (firstRow == lastRow)    return;

    auto t1 =std::async(pMatTransposeRecursive&lt;T&gt;, std::ref(A), firstRow, (firstRow +lastRow)/2, firstColumn, (firstColumn+lastColumn)/2);
    auto t2 =std::async(pMatTransposeRecursive&lt;T&gt;, std::ref(A), (firstRow +lastRow)/2+1, lastRow, firstColumn, (firstColumn+lastColumn)/2);
    auto t3 =std::async(pMatTransposeRecursive&lt;T&gt;, std::ref(A), firstRow, (firstRow +lastRow)/2, (firstColumn+lastColumn)/2+1, lastColumn);
    pMatTransposeRecursive&lt;T&gt;(std::ref(A), (firstRow +lastRow)/2+1, lastRow, (firstColumn+lastColumn)/2+1, lastColumn);
    t1.get();
    t2.get();
    t3.get();
    size_t n = (lastColumn-firstColumn+1)/2;
    parallelForRowsTrans&lt;T&gt;(std::ref(A), firstRow, firstRow+n-1, firstColumn, firstColumn+n-1, n);

}

template &lt;typename T&gt;
void transpose(std::vector&lt;std::vector&lt;T&gt;&gt;&amp; A){
    pMatTransposeRecursive( A, 0, A.size()-1, 0, A[0].size()-1);
}
int main(){

    std::vector&lt;std::vector&lt;int&gt;&gt; A = {{1,2,3,4,7,7,7,8}, {5,6,7,8,4,5,1,1}, {9,10,5,5,11,12,4,79}, {7,8,13,14,15,16,44,6}, {13,-14,7,-7,15,-16,-44,6}, {13,-14,105,106,404,6,9,9}, {13,-14,7,-7,15,-16,-44,6}, {13,-14,105,106,404,6,9,9}};
    transpose(A);
    for(auto &amp; el:A){
        for(auto&amp; ele:el) std::cout &lt;&lt; ele &lt;&lt; std::setw(4) ;
        std::cout &lt;&lt; "\n";

    }
}
Is it worth parallelising?

When you are parallelizing code you have to ask yourself if it's worth doing that. Parallel code doesn't magically give a speedup, because there are various things that can actually slow you down when using parallelism, for example:


Spawning and waiting for threads itself costs some time.
Threads might be fighting for resources, like locks, but even just memory access might cause contention.
Code that is not trivially parallelizable might require more computations when parallelized than when running single-threaded.


In the case of transposing matrices, there are almost no computations involved, the work is completely dominated by reading and writing to memory. A good single-threaded implementation, which reads sequentially as much as possible, will likely be able to saturate the memory bus on typical desktop machines.

In your implementation, you have a huge overhead just from starting all the async work items: you call async() more often than there are elements in the matrix. So that alone will make this horribly slow. Most good parallel algorithms try to limit the number of threads to the number of CPU cores or hardware threads that are available.

Even if you didn't parallelize, but kept the structure of the code the same (just not use async()), then the recursive divide-and-conquer approach will cause a non-sequential memory access pattern.

Code review

Nested std::vector&lt;&gt;s are not efficient containers for matrices

While it's convenient to declare a 2D matrix using std::vector&lt;std::vector&lt;T&gt;&gt;, it is not very efficient, since there is a lot of indirection. It is more efficient to declare a single std::vector&lt;T&gt; of size n * n, and index the vector using [row * n + col], or use a C++ library that provides proper matrix classes.

Use std::swap()

The standard library provides std::swap(), which swaps two variables for you.