[cpp-threads] C++ memory model

[N.M. Maclaren]

I have some initial comments on this; I may get time to look in more
detail later, but I probably won't :-(

My first comment is that I hope that you will put this on the Web.  The
C++ model (and the papers behind it) are already extremely useful for
raising in the context of other languages standards, as examples of what
is needed.  This would be useful when someone says "Ah, but have they
got it right?"

As an aside, Fortran has backed off from this, and has specified a
simple sequentially consistent segment model, with implementation
dependent atomic semantics.  There are good reasons for this, as it is
targetting a much wider range of architectures (including distributed
memory clusters), and considerable scalability (thousands of threads and
upwards).  Sequentially consistent atomics are not good news for such
requirements ....


2.1 Memory Actions says "The memory action does not explicitly contain a
location on which the operation acts.  ...  This is a trivial omission
and is the location is clearly intended to be part of this structure."
This issue is described further in 3.1.

    2.2 Access Types and Locations says "Given an atomic, non-atomic or
locking location, it is not clear whether operations of a different type
can be applied to it. For instance what does it mean for a locked
location to be read from and written to by an atomic read-modify-write
operation? Which value should an atomic read return when it follows an
atomic write then a non-atomic write at the same location?"

There is a similar problem to do with updates performed via calls to the
inherited C and other non-C++ libraries.  Nowhere in the C standard (or
POSIX, for that matter) is this issue addressed; we had a vigorous
debate in Fortran on the matter.  This is NOT just a theoretical point
as, for example, the Intel memory consistency model does not require
full-size SSE accesses to be atomic, so a vectorised library function
interacts in unspecified ways with all 'simple' accesses.

While I personally agree with your solution, which has similarities to
the one that Fortran has adopted, it has the consequence of preventing a
lot of reasonable constructions.  For example, such objects could not be
accessed by any of the functions in <cstring>, nor could they be
transferred in I/O.  It's a knotty problem.


2.3 Consideration of the Initial State says "BA08 does not mention the
initial state of the memory. It is not explained under what
circumstances a read can return the value of the initial state. ..."
3.4 specifies this by introducing the concept of an initial value,
which is a bigger change than it might appear.

C++ uses the term "indeterminate value" for what uninitialised objects
are set to, but does not seem to define it.  C99 defines it in 3.17.2 as
"either an unspecified value or a trap representation".

The reason for that is the nasty question of whether an object HAS an
initial value as an array of unsigned char - i.e. precisely which
meaning of "undefined" applies.  There have been (and perhaps still are)
architectures where the value returned may vary according to the type of
access.  It isn't implausible that the thread that allocates an object
might see a different initial value from other threads, especially for
pointers.  Is that allowed?


2.5 Additions for Proofs says "Second, the actions must be countable,
where (as usual) a set is countable if there is an injective function
that maps each element of the set to the natural numbers. This prevents
the actions unrelated by the relation being an uncountable set, which
could make it impossible to extend the partial order to a total order in
a way that would preserve infinite prefixes."  You explicitly specify a
form of the Axiom of Choice (actually, the Well-Ordering Principle) in
3.4.

I am truly baffled.  While that IS true, the mathematics of finite state
machines with non-countable, non-continuous time is fiendish almost
beyond imagination and a huge number of mathematical truisms stop
working (or so I was told when I was being taught Markov theory).  Are
people seriously working on the theory of (what are clearly not) Turing
machines using such a time base, or is this solely to make the Axiom of
Choice hold?

Surely this is a bit arcane for a language standard?  Everyone has
assumed discreteness for finite state machines since the 1920s, and
possibly earlier.


Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
Email:  nmm1 at cam.ac.uk
Tel.:  +44 1223 334761    Fax:  +44 1223 334679