6 ms·

Why would you even need non-shortcircuiting behavior in boolean expressions? Because either side of the operator has side effects that you want to happen uncond

by anyfoo 5y ago

Why would you even need non-shortcircuiting behavior in boolean expressions? Because either side of the operator has side effects that you want to happen unconditionally? Please just write it out as an extra statement then instead of hammering it into place with an implicit coercion to an integer type only so you can abuse bitwise AND and OR only to force that side effect to... you can see why this is probably not the most elegant idea.

slavik81 5y ago
Matt Godbolt gave an example of a significant performance hit caused by unnecessary short-circuiting in his CppCon 2019 talk[1]. EDIT: Deleted tangent. [1]: https://youtu.be/HG6c4Kwbv4I?t=45m https://youtu.be/HG6c4Kwbv4I?t=45m
- thaumasiotes 5y ago
  This example is interesting enough that it deserves to be written up for convenience. The reason there is a performance hit is that the example involves a lot of mispredicted branches. The setup is that we have a large number of tiny triangles, we cast a ray in a random direction, and we want to detect whether it intersects any of the triangles. The summarized code looks like this: for (/* all triangles */) { auto u = calcU(/*...*/); if (u < 0 || u > 1) { continue; } auto v = calcV(/*...*/); if (v < 0 || u + v > 1) { continue; } auto dist = calcD(/*...*/); if (dist < nearest) { nearest = dist; } } So what's happening? We calculate the (x,y) coordinates of the point where our ray intersects the plane in which the triangle lies. We convert those (x,y) coordinates to (u,v) coordinates, where the vectors u and v are parallel to two sides of the triangle. (And equal in length.) In our transformed (u,v) space, determining whether a point lies inside the triangle is very easy. With the origin at the corner of the triangle from which the u and v sides emanate, a point is out of bounds if its u-coordinate lies outside the interval [0, 1], or if its v-coordinate lies outside [0, 1-u]. That's what the ifs after calcU and calcV are checking. When we detect that a point is out of bounds, we move on to the next triangle. The triangles are small and the ray is random, so the intersection of the ray with the plane will strike at a random point. It is almost always the case that the point will lie outside the triangle. This means that the full conditional (u < 0 || u > 1) will almost always be false. But the two subconditions u < 0 and u > 1 will each be true 50% of the time. They are individually impossible to predict, which causes branch prediction on the first one, u < 0, to fail about 50% of the time. But they are jointly easy to predict. There is a huge performance gain from switching to (u < 0 | u > 1) -- in this case, 50% of the time we will do the work of calculating whether u > 1 even though we didn't have to. But the reward we get for that extra work is that branch prediction drops from a 50% failure rate (actually 45%) to a very low failure rate. Including the v-coordinate makes the full check, ((u < 0) | (u > 1) | (v < 0) | (u + v > 1)), even more easy to predict. We've decided to guarantee that we will always do the full amount of work, and most of it is unnecessary. But it's easier to do 2x or more the amount of work and test a condition that fails consistently than to do less work and keep having to clear the instruction pipeline.
MauranKilom 5y ago
What I would like to write in unit tests: for (auto x : y) ok &= check(x); That gets you angry messages from static analysis, so you probably have to write (since there is no corresponding assignment operator) for (auto x : y) ok = ok && check(x); ...except now you don't actually perform checks after the first failure. That may or may not be intentional (or even confusing - depending on logging). What you'd really need to write to preserve the original logic is for (auto x : y) ok = check(x) && ok; Now the `&& ok` is much easier to miss (both in writing and reading) and the intent is much less clear. I really do wonder why the standard doesn't just specify the behavior of bool & bool. Is it just because of holdover from C?
- dataflow 5y ago
  > I really do wonder why the standard doesn't just specify the behavior of bool & bool. Confused about your question. Did you have a typo? bool & bool is valid in C++.
  - thaumasiotes 5y ago
    I'm guessing the question is related to this complaint: > What I would like to write in unit tests: > ok &= check(x); > That gets you angry messages from static analysis
    - dataflow 5y ago
      That has nothing to do with the standard though? The behavior is well-defined, it's just compilers warning about use of & tending to be error-prone (rightly or wrongly).
- gpderetta 5y ago
  I lost track how many times I have been bitten by the ok = ok && ... trap.
