[cpp-threads] Whence Sequential Consistency?

[Paul E. McKenney]

On Fri, Jan 19, 2007 at 06:16:21PM -0800, Lawrence Crowl wrote:
> 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:
> >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.

Agreed.  But please keep in mind that money can be lost due to
too-tight of restrictions just as easily as it can be due to lack
of restrictions.  Any decision heuristic similar to "it is tighter,
therefore better" is flawed.  Tighter is -often- better, but by
no means -always- better.

> >> >[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.

Again, no.  The "before" version releases the lock prior to return,
so that there is no "freshness" guarantee in either case.

> >> >>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;
>         }

Which does at least have the virtue of neatly slithering around the point.  ;-)

Switching from integer to floating point, even though both are in some
sense "numbers" can introduce strange failures due to non-obvious
properties of both floating point and integer.

> >> >>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.

If you point is that SC atomics offer relatively little benefit compared
to non-SC atomics, then we just might be in violent agreement.  ;-)

> >> >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.

Could it be that we are in near-total violent agreement???  ;-)

> >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.  :-)

Whatever works!  ;-)

						Thanx, Paul