Why is TArray.BinarySearch slower than normal binary search function?
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!
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?