Which loop optimization is the compiler performing here?

user_5404647 0
Viewed 112

Suppose the following code:

#include <thread>
#include <iostream>
#include <vector>
#include <future>
#include <chrono>
#include <cmath>

long long int partialSum(const std::vector<int>& v, int begin, int end) {
    long long int sum = 0;
    for (int i = begin; i < end; i++) {
        sum += (v[i]);
    }
    return sum;
}

int main() {
    std::vector<int> v(10000000, 1);

    //2 threads
    auto start = std::chrono::high_resolution_clock::now();
    std::future<long long int> f1 = std::async(std::launch::async, partialSum, v, 0, 10000000 /2);
    std::future<long long int> f2 = std::async(std::launch::async, partialSum, v, 10000000 / 2, 10000000);
    volatile long long int a = f1.get() + f2.get();
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono:: duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "With 2 threads-> " << duration.count() << std::endl;

    //1 thread
    start = std::chrono::high_resolution_clock::now();
    volatile long long int b = partialSum(v, 0, 10000000);
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "With 1 thread-> " << duration.count() << std::endl;
}

And the output for my machine (VS2019):

With 2 threads-> 35477
With 1 thread-> 7000

Note that I had to add volatile to avoid more optimization being performed by the compiler. Also note that I know that there is an accumulate in the std, but I'm currently learning about multithreading and this was a POC. Basically, I want to know which kind of optimization the compiler is doing here, because it's optimizing it really well compared to the threaded version. When I change partialSum and replace the operation (maybe log10), then the threaded version is twice as better as the regular one.

Edit: After some suggestions, I changed the code to the following one:

#include <thread>
#include <iostream>
#include <vector>
#include <future>
#include <chrono>
#include <cmath>

long long int partialSum(const std::vector<int>& v, int begin, int end) {
    long long int sum = 0;
    for (int i = begin; i < end; i++) {
        sum += (v[i]);
    }
    return sum;
}

int main() {
    std::vector<int> v(10000000, 1);

    //2 threads
    auto start = std::chrono::high_resolution_clock::now();
    std::future<long long int> f1 = std::async(std::launch::async, partialSum, std::cref(v), 0, 10000000 /2);
    std::future<long long int> f2 = std::async(std::launch::async, partialSum, std::cref(v), 10000000 / 2, 10000000);
    volatile long long int a = f1.get() + f2.get();
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono:: duration_cast<std::chrono::microseconds>(end - start);
    std::cout << "With 2 threads-> " << duration.count() << std::endl;

    //1 thread
    start = std::chrono::high_resolution_clock::now();
    f1 = std::async(std::launch::async, partialSum, std::cref(v), 0, 10000000);
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << "With 1 thread-> " << duration.count() << std::endl;
}

And output:

With 2 threads-> 11835
With 1 thread-> 0
for-loop optimization multithreading c++
1 Answers

The performance gap is there because you are actually copying the vectors here:

std::future<long long int> f1 = std::async(std::launch::async, partialSum, v, 0, 10000000 /2);
std::future<long long int> f2 = std::async(std::launch::async, partialSum, v, 10000000 / 2, 10000000);

Use std::cref to pass them by const reference:

std::future<long long int> f1 = std::async(std::launch::async, partialSum, std::cref(v), 0, 10000000 /2);
std::future<long long int> f2 = std::async(std::launch::async, partialSum, std::cref(v), 10000000 / 2, 10000000);

Then try measuring the performance again. For me, 2 threads version is faster after making this change. Try it here: Godbolt link

Your second snippet is printing 0 for 1 thread because you are not waiting for f1 to finish.

put this before getting the end value:

volatile long long int b = f1.get();

As for the loop optimization (this part maybe unnecessary for the OP) the compiler(GCC) is vectorizing the loop(without any -march= option). The generated asm looks like:

.L399:
        movdqu  xmm0, XMMWORD PTR [rax]
        movdqa  xmm2, xmm4
        add     rax, 16
        pcmpgtd xmm2, xmm0
        movdqa  xmm3, xmm0
        punpckldq       xmm3, xmm2
        punpckhdq       xmm0, xmm2
        paddq   xmm1, xmm3
        paddq   xmm1, xmm0
        cmp     rdx, rax
        jne     .L399

We can make it a bit easy for compiler to optimize this further if we use int instead of long long int. The asm output is then reduced to:

        pxor    xmm0, xmm0
.L13:
        movdqu  xmm2, XMMWORD PTR [rdx]
        add     rdx, 16
        paddd   xmm0, xmm2
        cmp     rcx, rdx
        jne     .L13
user_22794220
Related