Comparison of three algorithms for summing an array of integers

This article shares a comparison of the time taken to sum an array of integers. This article tests three algorithms for summing the array.

• A sequential summation using a single Ada task.

• A concurrent summation using 16 Ada tasks coordinating using the Ada Rendezvous mechanism.

• A concurrent summation using 16 Ada tasks coordinating using a shared buffer.

This test personal computer has the following characteristics.

• Processor : AMD Ryzen 7 7800X3D 8-Core Processor with baseline speed of  4.20 Ghz

• RAM: 64.0 GB (63.2 GB usable) of DDR5 RAM

• Operating System: Windows 11 Home

The software for this test is written in the Ada programming language using the GNAT Community Edition 2021 compiler.

The program source code is contained in three files.

There is one custom Ada package defined for this test. The package is named array_sums. Ada packages separate the interface definition from the implementation. The interface definition, or package specification, as it is called in Ada, is in a file named array_sums.ads.

generic
   Num_Tasks : Positive;
package array_sums is
   type Data_Array is array (Integer range <>) of Integer;
   type Data_Access is access all Data_Array;
   function Sum_Sequential (Item : in not null Data_Access) return Integer;
   function Sum_Buffered (Item : in not null Data_Access) return Integer;
   function Sum_Rendezvous (Item : in not null Data_Access) return Integer;
end array_sums;

This is a generic package. The generic parameter is named Num_Tasks. Num_Tasks must be an integer value greater than 0. The package specification defines two data types.

• Type Data_Array is an unconstrained array of Integer values indexed by the Integer type.

• Type Data_Access is an access type accessing an instance of Data_Array. Access types are similar to references in C++ or Java.

The three functions to be compared are declared.

• Function Sum_Sequential sums an instance of Data_Access, which cannot be null, and returns the sum.

• Function Sum_Buffered sums an instance of Data_Access, which cannot be null, and returns the sum.

• Function Sum_Rendezvous sums an instance of Data_Access, which cannot be null, and returns the sum.

This article will compare the time taken to execute each of the three functions above.

Implementation Source Code

All three functions to sum the Data_Array references by an instance of Data_Access are implemented in the package body. I will first isolate and explain each function.

Sum_Sequential

This function is the simplest function to write and explain. It operates in a single Ada task which sequentially sums all the elements in the array passed to it.

   function Sum_Sequential (Item : in not null Data_Access) return Integer    is
      total : Integer := 0;
   begin
      for value of Item.all loop
         total := total + value;
      end loop;
      return total;
   end Sum_Sequential;

This function uses a single for loop to iterate through every value in the array, adding that value to the local variable total in each iteration. Upon completing the iterations the value of total is returned.

Sum_Buffered

