Multithreaded function performance worse than single threaded

Question

I wrote an update() function which ran on a single thread, then I wrote the below function updateMP() which does the same thing except I divide the work in my two for loops here amongst some threads:

void GameOfLife::updateMP()
{
    std::vector<Cell> toDie;
    std::vector<Cell> toLive;

#pragma omp parallel
    {
        // private, per-thread variables
        std::vector<Cell> myToDie;
        std::vector<Cell> myToLive;

#pragma omp for
        for (int i = 0; i < aliveCells.size(); i++) {
            auto it = aliveCells.begin();
            std::advance(it, i);

            int liveCount = aliveCellNeighbors[*it];
            if (liveCount < 2 || liveCount > 3) {
                myToDie.push_back(*it);
            }
        }

#pragma omp for
        for (int i = 0; i < aliveCellNeighbors.size(); i++) {
            auto it = aliveCellNeighbors.begin();
            std::advance(it, i);

            if (aliveCells.find(it->first) != aliveCells.end()) // is this cell alive?
                continue; // if so skip because we already updated aliveCells

            if (aliveCellNeighbors[it->first] == 3) {
                myToLive.push_back(it->first);
            }
        }

#pragma omp critical
        {
            toDie.insert(toDie.end(), myToDie.begin(), myToDie.end());
            toLive.insert(toLive.end(), myToLive.begin(), myToLive.end());
        }
    }

    for (const Cell& deadCell : toDie) {
        setDead(deadCell);
    }

    for (const Cell& liveCell : toLive) {
        setAlive(liveCell);
    }
}

I noticed that it performs worse than the single threaded update() and seems like it's getting slower over time.

I think I might be doing something wrong by having two uses of omp for? I am new to OpenMP so I am still figuring out how to use it.

Why am I getting worse performance with my multithreaded implementation?

EDIT: Full source here: https://github.com/k-vekos/GameOfLife/tree/hashing?files=1

Answer 1

Why am I getting worse performance with my multithreaded implementation?

Classic question :)

You loop through only the alive cells. That's actually pretty interesting. A naive implementation of Conway's Game of Life would look at every cell. Your version optimizes for a fewer number of alive than dead cells, which I think is common later in the game. I can't tell from your excerpt, but I assume it trades off by possibly doing redundant work when the ratio of alive to dead cells is higher.

A caveat of omp parallel is that there's no guarantee that the threads won't be created/destroyed during entry/exit of the parallel section. It's implementation dependent. I can't seem to find any information on MSVC's implementation. If anyone knows, please weight in.

So that means that your threads could be created/destroyed every update loop, which is heavy overhead. For this to be worth it, the amount of work should be orders of magnitude more expensive than the overhead.

You can profile/measure the code to determine overhead and work time. It should also help you see where the real bottlenecks are.

Visual Studio has a profiler with a nice GUI. You need to compile your code with release optimizations but also include the debug symbols (those are excluded in the default release configuration). I haven't looked into how to set this up manually because I usually use CMake and it sets up a RelWithDebInfo configuration automatically.

Use high_resolution_clock to time sections that are hard to measure with the profiler.

If you can use C++17, it has a standard parallel for_each (the ExecutionPolicy overload). Most of the algorithmy standards functions do. https://en.cppreference.com/w/cpp/algorithm/for_each. They're so new that I barely know anything about them (they might also have the same issues as OpenMP).

seems like it's getting slower over time.

Could it be that you're not cleaning up one of your vectors?

Answer 2

First off, if you want any kind of performance, you must do as little work as possible in a critical section. I'd start by changing the following:

std::vector<Cell> toDie;
std::vector<Cell> toLive;

to

std::vector<std::vector<Cell>> toDie;
std::vector<std::vector<Cell>> toLive;

Then, in your critical section, you can just do:

toDie.push_back(std::move(myToDie));
toLive.push_back(std::move(myToLive));

Arguably, a vector of vector isn't cute, but this will prevent deep-copying inside the CS which is unnecessary time consumption.

[Update] IMHO there's no point in using multithreading if you are using non-contiguous data structures, at least not in that way. The fact is you'll spend most of your time waiting on cache misses because that's what associative containers do, and little doing the actual work. I don't know how this game works. It feels like if I had to do something with numerous updates and render, I would have the updates done as quickly as possible on the 'main' thread', and I would have another (detached) thread for the renderer. You could then just give the renderer the results after every "update", and perform another update while it's rendering.

Also, I'm definitely not an expert in hashing, but hash<int>()(k.x * 3 + k.y * 5) seems like a high-collision hashing. You can certainly try something else like what's proposed here