[cpp-threads] Whence Sequential Consistency?

[Lawrence Crowl]

On 1/19/07, Paul E. McKenney <paulmck at linux.vnet.ibm.com> wrote:
> On Fri, Jan 19, 2007 at 02:34:30PM -0800, Lawrence Crowl wrote:
> [ . . . ]
> > "Paul E. McKenney" <paulmck at linux.vnet.ibm.com> writes:
> > >A programmer cannot -in- -general- mechanically replace a
> > >lock-based data structure with a lockless data structure.
> >
> > This statement worries me.  It will severely inhibit code evolution.
> > What can we do to enable evolution?  I do not wish to require
> > mechanical evolution, but I don't want to require changing users
> > of an abstraction.
>
> Eh???  This is Computer Science we are talking about here -- the
> field where there is an impossibility proof for almost every general
> property one might desire, after all!  ;-)

Touche.

> Locking has some very nice properties.  When you move to a lockless
> algorithm, you are giving up some of those properties.  You cannot
> reasonably expect this to be free of consequences.

True, but the next C++ standard will be at the center of billions of dollars
of software investment.  A little extra thinking on our part will save lots
of money, money that might be better used for other purposes.

> > >[do_it example omitted] This gives up some consistency in exchange
> > >for reduced lock contention and higher do_it_count() performance.
> >
> > In this example, you changed the interface, which isn't really
> > relevant to my point.  Sometimes changing the interface is the
> > right thing to do, but sometimes it is not.
>
> No -- "int do_it_count(void)" in both cases -- same API.

The syntax is the same, but you changed the "freshness" guarantee,
which is part of the interface.

> > >>An important property of programming languages is interface
> > >>invariance.  It ought to be possible for the implementation of an
> > >>interface to change without changing the properties of the interface.
> >
> > >      int not_associative(int a, int b, int c)
> > >      float not_associative(float a, float b, float c)
> >
> > Again, in this case, you have changed the interface.
>
> OK.  Easily fixed, so that the point still stands:
>
>         int not_associative(float a, float b, float c)
>         {
>                 int delta;
>                 int ia = (int)a, ib = (int)b, ic = (int)c;
>
>                 delta = ((ia + ib) + ic) - (ia + ib) + ic;
>                 return delta != 0;
>         }
>
>         int not_associative(float a, float b, float c)
>         {
>                 float delta;
>
>                 delta = ((a + b) + c) - (a + b) + c;
>                 return delta != 0;
>         }

Note that I didn't say changing the implementation couldn't change
the interface, I said that it should be possible to reasonably change the
implementation without changing the interface.  In this case, perhaps

         int not_associative(float a, float b, float c)
         {
                 float delta;
                 float cse = a + b;
                 delta = (cse + c) - cse + c;
                 return delta != 0;
         }

>
> > >>So, if locks and atomics have different sequential consistency
> > >>properties, how do I not get sequential consistency by adding locks?
> > >>How do I preserve sequential consistency when removing locks?
> >
> > >This begs the question of whether sequential consistency should be
> > >considered an absolute requirement for all uses of atomics.
> >
> > On the contrary, it gets to the heart of the question.  If non-SC
> > atomics can produce SC programs, they can be useful.  If SC atomics
> > can yield non-SC programs, what is the point of having them?
>
> I am glad that you agree that non-SC atomics can be useful.
>
> That said, your second sentence assumes that programs must be SC to
> be useful.  This assumption is incorrect.  Again, see N2153 Section 5.1
> pages 5-6 for an example.

I don't think my second sentence makes that assumption.  The point was
that if you _want_ SC programs, and SC atomics won't get you there,
then you have to do other work, which may make the difference between
SC atomics and non-SC atomics moot.

> > >When you insist on SC atomics, you are telling me that this
> > >split-counter use case should be abolished.  Given that its use is
> > >well-nigh universal, you will have to give some extremely compelling
> > >reasons to abolish it.
> >
> > I am not insisting on SC atomics.  (See N2145.)  I am reqesting that
> > we be very clear on the kinds of programs we are enabling and the
> > consequences on software development.  At present, there have been
> > many examples of code, but less discussion of these latter issues.
>
> Glad to hear that you are OK with non-SC atomics -- this was not
> apparent to me from your earlier post.  You do seem to be objecting
> to non-SC programs, despite their common usage.

I am not objecting to non-SC programs.  Please don't read motives into
my statements unless I am very explicit about it.  (I have this problem
often, so it must be me.)  What I am trying to do is clarify the relationship
between our goals and our mechanisms.

> I assert that our proposals need to support idioms currently being used.
> We should be codifying current practice rather than outlawing it.
> There might well be some examples of current practice that deserve
> to be outlawed, but this would be a matter for a different forum.
>
> > Please forgive me for being obtuse, but I think there is something we
> > are collectively missing, and I want to learn what that is.
>
> Give the tone of some of my emails to this list, I can only assume that
> you are asking forgiveness from Jeremy, Raul, and Doug rather than from
> myself.  ;-)

Equal opportunity forgiveness.  :-)

-- 
Lawrence Crowl