Why is TArray.BinarySearch slower than normal binary search function?

[Mike Torrettinni 198]

My simple test shows TArray.BinarySearch is about 6x slower than custom binary search function:

GetName_TArrayBinarySearch: 858
GetName_CustomBinarySearch: 131

 

I was expecting similar timings. Is this just a fact or did I set up this example wrongly:

 

program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils, System.Generics.Collections, System.Generics.Defaults, System.Math, System.Diagnostics;

type
  TDataLine = record
    SeqNo: integer;
    CustomName: string;
  end;

const cNOfORecords = 1000000;
var xData: TArray<TDataLine>;

procedure PrepData;
var i: Integer;
begin
  SetLength(xData, cNOfORecords);
  for i := 0 to cNofORecords do
  begin
    xData[i].SeqNo := i + 1;
    xData[i].CustomName := i.ToString;
  end;
end;

function GetName_TArrayBinarySearch(const aData: TArray<TDataLine>; const aItem: TDataLine): string;
var vIdx: integer;
begin
  if TArray.BinarySearch<TDataLine>(aData, aItem, vIdx,
    TComparer<TDataLine>.Construct(
      function (const Left, Right: TDataLine): Integer
      begin
       Result := CompareValue(Left.SeqNo, Right.SeqNo);
      end
      ))
  then
      Result := aData[vIdx].CustomName;
end;

function GetName_CustomBinarySearch(const aData: TArray<TDataLine>; const aItem: TDataLine): string;
var L, H, i, c: Integer;
begin
  Result := '';
  L := 0; H := High(aData);
  while L <= H do
  begin
    i := L + (H - L) shr 1;
    c := CompareValue(aData[i].SeqNo, aItem.SeqNo);
    if c < 0 then
      L := i + 1
    else
    begin
      if c = 0 then
        Exit(aData[i].CustomName);
      H := i - 1;
    end;
  end;
end;

var vDataLine: TDataLine;
    vName: string;
    i: integer;
    vSW: TStopWatch;
begin
  PrepData; // prepares data, sorted by integer

  vSW := TStopwatch.StartNew;
  for i := 1 to cNOfORecords do
  begin
    vDataLine.SeqNo := i;
    vName := GetName_TArrayBinarySearch(xData, vDataLine);
  end;
  writeln('GetName_TArrayBinarySearch: ' + vSW.ElapsedMilliseconds.ToString);

  vSW := TStopwatch.StartNew;
  for i := 1 to cNOfORecords do
  begin
    vDataLine.SeqNo := i;
    vName := GetName_CustomBinarySearch(xData, vDataLine);
  end;
  writeln('GetName_CustomBinarySearch: ' + vSW.ElapsedMilliseconds.ToString);

  readln;

end.

 

Any advice appreciated, thanks!

 

 

 

 

[Stefan Glienke 2002]

Because IComparer<T> created via TComparer.Construct (TDelegatedComparer<T>) suffer from this issue: https://www.idefixpack.de/blog/2016/05/whats-wrong-with-virtual-methods-called-through-an-interface/

 

Furthermore every call to GetName_TArrayBinarySearch constructs the comparer again. Eliminating that as well gives me a result of 159 vs 105 which then can be explained by the additional calls through IComparer<T> and the probably a little less optimal allocated registers in the actual method that performs the search because that is the one with many more arguments in 

class function TArray.BinarySearch<T>(const Values: array of T; const Item: T; out FoundIndex: Integer; const Comparer: IComparer<T>; Index, Count: Integer): Boolean;

 

FWIW your implementation is not exactly the same as the RTL one as you exit as soon as you find a match while the RTL implementation because it returns the index goes on because it returns the first index in case there are successive elements matching.

Edited March 1, 2021 by Stefan Glienke

[Mike Torrettinni 198]

1 hour ago, Stefan Glienke said:

Furthermore every call to GetName_TArrayBinarySearch constructs the comparer again. Eliminating that

How did you eliminate constructing the comparer each call? I tried to 'pre-construct' comparer like this:

 

// new comparer definitions
var
  xComparison: TComparison<TDataLine>;
  xComparer: IComparer<TDataLine>;


// Function that does the value comparison
function CompareIDs(const Left, Right: TDataLine): Integer;
begin
  Result := CompareValue(Left.SeqNo, Right.SeqNo);
end;

// and I 'pre-construct' Comparer before first GetName_TArrayBinarySearch call
...
  xComparison := CompareIDs;
  xComparer := TComparer<TDataLine>.Construct(xComparison);
