Simple C++ Loop Not Benefitting from Multithreading

Question

I have some extremely simple C++ code that I was certain would run 3x faster with multithreading but somehow only runs 3% faster (or less) on both GCC and MSVC on Windows 10.

There are no mutex locks and no shared resources. And I can't see how false sharing or cache thrashing could be at play since each thread only modifies a distinct segment of the array, which has over a billion int values. I realize there are many questions on SO like this but I haven't found any that seem to solve this particular mystery.

One hint might be that moving the array initialization into the loop of the add() function does make the function 3x faster when multithreaded vs single-threaded (~885ms vs ~2650ms).

Note that only the add() function is being timed and takes ~600ms on my machine. My machine has 4 hyperthreaded cores, so I'm running the code with threadCount set to 8 and then to 1.

Any idea what might be going on? Is there any way to turn off (when appropriate) the features in processors that cause things like false sharing (and possibly like what we're seeing here) to happen?

#include <chrono>
#include <iostream>
#include <thread>

void startTimer();
void stopTimer();
void add(int* x, int* y, int threadIdx);

namespace ch = std::chrono;
auto start = ch::steady_clock::now();
const int threadCount = 8;
int itemCount = 1u << 30u; // ~1B items
int itemsPerThread = itemCount / threadCount;

int main() {
    int* x = new int[itemCount];
    int* y = new int[itemCount];

    // Initialize arrays
    for (int i = 0; i < itemCount; i++) {
        x[i] = 1;
        y[i] = 2;
    }

    // Call add() on multiple threads
    std::thread threads[threadCount];
    startTimer();
    for (int i = 0; i < threadCount; ++i) {
        threads[i] = std::thread(add, x, y, i);
    }
    for (auto& thread : threads) {
        thread.join();
    }
    stopTimer();

    // Verify results
    for (int i = 0; i < itemCount; ++i) {
        if (y[i] != 3) {
            std::cout << "Error!";
        }
    }

    delete[] x;
    delete[] y;
}

void add(int* x, int* y, int threadIdx) {
    int firstIdx = threadIdx * itemsPerThread;
    int lastIdx = firstIdx + itemsPerThread - 1;

    for (int i = firstIdx; i <= lastIdx; ++i) {
        y[i] = x[i] + y[i];
    }
}

void startTimer() {
    start = ch::steady_clock::now();
}

void stopTimer() {
    auto end = ch::steady_clock::now();
    auto duration = ch::duration_cast<ch::milliseconds>(end - start).count();
    std::cout << duration << " ms\n";
}

Answer 1

Your problem is not the processor. You ran against the RAM read and write latency. As your cache is able to hold some megabytes of data and you exceed this storage by far. Multi-threading is so long useful, as long as you can shovel data into your processor. The cache in your processor is incredibly fast, compared to your RAM. As you exceed your cache storage, this results in a RAM latency test.

If you want to see the advantages of multi-threading, you have to choose data sizes in range of your cache size.

---

EDIT

Another thing to do, would be to create a higher workload for the cores, so the storage latency goes unrecognized.

sidenote: keep in mind, your core has several execution units. one or more for each type of operation - integer, float, shift and so on. That means, one core can execute more then one command per step. In particular one operation per execution unit. You can keep the data size of the test data and do more stuff with it - be creative =) Filling the queue with integer operations only, will give you an advantage in multi-threading. If you can variate in your code, when and where you do different operations, do it, this also will show impact on the speedup. Or avoid it, if you want to see a nice speedup on multi-threading.

to avoid any kind of optimization, you should use randomized test data. so neither the compiler nor the processor itself can predict what the outcome of your operation is.

Also avoid doing branches like if and while. Each decision the processor has to predict and execute, will slow you down and alter the result. With branch-prediction, you will never get a deterministic result. Later in a "real" program, be my guest and do what you want. But when you want to explore the multi-threading world, this could lead you to wrong conclusions.

---

BTW

Please use a delete for every new you use, to avoid memory leaks. AND even better, avoid plain pointers, new and delete. You should use RAII. I advice to use std::array or std::vector, simple a STL-container. This will save you tons of debugging time and headaches.

Answer 2

Speedup from parallelization is limited by the portion of the task that remains serial. This is called Amdahl's law. In your case, a decent amount of that serial time is spent initializing the array.

Are you compiling the code with -O3? If so, the compiler might be able to unroll and/or vectorize some of the loops. The loop strides are predictable, so hardware prefetching might help as well.

You might want to also explore if using all 8 hyperthreads are useful or if it's better to run 1 thread per core (I am going to guess that since the problem is memory-bound, you'll likely benefit from all 8 hyperthreads).

Nevertheless, you'll still be limited by memory bandwidth. Take a look at the roofline model. It'll help you reason about the performance and what speedup you can theoretically expect. In your case, you're hitting the memory bandwidth wall that effectively limits the ops/sec achievable by your hardware.

Answer 3

You may be simply hitting the memory transfer rate of your machine, you are doing 8GB of reads and 4GB of writes.

On my machine your test completes in about 500ms which is 24GB/s (which is similar to the results given by a memory bandwidth tester).

As you hit each memory address with a single read and a single write the caches aren't much use as you aren't reusing memory.