Micro optimization: Math.InRange

[Mike Torrettinni 198]

I have some reports that use For loop with condition of value between 2 numbers like this:

for i := 1 to n do
  if (Data[i].ProjId >= X) and (Data[i].ProjId <= Y) then

So, to refactor and simplify code, I looked into InRange function in System.Math unit, but why is it designed this way:

 

function InRange(const AValue, AMin, AMax: Integer): Boolean;
var
  A, B: Boolean;
begin
  A := (AValue >= AMin);
  B := (AValue <= AMax);
  Result := B and A;
end;

Why does it need 2 variables, if simple Result := (AValue >= AMin) and (AValue <= AMax); is all that is needed.

 

So, I measured the performance difference with function without variables:

function IsInRange(const AValue, AMin, AMax: Integer): Boolean; inline;
begin
  Result := (AValue >= AMin) and (AValue <= AMax);
end;

And is a little faster. But they are both still 100% slower than just If statement:

 

32bit:

 

and once again we see how 64bit is so much worse than 32 bit, while single line function is almost 20% faster than Math.InRange:

 

Why would they design function with 2 variables, if they are useless? Is it just readability or am  missing something obvious?

 

and code:

 

program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils, System.Math, System.Diagnostics;

const cLoop: integer = 10000000000;
var
  vSW: TStopWatch;

// Single line function replacing System.Math.InRange
function IsInRange(const AValue, AMin, AMax: Integer): Boolean; inline;
begin
  Result := (AValue >= AMin) and (AValue <= AMax);
end;

procedure Test1;
var i, a, b: integer;
begin
  a := 999;
  b := 999999;
  vSW := TStopwatch.StartNew;
  for i := 1 to cLoop do
    if System.Math.InRange(i, a, b) then;
  writeln('Math.InRange: '+vSW.ElapsedMilliseconds.ToString);
end;

procedure Test2;
var i, a, b: integer;
begin
  a := 999;
  b := 999999;
  vSW := TStopwatch.StartNew;
  for i := 1 to cLoop do
    if IsInRange(i, a, b) then;
  writeln('IsInRange:    ' + vSW.ElapsedMilliseconds.ToString);
end;

procedure Test3;
var i, a, b: integer;
begin
  a := 999;
  b := 999999;
  vSW := TStopwatch.StartNew;
  for i := 1 to cLoop do
    if (i >= a) and (i<=b) then;
  writeln('If:           ' + vSW.ElapsedMilliseconds.ToString);
end;

begin
  Test1;
  Test2;
  Test3;
  Readln;
end.

 

 

 

 

 

[Vandrovnik 214]

Your cLoop constant is out of range, so I deleted one zero.

Results on an old i7 920, Delphi 10.4.2 Pro, Release:

32bit:
Math.InRange: 1083
IsInRange:    766
If:           759

64bit:
Math.InRange: 722
IsInRange:    725
If:           721

K.

 

 

 

[Mike Torrettinni 198]

4 minutes ago, Vandrovnik said:

Your cLoop constant is out of range, so I deleted one zero.

Thanks, rookie mistake.

 

5 minutes ago, Vandrovnik said:

64bit: 
Math.InRange: 722 
IsInRange:    725 
If:           721

 

Thanks, I assume 64bit got some optimization. Nice!

 

 

But, is interesting how your benchmark shows IF almost same as IsInRange, 32bit, but on my PC it shows 100% difference.  Do you have any ideas why that is?

[Vandrovnik 214]

When you have something after "then", things change.

if ... then asm nop end;
 

32bit:
Math.InRange: 1081
IsInRange:    1078
If:           1077

 

[Mike Torrettinni 198]

3 hours ago, Vandrovnik said:

if ... then asm nop end;

What would be nop for 64bit, since asm is not available?

[Vandrovnik 214]

6 hours ago, Mike Torrettinni said:

What would be nop for 64bit, since asm is not available?

I used "inc(x);" for 64bit (global variable).

You can have nop in a procedure:
 

