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

* Randy Brukardt:

> "Maciej Sobczak" <see.my.homepage@gmail.com> wrote in message
> news:89af8399-94fb-42b3-909d-edf3c98d32e5@n75g2000hsh.googlegroups.com...
> ...
>> Take for example lock-free algorithms. There is no visible research on
>> this related to Ada, unlike Java and C++ (check on
>> comp.programming.threads).
>
> Perhaps I'm showing my ignorance, but does there need to be any?

If you actually want to go thoroughly multi-core, you often need
non-blocking algorithms. It is not possible to write them in Ada
because Ada lacks the required primitives (mainly compare-and-swap or
something equivalent).

> Ada supports lock-free threads quite well using pragma Atomic.

Try implementing Azul's concurrent hashtable in Ada:

<http://blogs.azulsystems.com/cliff/2007/03/a_nonblocking_h.html>

(Portable Java source code is available.)

* ME:

> As many of may have already noticed, there has been a tremendous furor
> over the lack of multicore support in the common languages like C and
> C++. I have been reading these articles in EE Times and elsewhere
> discussing this disaster with all the teeth gnashing and handwringing
> acting as though Ada never existed. Robert Dewar ,our hero, has
> written an absolutely excellent article with a clever intro.
> http://www.eetimes.com/news/design/s...leID=206900265

GNAT indirectly inherits most C/C++ ambiguities regarding concurrency
because Ada code is compiled to GIMPLE, an intermediate language which
is heavily influenced by C/C++ requirements and which lacks a rigorously
specified memory model (among other things).

In fact, for most C/C++ concurrency surprises (for instance, a
conditional write turned into an unconditional one by GCC), Ada test
cases could be produced which showed the same problem. For Ada, these
are defects in the toolchain. For C/C++, they are mere
quality-of-implementation issues. Is this a major difference? Probably
not, because you may still have to convince your Ada vendor that their
reading of the standard is incorrect, and the concurrency anomaly you're
observing is actually an implementation defect.

* Ole-Hjalmar Kristensen:

> If the compiler is smart enough to optimize this case, an entryless
> protected object would be a good building block.
>
> The AARM states that "Entryless protected objects are intended to be
> treated roughly like atomic objects -- each operation is indivisible
> with respect to other operations (unless both are reads), but such
> operations cannot be used to synchronize access to other nonvolatile
> shared variables"

You need some signaling for a shared hash table, otherwise reading a
freshly-added object from a different thread might not give you the data
you want (strictly speaking, even just comparing the might cause
issues).

If you mean that it may be difficult to optimize, I agree, but I
cannot agree that you need *more* than an entryless protected object
to implement a hash table, since it guarantees that each operation on
the object is indivisible.

The simplest case (for the programmer) is of course to put both key
and value inside the protected object, Then a reader will either see
the key, value pair as it was before the update or as it is after the
update. The problem is that although reads within a procedure may be
optimistic, the compiler probably needs to insert at least a spin lock
during the actual update of the object.

What I was thinking of was to recognize the special case where the
entryless protected object contains only a single entity which can be
updated atomically with a compare and swap. In that case, you could
skip the spin lock in the update phase and use CAS directly. In this
case the key and the value would be in separate protected objects, and
the implementation of the hash table could follow the pattern of the
hash table you mentioned.

On the other hand, I cannot see any reason why Annex C just couldn't
say that intrinsic subprograms for compare-amd-swap and similar
machine operations shall be provided *if* they are available on a
platform.
That would at least save me the work of writing the bindings myself.


>>>>> "FW" == Florian Weimer <fw@deneb.enyo.de> writes:

FW> * Ole-Hjalmar Kristensen:
>> If the compiler is smart enough to optimize this case, an entryless
>> protected object would be a good building block.
>>
>> The AARM states that "Entryless protected objects are intended to be
>> treated roughly like atomic objects -- each operation is indivisible
>> with respect to other operations (unless both are reads), but such
>> operations cannot be used to synchronize access to other nonvolatile
>> shared variables"

FW> You need some signaling for a shared hash table, otherwise reading a
FW> freshly-added object from a different thread might not give you the data
FW> you want (strictly speaking, even just comparing the might cause
FW> issues).

--
C++: The power, elegance and simplicity of a hand grenade.

* Ole-Hjalmar Kristensen:

> If you mean that it may be difficult to optimize, I agree, but I
> cannot agree that you need *more* than an entryless protected object
> to implement a hash table, since it guarantees that each operation on
> the object is indivisible.

You need some kind of signaling construct. Suppose you put some access
value as a value into the hash table. If there's no signaling (the case
of an entryless protected object, it seems), a task that retrieves the
value from the table cannot make any assumptions regarding the object
the access value refers to, unless there is some other form of
synchronization.

> On the other hand, I cannot see any reason why Annex C just couldn't
> say that intrinsic subprograms for compare-amd-swap and similar
> machine operations shall be provided *if* they are available on a
> platform.

CAS alone is not sufficient, you also need some sort of barrier (both
against compiler optimizations and reordering in the silicon).

"Ole-Hjalmar Kristensen"
<ole-hjalmar.kristensen@substitute_employer_here.com> wrote in message
news:wvbrlk44zf5l.fsf@astra06.norway.sun.com...
....
> On the other hand, I cannot see any reason why Annex C just couldn't
> say that intrinsic subprograms for compare-amd-swap and similar
> machine operations shall be provided *if* they are available on a
platform.
> That would at least save me the work of writing the bindings myself.

