hI, I may have stumbled onto my first task elaboration order issue, hourra !
raised PROGRAM_ERROR : System.Tasking.Stages.Activate_Tasks: Some tasks have not been elaborated
pragma Ada_2022;
with Ada.Numerics.Discrete_Random, Ada.Text_IO;
procedure Main is
Limit: Positive := 10;
TaskResults : array (1..Limit) of Integer := [others => Integer'first];
package NewRan is new Ada.Numerics.Discrete_Random (Integer);
use NewRan, Ada.Text_IO;
G: Generator;
task type Filters (Stage: Positive) is
entry Sort (Take: in Integer);
end Filters;
TaskArray: array (1..Limit) of access Filters := (for I in 1..Limit => new Filters(I));
task body Filters is
Temp: Integer;
begin
accept Sort (Take: in Integer) do
TaskResults(Stage) := Take;
end Sort;
end Filters;
begin
null;
end Main;
… Don’t tell me the tasks start before their body appear. This can’t be so idiotic. How do you get around this ?
I used an access type because apparently “error: task type cannot be used as type mark within its own spec or body”, so you can’t have tasks referencing to another task of the same type, really ?
I think this is happening because you’re creating Filters (new Filters (I)) before the body is seen. Try moving that TaskArray to after the body of Filters.
GNAT usually gives you a warning when you do things like this, I suppose the warning is missing because it’s all in a subprogram. It is behaving correctly though.
So this is indeed an idiotic behavior (when would you ever want to run an non-elaborated object ?). I can not move the array definition, because this is the original code (don’t comment the algo itself, it would be no fun):
pragma Ada_2022;
with Ada.Numerics.Discrete_Random, Ada.Text_IO;
procedure Main is
Limit: constant Positive := 10;
package NewRan is new Ada.Numerics.Discrete_Random (Integer);
use NewRan, Ada.Text_IO;
G: Generator;
task type Filters (Stage: Positive) is
entry Sort (Take: in Integer);
end Filters;
TaskArray: array (1..Limit) of access Filters := (for I in 1..Limit => new Filters(I));
TaskResults : array (1..Limit) of Integer := [others => Integer'first];
task body Filters is
Temp: Integer;
begin
accept Sort (Take: in Integer) do
TaskResults(Stage) := Take;
end Sort;
for I in 1..Limit-Stage loop
accept Sort (Take: in Integer) do
Temp := Take;
end Sort;
if Temp > TaskResults(Stage) then
TaskArray(Stage + 1).Sort(Temp);
else
TaskArray(Stage + 1).Sort(TaskResults(Stage));
TaskResults(Stage) := Temp;
end if;
end loop;
end Filters;
begin
for I in 1..Limit loop
TaskArray(1).Sort(Random(G));
end loop;
Put_line (TaskResults'Image);
end Main;
I must refer to the task array from within the task. I know I could use an access discriminant but then I would have forgo the iterated expression entirely. It would be ugly.
I have this kind of circular issue all the time when writing concurrent algorithms.
You could maybe keep the declaration where it is and move the array assignment until after. So declare TaskArray before the body like it is right now, but don’t assign to it (thus allocating the Filters tasks) until after, in the body of Main.
pragma Ada_2022;
with Ada.Numerics.Discrete_Random, Ada.Text_IO;
procedure Main is
package NewRan is new Ada.Numerics.Discrete_Random (Integer);
use NewRan, Ada.Text_IO;
Limit : constant Positive := 10;
G : Generator;
task type Filters (Stage : Positive := 1) is
entry Sort (Take : in Integer);
end Filters;
function Make_Filters (Stage : Positive) return Filters is
begin
return X : Filters (Stage);
end Make_Filters;
TaskArray : array (1 .. Limit) of Filters :=
(for I in 1 .. Limit => Make_Filters (I));
TaskResults : array (1 .. Limit) of Integer := [others => Integer'first];
task body Filters is
Temp : Integer;
begin
accept Sort (Take : in Integer) do
TaskResults (Stage) := Take;
end Sort;
for I in 1 .. Limit - Stage loop
accept Sort (Take : in Integer) do
Temp := Take;
end Sort;
if Temp > TaskResults (Stage) then
TaskArray (Stage + 1).Sort (Temp);
else
TaskArray (Stage + 1).Sort (TaskResults (Stage));
TaskResults (Stage) := Temp;
end if;
end loop;
end Filters;
begin
for I in 1 .. Limit loop
TaskArray (1).Sort (Random (G));
end loop;
Put_Line (TaskResults'Image);
end Main;
pragma Ada_2022;
with Ada.Numerics.Discrete_Random, Ada.Text_IO;
procedure Main is
package NewRan is new Ada.Numerics.Discrete_Random (Integer);
use NewRan, Ada.Text_IO;
Limit : constant Positive := 10;
G : Generator;
TaskResults : array (1 .. Limit) of Integer := [others => Integer'first];
task type Filters (Stage : Positive := 1) is
entry Sort (Take : in Integer);
end Filters;
type TaskArrayType is array (1 .. Limit) of Filters;
function Make_Filters (Stage : Positive) return Filters is
begin
return X : Filters (Stage);
end Make_Filters;
A: access constant TaskArrayType;
task body Filters is
Temp : Integer;
begin
accept Sort (Take : in Integer) do
TaskResults (Stage) := Take;
end Sort;
for I in 1 .. Limit - Stage loop
accept Sort (Take : in Integer) do
Temp := Take;
end Sort;
if Temp > TaskResults (Stage) then
A (Stage + 1).Sort (Temp);
else
A (Stage + 1).Sort (TaskResults (Stage));
TaskResults (Stage) := Temp;
end if;
end loop;
end Filters;
begin
Reset (G);
declare
TaskArray: aliased TaskArrayType := (for I in 1 .. Limit => Make_Filters (I));
begin
A := TaskArray'Unrestricted_Access;
for I in 1 .. Limit loop
TaskArray (1).Sort (Random (G, 0, 20));
end loop;
end;
Put_Line (TaskResults'Image);
end Main;
The ‘Unrestricted_Access type was necessary so all tasks finish before printing the result.
The next version of Ada should really have a better of recursive and self-referential types, I am really bummed as what I really wanted is to give each task an access discriminant pointing to the enclosing array, but an array definition can not reference a current instance like record types can. And we need task aggregates…
You can already do that, it’s not how I would approach this, but I don’t know why you’re assuming it’s not possible:
procedure Example is
type Task_Array_Type;
type Task_Array_Type_Access is not null access Task_Array_Type;
task type Filters
(Arr : Task_Array_Type_Access := null;
Stage : Positive := 1)
is
end Filters;
type Task_Array_Type is array (1 .. 5) of Filters;
task body Filters is
begin
null;
end Filters;
begin
null;
end Example;
Also your code isn’t correct at all, there’s race conditions everywhere.
I don’t understand, where are any reference to an enclosing array here ? You give all the tasks a null access discriminant I fail to see the use of. Also, I ran the program for hundreds of thousands of loop and can’t find the race condition you speak off.
As you’ve found, tasks created using an allocator start immediately, so the body needs to have been elaborated. Tasks created by a declaration start when the enclosing declarative part is finished elaborating.
But your design is over-complex. Each task needs to know only its current value, and how to talk to the next task in the sequence. The driver needs only to know how to talk to the first task. This is indicative of a concurrent sieve. In a concurrent sieve, each task receives a sequence of values. Based on a value and the task’s state, the task decides what to do with the value, which may involve talking to the next task, which is created if it doesn’t exist. That results in a program like
with Ada.Numerics.Discrete_Random;
with Ada.Text_IO;
procedure Sieve_Sort is
package Int_Random is new Ada.Numerics.Discrete_Random (Result_Subtype => Integer);
task type Sorter is
entry Sort (Number : in Integer);
entry Put;
end Sorter;
type Sorter_Ptr is access Sorter;
function New_Sorter return Sorter_Ptr is (new Sorter);
task body Sorter is
Value : Integer;
Temp : Integer;
Next : Sorter_Ptr;
begin -- Sorter
accept Sort (Number : in Integer) do
Value := Number;
end Sort;
All_Actions : loop
select
accept Sort (Number : in Integer) do
Temp := Number;
end Sort;
if Next = null then
Next := New_Sorter;
end if;
if Temp >= Value then
Next.Sort (Number => Temp);
else
Next.Sort (Number => Value);
Value := Temp;
end if;
or
accept Put;
Ada.Text_IO.Put (Item => ' ' & Value'Image);
if Next = null then
Ada.Text_IO.New_Line;
else
Next.Put;
end if;
exit All_Actions;
end select;
end loop All_Actions;
end Sorter;
Gen : Int_Random.Generator;
Value : Integer;
First : Sorter;
begin -- Sieve_Sort
Int_Random.Reset (Gen => Gen);
All_Numbers : for I in 1 .. 10 loop
Value := Int_Random.Random (Gen);
Ada.Text_IO.Put (Item => ' ' & Value'Image);
First.Sort (Number => Value);
end loop All_Numbers;
Ada.Text_IO.New_Line;
First.Put;
end Sieve_Sort;
It’s instructive to compare this approach to a version in which all communication between the tasks is done through protected objects. The concurrent sieve is named after a similar concurrent implementation of the Sieve of Eratosthenes.
Quite elegant !
But I just don’t like at all creating new objects dynamically when we already know how many we need from the start. We need n processes for n numbers. Which… means I can just forget forgo the discriminant, and just use an index behind a PO incremented as tasks elaborate that determines its position in the chain. That should work.
You can pass in an access to the array there since it has the same type as the array. It’s null by default because you need defaults on discriminants for the type to by constrained so you can put it in an array.
What I presented is a general solution, which works when the number of tasks needed is not known in advance. It is also usually acceptable for cases when the number of tasks is known. It’s relatively easy to modify to deallocate the tasks when they’re finished, when that is a concern, but I thought I’d leave that as an exercise for the reader. It also demonstrates some general principles for concurrent software: keep as much information as possible internal to the tasks. Avoid global variables.
Yes, there may be cases when this design will not be suitable, though they are less common than usually thought. The general approach of creating software that is correct and clear, then measuring it, and only modifying it if it doesn’t meet the requirements, applies equally for concurrent software.