Re^5: Threads From Hell #3: Missing Some Basic Prerequisites

[BrowserUk]

I think $Q->enqueue( $Y, @colors ); is a typo - it should be $Q->enqueue( $y, @colors );.

Indeed. A typo. (Talking of which: for my $y ( 0 .. $width - 1 ) {, y is normally height not width; ditto for x/height.)

In your while loop i ran into some undefinedness which i tried to fix.

A few more details on that?

I was quite surprised that $image->setpixel( $_, $y, $colors $_ ) for 0 .. $#colors; works. Learning never stops.

You can take that a couple of stages further:

1. At least for the full Mandelbrot set, large segments (stretches of adjacent pixels) of each X-line are the same color.

   First, to further save on inter-thread comms traffic, you can coalesce those runs of same colored pixels.

   After you've populate @colors, you compress them to pairs of color/run length like so:

           my( $c, @lineSegs ) = 1;
           for my $x ( 0 .. $X - 2 ) {
               ++$c, next if $colors[ $x ] == $colors[ $x + 1 ];
               push @lineSegs, [ $c, $colors[ $x ] ];
               $c = 1;
           }
           push @lineSegs, [ $c, $colors[ - 1] ];
           $Qout->enqueue( [ $y, \@lineSegs ] );
   

   Then when it comes to draw them, instead of drawing a bunch of same colored pixels with individual calls to setpixel(), you draw lines:

       while( my $line = $Qresults->dequeue ) {
           my( $y, $l ) = @{ $line };
           for( @$l ) {
               my( $count, $color ) = @{ $_ };
               $i->line( $x, $y, $x + $count, $y, $color );
               $x += $count;
           }
   

   Drawing a series of short line segments rather than individual pixels reduces the number of Perl-to-C graphics library calls; and has each call do more work.

2. The (full) Mandelbrot set is symmetrical about the horizontal (or vertical if you draw it that way) center line.

   So rather than calculating the whole line, you can calculate only half of the line; compress it to line segments, and queue that to the drawing thread.

   On receipt, you the get the second half of the line by duplicating and reversing the first half:

           ## calculate the Mandelbrot values for half the line
           my @colors;
           for my $x ( 0 .. $halfX - 1  ) {
               push( @colors, rgb2n( (0)x3 ) ), next if clip( $x, $y );
               my $m = mandelbrot( ( $x - $halfX ) / $halfX, ( $y - $half
   +Y ) / $halfY );
               my $c = mapColors( $m );
               push @colors, $m == 0 ? 0 : $c;
           }
           ## compress pixels to count/color pairs (line segments)
           my( $c, @lineSegs ) = 1;
           for my $x ( 0 .. $halfX - 2 ) {
               ++$c, next if $colors[ $x ] == $colors[ $x + 1 ];
               push @lineSegs, [ $c, $colors[ $x ] ];
               $c = 1;
           }
           push @lineSegs, [ $c, $colors[ - 1] ];
           
           ## Queue back the line segments for half the line.
           $Qout->enqueue( [ $y, \@lineSegs ] );
   

   Then in the drawing thread:

       while( my $line = $Qresults->dequeue ) {
           my( $y, $l ) = @{ $line };
           my $x = 0;
           ## for all the line segments, and those same segments ( again 
   +in reverse order )
           for( @$l, reverse @$l ) {
               ## extract the count and the color
               my( $count, $color ) = @{ $_ };
               ## draw the line segment
               $i->line( $x, $y, $x + $count, $y, $color );
               ## accumulating your current x position as you go.
               $x += $count;
           }
       }
   

Queue Size 640.627 MByte

That's a big queue; and a performance killer. You'd be better using a self-limiting queue (like this one I posted a couple of years ago), to prevent the queue growing so big. Of course, that won't work unless you actually have separate threads feeding the queue and reading from it. If you try it, start with a queue size of say 1000, and try varying it up and down to see how it affects performance. Often, you only need 100 or so for best performance.

[karlgoethebier]

"A few more details on that?"

My pleasure:

use Thread::Queue;
use strict;
use warnings;
use feature qw(say);

my $width  = 10;
my $height = 10;
my $queue = Thread::Queue->new();

for my $y ( 0 .. $width - 1 ) {
    my @colors;
    for my $x ( 0 .. $height - 1 ) {
        push @colors, mandelbrot();
    }
    $queue->enqueue( [ $y, @colors ] );
}

$queue->end;

while ( my ( $y, @colors ) = @{ $queue->dequeue } ) {
    say qq($_, $y, $colors[$_])for  0 .. $#colors;
}

# this is still a fake!
sub mandelbrot {
    int rand 20;
}

__END__

\monks>undef.pl
0, 0, 8
1, 0, 4
2, 0, 7
...
7, 9, 10
8, 9, 3
9, 9, 0
Can't use an undefined value as an ARRAY reference at C:\Dokumente und
+ Einstellungen\karl\Desktop\monks\undef.pl line 20.

This doesn't complain:

while ( my $item = $queue->dequeue ) {
    my ( $y, @colors ) = @$item;
    say qq($_, $y, $colors[$_]) for 0 .. $#colors;
}

Best regards, Karl

[BrowserUk]

Okay. So when there's nothing left in the queue, my composite dequeue & deref tries to deref before detecting there's nothing to deref, but the fix is obvious.

The vagaries of typing ideas directly into the browser. Sorry.

[karlgoethebier]

...Talking of which...

With some delay...my obligatory D'oh!

Sorry and regards, Karl

[karlgoethebier]

 
## draw the line segment
$i->line( $x, $y, $x + $count, $y, $color );
## accumulating your current x position as you go.

Very cool, but doesn't this close the door to images with colour gradients?

Ok, the beautiful example zooms also, but this is another problem.

Edit: Corrected bad copy&paste.

Regards, Karl

[BrowserUk]

but doesn't this close the door to images with colour gradients?

First, and take this with a pinch of salt but I concluded a long time ago that interpolating gradients between calculated points on the Mandelbrot Set was cheating, and unnecessary.

(To me) The interesting bits of the MS, are the details that are too fine to interpolate -- ie. the adjacent individual pixels all have different values -- not the interstigal bits which tend to fade away to blandness at higher rep counts and resolutions. As such interpolating those bland spaces detracts from the good bits, and is really only used to distract from the low resolution of the pretty bits.

That said, interpolation does make for some very pretty pictures without having to wait hours for the render.

And good news: no, the run length encoding scheme doesn't mean you have to give it up. In fact, it has done half the work you would need to do anyway.

Given the run sequence (count/color): [10,100], [10,200], [10,300] then you want to get to a pixel color sequence something like:

100, 107, 113, 120, 127, 133, 140, 147, 153, 160, 167, 173, 180, 187, 
+193, 200, 207, 213, 200, 227, 233, 240, 247, 253, 260, 267, 273, 280,
+ 287, 293, 300

Note: Those are really pre color mapping iteration counts rather than colors.

Of course, if your graphics library doesn't provide an interpolate line draw, then you're back to drawing individual pixels; but the run-length encoding tells you how many pixels and between what range of "colors" you need to interpolate.

And if your GL does do interpolated line drawing then you have the information to set the color end points and lines lengths to hand.