[cpp-threads] Whence Sequential Consistency?

[Paul E. McKenney]

On Thu, Jan 18, 2007 at 06:14:10PM -0800, Lawrence Crowl wrote:
> Something about sequential consistency has been bothering me for a
> while, and I am not sure how to articulate the problem, but I will
> give it a shot.

[ cutting things responded to by earlier posts ]

> More importantly, a difference in sequential consistency between
> locks and atomics implies that a programmer _cannot_ replace a
> poor-performing lock-based data structure with a lock-free data
> structure.  The reason is that sequential consistency became an
> implied property of the locked data structure and removing that
> property would throw unknown numbers of clients into the land of
> undefined and untested behavior.

Almost.  A programmer cannot -in- -general- mechanically replace a
lock-based data structure with a lockless data structure.  However,
programmers -can- often replace lock-based data structures with lockless
data structure in special cases, with some redesign and recoding.
Programmers can also often reduce the scope of the lock.  For example:

	DEFINE_SPINLOCK(my_lock);
	int did_something_count();
	extern void do_something(void);

	void do_it(void)
	{
		spin_lock(&my_lock);
		do_something();
		did_something_count++;
		spin_unlock(&my_lock);
	}

	int do_it_count(void)
	{
		int n;

		spin_lock(&my_lock);
		n = did_something_count;
		spin_unlock(&my_lock);
		return n;
	}

If this implementation was suffering excessive lock contention on
my_lock, and if this contention was caused by a large number of
calls to do_it_count(), and if the compiler and CPU supported atomic
access to aligned ints to normal loads and stores, then one might
safely replace do_it_count() with the following:

	int do_it_count(void)
	{
		return did_something_count;
	}

This gives up some consistency in exchange for reduced lock contention
and higher do_it_count() performance.

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

Hmmm...

Let us use (((a + b) + c) - (a + b) + c) as an example.

	int not_associative(int a, int b, int c)
	{
		int delta;

		delta = ((a + b) + c) - (a + b) + c;
		return delta != 0;
	}

This will always return zero on machines that do not raise exceptions
for integer overflow (which would be all of the ones I have worked
with any time recently).

By your invariance property, the following should behave the same:

	float not_associative(float a, float b, float c)
	{
		float delta;

		delta = ((a + b) + c) - (a + b) + c;
		return delta != 0;
	}

But it does not -- there are values of a, b, and c such that the
floating-point variant will return 1.

So although your invariance property is a good general rule, it clearly
cannot be interpreted as a universal iron-clad constraint.

> 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.  For but
one counterexample of many, please see N2153 Section 5.1 pages 5-6 for a
non-SC use of atomics.  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.

							Thanx, Paul