C++ plotting Mandlebrot set, bad performance

Question

I'm not sure if there is an actual performance increase to achieve, or if my computer is just old and slow, but I'll ask anyway.

So I've tried making a program to plot the Mandelbrot set using the cairo library.

The loop that draws the pixels looks as follows:

vector<point_t*>::iterator it;
for(unsigned int i = 0; i < iterations; i++){
  it = points->begin();
  //cout << points->size() << endl;
  double r,g,b;
  r = (double)i+1 / (double)iterations;
  g = 0;
  b = 0;
  while(it != points->end()){
    point_t *p = *it;
    p->Z = (p->Z * p->Z) + p->C;
    if(abs(p->Z) > 2.0){
      cairo_set_source_rgba(cr, r, g, b, 1);
      cairo_rectangle (cr, p->x, p->y, 1, 1);
      cairo_fill (cr);
      it = points->erase(it);
    } else {
      it++;
    }
  }
}

The idea is to color all points that just escaped the set, and then remove them from list to avoid evaluating them again.

It does render the set correctly, but it seems that the rendering takes a lot longer than needed.

Can someone spot any performance issues with the loop? or is it as good as it gets?

Thanks in advance :)

SOLUTION

Very nice answers, thanks :) - I ended up with a kind of hybrid of the answers. Thinking of what was suggested, i realized that calculating each point, putting them in a vector and then extract them was a huge waste CPU time and memory. So instead, the program now just calculate the Z value of each point witout even using the point_t or vector. It now runs A LOT faster!

Answer 1

Edit: I think the suggestion in the answer of kuroi neko is also a very good idea if you do not care about "incremental" computation, but have a fixed number of iterations.

1. You should use vector<point_t> instead of vector<point_t*>.

   A vector<point_t*> is a list of pointers to point_t. Each point is stored at some random location in the memory. If you iterate over the points, the pattern in which memory is accessed looks completely random. You will get a lot of cache misses.

   On the opposite vector<point_t> uses continuous memory to store the points. Thus the next point is stored directly after the current point. This allows efficient caching.

2. You should not call erase(it); in your inner loop.

   Each call to erase has to move all elements after the one you remove. This has O(n) runtime. For example, you could add a flag to point_t to indicate that it should not be processed any longer. It may be even faster to remove all the "inactive" points after each iteration.

3. It is probably not a good idea to draw individual pixels using cairo_rectangle. I would suggest you create an image and store the color for each pixel. Then draw the whole image with one draw call.

Your code could look like this:

for(unsigned int i = 0; i < iterations; i++){
  double r,g,b;
  r = (double)i+1 / (double)iterations;
  g = 0;
  b = 0;
  for(vector<point_t>::iterator it=points->begin(); it!=points->end(); ++it) {
    point_t& p = *it;
    if(!p.active) {
      continue;
    }
    p.Z = (p.Z * p.Z) + p.C;
    if(abs(p.Z) > 2.0) {
      cairo_set_source_rgba(cr, r, g, b, 1);
      cairo_rectangle (cr, p.x, p.y, 1, 1);
      cairo_fill (cr);
      p.active = false;
    }
  }
  // perhaps remove all points where p.active = false
}

If you can not change point_t, you can use an additional vector<char> to store if a point has become "inactive".

Answer 2

The Z_n divergence computation is what makes the algorithm slow (depending on the area you're working on, of course). In comparison, pixel drawing is mere background noise.

Your loop is flawed because it makes the Z_n computation slow.

The way to go is to compute divergence for each point in a tight, optimized loop, and then take care of the display.

Besides, it's useless and wasteful to store Z permanently.
You just need C as an input and the number of iterations as an output.

Assuming your points array only holds C values (basically you don't need all this vector crap, but it won't hurt performances either), you could do something like that :

for(vector<point_t>::iterator it=points->begin(); it!=points->end(); ++it)
{
    point_t Z = 0;
    point_t C = *it;
    for(unsigned int i = 0; i < iterations; i++) // <-- this is the CPU burner
    {
        Z = Z * Z + C;
        if(abs(Z) > 2.0) break;
    }
    cairo_set_source_rgba(cr, (double)i+1 / (double)iterations, g, b, 1);
    cairo_rectangle (cr, p->x, p->y, 1, 1);
    cairo_fill (cr);
}

Try to run this with and without the cairo thing and you should see no noticeable difference in execution time (unless you're looking at an empty spot of the set).

Now if you want to go faster, try to break down the Z = Z * Z + C computation in real and imaginary parts and optimize it. You could even use mmx or whatever to do parallel computations.

And of course the way to go to gain another significant speed factor is to parallelize your algorithm over the available CPU cores (i.e. split your display area is subsets and have different worker threads compute these parts in parallel).

This is not as obvious at it might seem, though, since each sub-picture will have a different computation time (black areas are very slow to compute while white areas are computed almost instantly).
One way to do it is to split the area is a large number of rectangles, and have all worker threads pick a random rectangle from a common pool until all rectangles have been processed.
This simple load balancing scheme that makes sure no CPU core will be left idle while its buddies are busy on other parts of the display.

Answer 3

The first step to optimizing performance is to find out what is slow. Your code mixes three tasks- iterating to calculate whether a point escapes, manipulating a vector of points to test, and plotting the point.

Separate these three operations and measure their contribution. You can optimise the escape calculation by parallelising it using simd operations. You can optimise the vector operations by not erasing from the vector if you want to remove it but adding it to another vector if you want to keep it ( since erase is O(N) and addition O(1) ) and improve locality by having a vector of points rather than pointers to points, and if the plotting is slow then use an off-screen bitmap and set points by manipulating the backing memory rather than using cairo functions.

(I was going to post this but @Werner Henze already made the same point in a comment, hence community wiki)