Parallel Sieve Of Eratosthenes

[Lawrence D'Oliveiro]

with Ada.Text_IO;
use Ada;
procedure parasieve1 is

task type child is

entry next_int(i : integer);

end child;

subtype offspring is child;
-- need another name because "child" within child refers to
-- current task, not to the type

task body child is

my_prime : integer;
subchild : access offspring;

begin
accept next_int(i : integer) do
my_prime := i;
Text_IO.Put_line(integer'image(my_prime));
end next_int;
subchild := new offspring;
loop
accept next_int(i : integer) do
if i mod my_prime /= 0 then
subchild.next_int(i);
end if;
end next_int;
end loop;
end child;

first_child : child;
i : integer;

begin -- parasieve1
i := 1;
loop
i := i + 1;
first_child.next_int(i);
end loop;
end parasieve1;

[Lawrence D'Oliveiro]

This version uses a protected type to pass the stream of integers from
one task to the next. It seems to be much faster.
----
with Ada.Text_IO;
use Ada;
procedure parasieve2 is

protected type int_buffer is

entry put(i : in integer);
entry get(i : out integer);

private
last_i : integer;
got_i : boolean := false;
end int_buffer;

protected body int_buffer is

entry put(i : in integer) when not got_i is
begin
last_i := i;
got_i := true;
end put;

entry get(i : out integer) when got_i is
begin
i := last_i;
got_i := false;
end get;

end int_buffer;

type int_buffer_ptr is access int_buffer;

task type child(from_parent : int_buffer_ptr) is
end child;

subtype offspring is child;
-- need another name because "child" within child refers to
-- current task, not to the type

task body child is

my_prime, i : integer;
subchild : access offspring;
to_child : int_buffer_ptr;

begin
from_parent.get(my_prime);
Text_IO.Put_line(integer'image(my_prime));
to_child := new int_buffer;
subchild := new offspring(to_child);
loop
from_parent.get(i);
if i mod my_prime /= 0 then
to_child.put(i);
end if;
end loop;
end child;

to_first_child : int_buffer_ptr;
first_child : access child;
i : integer;

begin -- parasieve2
i := 1;
to_first_child := new int_buffer;
first_child := new child(to_first_child);
loop
i := i + 1;
to_first_child.put(i);
end loop;
end parasieve2;

[J-P. Rosen]

Post by Lawrence D'Oliveiro
This version uses a protected type to pass the stream of integers from
one task to the next. It seems to be much faster.

That's because in your first version, you call the child within the
accept statement. Therefore you wait for the value to go to the end of
the pipeline before processing the next value.
Try to copy the number to a variable, and call the child after the end
of the accept. This will give you 100% CPU time usage.

BTW, you don't need an access type. Just use a declare block to create
the child after the first accept.

[Lawrence D'Oliveiro]

Post by J-P. Rosen
That's because in your first version, you call the child within the
accept statement. Therefore you wait for the value to go to the end of
the pipeline before processing the next value.
Try to copy the number to a variable, and call the child after the end
of the accept. This will give you 100% CPU time usage.
BTW, you don't need an access type. Just use a declare block to create
the child after the first accept.

Thanks for the comments, how about this slight rework of the first
version. It does seem faster, but I’m not sure it’s as fast as the second
version.
----
with Ada.Text_IO;
use Ada;
procedure parasieve1b is

task type child is

entry next_int(i : integer);

end child;

subtype offspring is child;
-- need another name because "child" within child refers to
-- current task, not to the type

task body child is

my_prime : integer;

begin
accept next_int(i : integer) do
my_prime := i;
Text_IO.Put_line(integer'image(my_prime));
end next_int;
declare
subchild : offspring;
ii : integer;
begin
loop
accept next_int(i : integer) do
if i mod my_prime /= 0 then
ii := i;
else
ii := 0;
end if;
end next_int;
if ii /= 0 then
subchild.next_int(ii);
end if;
end loop;
end;
end child;

first_child : child;
i : integer;

begin -- parasieve1b
i := 1;
loop
i := i + 1;
first_child.next_int(i);
end loop;
end parasieve1b;

[J-P. Rosen]

Post by Lawrence D'Oliveiro

Post by J-P. Rosen
That's because in your first version, you call the child within the
accept statement. Therefore you wait for the value to go to the end of
the pipeline before processing the next value.
Try to copy the number to a variable, and call the child after the end
of the accept. This will give you 100% CPU time usage.
BTW, you don't need an access type. Just use a declare block to create
the child after the first accept.

Thanks for the comments, how about this slight rework of the first
version. It does seem faster, but I’m not sure it’s as fast as the second
version.

That's better, but as a general principle, you should move as much as
you can out of the rendezvous (minimize critical sequences). For example:

accept next_int(i : integer) do
my_prime := i;
end next_int;
Text_IO.Put_line(integer'image(my_prime)); -- moved
declare
subchild : offspring;
ii : integer;
begin
loop
accept next_int(i : integer) do
ii := i;
end next_int;
if ii mod my_prime /= 0 then --moved
subchild.next_int(ii);
end if;
end loop;

[Lawrence D'Oliveiro]

Post by J-P. Rosen
That's better, but as a general principle, you should move as much as
you can out of the rendezvous (minimize critical sequences).

Still, it looks like protected types are the way to go.