josefx 5y ago
Reduced unit test complexity? Short circuiting implies more branches, more branches means more tests for 100% coverage. Of course for that to be a downside someone would have to write tests for security critical code, which obviously did not happen.
- snovv_crash 5y ago
  That is just gaming your coverage stats, there are still the different branches they just aren't visible now.
  - thaumasiotes 5y ago
    That's not true. Compare `( a() || b() || c() ) ? yes() : no()` to `( a() | b() | c() ) ? yes() : no()`. In the second case, there are two paths through the code: a() b() c() yes() a() b() c() no() But in the first case, there are more paths: a() /* true */ yes() a() /* false */ b() /* true */ yes() a() /* false */ b() /* false */ c() /* true */ yes() a() /* false */ b() /* false */ c() /* false */ no() That is because there are fewer branches in the second statement (just one) than there are in the first statement (three).
    - GoblinSlayer 5y ago
      The code is correct if you hit yes() and no() correctly depending on three conditions. There are 8 possibilities in both cases and thus you need 8 tests in both cases. Shortcircuiting is optimization, it doesn't reduce complexity of the logic.
      - thaumasiotes 5y ago
        That is a concern, but it's not one related to how many branches exist in the code. "How did we get here?" and "Are we in the right place?" are distinct questions.
    - snovv_crash 5y ago
thaumasiotes 5y ago
> Why would you even need non-shortcircuiting behavior in boolean expressions? Because either side of the operator has side effects that you want to happen unconditionally? Interestingly, the example provided by slavik81 is able to tolerate non-shortcircuiting behavior specifically because no side effects are involved. It's more of a case of "we don't care about the result of this work, but we have to do it anyway, because it's better to do a lot of extra work concurrently than to do only the necessary work sequentially." And doing the extra work is OK because it doesn't have any side effects. If side effects were involved, you'd be stuck needing to short-circuit despite the fact that it's slower. There are also areas in cybersecurity where you'd like the time taken for some operation to be insensitive to the input; short-circuiting is bad there too.
- anyfoo 5y ago
  It's usually wrong to assume that expressions that ultimately have the same effect (such as a || b and a | b when both a and b are simple booleans, so no side effects) will make the compiler generate different code depending on which variant to use. The compiler knows that both variants resolve to the same result with no side effects, so it should try to generate whatever code is more efficient. Depending on several factors, that may be machine code that effectively exhibits short circuit behavior or not, for either expression (so even a|b might end up having a short circuit on the lowest level). This would be different if you, e.g., sprinkle some volatile keywords (which effectively introduces side effects), but then you'd probably still want to take more care and split the expressions up, unless you really don't care about the order of your forced memory accesses (i.e. if I recall correctly, there is no guarantee that a|b will access a first, then b). And that's not even going into barriers.
GoblinSlayer 5y ago
When you check for error conditions shortcircuiting is unlikely and thus useless. if(error1|error2)abort();
- anyfoo 5y ago
  But it semantically resolves to the exact same, and so the compiler will likely treat it the same and optimize for whatever makes most sense. This may both make a written "a|b" short-circuiting, and a written "a||b" non-short-circuiting, as long as the result stays the same (which for simple bool a,b it always does).

by anyfoo 5y ago

slavik81 5y ago

Matt Godbolt gave an example of a significant performance hit caused by unnecessary short-circuiting in his CppCon 2019 talk[1]. EDIT: Deleted tangent. [1]: https://youtu.be/HG6c4Kwbv4I?t=45m https://youtu.be/HG6c4Kwbv4I?t=45m

thaumasiotes 5y ago
This example is interesting enough that it deserves to be written up for convenience. The reason there is a performance hit is that the example involves a lot of mispredicted branches. The setup is that we have a large number of tiny triangles, we cast a ray in a random direction, and we want to detect whether it intersects any of the triangles. The summarized code looks like this: for (/* all triangles */) { auto u = calcU(/*...*/); if (u < 0 || u > 1) { continue; } auto v = calcV(/*...*/); if (v < 0 || u + v > 1) { continue; } auto dist = calcD(/*...*/); if (dist < nearest) { nearest = dist; } } So what's happening? We calculate the (x,y) coordinates of the point where our ray intersects the plane in which the triangle lies. We convert those (x,y) coordinates to (u,v) coordinates, where the vectors u and v are parallel to two sides of the triangle. (And equal in length.) In our transformed (u,v) space, determining whether a point lies inside the triangle is very easy. With the origin at the corner of the triangle from which the u and v sides emanate, a point is out of bounds if its u-coordinate lies outside the interval [0, 1], or if its v-coordinate lies outside [0, 1-u]. That's what the ifs after calcU and calcV are checking. When we detect that a point is out of bounds, we move on to the next triangle. The triangles are small and the ray is random, so the intersection of the ray with the plane will strike at a random point. It is almost always the case that the point will lie outside the triangle. This means that the full conditional (u < 0 || u > 1) will almost always be false. But the two subconditions u < 0 and u > 1 will each be true 50% of the time. They are individually impossible to predict, which causes branch prediction on the first one, u < 0, to fail about 50% of the time. But they are jointly easy to predict. There is a huge performance gain from switching to (u < 0 | u > 1) -- in this case, 50% of the time we will do the work of calculating whether u > 1 even though we didn't have to. But the reward we get for that extra work is that branch prediction drops from a 50% failure rate (actually 45%) to a very low failure rate. Including the v-coordinate makes the full check, ((u < 0) | (u > 1) | (v < 0) | (u + v > 1)), even more easy to predict. We've decided to guarantee that we will always do the full amount of work, and most of it is unnecessary. But it's easier to do 2x or more the amount of work and test a condition that fails consistently than to do less work and keep having to clear the instruction pipeline.

