Multi-threaded Mandelbrot set generator slower than single thread

Question

I am new to parallel programming. I have been playing around with multi-threading and for some reason, multi-threading the Mandelbrot set is slower than running a single thread. I have been trying to figure it out for hours. Are there any improvements that you could suggest or perhaps something is wrong with some parts?

Mandelbrot.cpp:

// Write the image to a TGA file with the given name.
void Mandelbrot::write_tga(const char* filename)
{

    ofstream outfile(filename, ofstream::binary);

    uint8_t header[18] = {
        0, // no image ID
        0, // no colour map
        2, // uncompressed 24-bit image
        0, 0, 0, 0, 0, // empty colour map specification
        0, 0, // X origin
        0, 0, // Y origin
        WIDTH & 0xFF, (WIDTH >> 8) & 0xFF, // width
        HEIGHT & 0xFF, (HEIGHT >> 8) & 0xFF, // height
        24, // bits per pixel
        0, // image descriptor
    };
    outfile.write((const char*)header, 18);

    for (int y = 0; y < HEIGHT; ++y)
    {
        for (int x = 0; x < WIDTH; ++x)
        {
            uint8_t pixel[3] = {
                image[y][x] & 0xFF, // blue channel
                (image[y][x] >> 8) & 0xFF, // green channel
                (image[y][x] >> 16) & 0xFF, // red channel
            };
            outfile.write((const char*)pixel, 3);
        }
    }

    outfile.close();
    if (!outfile)
    {
        // An error has occurred at some point since we opened the file.
        cout << "Error writing to " << filename << endl;
        exit(1);
    }
}


void Mandelbrot::printProgress() {
    // *** CONSUMER *** //

    while (progressPercentage <= 100.00)
    {
        //std::cout << "\nAquiring lock in PrintProgress\n";
        unique_lock<mutex> lock(progressMutex);

        while (!progressReady)
        {
            progressConditionVariable.wait(lock);
        }
        //std::cout << "\nlock aquired\n";
        

        progressReady = false;

        cout << progressPercentage << endl;
        
    }
    
}

void Mandelbrot::calcProgress() {
    // *** PRODUCER *** // 

    //shared progress variable
    //protect with a mutex
    //print_func() waits to be signaled by worker threads and outputs
    //condition variables

    unique_lock<mutex> lock(progressMutex);
    progressCount += 1;

    //double ThreadNum = numOfThreads;
    progressPercentage = (double)progressCount / (double)numOfThreads;
    progressReady = true;
    lock.unlock();

    // progress condition variable
    progressConditionVariable.notify_one();

}

// Render the Mandelbrot set into the image array.
// The parameters specify the region on the complex plane to plot.
void Mandelbrot::compute_mandelbrot(double left, double right, double top, double bottom, int startNum, int endNum, int y)
{

    // The number of times to iterate before we assume that a point isn't in the
    // Mandelbrot set.
    // (You may need to turn this up if you zoom further into the set.)
    const int MAX_ITERATIONS = 500;

    for (int x = 0; x < WIDTH ; ++x)
    {

        // Work out the point in the complex plane that
        // corresponds to this pixel in the output image.
        complex<double> c(left + (x * (right - left) / WIDTH),
            top + (y * (bottom - top) / HEIGHT));

        // Start off z at (0, 0).
        complex<double> z(0.0, 0.0);

        // Iterate z = z^2 + c until z moves more than 2 units
        // away from (0, 0), or we've iterated too many times.
        int iterations = 0;
        while (abs(z) < 2.0 && iterations < MAX_ITERATIONS)
        {
            z = (z * z) + c;
            ++iterations;
        }

        if (iterations == MAX_ITERATIONS)
        {
            // z didn't escape from the circle.
            // This point is in the Mandelbrot set.
            
            image[y][x] = 0xFCC2E6; // darker pink
        }
        else
        {
            // z escaped within less than MAX_ITERATIONS
            // iterations. This point isn't in the set.
            //image[y][x] = 0xFFEAF7; // pink


            int i = iterations;
            if (i < 5)
                image[y][x] = 0xFFEAF7;
            else if (i < 10)
                image[y][x] = 0xF9BCDD;
            else if (i < 40)
                image[y][x] = 0xD5A4CF;

        }

    image[endNum - 1][x] = 0xFF0000;

    }
    // call progress function 
    calcProgress();
}

Mandelbrot.h:

#pragma once

#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <complex>
#include <fstream>
#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <atomic>

#include "Mandelbrot.h"

const int WIDTH = 1020;  //ori 1920 
const int HEIGHT = 600; // ori 1200

// Import things we need from the standard library
using std::chrono::duration_cast;
using std::chrono::milliseconds;
using std::complex;
using std::cout;
using std::endl;
using std::ofstream;
using std::thread;
using std::mutex;
using std::condition_variable;
using std::unique_lock;


class Mandelbrot
{
private:

public:
    // initialise variables 
    mutex progressMutex;
    condition_variable progressConditionVariable;
    bool progressReady = false;
    int progressCount = 0;
    int numOfThreads = 10;
    double progressPercentage = 0;

    // The image data.
    // The size of the image to generate.
    uint32_t image[HEIGHT][WIDTH];


    //functions
    void write_tga(const char* filename);
    void printProgress();
    void calcProgress();
    void compute_mandelbrot(double left, double right, double top, double bottom, int startNum, int endNum, int y);

};

source.cpp:

#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <complex>
#include <fstream>
#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <atomic>

// Import things we need from the standard library
using std::chrono::duration_cast;
using std::chrono::milliseconds;
using std::complex;
using std::cout;
using std::endl;
using std::ofstream;
using std::thread;
using std::mutex;
using std::condition_variable;
using std::unique_lock;


