How to determine what is 'sequenced before' others?

Question

I went through this excellent answer regarding Undefined Behaviour and Sequenced [Before/After] relations in C++11. I understand the binary relation concepts, but am missing what the new rules governing sequencing are.

For these familiar examples, how do the new sequencing rules apply?

1. i = ++i;
2. a[++i] = i;

More specifically, what are the new C++11 sequencing rules?

I am looking for some rules like (this one is completely made up)

The lhs of an '=' statement is always sequenced before the rhs, and is thus evaluated first.

In case these are available in the standard itself, can someone quote the same here?

Angellaangelle

There are supposed to be no changes to the rules of sequence points, as old code must work just the way it did before. It is just rephrased to cope with threading. – Sentimentalize

@BoPersson: but the new rules can be (and are) more precise. Things that used to be UB can be well-defined in C++11 without breaking old code. :) – Indoaryan

Answer 1

The sequenced-before relationship, and the rules concerning it are a "tidying up" of the prior rules on sequence points, defined in a consistent way with the other memory model relationships such as happens-before and synchronizes-with so that it can be precisely specified which operations and effects are visible under which circumstances.

The consequences of the rules are unchanged for simple single-threaded code.

Let's start with your examples:

1. i = ++i;

If i is a built-in type such as int then there are no function calls involved, everything is a built-in operator. There are thus 4 things that happen:

(a) The value computation of ++i, which is original-value-of-i +1

(b) The side effect of ++i, which stores original-value-of-i +1 back into i

(c) The value computation of the assignment, which is just the value stored, in this case the result of the value computation of ++i

(d) The side effect of the assignment, which stores the new value into i

All of these things are sequenced-before the following full expression. (i.e. they are all complete by the final semicolon of the statement)

Since ++i is equivalent to i+=1, the side effect of storing the value is sequenced-before the value computation of ++i, so (b) is sequenced-before (a).

The value computation of both operands of an assignment is sequenced-before the value computation of the assignment itself, and that is in turn sequenced-before the side effect of storing the value. Therefore (a) is sequenced before (c), and (c) is sequenced-before (d).

We therefore have (b) -> (a) -> (c) -> (d), and this is thus OK under the new rules, whereas it was not OK under C++98.

If i was a class, then the expression would be i.operator=(i.operator++()), or i.operator=(operator++(i)), and all effects of the operator++ call are sequenced-before the call to operator=.

2. a[++i] = i;

If a is an array type, and i is an int, then again the expression has several parts:

(a) The value computation of i

(b) The value computation of ++i

(c) The side effect of ++i, which stores the new value back into i

(d) The value computation of a[++i], which returns an lvalue for the element of a indexed by the value computation of ++i

(e) The value computation of the assignment, which is just the value stored, in this case the result of the value computation of i

(f) The side effect of the assignment, which stores the new value into the array element a[++i]

Again, all of these things are sequenced-before the following full expression. (i.e. they are all complete by the final semicolon of the statement)

Again, since ++i is equivalent to i+=1, the side effect of storing the value is sequenced-before the value computation of ++i, so (c) is sequenced-before (b).

