Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

Author Topic: Boolean evaluation  (Read 7652 times)

typo

• Hero Member
• Posts: 3051
Boolean evaluation
« on: April 19, 2010, 05:48:12 pm »
How is the FPC standard boolean evaluation, complete? Anyone knows?

The \$B directive switches between the two different models of Delphi code generation for the and and or Boolean operators.

In the {\$B+} state, the compiler generates code for complete Boolean expression evaluation. This means that every operand of a Boolean expression built from the and and or operators is guaranteed to be evaluated, even when the result of the entire expression is already known.

In the {\$B-} state, the compiler generates code for short-circuit Boolean expression evaluation, which means that evaluation stops as soon as the result of the entire expression becomes evident in left to right order of evaluation.
« Last Edit: April 19, 2010, 06:07:21 pm by typo »

Zoran

• Hero Member
• Posts: 1611
Re: Boolean evaluation
« Reply #1 on: April 19, 2010, 07:38:23 pm »
Making simple test gives the answer, I just tried:

Code: [Select]
`procedure TForm1.Button1Click(Sender: TObject);begin  if (MessageDlg('1', mtConfirmation, [mbYes, mbNo], 0) = mrYes)       and (MessageDlg('2', mtConfirmation, [mbYes, mbNo], 0) = mrYes) then    ShowMessage('yes, yes');end;`

Only if you put {\$B+} above the procedure, you are asked the second time, regardless of your first answer.

So, the default is short-curcuit.
« Last Edit: April 19, 2010, 07:40:37 pm by Zoran »

typo

• Hero Member
• Posts: 3051
Re: Boolean evaluation
« Reply #2 on: April 19, 2010, 08:07:30 pm »
Thanks.

HenrikErlandsson

• New Member
• Posts: 19
• ^ Happy coder :)
Re: Boolean evaluation
« Reply #3 on: January 04, 2019, 04:21:56 am »
Making simple test gives the answer, I just tried:

Code: [Select]
`procedure TForm1.Button1Click(Sender: TObject);begin  if (MessageDlg('1', mtConfirmation, [mbYes, mbNo], 0) = mrYes)       and (MessageDlg('2', mtConfirmation, [mbYes, mbNo], 0) = mrYes) then    ShowMessage('yes, yes');end;`

Only if you put {\$B+} above the procedure, you are asked the second time, regardless of your first answer.

So, the default is short-curcuit.
This topic is quite old (so guilty of necroing again), but is there a way to thumb up answers on this forum?

I have to type +1?

+1.
Turbo Pascal was the tool of my trade as a young professional.

Zoran

• Hero Member
• Posts: 1611
Re: Boolean evaluation
« Reply #4 on: January 04, 2019, 11:02:49 am »
This topic is quite old (so guilty of necroing again), but is there a way to thumb up answers on this forum?

I have to type +1?

+1.

dubst3pp4

• Jr. Member
• Posts: 86
• Retro computing ~ GNU/Linux
Re: Boolean evaluation
« Reply #5 on: January 04, 2019, 11:35:35 am »
Thanks for trying it out
Btw. I also found the answer in the documentation, have a look at the remark at: https://www.freepascal.org/docs-html-3.0.0/ref/refsu48.html
Jabber: xmpp:marc.hanisch@member.fsf.org -- Support the Free Software Foundation: https://my.fsf.org/donate

• Hero Member
• Posts: 10606
Re: Boolean evaluation
« Reply #6 on: January 04, 2019, 11:45:47 am »
I thought I explained that? Anyway....

Note that this can have major side effects like timing hacks.... That's why I got some bug reports implemented on hashes (already in 3.0.2) . I know this is not obvious  to normal people.
To avoid time differences on different values you need full Boolean evaluation. Shortcuts WILL give time differences and so can be hacked. Timing attacks are my favorite....
Anyway: apart from cryptography or in general linear time relevant code, boolean shortcuts  speed up your code, so usually: use it.

(In general: if you know the equidistribution of an alphabet (maybe for a given language, but that does not matter too much) you can decode a lot. Subsequent  efforts will decode everything.
That's because testing for equidistribution with a timing attack reveals a large part of that distribution. This is not a noobs hack, but tools exist for noobs to do just that, and most  based on a boolean shortcut attack)
« Last Edit: January 04, 2019, 12:11:02 pm by Thaddy »

Zoran

• Hero Member
• Posts: 1611
Re: Boolean evaluation
« Reply #7 on: January 04, 2019, 02:29:03 pm »
I thought I explained that? Anyway....

Did you notice that this topic is from before you registered on the forum?

I'd say, if full evaluation is needed, use it explicitly.

Code: Pascal  [Select][+][-]
1.   if BoolExpresion1 and BoolExpresion2 then
2.     DoSomething;
3.

You might write:

Code: Pascal  [Select][+][-]
1. var
2.   FirstConditionSatisfied: Boolean;
3. ...
4.
5. FirstConditionSatisfied := BoolExpresion1;
6. if BoolExpresion2 then
7.   if FirstConditionSatisfied then
8.     DoSomething;
9.
10.

You may also create a function with two parameters, they will both be evaluated when calling.

Code: Pascal  [Select][+][-]
1. function CheckTwoConditions(Condition1, Condition2: Boolean): Boolean;
2. begin
3.   Result := Condition1 and Condition2;
4. end;
5.
6. ...
7. // then use it instead of direct:
8. if CheckTwoConditions(BoolExpression1, BoolExpression1) then
9.   DoSomething;
10.

Now, interesting question is -- if this function is inlined, will both still be evaluated?

Well, I'm going to test it now.

HenrikErlandsson

• New Member
• Posts: 19
• ^ Happy coder :)
Re: Boolean evaluation
« Reply #8 on: January 04, 2019, 02:45:58 pm »

