[cpp-threads] Whence Sequential Consistency?

[Paul E. McKenney]

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!  ;-)

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.

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

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

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

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

						Thanx, Paul