This function is the largest function of the three because a thread-safe shared buffer is defined to collect the total of all the concurrent tasks iterating through distinct slices of the array passed to the Sum_Buffered function.

   function Sum_Buffered (Item : in not null Data_Access) return Integer is
      protected final_Total is
         procedure Add (Value : in Integer);
         function Report return Integer;
      private
         Total : Integer := 0;
      end final_Total;

      protected body final_Total is
         procedure Add (Value : in Integer) is
         begin
            Total := Total + Value;
         end Add;

         function Report return Integer is
         begin
            return Total;
         end Report;

      end final_Total;

      task type Adder is
         entry Set (Min : Integer; Max : Integer);
      end Adder;

      task body Adder is
         Total : Integer := 0;
         First : Integer;
         Last  : Integer;
      begin
         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;

         for I in First .. Last loop
            Total := Total + Item (I);
         end loop;

         final_Total.Add (Total);

      end Adder;

   begin

      declare
         type Adders is array (1 .. Num_Tasks) of Adder;

         The_Adders   : Adders;
         Num_Elements : Integer := (Item.all'Length) / Num_Tasks;
         Slice_Start  : Integer := Item.all'First;
         Slice_Max    : Integer := Item.all'First;
      begin

         for I in The_Adders'Range loop
            if I = The_Adders'Last then
               Slice_Max := Item'Last;
            else
               Slice_Max := Slice_Max + Num_Elements;
            end if;
            The_Adders (I).Set (Min => Slice_Start, Max => Slice_Max);
            if I < The_Adders'Last then
               Slice_Start := Slice_Max + 1;
            else
               Slice_Start := Slice_Start + Num_Elements;
            end if;
         end loop;
      end;

      return final_Total.Report;
   end Sum_Buffered;

Shared buffer

The shared buffer is defined as an Ada protected object named final_Total. The protected object implicitly handles locking to prevent race conditions. It contains two methods. A procedure named add which takes an IN parameter of type Integer and adds that integer to the data field in final_Total named Total. A protected procedure implicitly implements a read-write lock on the data. The second method is a function named Report which returns the value of Total. Ada protected functions are not allowed to modify the value of the protected object. Protected functions are read-only methods. Ada protected functions implicitly implement a shared read lock on the data, allowing multiple functions to access the data simultaneously.

Adder task type

Ada tasks are analgous to threads and are often implemented using operating system threads. A task type defines the behavior of a particular kind of task which can be duplicated by creating multiple instances of the task type, just as if the task type were a data type.

Ada task types, like packages, have separate specifications and implementations. The specification for the Adder task type is:

      task type Adder is
         entry Set (Min : Integer; Max : Integer);
      end Adder;

This task type specification declares the Adder type to have one entry named Set. The Set entry has two parameters named Min and Max. Each parameter passes an integer into the instance of the task type. Languages such as C++ and Java would accomplish this through the use of a constructor for a thread class.

The task type implementation is defined in the task body.

      task body Adder is
         Total : Integer := 0;
         First : Integer;
         Last  : Integer;
      begin
         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;

         for I in First .. Last loop
            Total := Total + Item (I);
         end loop;

         final_Total.Add (Total);

      end Adder;

The task encounters an accept statement before it does anything else. The accept statement implements an Ada Rendezvous with a calling task. This Rendezvous completes the entry specified in the task specification. The task will suspend until another task passes the Min and Max values to the instance of the task type. Within the accept statement the entry parameter values are copied into the local variables First and Last.

The task instance then iterates through the set of array values starting with the index value contained in the First variable through the index value contained in the Last variable, totalling all the values. Upon completion of the for loop the value of Total is added to the final_Total protected object.

Sum_Buffered execution

The Sum_Buffered function begins its execution at the begin reserved word following the end of the declaration of the Adder task type. 

An inner block is declared within the Sum_Buffered function in which all the instances of the Adder task type are declared and executed. The Sum_Buffered function outer block will wait for all the tasks defined in the inner block to complete. This behavior is similar to calling a join method in C++ or Java for each of the declared task instances.

   begin
      declare
         type Adders is array (1 .. Num_Tasks) of Adder;

         The_Adders   : Adders;
         Num_Elements : Integer := (Item.all'Length) / Num_Tasks;
         Slice_Start  : Integer := Item.all'First;
         Slice_Max    : Integer := Item.all'First;
      begin

         for I in The_Adders'Range loop
            if I = The_Adders'Last then
               Slice_Max := Item'Last;
            else
               Slice_Max := Slice_Max + Num_Elements;
            end if;
            The_Adders (I).Set (Min => Slice_Start, Max => Slice_Max);
            if I < The_Adders'Last then
               Slice_Start := Slice_Max + 1;
            else
               Slice_Start := Slice_Start + Num_Elements;
            end if;
         end loop;
      end;

      return final_Total.Report;
   end Sum_Buffered;

The inner block declares an array type and four variables which only exist within the inner block.

• Type Adders is an array of Adder indexed by the values 1 through Num_Tasks. Rememer that Num_Tasks was the generic parameter passed to the package specification.

• The_Adders is an instance of Adders. All the tasks in the Adders array implicitly start at this point, and are immediatly suspended waiting for their Set entry to be called.

• Num_Elements is an Integer containing the number of array elements processed by each of the Num_Elements task objects, except the last task in the array which may contain more tasks because the number of data elements may not evenly divide into Num_Tasks and the extra elements are processed by the last task in the array.

• Slice_Start is an data_array index value specifying the first index value to be processed by a particular task.

• Slice_Max is a data_array index value specifying the maximum index value to be processed by a particular task.

The for loop iterates through all the index values in the The_Adders array, assigning Slice_Start and Slice_Max to each instance by calling that instance’s Set entry.

The inner block completes when all Num_Tasks of the array have completed. At that point all the data elements declared in the inner block are recovered and the Sum_Buffered function returns the value produced by calling final_Total.Report.

Sum_Rendezvous

Sum_Rendezvous has many similarities with Sum_Buffered. Sum_Rendezvous does not use a shared buffer to collect the subtotals from all the tasks. Instead it uses a second entry to report the subtotals.

Sum_Rendezvous also does not use an inner block because the second entry will cause the Sum_Rendezvous function to suspend until the task it calls accepts the Report entry.

   function Sum_Rendezvous (Item : in not null Data_Access) return Integer is

      task type Adder is
         entry Set (Min : Integer; Max : Integer);
         entry Report (Total : out Integer);
      end Adder;

      task body Adder is
         Subtotal : Integer := 0;
         First    : Integer;
         Last     : Integer;
      begin
         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;

         for I in First .. Last loop
            Subtotal := Subtotal + Item (I);
         end loop;

         accept Report (Total : out Integer) do
            Total := Subtotal;
         end Report;

      end Adder;

      type Adders is array (1 .. Num_Tasks) of Adder;

      The_Adders   : Adders;
      Num_Elements : Integer := (Item.all'Length) / Num_Tasks;
      Slice_Start  : Integer := Item.all'First;
      Slice_Max    : Integer := Item.all'First;
      Subtotal     : Integer;
      Grand_Total  : Integer := 0;
   begin

      for I in The_Adders'Range loop
         if I = The_Adders'Last then
            Slice_Max := Item'Last;
         else
            Slice_Max := Slice_Max + Num_Elements;
         end if;
         The_Adders (I).Set (Min => Slice_Start, Max => Slice_Max);
         if I < The_Adders'Last then
            Slice_Start := Slice_Max + 1;
         else
            Slice_Start := Slice_Start + Num_Elements;
         end if;
      end loop;

      for T of The_Adders loop
         T.Report (Subtotal);
         Grand_Total := Grand_Total + Subtotal;
      end loop;

      return Grand_Total;

   end Sum_Rendezvous;

Adder task specification

The Adder task specification for Sum_Rendezvous adds a second entry to the Adder task specification declared in the Sum_Buffered function.

      task type Adder is
         entry Set (Min : Integer; Max : Integer);
         entry Report (Total : out Integer);
      end Adder;

The Set entry passes two values into an instance of the Adder task type. The Report entry passes a single value out of the instance of the Adder task type.

Adder task body

         task body Adder is
         Subtotal : Integer := 0;
         First    : Integer;
         Last     : Integer;
      begin
         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;

         for I in First .. Last loop
            Subtotal := Subtotal + Item (I);
         end loop;

         accept Report (Total : out Integer) do
            Total := Subtotal;
         end Report;

      end Adder;

The Adder instance suspends on the accept call for the Set entry, just as we say in the Sum_Buffered function. It then iterates through the array slice of the Data_Array just as the function in the Sum_Buffered function. The difference is seen after the for loop completes. Instead of calling a protected procedure to add the subtotal to a total, the function simply accepts the Report entry and passes the subtotal out to the calling task.

Array_sums_main

The entry point for this comparison program is a procedure named array_sums_main. The purpose of this procedure is to execute each of the three array summing functions in the adder_sums package and display the results and timing for each function.

with Array_Sums;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Calendar; use Ada.Calendar;

procedure array_Sums_main is
   Start : Time;
   Finis : Time;
   Final_Total : Integer;
   exec_time : Duration;
   package sums is new Array_Sums(16);
   use Sums;
   The_Array : Data_Access := new Data_Array (1 .. Integer'Last);
begin
   The_Array.all := (Others => 1);
   Put_Line
     ("The size of the data array is" & Integer'Image (The_Array'Length));
   New_Line;
   Put_Line ("Sequential algorithm");
   Start := clock;
   Final_Total := Sum_Sequential(The_Array);
   Finis := clock;
    Put_Line ("Array total:" & Final_Total'Image);
   New_Line;
   exec_time := Finis - Start;
   Put_Line ("Elapsed calculation time:" & exec_time'Image & " seconds");
   Put_Line
     ("Time per addition operation:" &
        Float'Image (Float (exec_time) / Float (The_Array'Length)) & "
seconds");
   New_Line;
   Put_Line("Concurrent algorithm coordinating using Rendezvous");
   Start := clock;
   Final_Total := Sum_Rendezvous(The_Array);
   Finis := clock;
    Put_Line ("Array total:" & Final_Total'Image);
   New_Line;
   exec_time := Finis - Start;
   Put_Line ("Elapsed calculation time:" & exec_time'Image & " seconds");
   Put_Line
     ("Time per addition operation:" &
        Float'Image (Float (exec_time) / Float (The_Array'Length)) & " seconds");
   New_Line;
   Put_Line("Concurrent algorithm coordinating using shared buffer");
   Start := clock;
   Final_Total := Sum_Buffered(The_Array);
   Finis := clock;
   Put_Line ("Array total:" & Final_Total'Image);
   New_Line;

   exec_time := Finis - Start;
   Put_Line ("Elapsed calculation time:" & exec_time'Image & " seconds");
   Put_Line
     ("Time per addition operation:" &
        Float'Image (Float (exec_time) / Float (The_Array'Length)) & " seconds");  
end array_sums_main;


The array_sums generic package is instantiated passing the value 16 as the generic parameter. This causes the concurrent functions each to use 16 tasks to complete their calculations.

Comparison output

The output of this procedure is:

The size of the data array is 2147483647

Sequential algorithm
Array total: 2147483647

Elapsed calculation time: 6.531004600 seconds
Time per addition operation: 3.04124E-09 seconds

Concurrent algorithm coordinating using Rendezvous
Array total: 2147483647

Elapsed calculation time: 0.410473000 seconds
Time per addition operation: 1.91141E-10 seconds

Concurrent algorithm coordinating using shared buffer
Array total: 2147483647

Elapsed calculation time: 0.360019200 seconds
Time per addition operation: 1.67647E-10 seconds

It is clear that all three functions totaled the same set of values. The timings of the concurrent algorithms are clearly faster than the timing for the sequential algorithm, with the best timing coming from the Sum_Buffered function.

Comparing Sleeping Barber Implementations in Java and Ada

 

Sleeping Barber Problem 

Implemented in Ada and Java.  The Java implementation is taken from Java Sleeping Barber.

Problem Description:

Simulate a barber shop with one barber, one barber chair and a waiting room with N chairs for waiting customers. When the barber finishes cutting the hair of one customer he dismisses the customer and goes to the waiting room to see if another customer is waiting. If the customer is waiting the barber cuts the customer's hair. If no customers are waiting the barber goes to sleep on the barber chair. The next customer to arrive must awaken the barber.

If all waiting room chairs are full when a new customer arrives that arriving customer will leave the barbershop. If the barbershop is closed all arriving customers will leave the barbershop. The barber will cut the hair of all customers already in a chair when the barbershop closes.

In these examples there are 4 chairs in the Barber Shop waiting room.

Further Requirements:

• Thee problem is solved using threads in Java and tasks in Ada
• The solution must demonstrate how to close the barber shop and shut down the simulation.

The organization of the Ada program differs significantly from the organization of the Java program.

---

Java Program:

Barber.java

public class Barber {     public void cutHair() {         System.out.println("Barber: Cutting Hair --- " + Thread.currentThread().getName());     } } public class Customer {     public void enter() {         System.out.println("Customer: Enters the shop --- " + Thread.currentThread().getName());     }     public void getHairCut() {         System.out.println("Customer: Getting Haircut --- " + Thread.currentThread().getName());     }     public void leave() {         System.out.println("Customer: Leaves the shop --- " + Thread.currentThread().getName());     } }

  Barbershop.java

public class Barbershop {    private final int limit;    public int customers;    private final Barber barber;    private final Semaphore customerReady;    private final Semaphore barberReady;    private final Semaphore customerDone;    private final Semaphore barberDone;    private final ReentrantLock mutex;    public Barbershop(int limit) {        this.limit = limit;        customers = 0;        customerReady = new Semaphore(0);        barberReady = new Semaphore(0);        customerDone = new Semaphore(0);        barberDone = new Semaphore(0);        mutex = new ReentrantLock();        barber = new Barber();    }    public Void startService() {        // wait for a customer to arrive        try {            customerReady.acquire();        } catch (InterruptedException e) {            System.out.println("Barber wait task is interrupted: " + e.getMessage());        }        // signal that barber is ready        barberReady.release();        // give a haircut        barber.cutHair();        // wait for a customer to approve done        try {            customerDone.acquire();        } catch (InterruptedException e) {            System.out.println("Barber wait task is interrupted: " + e.getMessage());        }        // signal the customer that barber is done        barberDone.release();        System.out.println("Haircut is done");        return null;    }    public Void receiveNewCustomer() {        Customer customer = new Customer();        customer.enter();        mutex.lock();        if (customers == limit) {            mutex.unlock();            customer.leave();            return null;        }        customers += 1;        mutex.unlock();        customerReady.release();        // wait for the barber to be available        try {            barberReady.acquire();        } catch (InterruptedException e) {            System.out.println("Customer wait task is interrupted: " + e.getMessage());        }        // get the haircut        customer.getHairCut();        // signal that customer is done        customerDone.release();        // wait for barber to approve done        try {            barberDone.acquire();        } catch (InterruptedException e) {            System.out.println("Customer wait task is interrupted: " + e.getMessage());        }        mutex.lock();        customers -= 1;        mutex.unlock();        return null;    } }

 Simulator.java

public class Simulator {    private static final int NUM_ITERATION = 8;    public static void main(String[] args) {        ExecutorService executor = Executors.newWorkStealingPool();        Barbershop barbershop = new Barbershop(4);        Callable<Void> barbershopTask = barbershop::startService;        Callable<Void> receiveCustomerTask = barbershop::receiveNewCustomer;        List <Future<Void>> barberFutures = new ArrayList<>();        List <Future<Void>> customerFutures = new ArrayList<>();        for (int i=0; i<NUM_ITERATION; i++) {            Future <Void> barberFuture = executor.submit(barbershopTask);            barberFutures.add(barberFuture);            Future <Void> customerFuture = executor.submit(receiveCustomerTask);            customerFutures.add(customerFuture);        }        barberFutures.forEach(future -> {            try {                future.get();            } catch (InterruptedException | ExecutionException e) {                e.printStackTrace();            }        });        customerFutures.forEach(future -> {            try {                future.get();            } catch (InterruptedException | ExecutionException e) {                e.printStackTrace();            }        });    } }

 Analysis of the Java version

Size

167 lines of source code.

Barber

Only cuts hair. Does not sleep. Does not close store.

Customer

Enters barber shop. Waits for the barber to be available. Gets haircut. 

Barbershop

Creates semaphores and a mutex. Creates an instance of Barber. Implements startService and receiveNewCustomer.

Simulator

Creates an instance of Barbershop with 4 chairs. Creates a Callable named barberShopTask which executes startService. Creates a Callable named receiveCustomerTask which executes receiveNewCustomer. Creates lists named barberFutures and customerFutures. Iterates 8 times, each time creating a barberFuture from the execution of barbershopTask and then adds the future to barberFutures, then creats a customerFuture from the execution of receiveCustomerTask and add the future to customerFutures. After the creation of the futures each future in the barberFutures is executed. After executing all the barberFutures each future in customerFutures is executed.

The barbershop is implicitly closed when all 8 sets of futures have completed. There is no explicit command to close the barbersop after being open a specified length of time.

The Java version has a confusing set of responsibilities and there is no indication that the barber is sleeping while the barbershop waiting room is empty.

The logic of the interaction of barber behavior and customer behavior is controlled by the Barbershop class and not be either the barber or the customer. Neither the barber nor the customer know whether or not the waiting room is empty or full.

---

Ada version

barbershop.ads

package Barber_Shop is   task Barber is      entry Close_Shop;   end Barber;   task Customers; end Barber_Shop;

barbershop.adb

with Ada.Text_IO;               use Ada.Text_IO; with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; package body Barber_Shop is   Seed : Generator;   type Num_Seats is range 0 .. 5;   protected Shop is      function Is_Open return Boolean;      function Shop_Empty return Boolean;      entry Take_Seat;      entry Serve_Customer;      procedure Close_Shop;   private      Shop_Open      : Boolean   := True;      Occupied_Seats : Num_Seats := 0;   end Shop;   protected body Shop is      function Is_Open return Boolean is      begin         return Shop_Open;      end Is_Open;      function Shop_Empty return Boolean is      begin         return Occupied_Seats = 0;      end Shop_Empty;      entry Take_Seat when Shop_Open and then                               Occupied_Seats < Num_Seats'Last is      begin         Occupied_Seats := Occupied_Seats + 1;      end Take_Seat;      entry Serve_Customer when Occupied_Seats > 0 is      begin         Occupied_Seats := Occupied_Seats - 1;      end Serve_Customer;      procedure Close_Shop is      begin         Shop_Open := False;      end Close_Shop;   end Shop;   ------------   -- Barber --   ------------   task body Barber is      procedure Cut_Hair is      begin         Put_Line ("Luigi is serving a customer.");         delay Duration (Random (Seed) * 3.0);      end Cut_Hair;   begin      loop         select            accept Close_Shop;            Put_Line ("Luigi is closing the shop");            Shop.Close_Shop;         else            if Shop.Is_Open then               if Shop.Shop_Empty then                  Put_Line ("Luigi is sleeping.");               end if;               Shop.Serve_Customer;               Cut_Hair;            else               while not Shop.Shop_Empty loop                  Shop.Serve_Customer;                  Cut_Hair;               end loop;               exit;            end if;         end select;      end loop;   end Barber;   ---------------   -- Customers --   ---------------   task body Customers is   begin      loop         delay Duration (Random (Seed) * 2.5);         select            Shop.Take_Seat;            Put_Line ("A customer took a seat");         else            if Shop.Is_Open then               Put_Line (                "A customer left because all the seats were taken.");            else               Put_Line (                  "A customer left because the shop is closed.");               exit;            end if;         end select;      end loop;   end Customers; begin   Reset (Seed); end Barber_Shop;

 main.adb

with Barber_Shop; use Barber_Shop; procedure Main is begin   delay 60.0;   Barber.Close_Shop; end Main;

Analysis of Ada Version  

Size

119 lines of source code.

Barber_Shop package

Declares and defines a protected object named Shop. Declares and defines a task named Barber. Declares and defines a task called Customers. Declares the integer type Num_Seats with valid values in the range of 0 through 5.

Shop protected object

Declares and defines the protected operations named: function Is_Open return Boolean; function Shop_Empty return Boolean; entry Take_Seat; entry Serve_Customer; procedure Close_Shop;. Declares private data members: Shop_Open      : Boolean   := True;,  Occupied_Seats : Num_Seats := 0;. Function Is_Open returns True when the shop is open and False when the shop is closed. entry Take_Seat executes only when the shop is open and the value of Occupied_Seats is less than the maximum value of the type Num_Seats. entry Serve_Customer only executes when Occupied_Seats is greater than 0. procedure Close_Shop sets Shop_Open to False.

Barber task

Iterates until the shop is closed and all customers in the waiting room have had their haircuts. Each iteration Barber checks to see if its Close_Shop entry has been called. If the entry has not yet been called the Barber attempts to cut a customer's hair. If Close_Shop has been called Barber calls the Close_Shop procedure in the Shop protected object. In each iteration while the shop is open the barber calls Shop.Shop_Empty to determine if the shop is currently empty. If it is the Barber outputs "Luigi is sleeping". Whether or not the Shop is empty Barber calls Shop.Serve_Customer. Barber will be suspended while there are no customers in the waiting room and will awaken and server the customer(s) when there are one or more customers in the waiting room. Cutting a customer's hair takes a random time from 0 through 3 seconds. If the shop is closed the Barber cuts the hair of every customer in the waiting room and then terminates.

Customers task

Loops until the shop is closed. Each iteration of the loop begins with a random delay of 0 through 2.5 seconds. Each iteration a customer attempts to take a seat. If the customer cannot take a seat either the waiting room is full or the shop is closed. The customers task outputs a message saying the waiting room is full if the shop is open or a message saying the shop is closed when the shop is closed. After outputting a message stating the shop is closed the Customers task terminates.

Main procedure

The Main procedure context clause declares a dependency on the Barber_Shop package, which causes the Barber task and the Customers task to begin executing. The Main procedure delays for 60 seconds then calls the Close_Shop entry of the Barber task.

The simulation ends after Main calls the Barber Close_Shop entry is called and then all the waiting customers have received their haircuts. The Customer task starts up to 2.5 seconds after the Barber task, allowing the Barber to sleep at the beginning of the simulation.

The Shop protected object is a passive unit of concurrency, only executing when called by either Barber or Customers. The Shop protected object only deals with the states of the Shop. Those states are the number of Occupied_Seats and whether or not the Shop is open.

The Barber task only deals with customers when they are available and with closing the shop.

The Customers task only deals with taking a seat or leaving if no seat can be taken.

The Main procedure causes the Barber and Customers tasks to start, waits 60 seconds and then signals the Barber to close the shop.

Comparing Array handling in C and Ada

 

Problem Description: Find the Median of two merged sorted arrays.

This article demonstrates some of the differences in array handling using the C language and the Ada language.

C version:

int* merge(int arr1[], size_t len1, int arr2[], size_t len2) {     int * const ret = malloc((len1 + len2) * sizeof(int));     int *wr = ret;       // merge the two arrays while they both have values     for(;len1 && len2; ++wr) {         if(*arr1 < *arr2) {                       *wr = *arr1++;             --len1;         } else {             *wr = *arr2++;             --len2;         }     }     // here either len1 or len2 or both are zero     // fill with any residue from arr1     while(len1--) *wr++ = *arr1++;      // fill with any residue from arr2     while(len2--) *wr++ = *arr2++;         return ret; }   double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {     int *arr = merge(nums1, nums1Size, nums2, nums2Size), len = nums1Size+ nums2Size;     double mid;     if(len % 2 == 1)     {         mid = *(arr + len/2);     }     else     {         mid = (*(arr+len/2)+*(arr+len/2+1))/2.0;     }     free(arr);     return mid; }

 

The C language provides no way to declare an array type. Furthermore only a pointer to the first element of an array is passed to a function parameter when the programmer specifies the array name to be passed. The second parameter associated with each array passed in this example is the number of elements in the array.

The C language does not provide a general concatenation operator for arrays that works with parameters passed to a function because the general case for an array does not carry any information about the number of elements in the array instance. That information is only available within the scope in which the array instance is declared.

The merge function shown above is a solution to these problems. The programmer is required to write their own array concatenation function.

This C language solution produces a merged, but not necessarily sorted, array.

 

Ada version:

The Ada language allows subprograms to be defined within other subprograms. The solution below defines the Find_Median function within the Main procedure.

The Find_Median function is shown below.

type Flt_Array is array (Positive range <>) of Float;    function Find_Median (A : Flt_Array; B : Flt_Array) return Float is       procedure Sort is new Ada.Containers.Generic_Array_Sort         (Index_Type => Positive, Element_Type => Float,          Array_Type => Flt_Array);       Mid  : Positive;       Temp : Flt_Array := A & B;    begin       Sort (Temp);       Mid := (Temp'First + Temp'Last) / 2;       return Temp (Mid);    end Find_Median;

 

Arrays are first class types. The Ada example declares an unconstrained array type indexed by the subtype Positive. The subtype positive is a subtype of the Integer type. Integer is a signed 32-bit integer with a maximum valid value of 2^31 – 1. Subtype Positive is a constrained subtype of Integer with a minimum value of 1 and a maximum value of 2^31 – 1. Each element of the array is a Float. Unconstrained array types allow instances of the array type to have different numbers of elements. Each instance is constrained in its size.

An Ada array instance passed to a function does not “decay” to a pointer to the first object. All information about the array including its element type, the range of index values, and the number of elements in the array instance are passed with the array.

The Find_Median function takes two parameters of type Flt_Array and returns a Float.

The variable Mid is an instance of the subtype Positive, which is the same type as the array index type.

The Temp variable is an instance of Flt_Array initialized by the concatenation of the array passed to parameter A and the array passed to parameter B. The “&” operator in Ada concatenates two arrays of the same type. The “&” operator plus the sort procedure replace the merge function in the C example.

Ada.Containers.Generic_Array_Sort is a pre-defined generic sort procedure for unconstrained arrays. The parameters passed to the generic sort procedure create a concrete procedure specialized for sorting the Flt_Array type.

The index of the mid-point in the array is calculated as

Mid := (Temp'First + Temp'Last) / 2;

 

The minimum index value of an unconstrained array instance may be any valid value within the specified array index subtype. In this case the minimum value may be any number from 1 through 2^31 – 1. Temp’First evaluates to the minimum index value of the array Temp. Temp’Last evaluates to the maximum index value of the array Temp. The middle index value in the array is calculated by summing the minimum and maximum index values and dividing that sum by 2.

The Temp array in the Find_Median function is declared on the function stack. It therefore is reclaimed with the rest of the stack data when the function completes.

The function returns the value of the array indexed by the variable Mid.

A full program declaring and using the Find_Median function is:

with Ada.Text_IO; use Ada.Text_IO; with Ada.Containers.Generic_Array_Sort;   procedure Main is    type Flt_Array is array (Positive range <>) of Float;      function Find_Median (A : Flt_Array; B : Flt_Array) return Float is         procedure Sort is new Ada.Containers.Generic_Array_Sort         (Index_Type => Positive, Element_Type => Float,          Array_Type => Flt_Array);         Mid  : Positive;       Temp : Flt_Array := A & B;    begin       Sort (Temp);       Mid := (Temp'First + Temp'Last) / 2;       return Temp (Mid);    end Find_Median;    A1 : Flt_Array := (1.0, 3.0, 5.0, 7.0, 9.0, 11.0, 13.0, 15.0);    A2 : Flt_Array := (2.0, 4.0, 6.0, 8.0,   10.0, 12.0, 14.0); begin    Put_Line ("The median of A1 and A2 is " &              Float'Image (Find_Median (A1, A2))); end Main;

 

The output of this program is:

The median of A1 and A2 is  8.00000E+00