MauranKilom 5y ago

What I would like to write in unit tests: for (auto x : y) ok &= check(x); That gets you angry messages from static analysis, so you probably have to write (since there is no corresponding assignment operator) for (auto x : y) ok = ok && check(x); ...except now you don't actually perform checks after the first failure. That may or may not be intentional (or even confusing - depending on logging). What you'd really need to write to preserve the original logic is for (auto x : y) ok = check(x) && ok; Now the `&& ok` is much easier to miss (both in writing and reading) and the intent is much less clear. I really do wonder why the standard doesn't just specify the behavior of bool & bool. Is it just because of holdover from C?

dataflow 5y ago
> I really do wonder why the standard doesn't just specify the behavior of bool & bool. Confused about your question. Did you have a typo? bool & bool is valid in C++.
- thaumasiotes 5y ago
  I'm guessing the question is related to this complaint: > What I would like to write in unit tests: > ok &= check(x); > That gets you angry messages from static analysis
  - dataflow 5y ago
    That has nothing to do with the standard though? The behavior is well-defined, it's just compilers warning about use of & tending to be error-prone (rightly or wrongly).
gpderetta 5y ago
I lost track how many times I have been bitten by the ok = ok && ... trap.

josefx 5y ago

Reduced unit test complexity? Short circuiting implies more branches, more branches means more tests for 100% coverage. Of course for that to be a downside someone would have to write tests for security critical code, which obviously did not happen.

snovv_crash 5y ago
That is just gaming your coverage stats, there are still the different branches they just aren't visible now.
- thaumasiotes 5y ago
  That's not true. Compare `( a() || b() || c() ) ? yes() : no()` to `( a() | b() | c() ) ? yes() : no()`. In the second case, there are two paths through the code: a() b() c() yes() a() b() c() no() But in the first case, there are more paths: a() /* true */ yes() a() /* false */ b() /* true */ yes() a() /* false */ b() /* false */ c() /* true */ yes() a() /* false */ b() /* false */ c() /* false */ no() That is because there are fewer branches in the second statement (just one) than there are in the first statement (three).
  - GoblinSlayer 5y ago
    The code is correct if you hit yes() and no() correctly depending on three conditions. There are 8 possibilities in both cases and thus you need 8 tests in both cases. Shortcircuiting is optimization, it doesn't reduce complexity of the logic.
    - thaumasiotes 5y ago
      That is a concern, but it's not one related to how many branches exist in the code. "How did we get here?" and "Are we in the right place?" are distinct questions.
  - snovv_crash 5y ago

thaumasiotes 5y ago

> Why would you even need non-shortcircuiting behavior in boolean expressions? Because either side of the operator has side effects that you want to happen unconditionally? Interestingly, the example provided by slavik81 is able to tolerate non-shortcircuiting behavior specifically because no side effects are involved. It's more of a case of "we don't care about the result of this work, but we have to do it anyway, because it's better to do a lot of extra work concurrently than to do only the necessary work sequentially." And doing the extra work is OK because it doesn't have any side effects. If side effects were involved, you'd be stuck needing to short-circuit despite the fact that it's slower. There are also areas in cybersecurity where you'd like the time taken for some operation to be insensitive to the input; short-circuiting is bad there too.

anyfoo 5y ago
It's usually wrong to assume that expressions that ultimately have the same effect (such as a || b and a | b when both a and b are simple booleans, so no side effects) will make the compiler generate different code depending on which variant to use. The compiler knows that both variants resolve to the same result with no side effects, so it should try to generate whatever code is more efficient. Depending on several factors, that may be machine code that effectively exhibits short circuit behavior or not, for either expression (so even a|b might end up having a short circuit on the lowest level). This would be different if you, e.g., sprinkle some volatile keywords (which effectively introduces side effects), but then you'd probably still want to take more care and split the expressions up, unless you really don't care about the order of your forced memory accesses (i.e. if I recall correctly, there is no guarantee that a|b will access a first, then b). And that's not even going into barriers.

GoblinSlayer 5y ago

When you check for error conditions shortcircuiting is unlikely and thus useless. if(error1|error2)abort();

anyfoo 5y ago
But it semantically resolves to the exact same, and so the compiler will likely treat it the same and optimize for whatever makes most sense. This may both make a written "a|b" short-circuiting, and a written "a||b" non-short-circuiting, as long as the result stays the same (which for simple bool a,b it always does).