[cpp-threads] Alternatives to SC

[Herb Sutter]

Paul wrote:
> But I get the feeling that we are talking past each other.

I think so too. I'll try to just respond to selected places where I think that seems to be happening, rather than reply exhaustively.

> > The fundamental philosophy of CCCC seems to be:
> >
> >   Correctly locked programs are SC.
>
> We could probably get ten programmers together and get twenty different
> definitions of "correctly locked".  ;-)

I didn't think the term was confusing in this group. Informally, 'correctly locked' means that if two otherwise concurrent pieces of code (i.e., neither is otherwise ordered before the other) could manipulate the same shared variable and at least one is a writer, then they must manipulate that variable only while holding the same lock (so as to order themselves w.r.t. each other).


> Don't you agree that there should be rules governing use of atomics
> just like there are rules covering use of locking?

Sure, but I believe in defaults that are easy to use correctly and hard to use incorrectly. SC atomics fit that, and the other extreme of 'write explicit fences' fits the reverse. CCCC is trying to fall in between, and on the safe end of the spectrum, which is laudable.


> >   Is an atomic variable a monitor?
>
> The word "monitor" has all sorts of connotations, and I so I am not
> sure I understand the question.

Sorry, I thought I was being clear. I added:

> > Or equivalently:
> >
> >   Does an atomic variable have internally-locked semantics?

Another attempt: Is there a total order on operations on the variable? (And does it correspond to program order so that the programmer can express what the order is?)


> > (Aside: Relationships to lock semantics keep coming up. This question
> > is indirectly related to the question of whether transactional memory
> > systems should obey "single global lock" semantics.)
>
> I do not believe that transactional memory is ready for
> standardization.

Sure, it's far from that. I'm just pointing out a recurring consideration.


> On the other hand, why anyone be telling people that atomics are
> monitors?
> If you want monitors, after all, you can easily use locking.

It's not that anyone is telling them to. It's that people (and even many of us on this list) constantly do assume it, even when they know better and are trying to analyze a weaker model. Humans find it very difficult to reason about partial orders.

As just noted elsewhere in this thread, even the best peer-reviewed lock-free papers (which I think we can agree are by and for rocket scientists only) usually assume SC in their code, and at that are liable to be corrected. Nearly none try to show code written to something looser, say a fence-based model, _and_ say where fences should go. That makes me worry that it's too high a bar for real-world programming.


> > So let me ask whether this is really what you intended:
> >
> >   Q1: If you think that for program 1 the non-SC result should be
> > allowed, do you also agree that for program 2 the non-SC result
> should
> > be allowed? If not, why not?
>
> I do believe that a non-SC result should be allowed for Program 1, and
> that it is reasonable to expect that Program 2 would always give SC
> results (though, again, I have not thoroughly analyzed Program 2).
>
> I believe that it is eminently reasonable to expect different results
> because very different materials are being used in construction of the
> two programs.
>
> There are any number of analogs to this situation.  I will choose
> integer
> and floating-point arithmetic.  Integer arithmetic is associative,
> while floating-point arithmetic is not necessarily associative.
> Different materials, different results.

Although I disagree, being able to better understand your view is helpful.

You see it as a difference in kind. I see the two cases as not different in kind because the question is whether programmers can successfully reason about their code.

Let me try again to put it still another way:

  In program 2 (IRIW using a lock each for x and y), do we think programmers need SC to write code that they can understand and reason about reliably?

  If yes, what makes us think they don't need it for program 1, which is otherwise equivalent?

  If no, why are we considering it a benefit that CCCC programs are still SC, and not trying to jettison that restriction too for still more potential performance?

Regardless of whether SC vs. CCCC is "better", I'm trying to understand why isn't not inconsistent to say that "CCCC maintains SC for correctly locked code" (incl. lock-based IRIW) is desirable and necessary for the programmer to be able to reason reliably about the meaning of his code, but that it's not necessary for the same example converted to atomics. Either SC is necessary for both, unnecessary for both, or the programmer's views of these cases are different in a way not yet quantified.

There may be a good answer why these cases are different in terms of the programmer being able to reason about the code, but I haven't heard it yet -- saying "the proposed rules are just different" isn't an answer when the question is about whether the rules are necessary for a programmer to reason with confidence.


> >   Q3: Combining the two parts, why do the cases where non-SC creates
> > problems for lock-based programs not apply equivalently to program 1?
>
> Nice try.  ;-)
>
> Please note that I did not say that non-SC creates problems for lock-based
> programs.  I -did- agree that restricted (but common) uses of locking
> might hide non-SC behavior from the programmer, however, it is quite
> trivial to construct non-SC locked programs.  Take any non-SC program,
> and have each thread acquire its own per-thread lock at start, and
> release this lock upon exit.  The program is fully locked, but retains
> any non-SC behavior that it started with.

This hasn't helped me, unfortunately, because it hasn't addressed my question and because the example is not correctly locked by any reasonable definition.

The way to address the question would be to consider the cases where/why SC (and global ordering) are considered important for lock-based code that programmers can reason about, and then say why those are not important for being able to reason about the equivalent atomic-based code.


> > I realize that this comes around to the question of whether atomic
> > operations, like locks, should be a global property, and I realize
> > people want to make it not a global property. But if it's not global,
> > then atomics aren't monitors, and I now realize it's that consequence
> > that I haven't been able to swallow yet.
>
> This may be a key point -- I never have treated atomic variables as
> if they were monitors.
>
> So, why do you want atomic variables to act like monitors when you
> already have locking from which to construct monitors?

Because programmers, including experts who know better, continually make the mistake of treating them that way. It's not that we haven't tried; we just haven't yet come up with a weaker model which real-world experienced programmers have got used to using and are consistently able to reason about with confidence. IMO.

For example, I think today most people probably accept that asking the programmer to write explicit fences is a failure as a usable programming model, and that in practice, despite experience and effort, programmers routinely write bugs due to inadequate fences, performance hits due to overuse of fences, and often both.

> You still need to show me a compelling reason why we need atomics to be
> monitors, especially given that we already have locking for that
> purpose.

Because locks aren't only about that. Telling people "oh, if you want SC, use locks" is inadequate because: (a) locks carry other tradeoffs (e.g., they buy you SC, but they also buy you potential deadlock); and (b) it ignores that people have valid motivation to want to eliminate locks to avoid their drawbacks while not wanting to give up being able to reason successfully in terms of a monolithic shared memory.

Herb