...  

// New search function
function GetName_TArrayBinarySearch(const aData: TArray<TDataLine>; const aItem: TDataLine): string;
var vIdx: integer;
begin
  if TArray.BinarySearch<TDataLine>(aData, aItem, vIdx, xComparer) // using pre-constructed xComparer
  then
      Result := aData[vIdx].CustomName;
end;

But this only speeds up a little bit, still: 776 vs 129 ms. So, this is not the correct solution, right?

 

[Mike Torrettinni 198]

When I debug step by step, I see that the Comparison assignment to CompareIDs method is made on every binary search call, again and again!? I assumed if I move it before the actual call of BinarySearch method, it will assign and construct Comparer once and use it.

But the debugger keeps jumping to the line to xComparison := CompareIDs; while doing binary search.

 

I assume this is the cause for slower execution?

 

[Stefan Glienke 2002]

The main reason is in the very first sentence of my previous post.

Also as you are so into benchmarking I suggest you make yourself familiar with profilers so you don't have to guess or ask others what is taking time as you can very well see for yourself.

[Mike Torrettinni 198]

4 minutes ago, Stefan Glienke said:

The main reason is in the very first sentence of my previous post.

Also as you are so into benchmarking I suggest you make yourself familiar with profilers so you don't have to guess or ask others what is taking time as you can very well see for yourself.

Thanks, it makes sense. This jumping of debugger to the same line again and again, even though the flow should be past it, is something new to me. Cool stuff! 😉

[Stefan Glienke 2002]

9 minutes ago, Mike Torrettinni said:

Thanks, it makes sense. This jumping of debugger to the same line again and again, even though the flow should be past it, is something new to me. Cool stuff! 😉

That is because technically what the compiler generates for line 93 is this:

 

xComparison := function(const left, right: TDataLine): Integer begin Result := CompareIDs(left, right) end);

When you put a breakpoint there you have them in multiple lines: one time it gets hit for the assignment to xComparison and all other times for the Result := CompareIDs

[Mike Torrettinni 198]

4 minutes ago, Stefan Glienke said:

That is because technically what the compiler generates for line 93 is this:

 

xComparison := function(const left, right: TDataLine): Integer begin Result := CompareIDs(left, right) end);

When you put a breakpoint there you have them in multiple lines: one time it gets hit for the assignment to xComparison and all other times for the Result := CompareIDs

Aha, I assumed it's like OnClick assignment to event... the flow would go just to the assigned method.

[Mike Torrettinni 198]

On 3/1/2021 at 12:47 AM, Stefan Glienke said:

FWIW your implementation is not exactly the same as the RTL one as you exit as soon as you find a match while the RTL implementation because it returns the index goes on because it returns the first index in case there are successive elements matching.

Yes, this is because I'm implementing common fast class for lookup-up data. And in this case, the searched values are always unique. So, I can exit asap.

 

Well, I didn't really check what would happen with non-unique data, but I guess I lucked out with this.

 

 

[Mike Torrettinni 198]

Solution: Here is example of code where TArray.BinarySearch uses custom Comparer, initialized once only!

 

Interesting that 64bit results are much faster w/o custom comparer, but of course initializing custom comparer once and using it is better:

 

32bit:

 

64bit:

 

Source:

 

program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils, System.Generics.Collections, System.Generics.Defaults, System.Math, System.Diagnostics;

type
  TDataLine = record
    SeqNo: integer;
    CustomName: string;
  end;

type
  TCustomComparer = class(TInterfacedObject, IComparer<TDataLine>)
  public
    function Compare(const Left, Right: TDataLine): Integer;
  end;

const cNOfORecords = 1000000;
var xData: TArray<TDataLine>;
  xComparer:  IComparer<TDataLine>;

function TCustomComparer.Compare(const Left, Right: TDataLine): Integer;
begin
  Result := Left.SeqNo - Right.SeqNo;
end;

procedure PrepData;
var i: Integer;
begin
  SetLength(xData, cNOfORecords);
  for i := 0 to cNofORecords do
  begin
    xData[i].SeqNo := i + 1;
    xData[i].CustomName := i.ToString;
  end;
end;

function GetName_TArrayBinarySearch(const aData: TArray<TDataLine>; const aItem: TDataLine): string;
var vIdx: integer;
begin
  if TArray.BinarySearch<TDataLine>(aData, aItem, vIdx,
    TComparer<TDataLine>.Construct(
      function (const Left, Right: TDataLine): Integer
      begin
       Result := CompareValue(Left.SeqNo, Right.SeqNo);
      end
      ))
  then
      Result := aData[vIdx].CustomName;
