From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,e0e1d3b3f7c994b8 X-Google-Attributes: gid103376,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news3.google.com!proxad.net!feeder1-2.proxad.net!news.cs.univ-paris8.fr!news.side3.eu!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "(see below)" Newsgroups: comp.lang.ada Subject: Re: Robert Dewar's great article about the Strengths of Ada over other langauges in multiprocessing! Date: Wed, 02 Apr 2008 15:59:50 +0100 Message-ID: References: <13t4b2kkjem20f3@corp.supernews.com> <89af8399-94fb-42b3-909d-edf3c98d32e5@n75g2000hsh.googlegroups.com> <87bq56peg1.fsf@mid.deneb.enyo.de> <87bq516uri.fsf@mid.deneb.enyo.de> <87prtfzrtl.fsf@mid.deneb.enyo.de> <87wsnmg1ju.fsf@mid.deneb.enyo.de> Mime-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Trace: individual.net tYBMLy4bK1o9TZZcaEpcOAx/myEKtH0/eQ33552B3Jir+rNoZj Cancel-Lock: sha1:Cst+D31ATgupl8o7x9Bc5eze5u4= User-Agent: Microsoft-Entourage/12.1.0.080305 Thread-Topic: Robert Dewar's great article about the Strengths of Ada over other langauges in multiprocessing! Thread-Index: AciU0jMDjXviMiozJ0KU5SR4mzoYkw== Xref: g2news1.google.com comp.lang.ada:20758 Date: 2008-04-02T15:59:50+01:00 List-Id: On 02/04/2008 08:22, in article wvbr4pakzpo1.fsf@astra06.norway.sun.com, "Ole-Hjalmar Kristensen" 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 chez blueyonder.co.uk