And yes, I could have tested with a function, or even simpler with division by zero.

Or measure whether I gained time, which was the real goal here. I will check how simple benchmarking is done.
Turbo Pascal was the tool of my trade as a young professional.

Zoran

• Hero Member
• Posts: 1611
Re: Boolean evaluation
« Reply #9 on: January 04, 2019, 02:50:23 pm »
Now, interesting question is -- if this function is inlined, will both still be evaluated?

Well, I'm going to test it now.

Tested.

This is the test programme:
Code: Pascal  [Select][+][-]
1. program Project1;
2.
3. {\$mode objfpc}
4. {\$inline on}
5.
6. function CheckTwoConditions(const Condition1, Condition2: Boolean): Boolean;
7. begin
8.   Result := Condition1 and Condition2;
9. end;
10.
11. function InlineCheckTwoConditions(const Condition1, Condition2: Boolean): Boolean; inline;
12. begin
13.   Result := Condition1 and Condition2;
14. end;
15.
16. var
17.   CallCount: Integer;
18.
19. function IsOne: Boolean;
20. var
21.   N: Integer;
22. begin
23.   Inc(CallCount);
24.   Write('enter 1 or 0: ');
26.   Result := N = 1;
27. end;
28.
29. begin
30.   CallCount := 0;
31.   if IsOne and IsOne then
32.     WriteLn('both true');
33.   WriteLn('Direct check -- IsOne was called ', CallCount, ' times.');
34.   WriteLn;
35.
36.   CallCount := 0;
37.   if CheckTwoConditions(IsOne, IsOne) then
38.     WriteLn('both true');
39.   WriteLn('Check through function -- IsOne was called ', CallCount, ' times.');
40.   WriteLn;
41.
42.   CallCount := 0;
43.   if InlineCheckTwoConditions(IsOne, IsOne) then
44.     WriteLn('both true');
45.   WriteLn('Check through inlined function -- IsOne was called ', CallCount, ' times.');
46.
48. end.
49.

And the output:
Quote
enter 1 or 0: 0
Direct check -- IsOne was called 1 times.

enter 1 or 0: 0
enter 1 or 0: 0
Check through function -- IsOne was called 2 times.

enter 1 or 0: 0
enter 1 or 0: 0
Check through inlined function -- IsOne was called 2 times.

So, you can freely inline this function.

ASerge

• Hero Member
• Posts: 1694
Re: Boolean evaluation
« Reply #10 on: January 04, 2019, 06:12:40 pm »
I use "BOOLEVAL ON" mode only for deep optimization. In this case, double if or inline functions do not help. Example:
Code: Pascal  [Select][+][-]
1. {\$mode objfpc}
2.
3. function InlineCheckTwoConditions(const Condition1, Condition2: Boolean): Boolean; inline;
4. begin
5.   Result := Condition1 and Condition2;
6. end;
7.
8. function AlwaysFalse: Boolean;
9. begin
10.   Result := False;
11. end;
12.
13. function TestNormal(const Condition1, Condition2: Boolean): Boolean;
14. begin
15.   Result := Condition1 and Condition2;
16. end;
17.
18. function TestDoubleIf(const Condition1, Condition2: Boolean): Boolean;
19. begin
20.   if Condition1 then
21.     Result := Condition2
22.   else
23.     Result := False;
24. end;
25.
26. {\$BOOLEVAL ON}
27.
28. function TestWithInline(const Condition1, Condition2: Boolean): Boolean;
29. begin
30.   Result := InlineCheckTwoConditions(Condition1, Condition2);
31. end;
32.
33. function TestWithFullEval(const Condition1, Condition2: Boolean): Boolean;
34. begin
35.   Result := Condition1 and Condition2;
36. end;
37.
38. begin
39.   TestNormal(AlwaysFalse, AlwaysFalse);
40.   TestDoubleIf(AlwaysFalse, AlwaysFalse);
41.   TestWithInline(AlwaysFalse, AlwaysFalse);
42.   TestWithFullEval(AlwaysFalse, AlwaysFalse);
43. end.
Generated code for functions (Intel x64).
TestNormal and TestWithInline equal:
Code: ASM  [Select][+][-]
1.         testb   %cl,%cl
2.         je      .Lj16
3.         testb   %dl,%dl
4.         je      .Lj16
5.         movb    \$1,%al
6.         jmp     .Lj18
7. .Lj16:
8.         movb    \$0,%al
9. .Lj18:
10.         andl    \$255,%eax
11.         ret
TestDoubleIf:
Code: ASM  [Select][+][-]
1.         testb   %cl,%cl
2.         je      .Lj22
3.         movb    %dl,%al
4.         jmp     .Lj25
5. .Lj22:
6.         movb    \$0,%al
7. .Lj25:
8.         andl    \$255,%eax
9.         ret
But TestWithFullEval:
Code: ASM  [Select][+][-]
1.         movb    %dl,%al
2.         andb    %cl,%al
3.         andl    \$255,%eax
4.         ret

del

• Full Member
• Posts: 185
Re: Boolean evaluation
« Reply #11 on: October 18, 2019, 11:50:11 pm »
Thanks for trying it out
Btw. I also found the answer in the documentation, have a look at the remark at: https://www.freepascal.org/docs-html-3.0.0/ref/refsu48.html

Yes. Documentation. Not a big fan of the laboratory approach. Thank you.