Re: Robert Dewar's great article about the Strengths of Ada over other langauges in multiprocessing!

["(see below)" <yaldnif.w@blueyonder.co.uk>]

On 02/04/2008 08:22, in article wvbr4pakzpo1.fsf@astra06.norway.sun.com,
"Ole-Hjalmar Kristensen"
<ole-hjalmar.kristensen@substitute_employer_here.com> wrote:

> Yes, I know. So pragma atomic does not help very much by itself in
> implementing lock-free algorithms.

Yes, it's only one essential aspect.
 
>>> Agreed, but you may able to cheat and pack a pair of integers into
>>> a 64-bit atomic, and a compare-and-swap is also much cheaper than a
>>> protected object it seems.
> 
>     (b> Yes, but this is completely implementation-dependent.
>     (b> Not much above the semantic level of assembly.
>     (b> I would take a lot of convincing that the performance
>     (b> improvement was actually necessary.
> 
> I agree that it rarely should be necessary. It would have been nice to
> have a way of implementing lock-free algorithms in Ada efficiently,
> but entryless protected objects seems to be the best solution if
> you want a portable program.

It would not take too much - perhaps just a standard library including
read-barrier and write-barrier operations, and a selection of things like
CAS, TAS, EXCH, etc; mapped to m/c codes where these are provided,
and implemented using the architecture's native sync operations where not.

Is this the basis for an AI?

Following on my second post to the point, I was reminded of the package
Ada.Synchronous_Task_Control, which must also impose memory barriers is it
is to work reliably on a multiprocessor; so I tried that in my Simpson's
algorithm test as well. Here is the code:

> with Ada.Synchronous_Task_Control;
> package body Wait_Free_Atomicity is
>     
>        procedure Sync is
>           use Ada.Synchronous_Task_Control;
>           Sema : Suspension_Object;
>           Bool : Boolean := Current_State(Sema); -- either this
>        begin
>            -- Set_True(Sema);                     -- or
>            -- Suspend_Until_True(Sema);           -- this
>        end Sync;
>     
>     procedure Update (Atomic_Item : in out an_Atomic; Item : in  an_Item) is
>         Row : constant a_Bistate := not Atomic_Item.Last_Row_Inspected;
>         Col : constant a_Bistate := not Atomic_Item.Last_Column_Updated(Row);
>     begin
>         Atomic_Item.Data_Slot_Matrix(Row, Col) := Item;
>         Atomic_Item.Last_Column_Updated(Row) := Col;
>         Atomic_Item.Last_Row_Updated := Row;
>         Sync;
>     end Update;
>     
>     procedure Inspect (Atomic_Item : in out an_Atomic; Item : out an_Item) is
>         Row : constant a_Bistate := Atomic_Item.Last_Row_Updated;
>         Col : a_Bistate;
>         pragma Atomic (Col);
>     begin
>         Atomic_Item.Last_Row_Inspected := Row;
>         Col  := Atomic_Item.Last_Column_Updated(Row);
>         Item := Atomic_Item.Data_Slot_Matrix(Row, Col);
>         Sync;
>     end Inspect;
> 
> end Wait_Free_Atomicity;

It works nicely, and is an order of magnitude faster than a protected
object:

20_000_000 updates

with Suspend_Until_True sync:
No consistency failures.
        7.30 real        14.14 user         0.04 sys

with Current_State sync:
No consistency failures.
        3.57 real         6.97 user         0.02 sys

-- 
Bill Findlay
<surname><forename> chez blueyonder.co.uk