// Define the alias "the_clock" for the clock type we're going to use.
typedef std::chrono::steady_clock the_clock;


int main(int argc, char* argv[])
{
    Mandelbrot* mandelbrot = new Mandelbrot;


    // This shows the whole set.
    int lastNum = 0;
    int calcHeight = HEIGHT / mandelbrot->numOfThreads;
    int End = calcHeight;

    std::vector<thread> threads;
    

    //std::thread Consume(mandelbrot->printProgress); //previous
    std::thread Consumer([&] {
        //lambda function

        while (mandelbrot->progressPercentage <= 100.00) {
            mandelbrot->printProgress();
        }

    });

    // Start timing
    the_clock::time_point start = the_clock::now();

    for (int i = 0; i < mandelbrot->numOfThreads; i++)
    {
        //std::thread newThread(mandelbrot->compute_mandelbrot(-2.0, 1.0, 1.125, -1.125, lastNum, End)); //previous
        std::thread newThread([&] {
            //lambda function

            for (int y = lastNum; y < End; ++y)
            {
                //std::cout << "Before compute\n";
                mandelbrot->compute_mandelbrot(-2.0, 1.0, 1.125, -1.125, lastNum, End, y);
            }
            lastNum = End;
            End = End + calcHeight;
        });

        //threads.push_back(thread(compute_mandelbrot, -2.0, 1.0, 1.125, -1.125, lastNum, End));
        threads.push_back(std::move(newThread));
    
    }

    // Wait for threads to finish.
    for (auto &t : threads) {
        t.join();
    }

    // Stop timing
    the_clock::time_point end = the_clock::now();


    Consumer.join();


    // Compute the difference between the two times in milliseconds
    auto time_taken = duration_cast<milliseconds>(end - start).count();
    cout << "Computing the Mandelbrot set took " << time_taken << " ms." << endl;

    mandelbrot->write_tga("output.tga");

    return 0;
}

Answer 1

Distributing the work among threads

D. Jurcau already mentioned that you are not distributing your work correctly. It's even worse than his terse answer hints at. One issue is that inside the lambda function, which is run in its own thread, you are modifying lastNum and End, but those variables are shared among all threads. Because you are not using any kind of locking, there is just no telling what values these variables will hold, as multiple threads can update them at the same time.

You should figure out the range of y values a thread should work on outside that thread, and pass that range to the lambda by value, like so:

for (int i = 0; i < mandelbrot->numOfThreads; ++i)
{
    threads.emplace_back([&mandelbrot, lastNum, End] {
        for (int y = lastNum; y < End; ++y)
        {
            mandelbrow->compute_mandelbrot(..., y);
        }
    });

    lastNum = End;
    End += calcHeight;
}

How to use threads effectively

Your way of distributing work over threads is very crude. Consider that some threads will finish more quickly than others; for example the regions that contain little to no black will be much faster to calculate than those which have a lot of black. Furthermore, why would 10 threads be the optimal number? This depends heavily on the number of CPU cores available. Ideally, you would split up the work into many small tasks (say, one line per task), and create a pool of worker threads corresponding to the number of CPU cores, and let each of those workers pick tasks at their own pace until all tasks have been done.

There are many implementations of thread pools here on Code Review that you can draw inspiration from.

You can use std::thread::hardware_concurrency() to find the number of threads that the hardware can run concurrently. For CPU-bound tasks, that's the appropriate number of threads to spawn.

Be sure to handle edge cases correctly

What if HEIGHT is not evenly divisible by mandelbrot->numOfThreads? That would cause the last few lines of the image to not be calculated. Make sure you handle edge cases correctly.

Avoid unnecessary threads

Your progress counter is using its own thread, and needs a mutex and a condition variable to coordinate with other threads when to print an update. For your program, this is overkill. Instead, you could just use a single mutex, and have compute_mandelbrot() itself print the progress right before it returns:

{
    lock_guard lock(progressMutex);
    progressCount++;
    double progressPercentage = 100.0 * progressCount / numOfThreads;
    cout << progressPercentage << '\n';
}

Alternatively, have the main thread call mandelbrot->printProgress() directly after starting all the worker threads.

Refactoring the code

The class Mandelbrot has a lot of functions, but while it clearly is designed to calculate the image using multiple threads, there is no member function that will manage those threads, that's left up to main(). This is a weird distribution of responsibilities. This might be a good time to rethink the structure of your code and to refactor it. Try to give classes only one responsibility each if possible. For example, have an Image class that just deals with images, nothing else. You might want to make a ThreadPool class to manage the threads, and even create a Timer class to do the time measurements.

Also note that not everything outside of main() needs to be in a class. Consider that if compute_mandelbrot() didn't have the responsibility of updating the progress counter, the only thing it needs apart from the parameters it already got is a reference to the image to store the results in. So it could just be a stand-alone function.

A good way to start refactoring the code is to try to imagine main() as concise as possible, for example you might want it to look like this:

int main()
{
    Image image(WIDTH, HEIGHT);
    Timer timer;

    {    
        ThreadPool threadpool;

        for (int y = 0; y < HEIGHT; y++) {
             threadpool.emplace_back([&image, =] {
                compute_mandelbrot(..., y, image);
             }
        }
    }

    cout << "Time taken: " << timer.get_elapsed() << '\n';
    image.write_tga("output.tga");
}

Then implement all of the required classes and functions. Again imagine each class and function you now have to write as something concise with few responsibilities, and add even more classes and functions when necessary, and so on.

Answer 2

You don't distribute work among your threads correctly. According to your code, only by the time a thread has completed its work is the start point for the next thread(s) updated.