It does, actually. See C.1(11-16). It's "only" Implementation Advice, but
that is necessary in any case, because the Standard can't require something
it can't define.

A more interesting question is whether implementations follow that advice
(in any useful manner).

Randy.

>>>>> "FW" == Florian Weimer <fw@deneb.enyo.de> writes:

FW> * Ole-Hjalmar Kristensen:
>> If you mean that it may be difficult to optimize, I agree, but I
>> cannot agree that you need *more* than an entryless protected object
>> to implement a hash table, since it guarantees that each operation on
>> the object is indivisible.

FW> You need some kind of signaling construct. Suppose you put some access
FW> value as a value into the hash table. If there's no signaling (the case
FW> of an entryless protected object, it seems), a task that retrieves the
FW> value from the table cannot make any assumptions regarding the object
FW> the access value refers to, unless there is some other form of
FW> synchronization.

First, I never said it can be used to synchronize something which is
outside the protected object or the hash table. But it will serialize
the access to the protected object, so any task will see consistent
key, value pairs, which is all the synchronization you need for the
hash table itself.

Second, I cannot find anything in the RM which says you can make *any*
assumptions about objects which are outside the protected object so I
cannot see how signaling will help you.

Actually there are two cases here:

1. The task is calling a protected function or procedure to retrieve
the pointer and accesses the object through the pointer after the
call. This is obviously bad code unless the object is atomic, which
in practice means a single word.

2. The task is calling a protected function or procedure and accesses
the object through the pointer while it is inside the protected
object. In both cases you are guaranteed that you will see any
previous updates to the protected object itself and that no one is
updating the protected object while you are inside, but unless the
other object is atomic I do not think you have the guarantee that
you even see previous updates to it, at least in the multiprocessor
case. You may speculate that since the implementation of a
protected call typically involves a memory barrier, it will be safe
to access data outside the protected object, but I would not bet on
it.

>> On the other hand, I cannot see any reason why Annex C just couldn't
>> say that intrinsic subprograms for compare-amd-swap and similar
>> machine operations shall be provided *if* they are available on a
>> platform.

FW> CAS alone is not sufficient, you also need some sort of barrier (both
FW> against compiler optimizations and reordering in the silicon).

Which is why I said compare-and-swap and similar machine operations.

With respect to compiler optimizations, I assume you are thinking of
the kind of reordering decribed by Boehm in his paper where some
compilers introduced extra reads and writes while the pthread mutex
was not held? This is obviously a problem, the compiler needs to know
whether a variable may be accessed by multiple threads or not to do
sensible optimizations. But I assume that pragma atomic would be
sufficient to take care of such cases (all atomic objects are volatile):

"15 For an atomic object (including an atomic component) all reads and
updates of the object as a whole are indivisible.

16 For a volatile object all reads and updates of the object as a whole are
performed directly to memory.

16.a Implementation Note: This precludes any use of register
temporaries, caches, and other similar optimizations for that object."

When it comes to reordering in the silicon, at least in the Solaris
case, this is already taken care of in the atomic library operations,
see under NOTES in the excerpt from the man page below. Only if you
need synchronization between *different* variables do you need memory
barriers.


Standard C Library Functions atomic_ops(3C)

NAME
atomic_ops - atomic operations

SYNOPSIS
#include <atomic.h>

DESCRIPTION
This collection of functions provides atomic memory opera-
tions. There are 8 different classes of atomic operations:

atomic_add(3C) These functions provide an atomic addition
of a signed value to a variable.

atomic_and(3C) These functions provide an atomic logical
'and' of a value to a variable.

atomic_bits(3C) These functions provide atomic bit setting
and clearing within a variable.

atomic_cas(3C) These functions provide an atomic comparison
of a value with a variable. If the com-
parison is equal, then swap in a new value
for the variable, returning the old value of
the variable in either case.

atomic_dec(3C) These functions provide an atomic decrement
on a variable.

atomic_inc(3C) These functions provide an atomic increment
on a variable.

atomic_or(3C) These functions provide an atomic logical
'or' of a value to a variable.

atomic_swap(3C) These functions provide an atomic swap of a
value with a variable, returning the old
value of the variable.

<snip>

NOTES
Atomic instructions ensure global visibility of atomically-
modified variables on completion. In a relaxed store order
system, this does not guarantee that the visibility of other
variables will be synchronized with the completion of the
atomic instruction. If such synchronization is required,
memory barrier instructions must be used. See
membar_ops(3C).


--
C++: The power, elegance and simplicity of a hand grenade.

* Ole-Hjalmar Kristensen:

> Second, I cannot find anything in the RM which says you can make *any*
> assumptions about objects which are outside the protected object so I
> cannot see how signaling will help you.

I think that's what 9.10 (Ada 95 without TC 1) is about.

"Florian Weimer" <fw@deneb.enyo.de> wrote in message
news:87wsnmg1ju.fsf@mid.deneb.enyo.de...
> * Ole-Hjalmar Kristensen:
>
> > Second, I cannot find anything in the RM which says you can make *any*
> > assumptions about objects which are outside the protected object so I
> > cannot see how signaling will help you.
>
> I think that's what 9.10 (Ada 95 without TC 1) is about.

Yes, that's right. The wording is pretty obscure, but it allows you
serialize access to anything.

Randy.