Jump to content
Mike Torrettinni

Micro optimization: Math.InRange

Recommended Posts

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:

image.png.2caa377fa5415eb6706af3267d15b87b.png

 

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:

image.png.25bde2733a294f3a6d964a3532788a7e.png

 

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.

 

 

 

 

 

Share this post


Link to post

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.

 

 

 

  • Thanks 1

Share this post


Link to post
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?

Share this post


Link to post

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

if ... then asm nop end;
 

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

 

Share this post


Link to post
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.

  • Thanks 1

Share this post


Link to post

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.

Share this post


Link to post

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

  • Thanks 1

Share this post


Link to post
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:

image.thumb.png.b194d7d0cc33c9c416a1d97ff0b7f830.png

Share this post


Link to post
5 minutes ago, Vandrovnik said:

I think it does not produce such jumps:

image.thumb.png.b194d7d0cc33c9c416a1d97ff0b7f830.png

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.

Share this post


Link to post
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.

Share this post


Link to post
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?

Share this post


Link to post
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.

Share this post


Link to post
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 by Rollo62
  • Thanks 1

Share this post


Link to post

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;

 

  • Like 2

Share this post


Link to post
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;

Share this post


Link to post
47 minutes ago, Clément said:

The code for IsInRangeEx and isInRangeEx2:

... can cause overflows. Consider the extremes.

  • Like 1

Share this post


Link to post
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 😞

Share this post


Link to post
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.

 

Share this post


Link to post
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 by Stefan Glienke

Share this post


Link to post
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));

 

Share this post


Link to post
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.

Share this post


Link to post
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.

Share this post


Link to post
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?

 

 

Share this post


Link to post

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

  • Like 4
  • Haha 1

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×