end;

function GetName_TArrayBinarySearch_w_Comparer(const aData: TArray<TDataLine>; const aItem: TDataLine): string;
var vIdx: integer;
begin
  if TArray.BinarySearch<TDataLine>(aData, aItem, vIdx, xComparer)
  then
      Result := aData[vIdx].CustomName;
end;

function GetName_CustomBinarySearch(const aData: TArray<TDataLine>; const aItem: TDataLine): string;
var L, H, i, c: Integer;
begin
  Result := '';
  L := 0; H := High(aData);
  while L <= H do
  begin
    i := L + (H - L) shr 1;
    c := CompareValue(aData[i].SeqNo, aItem.SeqNo);
    if c < 0 then
      L := i + 1
    else
    begin
      if c = 0 then
        Exit(aData[i].CustomName);
      H := i - 1;
    end;
  end;
end;

var vDataLine: TDataLine;
    vName: string;
    i: integer;
    vSW: TStopWatch;
begin
  PrepData; // prepares data, sorted by integer

  vSW := TStopwatch.StartNew;
  for i := 1 to cNOfORecords do
  begin
    vDataLine.SeqNo := i;
    vName := GetName_TArrayBinarySearch(xData, vDataLine);
  end;
  writeln('GetName_TArrayBinarySearch: ' + vSW.ElapsedMilliseconds.ToString);

  // New TArray.BinarySearch with Comparer
  xComparer  := TCustomComparer.Create; // initialize Comparer
  vSW := TStopwatch.StartNew;
  for i := 1 to cNOfORecords do
  begin
    vDataLine.SeqNo := i;
    vName := GetName_TArrayBinarySearch_w_Comparer(xData, vDataLine);
  end;
  writeln('GetName_TArrayBinarySearch w Comparer: ' + vSW.ElapsedMilliseconds.ToString);

  vSW := TStopwatch.StartNew;
  for i := 1 to cNOfORecords do
  begin
    vDataLine.SeqNo := i;
    vName := GetName_CustomBinarySearch(xData, vDataLine);
  end;
  writeln('GetName_CustomBinarySearch: ' + vSW.ElapsedMilliseconds.ToString);

  readln;

end.

 

 

Thanks  @Stefan Glienke and @balabuev

 

Edited March 18, 2021 by Mike Torrettinni

[Attila Kovacs 629]

@Mike Torrettinni folding code is a bit tricky. You have to add the spoiler tag first, then post the message, then edit it again and post the code into the folding area.

 

At least this was my workaround, to get it work. If anybody knows a better way to do it, please share.

[Stefan Glienke 2002]

4 hours ago, Mike Torrettinni said:

Interesting that 64bit results are much faster w/o custom comparer

First because 64bit does not suffer from the "virtual method glitch".

Second because even with a class implementing the IComparer interface you get adjustor thunks which you don't have with the default comparers provided by Generics.Collections.Defaults because those are directly crafted IMTs (interface method tables)

 

BTW: you again unnecessarily slow down your benchmark results by putting everything into the dpr main.

And you are comparing different things - your CustomBinarySearch uses CompareValue which is a function call.

So if you decide to roll your custom implementation then don't dumb it down:

 

function GetName_CustomBinarySearch2(const aData: TArray<TDataLine>; const aItem: TDataLine): string;
var L, H, i, c: Integer;
begin
  L := 0; H := High(aData);
  while L <= H do
  begin
    i := L + (H - L) shr 1;
    c := aData[i].SeqNo - aItem.SeqNo;
    if c < 0 then
      L := i + 1
    else if c > 0 then
      H := i - 1
    else
      Break;
  end;
  if L <= H then
    Result := aData[i].CustomName
  else
    Result := '';
end;

makes it almost twice as fast as your implementation. I decided to use the subtract approach as you did with the comparers - keep in mind this only works if there cant be an overflow which wont happen if SeqNo is just 0..MaxInt

Anyhow at least in this benchmark it did not make any noticable difference to writing:

 

    if aData[i].SeqNo < aItem.SeqNo then
      L := i + 1
    else if aData[i].SeqNo > aItem.SeqNo then
      H := i - 1
    else
      Break;

 

Edited March 18, 2021 by Stefan Glienke