procedure Nop; assembler;
 asm
 nop
end;

But as far as I know, this procedure cannot be inlined, so there will be a call.

[Rollo62 536]

Beside InRange, which I use for >=1-based indices,

I have defined my "InIndex" function, which is doing the same comparison, but optimized for 0-based indices,

as proposed for example also here.

Preferable I am using "InIndex" in my code.

[Stefan Glienke 2002]

While your assessment on Math.InRange is true (it is coded in a bad way plus the compiler produces way too many conditional jumps - https://quality.embarcadero.com/browse/RSP-21955) you certainly need to read some material on how to properly microbenchmark and how to read assembly.

 

First of all, even though the Delphi compiler is pretty terrible at optimizing away dead code it might omit the if statement if there is nothing to do after it.

Second - be careful if one of your loops spans multiple cache lines while others don't this affects the outcome slightly and can in such a case affect the result in a noticeable way.

Third - with a static test like this you prove nothing - the branch predictor will do its job. If you want to benchmark the raw performance of one vs the other you need to give it random data which does not follow the "not in range for a while, in range for a while, not in range until the end" pattern

[Vandrovnik 214]

14 minutes ago, Stefan Glienke said:

While your assessment on Math.InRange is true (it is coded in a bad way plus the compiler produces way too many conditional jumps - https://quality.embarcadero.com/browse/RSP-21955) you certainly need to read some material on how to properly microbenchmark and how to read assembly.

I think it does not produce such jumps:

[Stefan Glienke 2002]

5 minutes ago, Vandrovnik said:

I think it does not produce such jumps:

Indeed here it's the opposite, due to the way it's written it always has to perform both checks (see my third point).

But depending on what you do after the if it could be done completely branchless.

[Mike Torrettinni 198]

3 hours ago, Stefan Glienke said:

Third - with a static test like this you prove nothing - the branch predictor will do its job. If you want to benchmark the raw performance of one vs the other you need to give it random data which does not follow the "not in range for a while, in range for a while, not in range until the end" pattern

I see. It's kind of hard to measure the performance, when adding additional conditions. I tried this:

 

for i := 1 to cLoop do
  if i mod 3 = 0 then
    if System.Math.InRange(i, i+1, b) then asm nop end // every 3rd will not meat criteria
  else
    if System.Math.InRange(i, a, b) then asm nop end;

And results are pretty much similar in percentages to each other, of course each test takes much longer now.

[Mike Torrettinni 198]

4 hours ago, Rollo62 said:

Beside InRange, which I use for >=1-based indices,

I have defined my "InIndex" function, which is doing the same comparison, but optimized for 0-based indices,

as proposed for example also here.

Preferable I am using "InIndex" in my code.

Why would comparison be different, 1-based or 0-based, if 0 is already in range, then starting point is -1. No?

[Stefan Glienke 2002]

29 minutes ago, Mike Torrettinni said:

I see. It's kind of hard to measure the performance, when adding additional conditions. I tried this:

 

for i := 1 to cLoop do
  if i mod 3 = 0 then
    if System.Math.InRange(i, i+1, b) then asm nop end // every 3rd will not meat criteria
  else
    if System.Math.InRange(i, a, b) then asm nop end;

And results are pretty much similar in percentages to each other, of course each test takes much longer now.

And even that depending on the CPU generation can possibly be detected by the branch predictor because it's a fixed pattern.

You need a random sequence of numbers that you check against.

However, keep in mind what exact use case you are benchmarking vs what you actually use this function for. Is it random data that needs to be checked for in range?

If you have a loop where at some point the counter is in range and at some point runs out of range then the loop counter itself should be limited to just run over the numbers that are in range.

[Rollo62 536]

22 minutes ago, Mike Torrettinni said:

Why would comparison be different, 1-based or 0-based, if 0 is already in range, then starting point is -1. No?

function InIndex( AIndex : Cardinal; ACount : Cardinal ) : Boolean;
begin
    if AIndex < ACount then  // Only need to compare against ACount
        Result := True
    else
        Result := False;
end;

 

Edited May 12, 2021 by Rollo62

[Clément 148]

I love these topics.

Under 64 bits:

Math.InRange: 859
IsInRange:    858
If:           860
IsInRangeEx:  858
IsInRangeEx2: 858


Under 32bits:

Math.InRange: 1288
IsInRange:    906
If:           906
IsInRangeEx:  858
IsInRangeEx2: 858

The code for IsInRangeEx and isInRangeEx2:

function IsInRangeEx(const AValue, AMin, AMax: Cardinal): Boolean; inline;
begin
  Result := (AValue - AMin) <= (aMax - aMin);
end;

function IsInRangeEx2(const AValue, AMin, AMax: Integer): Boolean; inline;
begin
  Result := ((AValue-AMax)*(aValue-AMin) <= 0);
end;

 

[Mark- 29]

32 minutes ago, Clément said:

I love these topics.

 

function IsInRangeEx(const AValue, AMin, AMax: Cardinal): Boolean; inline;
begin
  Result := (AValue - AMin) <= (aMax - aMin);
end;

 

 

I guess I am missing something. Perhaps I need more sleep.

if IsInRangeEx(5,10,20) then
 beep;

[Anders Melander 1782]

47 minutes ago, Clément said:

The code for IsInRangeEx and isInRangeEx2:

... can cause overflows. Consider the extremes.

[Clément 148]

28 minutes ago, Anders Melander said:

.. can cause overflows. Consider the extremes.

IsInRangeEx is using Cardinals as parameters. The ideia is to use the unsigned type. In the example Cardinal( 5 - 10 ) = 4294967291 as expected. IsInRangeEx will not accept negative numbers...
Using in extreme cases like: IsInRangeEx(cardinal(-2),Cardinal(-3),Cardinal(-1)) will also work.
IsInRangeEx2 will work with negative numbers.

 

I cannot see the overflows 😞

[Mark- 29]

10 minutes ago, Clément said:

IsInRangeEx will not accept negative numbers...

 

I cannot see the overflows 😞

Negative numbers are not passed to the function. The example is perfectly legit.

Exceptions do occur.

 

[Stefan Glienke 2002]

29 minutes ago, Clément said:

I cannot see the overflows 😞

Simple: AValue-AMin causes an overflow when AMin is bigger than AValue.

Your code is shifting the non-zero-based range to a zero-based range causing AValue to possibly become <0.

In fact, running the very benchmark code Mike posted will cause it!

 

Edited May 12, 2021 by Stefan Glienke

[Vandrovnik 214]

22 minutes ago, Clément said:

I cannot see the overflows 😞

IsInRangeEx looks OK for interval in ascending order.

But in these cases, first one returns false, second one true:

writeln(IsInRangeEx(10, 12, 8));
writeln(IsInRangeEx(316084043, 3932079699, 3000547150));

 

[Anders Melander 1782]

11 minutes ago, Vandrovnik said:

IsInRangeEx looks OK for interval in ascending order.

No. As Stefan pointed out, if AMin is smaller than AValue...

IsInRangeEx(0, 1, 2);

...you will get an Integer Overflow.

[Vandrovnik 214]

Just now, Anders Melander said:

No. As Stefan pointed out, if AMin is smaller than AValue...

IsInRangeEx(0, 1, 2);

...you will get an Integer Overflow.

Yes, but if you disable these checks, results for ascending intervals are OK.

[Mike Torrettinni 198]

3 hours ago, Stefan Glienke said:

If you have a loop where at some point the counter is in range and at some point runs out of range then the loop counter itself should be limited to just run over the numbers that are in range. 

Yes, that is how my data is,  in data array indexes of 1..1000 a sub-range is always continuous, 10..50, 300..400, sometimes full range 1..1000. 

What you are suggesting I would need to pre-process data and remember for each sub-range To and From indexes, and then I could loop just the sub-range. Right?

 

 

[David Heffernan 2345]

I'm betting that improving the performance of InRange has no impact on the performance of these reports.