The value computation of the array index ++i is *sequenced-before` the value computation of the element selection, so (b) is sequenced-before (d).

The value computation of both operands of an assignment is sequenced-before the value computation of the assignment itself, and that is in turn sequenced-before the side effect of storing the value. Therefore (a) and (d) are sequenced before (e), and (e) is sequenced-before (f).

We therefore have two sequences: (a) -> (d) -> (e) -> (f) and (c) -> (b) -> (d) -> (e) -> (f).

Unfortunately, there is no ordering between (a) and (c). Thus a side effect which stores to i is unsequenced with respect to a value computation on i, and the code exhibits undefined behaviour. This is again given by 1.9p15 of the C++11 standard.

As above, if i is of class type then everything is fine, because the operators become function calls, which impose sequencing.

The rules

The rules are relatively straightforward:

1. The value computations of the arguments of a built-in operator are sequenced-before the value computation of the operator itself.

2. The side effects of a built-in assignment operator or preincrement operator are sequenced-before the value computation of the result.

3. The value computation of any other built-in operator is sequenced-before the side effects of that operator.

4. The value computation and side-effects of the left-hand side of the built-in comma operator are sequenced-before the value computation and side-effects of the right-hand side.

5. All value computations and side effects of a full expression are sequenced-before the next full expression.

6. The value computation and side effects of the arguments of a function call are sequenced before the first full expression in the function.

7. The value computation and side effects of everything inside a function are sequenced-before the value computation of the result.

8. For any two function calls in the full expression, either the value computation of the result of one is sequenced-before the call to the other, or vice-versa. If no other rule specifies the ordering, the compiler may choose.

   Thus in a()+b(), either a() is sequenced-before b(), or b() is sequenced-before a(), but there is no rule to specify which.

9. If there are two side effects that modify the same variable, and neither is sequenced-before the other, the code has undefined behaviour.

10. If there is a side effect that modifies a variable, and a value computation that reads that variable, and neither is sequenced-before the other, the code has undefined behaviour.

Seeto

I think you got the first case wrong. ++i is equivalent to (i=i+1) and assignment value computation is sequenced after the side effect "In all cases, the assignment is sequenced after the value computation of the right and left operands, and before the value computation of the assignment expression." (section 5.17 [expr.ass] in my pdf) therefore the two write operations are sequenced and i=++i is valid. This also means that the new rules are different from old rules even in case of a single thread (i=++i is UB in old C++). – Marlyn

You are right that ++i is equivalent to i+=1. (5.3.2). I am not sure your conclusion follows. I'll have to recheck. – Seeto

Answer 2

This is in my opinion a much more complex rule than the old rule of sequence points, and I'm not 100% positive I understood it right... anyway IIUC it all boils down to if to get the value you need the side effect to have been already applied.

First case

i = ++i;

Here to do the assignment you need the value of the right part, and to get that value you need the side effect to have been already applied; therefore here the assignment is sequenced after the increment and all is fine. The important point here is that to do the assignment you need the value of RHS and only the address of LHS.

To recap:

1. assignment is sequenced after &i and ++i
2. ++i is sequenced after the increment
3. (transitivity) assignment is sequenced after increment

The value of i is read only once, after the increment. It is written twice, once by the increment and once by the assignment, but these two operations are sequenced (first the increment, then the assignment).

Second case

a[++i] = i;

Here instead you need the value of i for the RHS and the value of ++i for LHS. These two expressions however are not sequenced (the assignment operator is not imposing a sequencing) and therefore the result is undefined.

To recap:

1. assignment is sequenced after &a[++i] and i
2. &a[++i] is sequenced after ++i
3. ++i is sequenced after the increment

Here the value of i is read twice, once for the LHS of assignment and once for the RHS. The LHS part also does a modification (the increment). This write access and the read access of the assignment RHS are however not sequenced in respect to each other, and therefore this expression is UB.

Final rant

Let me repeat that I'm not sure of what I just said... my strong opinion is that this new sequenced before/after approach is much harder to understand. The new rules hopefully only made some expressions that were UB before now well defined (and UB is the worst possible result), but it also made the rules much more complex (it was just "don't change the same thing twice between sequence points"... you didn't have to do a mental topological sort to guess if something was UB or not).

In a sense the new rules did no damage to C++ programs (UB is the enemy, and now there's less UB in this area) but did a damage to the language by increasing complexity (and for sure something C++ didn't need was added complexity).

Note also that the funny thing about ++i is that the returned value is an l-value (that's why ++ ++ i is legal), so it's basically an address and it was not logically needed that the returned value is sequenced after the increment. But the standard says so and this is the rule you need to burn into your neurons. Of course to have a "usable" ++i you want the users of the value to get the updated value, but still as far as the ++ operator see things (it's returning an address that is unaffected by the increment) this sequencing was not formally needed.

With new rules you not only are needed to do a mental topological sort to see if an expression is valid, but you also need to do that using arbitrary sequence relations that you just need to memorize.

While of course you as a programmer will hopefully never write code that changes the same value multiple times without a crystal-clear sequence, still you will be faced with bugs in code written by other programmers... where things are not as clear and where you now need to think harder to just understand if something is legal C++ or not.

Marlyn

Oh, wow. I wasn't aware that this kind of rule change had occurred at all. I agree with your assessment. I wish whoever -1'ed your answer would give a reason. – Nutation

Perhaps the stricter rules for before/after were required in relation to the synchronizes-with relations needed for threading. Consider if the left/right side of the equation is an atomic the ordering now becomes more important. – Condescending

@Omnifarious: I'm used to C++ zealots that just start screaming like crazy once you say that C++ is not the most perfect language in the world. I like C++, but I think complexity was the one of the big problems of C++. The committee instead thought that speed was the problem (!) so now we have much more complex rules for example about r-value references (x&&) and copy constructor and assignment operator default implementation. – Marlyn

@6502: I agree that C++ is complex, however I disagree about the speed only focus. The move semantics are semantics. Their introduction allow the error-prone auto_ptr to be eliminated and replaced by the much better unique_ptr. Likewise, the introduction of threads allow a standardisation of existing practice toward better portability. Speed is a focus of C++, and weighs heavily on each decision, but it is not the sole focus. As for sequence points and sequence before/after; the new rules may be more complex, but I also tend to think they are more intuitive. Time will tell. – Recto

@Marlyn - I think complexity is a problem, but not one the standards committee can do a whole lot about. Except, of course, not add to the problem. I think though, that exploring the design space of how to make C++ faster is very worthwhile. I keep hoping someone will wrap up all these lessons in a nice, shiny, new language that has no automatic garbage collection or other missing 'features' and instead tries to be what C++ is, but streamlined and elegant. – Nutation

@Omnifarious: to be honest, I would be disappointed if a new language was created that had no garbage collection. I understand that lean and mean is an issue, but garbage collection is a keystone of modern languages. On the other hand, the Rust pointer types are quite interesting: the built-in equivalent of unique_ptr within the language help ensuring that some variables will not need garbage collection at all. – Recto

@MatthieuM.: I don't know enough C++11 to be able to grasp the reasons for those choices. I read somewhere that the main point of rvalue references was move construction, needed for speed. If this is the case then I think it's a bad move (if). Of course I agree that auto_ptr was a bad idea, and I never actually used it despite initial sponsoring by some gurus. I also agree time will tell... my simple mind (for now) hopes C++11 won't be a success: I fear C++11 requires even more debugging hours per line than the already high count of C++. – Marlyn

Sorry but I still do not understand, specifically this part - "Here to do the assignment you need the value of the right part, and to get that value you need the side effect to have been already applied, therefore here the assignment is sequenced after the increment ..". Why does = impose a sequencing in the first example but not in the second? Thanks! – Angellaangelle

@Lazer: you need the address of the left-hand expression and the value of the right-hand expression before you can perform the assignment. In the first case i = ++i, the address of i is known and ++i need be evaluated before the assignment (as you need the value), so everything is fine as ++i need be evaluated before the result of this expression is assigned. The order is perfectly defined. In the second case though a[++i] and i must both be evaluated before the assignment but both expression overlap. Depending on which you compute first, the value assigned change. – Recto

@6502: Oh, speed is a non-negligible factor in C++, but I don't think that it was the primary factor for move semantics. It is an interesting fallout, but we had similar speed with copy elision already and we could already use swap a lot (for hand-made versions had a similar code to today's move constructors). – Recto

IMO it makes sense to forget about the new rules and just go with the good old "Thou shalt not both read and modify a memory location in the same full-expression." It keeps the code much cleaner and you don't have to worry about UB. – Tenement

@Lazer: = is not imposing a sequencing between left and right part, but the assignment itself is sequenced after them. The value of the right part is however sequenced after the side effect of increment (because the standard says this explicitly, despite the value being indeed an address not affected by the increment) so due to transitivity you get that the assignment is sequenced after the increment and everything is fine. If you think this is too complex I agree... – Marlyn

@JohannesD: This is a good idea, but unfortunately is not enough: when you need to debug a program you want first to understand where the problem is. If who wrote the code didn't follow the old simplified rules you still have to think in terms of sequenced-before/after to understand if a piece of code is problematic or not. Like in the case of auto_ptr not using it is good but not enough, because you may need to understand why a program (not written by you) is using it and is behaving strangely. Pretending that auto_ptr doesn't exist works for writing new programs, but not for debugging. – Marlyn

@MatthieuM. - I flat out refuse to use any language that has garbage collection when I care about performance in any significant way. I use Python, and it is garbage collected, but I don't use it when I care about performance. The various smart pointer types in C++11 are a sort of garbage collection, but I get to choose exactly when and where to apply them, and that makes all the difference. – Nutation

@Omnifarious: well, Rust pushes the boundary a bit further with its 3 pointer types. One type simply forces move semantics onto you (a single owner at any time) while the 2 others are garbage collected (one within a single thread and the other shared across threads). This means that you choose whether to use garbage collection or not, and so the critical parts can be implemented without it. – Recto

@MatthieuM. - Well, I'll have to look at it then. My main complaint is that when a language becomes garbage collected it generally loses the ability for larger types to include instances of smaller, non-primitive types by value or to declare non-primitive types as local variables that have their values stored on the stack. This destroys locality of reference. It also creates an artificial division between 'primitive' types and user defined types, though there are language that don't, and end up extremely inefficient as a result. – Nutation

@Omnifarious: oh yes, I definitely agree that boxing of primitive types definitely is an issue for performance critical code. Stack allocation is unfortunately a bit more difficult to tackle, as you then need escape analysis, which is not trivial unfortunately. – Recto

Perhaps the new rules just seem to look harder to you because the old rules never were sufficient precise. They just left out detail. It is like describing the world with "God made it" and all becomes very easy. – Ranunculus

@JohannesSchaub-litb: I'm not sure I understand your point... if the old rules don't cover all cases and in some case they leave the behavior undefined... isn't the behavior "undefined" in those cases? Or do you mean they make undecidable if the behavior is defined? Or undecidable if it's decidable if the behavior is defined? Or undecidable if it's undecidable if it's undecidable if the beh**<stack overflow error>** – Marlyn

@AnthonyWilliams: No. On i=++i I think it's your answer that is wrong. 5.17.1(N3126=10-0116) says that the value computation of the assignment expression itself is sequenced after the assignment. ++i is equivalent to (i+=1) (5.3.2) and therefore its value computation is sequenced after the increment. The main assignment in i=++i is therefore sequenced by transitivity after the increment assignment and the expression is valid. The very fact that someone claiming your C++ experience can get this wrong also confirms (albeit anecdotally) that my rant on complexity is not totally foolish. – Marlyn

@6502: You are right. This was a deliberate change as per the DR that Johannes pointed out. It was silly of me to miss it. – Seeto

@6502: In my opinion, C++ became more "complete" and usable with the addition of rvalue references and move semantics. Previously, there were many cases where you had to copy even if you didn't want to or if you couldn't: you cannot copy a fstream object and you don't want to copy a map<string, big> object, but copying them was the only way to return them from a function. Hence the trick of declaring a default-initialized object and passing it as a lvalue reference, which sucks. Now, with move semantics, those old days are gone. – Crossgarnet

@Marlyn Final Rant: The new sequencing rules are more precise than the old rules, though they may appear a little more complex. (They could feel more intuitive, once you understand the concept of partial order relations.) Previously, sequencing was defined only in terms of seq-points on a 1-dimension line, and there were cases where you had to either impose excessive seq-points or get UB; e.g. you cannot represent an ordering relation of a<b<e && c<d<e. Now you can, and the new rules allow finer control. That's why some expressions that previously caused UB can now have well-defined behavior. – Crossgarnet