Deadlocked Multi-Threads

[Trebian]

I'm trying to optimize my program. So I decided to run 4 multi-threads to increase performance. However, the program runs barely any faster. I even tried to run a mutex, but that made difference. It's clear there is a deadlock problem with my threads, and that I'm not initiating them correctly. So I would greatly appreciate if I was told what changes needed to be made.

#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <complex>
#include <fstream>
#include <iostream>
#include <thread>
#include <vector>
#include <mutex>
#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::this_thread::sleep_for;
using std::vector;
using std::mutex;
using std::atomic_size_t;

class MyClass
{
	private:
		std::thread t1;
		std::thread t2;
		std::thread t3;
		std::thread t4;
		std::atomic_size_t counter = 0;
		int i;
		int left;
		int right;
		int top;
		int bottom;
		int y_start;
		int y_stop;
	public:
		MyClass();
		~MyClass();
};


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

// The size of the image to generate.
const int WIDTH = 1920;
const int HEIGHT = 1200;

//Splitting Image by an amount
const int thread = 4;



// 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;

int NUM_THREADS = 4; // number of chunks for parallel processing

// The image data.
// Each pixel is represented as 0xRRGGBB.
uint32_t image[HEIGHT][WIDTH];

int Colour1 = 0;
int Colour2 = 0;


// Write the image to a TGA file with the given name.
// Format specification: http://www.gamers.org/dEngine/quake3/TGA.txt
void 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);
	}
	
}
// Render the Mandelbrot set into the image array.
// The parameters specify the region on the complex plane to plot.
std::mutex m;
void compute_mandelbrot(double left, double right, double top, double bottom, unsigned y_start, unsigned y_stop)
{
	m.lock();
	for (int y = y_start; y < y_stop; ++y)
	{
		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] = Colour1; // black
			}
			else
			{
				// z escaped within less than MAX_ITERATIONS
				// iterations. This point isn't in the set.
				image[y][x] = Colour2; // white
			}
		}
	}
	m.unlock();
}



/*
// compute mandelbrot set on each chunk
MyClass::MyClass() :
	for (int i = 0; i < ::NUM_THREADS; ++i)
	{
		t[i](&compute_mandelbrot, left, right, top, bottom, y_start, y_stop));
	}
	{}
//cout << " [INFO] Threads created: " << ::NUM_THREADS << endl;

MyClass::~MyClass()
	for (int i = 0; i < ::NUM_THREADS; ++i)
	{
		t[i].join();
	}
*/


MyClass::MyClass():
	t1(&compute_mandelbrot, left, right, top, bottom, y_start, y_stop)
{}


MyClass::~MyClass()
{
	t1.join();
	t2.join();
	t3.join();
	t4.join();
}






int main(int argc, char* argv[])
{
	cout << "Please choose your first colour" << endl;
	cout << "Type 1 for red, 2 for blue, 3 for green:";

	std::cin >> Colour1;

	switch (Colour1)
	{
	case 1: Colour1 = 0xFF0000; //red
		break;       // exits switch
	case 2: Colour1 = 0x0000FF; //blue
		break;
	case 3: Colour1 = 0x00FF00; //green
		break;
	}

	cout << "Please choose second colour" << endl;
	cout << "Enter 1 for cyan, 2 for yellow and 3 for magenta:";

	std::cin >> Colour2;

	switch (Colour2)
	{
	case 1: Colour2 = 0x00FFFF; //cyan
		break;
	case 2: Colour2 = 0xFFFF00; //yellow
		break;
	case 3: Colour2 = 0xFF00FF; //magenta
		break;
	}

	MyClass myClass;
	
	//auto threads = std::make_unique<std::thread[]>(std::thread::hardware_concurrency());
	//std::thread t[number_of_threads];

	//std::thread t1(&compute_mandelbrot);
	//thread t2(compute_mandelbrot);

	//t1.join();
	//t2.join();
	
// compute mandelbrot set on each chunk
	
	
	//int i = 1;
	/*
	for (int i = 0; i < ::NUM_THREADS; ++i)
	{
		t[i] = thread(compute_mandelbrot);
	}

	cout << " [INFO] Threads created: " << ::NUM_THREADS << endl;

	for (int i = 0; i < ::NUM_THREADS; ++i)
	{
		t[i].join();
	}
	*/

	cout << "Calculating..." << endl;


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

	// This shows the whole set.
	for (int y = 0; y < HEIGHT; y += HEIGHT / thread)
	{
		compute_mandelbrot(-2.0, 1.0, 1.125, -1.125, y, y + HEIGHT / thread);

		// This zooms in on an interesting bit of detail.
		//compute_mandelbrot(-0.751085, -0.734975, 0.118378, 0.134488, y, y + HEIGHT / thread);

	}

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

	// 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;

	write_tga("output.tga");

	return 0;
}

[salem c]

Try this.

