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

[BrowserUk]

The snippet in my OP calculates the coordinates for the rows.

For $width = 4; $height = 4; $qsize = 4; the output is:

01 [
02   [[0, 0], [0, 1], [0, 2], [0, 3]],
03   [[1, 0], [1, 1], [1, 2], [1, 3]],
04   [[2, 0], [2, 1], [2, 2], [2, 3]],
05   [[3, 0], [3, 1], [3, 2], [3, 3]],
06 ]
<code>

@queue should perhaps better been named @rows. Then:
<code>
01 my $queue = Thread::Queue->new();
02 $queue->enqueue(\@rows);
03 my @threads = map { threads->create( \&process, $queue ); } 1 .. 4;
04 ...

So, you're generating an AoAoA of pixel coorinates and enqueueing it. Let's compare doing that with just setting the pixels in the nested loops you use to generate the AoAoAs:

<Reveal this spoiler or all in this thread>

The result is:

c:\test>junk999
Filling a 1000x1000 pixel image 1-pixel at a time took: 6.491771936s
Populating 1000x1000 AoAoAs and tranferring to another thread took: 30
+.876082897s

It takes five times longer to build the AoAoAs and pass it to another thread for drawing, than it does to do that drawing in the main thread!

But what is the purpose of generating the coordinates and wrapping them up in the AoAoAs, only for the other thread to have to use nested loops to access them, when you could just pass 1000x1000 and have the other thread do the iteration itself.

And what is the point of passing the entire data structure as a single entity? Only one thread will be able to receive it; so there's not even the possibility of using concurrency.

Perhaps your intention is to do: $Q->enqueue( @cols ); (Ie. enqueue the contents of the array, not a reference to it.)

That way, the row arrays would be pushed onto the queue as separate entities; which means that different threads could dequeue individual rows and operate upon them concurrently. Assuming a thread-safe graphics library.

But even then what is the point in generating zillions of iddy-biddy arrays containing pairs of coordinates; when you could (say) push just the information required to construct them in the target thread:

# main thread
my( $X, $Y ) = ...;

for my $y ( 0 .. $Y-1 ) {
    $Q->enqueue( [ $X, $y ] );     
}

## drawing thread
while( my( $x, $y ) = @{ $Q->dequeue } ) {
    $image->setpixel( $_, $y, ... ) for 0 .. $X-1;
}

You need the same loop code in the thread as you would to unpack the AoAs; but you only need to transfer a 1000th or less of the information between threads.

Of course, the Devil is in the detail. Those ... above represent the color; and I assume that although you haven't shown it, the intent is to calculate the color for your Mandelbrot pixels in the main thread and farm off the drawing to the threads. And your (unshown) intention is to actually enqueue [ x, y, color ], [ x, y, color ] .... But that still doesn't make sense.

Why transfer the same y-coordinate a thousand times (or however wide your image is) for each row?

And why transfer a thousand X-coordinates when they can be inferred.

Ie. Do this:

## main
for my $y ( 0 .. $Y ) {
    my @colors;
    for my $x ( 0 .. $X ) {
        push @colors, Mandelbrot( $x, $y );
    }
    $Q->enqueue( [ $Y, @colors ] );
}

### thread

while( my( $y, @colors ) = @{ $Q->dequeue } ) {
    $image->setpixel( $_, $y, $colors[ $_ ] ) for 0 .. $#colors;
}

The Y-coordinate once, and a list of colors for the pixels is transfered, and the X-coordinates are inferred. (The problem of thread-safety remains.)

[karlgoethebier]

This goes to the bone. I need a break for reflection.

Update:

A dialogue is an old but established didactic device:

Socrates: A man is a good adviser about anything, not because he has riches, but because he has knowledge?
Alcibiades: Assuredly.

Thank you very much for this excellent advice and best regards, Karl

[karlgoethebier]

"Φοβοῦ τοὺς Δαναοὺς καὶ δῶρα φέροντας."

I tried to make your idea my own, simplifying it as much i could:

#!/usr/bin/env perl

use strict;
use warnings;
use Thread::Queue;
use Data::Dump;

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 ( defined( my $item = $queue->dequeue ) ) {
    dd $item;
}

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

__END__

karls-mac-mini:monks karl$ ./queue2.pl 
[0, 1, 16, 19, 13, 18, 18, 7, 10, 8, 7]
[1, 2, 10, 0, 3, 2, 2, 2, 8, 3, 10]
[2, 12, 5, 10, 5, 0, 14, 10, 10, 18, 5]
[3, 13, 2, 11, 4, 16, 9, 19, 11, 5, 0]
[4, 14, 3, 7, 18, 0, 17, 17, 16, 0, 8]
[5, 4, 13, 3, 3, 10, 17, 13, 16, 11, 17]
[6, 5, 2, 0, 17, 10, 1, 13, 10, 12, 3]
[7, 18, 8, 1, 12, 13, 16, 0, 11, 14, 17]
[8, 5, 10, 5, 19, 6, 17, 3, 10, 18, 16]
[9, 1, 15, 10, 17, 8, 11, 18, 2, 18, 6]

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

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

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

Here is how i create my image and my palette:

use Imager;

open( URANDOM, "</dev/urandom" ) # NTSC ;-);
read( URANDOM, $_, 4 );
close URANDOM;
srand( unpack( "L", $_ ) );

my $image = Imager->new( xsize => $width, ysize => $height );
my $white = Imager::Color->new( 255, 255, 255 );
my $black = Imager::Color->new( 0,   0,   0 );
my @palette;

for ( 1 .. 20 ) {
    my ( $r, $g, $b ) = map { int rand 255 } 1 .. 3;
    push @palette, Imager::Color->new( $r, $g, $b );
}

# dd \@palette;

Well, still some omissions but perhaps step-by-step i get the idea.

Update:

...
use Devel::Size qw( total_size );
use Time::HiRes qw ( time );
...
$width  = 1280*4; 
$height = 1024*4;
...
__END__

Image Size 20 MP
Queue Size 640.627 MByte
Took 8.150 seconds

Best regards, Karl

[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

[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