Recent

Author Topic: Boolean evaluation  (Read 9148 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: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
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;

If your first answer is no, you are not asked for second time. Try it.

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: 33
  • ^ Happy coder :)
    • Coppershade
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;

If your first answer is no, you are not asked for second time. Try it.

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. :)
Pushed on stack: 6502 / Z80 / Amiga / ARM assembler, Pascal, Delphi, Lingo, Obj-C, Lua, FPC, C# + web front-/backend.

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
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
    • me on Mastodon
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

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
Re: Boolean evaluation
« Reply #6 on: January 04, 2019, 11:45:47 am »
I thought I explained that? Anyway.... ;D

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 »
Specialize a type, not a var.

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: Boolean evaluation
« Reply #7 on: January 04, 2019, 02:29:03 pm »
I thought I explained that? Anyway.... ;D

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


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

Instead of:

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: 33
  • ^ Happy coder :)
    • Coppershade
Re: Boolean evaluation
« Reply #8 on: January 04, 2019, 02:45:58 pm »
Appreciate the link dubst3pp4.  :)

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.
Pushed on stack: 6502 / Z80 / Amiga / ARM assembler, Pascal, Delphi, Lingo, Obj-C, Lua, FPC, C# + web front-/backend.

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
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: ');
  25.   readln(N);
  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.  
  47.   ReadLn;
  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: 2222
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

  • Sr. Member
  • ****
  • Posts: 258
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.

 

TinyPortal © 2005-2018