Topic: Optimizations for boolean comparisons
Author: NDos Dannyu <ndospark320@naver.com>
Date: Sun, 16 Oct 2016 04:02:54 -0700 (PDT)
Raw View
------=_Part_2848_305726622.1476615774588
Content-Type: multipart/alternative;
boundary="----=_Part_2849_1645429380.1476615774588"
------=_Part_2849_1645429380.1476615774588
Content-Type: text/plain; charset=UTF-8
Please read the following Q&A I posted on Stack Overflow:
http://stackoverflow.com/questions/40069217/comparison-operators-on-booleans-trick
As the answer "hvd" posted states, *P < Q* won't perform better than *!P &&
Q*, as well as the other comparison operators. So I think an optimization
should be there.
More specifically, the right operand of a comparison operator shouldn't be
evaluated if:
1. The left operand of *< *is evaluated to *true*, where the result will
be always *false*,
2. The left operand of *> *is evaluated to *false*, where the result
will be always *false*,
3. The left operand of *<=* is evaluated to *false*, where the result
will be always *true*,
4. The left operand of *>=* is evaluated to *true*, where the result
will be always *true*.
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/676d916d-cbe4-437b-b930-e9ba454a59b0%40isocpp.org.
------=_Part_2849_1645429380.1476615774588
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Please read the following Q&A I posted on Stack Overfl=
ow:=C2=A0<a href=3D"http://stackoverflow.com/questions/40069217/comparison-=
operators-on-booleans-trick">http://stackoverflow.com/questions/40069217/co=
mparison-operators-on-booleans-trick</a><div>As the answer "hvd" =
posted states, <b>P < Q</b>=C2=A0won't perform better than=C2=A0<b>!=
P && Q</b>, as well as the other comparison operators. So I think a=
n optimization should be there.</div><div>More specifically, the right oper=
and of a comparison operator shouldn't be evaluated if:</div><div><ol><=
li>The left operand of <b>< </b>is evaluated to <b>true</b>, where the r=
esult will be always <b>false</b>,</li><li>The left operand of=C2=A0<b>>=
=C2=A0</b>is evaluated to <b>false</b>, where the result will be always=C2=
=A0<b>false</b>,<br></li><li>The left operand of <b><=3D</b> is evaluate=
d to <b>false</b>, where the result will be always <b>true</b>,</li><li>The=
left operand of <b>>=3D</b>=C2=A0is evaluated to <b>true</b>, where the=
result will be always <b>true</b>.</li></ol></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/676d916d-cbe4-437b-b930-e9ba454a59b0%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/676d916d-cbe4-437b-b930-e9ba454a59b0=
%40isocpp.org</a>.<br />
------=_Part_2849_1645429380.1476615774588--
------=_Part_2848_305726622.1476615774588--
.
Author: "D. B." <db0451@gmail.com>
Date: Sun, 16 Oct 2016 13:42:20 +0100
Raw View
--047d7bd91ac05bb46a053efaca57
Content-Type: text/plain; charset=UTF-8
AFAICT comparing booleans using < et al is possible because of implicit
conversion to int, but should not be encouraged as a good means of
comparing bools, which adding special-case optimisations would encourage.
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CACGiwhE4TTYw%2Bhd316Y%3DUhnHV8s%2BkW8PQ%3DDKm7zqcqzyTk7bpw%40mail.gmail.com.
--047d7bd91ac05bb46a053efaca57
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">AFAICT comparing booleans using < et al is possible bec=
ause of implicit conversion to int, but should not be encouraged as a good =
means of comparing bools, which adding special-case optimisations would enc=
ourage.<br><br></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CACGiwhE4TTYw%2Bhd316Y%3DUhnHV8s%2BkW=
8PQ%3DDKm7zqcqzyTk7bpw%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfoo=
ter">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CACGiwhE4=
TTYw%2Bhd316Y%3DUhnHV8s%2BkW8PQ%3DDKm7zqcqzyTk7bpw%40mail.gmail.com</a>.<br=
/>
--047d7bd91ac05bb46a053efaca57--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Sun, 16 Oct 2016 10:15:29 -0700
Raw View
Em domingo, 16 de outubro de 2016, =C3=A0s 04:02:54 PDT, NDos Dannyu escrev=
eu:
> 1. The left operand of *< *is evaluated to *true*, where the result wi=
ll
> be always *false*,
K-map:
P\Q 0 1
0 0 1
1 0 0
Therefore, P<Q is the same as !P && Q, except that the current boolean=20
expression already has your short-circuiting request.
> 2. The left operand of *> *is evaluated to *false*, where the result
> will be always *false*,
P\Q 0 1
0 0 0
1 1 0
Therefore, this is the same as P && !Q.
> 3. The left operand of *<=3D* is evaluated to *false*, where the resul=
t
> will be always *true*,
P\Q 0 1
0 1 1
1 0 1
This is the same as !P || Q.
> 4. The left operand of *>=3D* is evaluated to *true*, where the result
> will be always *true*.
P\Q 0 1
0 1 0
1 1 1
This is the same as P || !Q.
--=20
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/38861546.FLO1N2NSPt%40tjmaciei-mobl1.
.
Author: John Yates <john@yates-sheets.org>
Date: Sun, 16 Oct 2016 14:26:56 -0400
Raw View
--001a113f224ab908e7053eff9a26
Content-Type: text/plain; charset=UTF-8
Replying to the OP.
There are 16 function of 2 Boolean variable A and B. Let us considered the
cases:
- Some depend neither on A nor on B (false, and true).
- Some depend on only a single variable (A, !A, B, !B).
- Some can never be resolved by looking at a single variable (A==B,
A!=B).
- The remaining 8 functions can sometimes be resolved by looking at only
one variable.
In the case of the two most common functions (AND: & and OR: |) C++
provides direct support for explicit short-circuit semantics (&& and ||
respectively). These come up frequently in situations where the expression
need not be materialized because it is being used only as a control
expression (*e.g.* verifying that a pointer is non-null before
dereferencing it). Unlike EXCLUSIVE-OR (A!=B) which has a inverse operator
(==) AND and OR do not, neither in their fully applicative form nor in
their short circuit form. In such cases a programmer is reduced to
applying DeMorgan.
Having accounted for 12 Boolean functions 4 remain (A<B, A<=B, A>B and
A>=B). I do write these occasionally but I never think of these in terms
of short circuiting for correctness. Instead I trust my compiler to
optimize their evaluation. That may involve not only choosing
short-circuit evaluation but also potentially evaluating B before A. As
long as it achieves the correct result why should I care?
/john
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAJnXXohTBwm96wQ5kFo4CU0W_Ui24TQ%2BWpk1SCYUxW4KVBoKug%40mail.gmail.com.
--001a113f224ab908e7053eff9a26
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif">Replying to the OP.</div><div class=3D"gmail_default" s=
tyle=3D"font-family:arial,helvetica,sans-serif"><br></div><div class=3D"gma=
il_default" style=3D"font-family:arial,helvetica,sans-serif">There are 16 f=
unction of 2 Boolean variable A and B.=C2=A0 Let us considered the cases:</=
div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-=
serif"><ul><li>Some depend neither on A nor on B (false, and true).</li><li=
>Some depend on only a single variable (A, !A, B, !B).<br></li><li>Some can=
never be resolved by looking at a single variable (A=3D=3DB, A!=3DB).</li>=
<li>The remaining 8 functions can sometimes be resolved by looking at only =
one variable.</li></ul>In the case of the two most common functions (AND: &=
amp; and OR: |) C++ provides direct support for explicit short-circuit sema=
ntics (&& and || respectively).=C2=A0 These come up frequently in s=
ituations where the expression need not be materialized because it is being=
used only as a control expression (<i>e.g.</i>=C2=A0verifying that a point=
er is non-null before dereferencing it).=C2=A0 Unlike EXCLUSIVE-OR (A!=3DB)=
which has a inverse operator (=3D=3D) AND and OR do not, neither in their =
fully applicative form nor in their short circuit form.=C2=A0 In such cases=
a programmer is reduced to applying DeMorgan.</div><div class=3D"gmail_def=
ault" style=3D"font-family:arial,helvetica,sans-serif"><br></div><div class=
=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif">Having =
accounted for 12 Boolean functions 4 remain (A<B, A<=3DB, A>B and =
A>=3DB).=C2=A0 I do write these occasionally but I never think of these =
in terms of short circuiting for correctness.=C2=A0 Instead I trust my comp=
iler to optimize their evaluation.=C2=A0 That may involve not only choosing=
short-circuit evaluation but also potentially evaluating B before A.=C2=A0=
As long as it achieves the correct result why should I care?</div><div cla=
ss=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif"><br><=
/div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans=
-serif">/john</div><div class=3D"gmail_default" style=3D"font-family:arial,=
helvetica,sans-serif"><br></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAJnXXohTBwm96wQ5kFo4CU0W_Ui24TQ%2BWp=
k1SCYUxW4KVBoKug%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">h=
ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAJnXXohTBwm96w=
Q5kFo4CU0W_Ui24TQ%2BWpk1SCYUxW4KVBoKug%40mail.gmail.com</a>.<br />
--001a113f224ab908e7053eff9a26--
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Sun, 16 Oct 2016 12:15:33 -0700 (PDT)
Raw View
------=_Part_934_1524941165.1476645333227
Content-Type: multipart/alternative;
boundary="----=_Part_935_2138108367.1476645333227"
------=_Part_935_2138108367.1476645333227
Content-Type: text/plain; charset=UTF-8
On Sunday, October 16, 2016 at 2:27:05 PM UTC-4, John Yates wrote:
>
> Replying to the OP.
>
> There are 16 function of 2 Boolean variable A and B. Let us considered
> the cases:
>
> - Some depend neither on A nor on B (false, and true).
> - Some depend on only a single variable (A, !A, B, !B).
> - Some can never be resolved by looking at a single variable (A==B,
> A!=B).
> - The remaining 8 functions can sometimes be resolved by looking at
> only one variable.
>
> In the case of the two most common functions (AND: & and OR: |) C++
> provides direct support for explicit short-circuit semantics (&& and ||
> respectively). These come up frequently in situations where the expression
> need not be materialized because it is being used only as a control
> expression (*e.g.* verifying that a pointer is non-null before
> dereferencing it). Unlike EXCLUSIVE-OR (A!=B) which has a inverse operator
> (==) AND and OR do not, neither in their fully applicative form nor in
> their short circuit form. In such cases a programmer is reduced to
> applying DeMorgan.
>
> Having accounted for 12 Boolean functions 4 remain (A<B, A<=B, A>B and
> A>=B). I do write these occasionally but I never think of these in terms
> of short circuiting for correctness. Instead I trust my compiler to
> optimize their evaluation. That may involve not only choosing
> short-circuit evaluation but also potentially evaluating B before A. As
> long as it achieves the correct result why should I care?
>
Actually, short-circuit evaluation is not allowed. Or at least, so long as
B is something which the compiler cannot guarantee will have visible side
effects, the compiler cannot choose not to evaluate it.
SCE is something people frequently rely on in boolean expressions. It's
used to do things like `if(ptr && ptr->foo())`. That only works if `ptr`
being NULL *guarantees* that `ptr->foo()` is never evaluated.
Now to be fair, I think the OP's idea is wrong for precisely that reason.
Namely... how often can you actually structure your code where SCE can work
with A < B, where both `A` and `B` are boolean expressions? I'd like to see
an example where SCE is *needed*. That is, show me a condition where you
legitimately would use `A < B`, and the evaluation of `B` will lead to a
runtime error/UB if `A` is not true.
And remember: both `A` and `B` must be actual boolean expressions (note
that `ptr` in my above example is not a boolean expression).
--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/5498d3e4-1082-4a07-b742-3a1e89c451ef%40isocpp.org.
------=_Part_935_2138108367.1476645333227
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Sunday, October 16, 2016 at 2:27:05 PM UTC-4, John Yate=
s wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0=
..8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div =
style=3D"font-family:arial,helvetica,sans-serif">Replying to the OP.</div><=
div style=3D"font-family:arial,helvetica,sans-serif"><br></div><div style=
=3D"font-family:arial,helvetica,sans-serif">There are 16 function of 2 Bool=
ean variable A and B.=C2=A0 Let us considered the cases:</div><div style=3D=
"font-family:arial,helvetica,sans-serif"><ul><li>Some depend neither on A n=
or on B (false, and true).</li><li>Some depend on only a single variable (A=
, !A, B, !B).<br></li><li>Some can never be resolved by looking at a single=
variable (A=3D=3DB, A!=3DB).</li><li>The remaining 8 functions can sometim=
es be resolved by looking at only one variable.</li></ul>In the case of the=
two most common functions (AND: & and OR: |) C++ provides direct suppo=
rt for explicit short-circuit semantics (&& and || respectively).=
=C2=A0 These come up frequently in situations where the expression need not=
be materialized because it is being used only as a control expression (<i>=
e.g.</i>=C2=A0verifying that a pointer is non-null before dereferencing it)=
..=C2=A0 Unlike EXCLUSIVE-OR (A!=3DB) which has a inverse operator (=3D=3D) =
AND and OR do not, neither in their fully applicative form nor in their sho=
rt circuit form.=C2=A0 In such cases a programmer is reduced to applying De=
Morgan.</div><div style=3D"font-family:arial,helvetica,sans-serif"><br></di=
v><div style=3D"font-family:arial,helvetica,sans-serif">Having accounted fo=
r 12 Boolean functions 4 remain (A<B, A<=3DB, A>B and A>=3DB).=
=C2=A0 I do write these occasionally but I never think of these in terms of=
short circuiting for correctness.=C2=A0 Instead I trust my compiler to opt=
imize their evaluation.=C2=A0 That may involve not only choosing short-circ=
uit evaluation but also potentially evaluating B before A.=C2=A0 As long as=
it achieves the correct result why should I care?</div></div></blockquote>=
<div><br>Actually, short-circuit evaluation is not allowed. Or at least, so=
long as B is something which the compiler cannot guarantee will have visib=
le side effects, the compiler cannot choose not to evaluate it.<br><br>SCE =
is something people frequently rely on in boolean expressions. It's use=
d to do things like `if(ptr && ptr->foo())`. That only works if =
`ptr` being NULL <i>guarantees</i> that `ptr->foo()` is never evaluated.=
<br><br>Now to be fair, I think the OP's idea is wrong for precisely th=
at reason. Namely... how often can you actually structure your code where S=
CE can work with A < B, where both `A` and `B` are boolean expressions? =
I'd like to see an example where SCE is <i>needed</i>. That is, show me=
a condition where you legitimately would use `A < B`, and the evaluatio=
n of `B` will lead to a runtime error/UB if `A` is not true.<br><br>And rem=
ember: both `A` and `B` must be actual boolean expressions (note that `ptr`=
in my above example is not a boolean expression).<br></div></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/5498d3e4-1082-4a07-b742-3a1e89c451ef%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/5498d3e4-1082-4a07-b742-3a1e89c451ef=
%40isocpp.org</a>.<br />
------=_Part_935_2138108367.1476645333227--
------=_Part_934_1524941165.1476645333227--
.