#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <complex>
#include <fstream>
#include <iostream>
#include <thread>
#include <vector>
#include <mutex>
#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::this_thread::sleep_for;
using std::vector;
using std::mutex;
using std::atomic_size_t;


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

// The size of the image to generate.
const int WIDTH = 1920;
const int HEIGHT = 1200;

// 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;

const int NUM_THREADS = 8; // number of chunks for parallel processing

// The image data.
// Each pixel is represented as 0xRRGGBB.
uint32_t image[HEIGHT][WIDTH];

int Colour1 = 0;
int Colour2 = 0;

class MyClass
{
  private:
    vector<thread> t;
  public:
    MyClass() = delete;
    MyClass(double left, double right, double top, double bottom, unsigned y_start, unsigned y_stop);
    ~MyClass();
};


// Write the image to a TGA file with the given name.
// Format specification: http://www.gamers.org/dEngine/quake3/TGA.txt
void 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);
  }

}
// Render the Mandelbrot set into the image array.
// The parameters specify the region on the complex plane to plot.
void compute_mandelbrot(double left, double right, double top, double bottom, unsigned y_start, unsigned y_stop)
{
  for (int y = y_start; y < y_stop; ++y)
  {
    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] = Colour1; // black
      }
      else
      {
        // z escaped within less than MAX_ITERATIONS
        // iterations. This point isn't in the set.
        image[y][x] = Colour2; // white
      }
    }
  }
}


// compute mandelbrot set on each chunk
MyClass::MyClass(double left, double right, double top, double bottom, unsigned y_start, unsigned y_stop)
{
  t.reserve(NUM_THREADS);
  unsigned step = (y_stop - y_start) / ::NUM_THREADS;
  for (int i = 0; i < ::NUM_THREADS; ++i)
  {
    t[i] = thread(compute_mandelbrot, left, right, top, bottom, y_start, y_start+step);
    y_start += step;
  }
}

MyClass::~MyClass()
{
  for (int i = 0; i < ::NUM_THREADS; ++i)
  {
    t[i].join();
  }
}

int main(int argc, char* argv[])
{
  cout << "Please choose your first colour" << endl;
  cout << "Type 1 for red, 2 for blue, 3 for green:";

  std::cin >> Colour1;

  switch (Colour1)
  {
  case 1: Colour1 = 0xFF0000; //red
    break;       // exits switch
  case 2: Colour1 = 0x0000FF; //blue
    break;
  case 3: Colour1 = 0x00FF00; //green
    break;
  }

  cout << "Please choose second colour" << endl;
  cout << "Enter 1 for cyan, 2 for yellow and 3 for magenta:";

  std::cin >> Colour2;

  switch (Colour2)
  {
  case 1: Colour2 = 0x00FFFF; //cyan
    break;
  case 2: Colour2 = 0xFFFF00; //yellow
    break;
  case 3: Colour2 = 0xFF00FF; //magenta
    break;
  }

  cout << "Calculating..." << endl;

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

  {
    MyClass myClass(-2.0, 1.0, 1.125, -1.125, 0, HEIGHT);
  }

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

  // 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;

  write_tga("output.tga");

  return 0;
}

[Trebian]

I get a vector subscript out of range error, which relates to line 1501.

[lastchance]

@Trebian,
Whose version of which code are you referring to?
There is no "line 1501" in anything here.

[Trebian]

It relates to this line of code in the vector library

    _NODISCARD _Ty& operator[](const size_type _Pos) noexcept /* strengthened */ {
        auto& _My_data = _Mypair._Myval2;
#if _CONTAINER_DEBUG_LEVEL > 0
        _STL_VERIFY(
            _Pos < static_cast<size_type>(_My_data._Mylast - _My_data._Myfirst), "vector subscript out of range");
#endif // _CONTAINER_DEBUG_LEVEL > 0

        return _My_data._Myfirst[_Pos];
    }

EDIT: I think it's to do with this line

  private:
    vector<thread> t;

[lastchance]

Trebian wrote:

I get a vector subscript out of range error, which relates to line 1501.

EDIT: I think it's to do with this line
private:
vector<thread> t;

Let's just say ... I don't understand your thought processes.

[salem c]

> EDIT: I think it's to do with this line
I think you need to post the code you tried.

I can break what I posted if I comment out
//t.reserve(NUM_THREADS);

So I'm guessing you borked your vector initialisation.


My results, with my code.

NUM_THREADS=2
Please choose your first colour
Type 1 for red, 2 for blue, 3 for green:1
Please choose second colour
Enter 1 for cyan, 2 for yellow and 3 for magenta:1
Calculating...
Computing the Mandelbrot set took 6069 ms.

NUM_THREADS=8
Please choose your first colour
Type 1 for red, 2 for blue, 3 for green:1
Please choose second colour
Enter 1 for cyan, 2 for yellow and 3 for magenta:1
Calculating...
Computing the Mandelbrot set took 3780 ms.