Micro optimization: Counting items: 1 vs multiple iterations

[Mike Torrettinni 198]

I was expecting that 1x iterating array would be 3x faster than 3x iterating and counting items.

 

I was refactoring counting of items in array and created a function that counts items per item type, and this one is then called multiple times. Then I needed a case where I need to count all items, so I called this new function for each item type.

And looking at the code I was assuming that multiple calls should be multiple times slower than single call.

 

So, count each type:

aQuotes := CountItems(aDocuments, dtQuote);
aOrders := CountItems(aDocuments, dtOrder);
aInvoices := CountItems(aDocuments, dtInvoice);

// CountItems function:
  for i := Low(aDocuments) to High(aDocuments) do
    if aDocuments[i].DocType = aDocType then
      Inc(Result);

vs

  for i := Low(aDocuments) to High(aDocuments) do
  case aDocuments[i].DocType of
     dtQuote: Inc(aQuotes);
     dtOrder: Inc(aOrders);
     dtInvoice: Inc(aInvoices);
  end;

But timing it, the multiple calls are not even 2x slower than single iteration, instead of 3x slower.

 

 

So, I looked into the generated asm and there is not a lot of difference between If and Case comparisons.

 

Comparing what it does, for 10mio items:

- 3calls: 30mio iterations + 30mio comparisons.

- 1 iteration: 10mio iterations + (10 to 30)mio comparisons (depends which item it is)

 

 

I guess this is one of those 'branch prediction, caching..' stuff I don't understand.  Still, if anybody has an easy explanation why 3x iteration is not 3x slower, please share. Thanks!

 

 

program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils,
  System.Diagnostics;

type
  TDocType = (dtQuote, dtOrder, dtInvoice);

  TDocLine = record
    ID: integer;
    DocType: TDocType;
  end;

  TDocuments = TArray<TDocLine>;

const
  cDocs: integer = 10000000;

function CountItems(const aDocuments: TDocuments; aDocType: TDocType): integer;
var i: Integer;
begin
  Result := 0;
  for i := Low(aDocuments) to High(aDocuments) do
    if aDocuments[i].DocType = aDocType then
      Inc(Result);
end;

procedure CountAllItems(aDocuments: TDocuments; var aQuotes, aOrders, aInvoices: integer);
begin
  aQuotes := CountItems(aDocuments, dtQuote);
  aOrders := CountItems(aDocuments, dtOrder);
  aInvoices := CountItems(aDocuments, dtInvoice);
end;

procedure CountAllItems2(aDocuments: TDocuments; var aQuotes, aOrders, aInvoices: integer);
var i: integer;
begin
  aQuotes := 0; aOrders := 0; aInvoices := 0;
  for i := Low(aDocuments) to High(aDocuments) do
  case aDocuments[i].DocType of
     dtQuote: Inc(aQuotes);
     dtOrder: Inc(aOrders);
     dtInvoice: Inc(aInvoices);
  end;
end;

procedure CountAllItems3(aDocuments: TDocuments; var aQuotes, aOrders, aInvoices: integer);
var i: integer;
begin
  aQuotes := 0; aOrders := 0; aInvoices := 0;
  for i := Low(aDocuments) to High(aDocuments) do
  begin
    if      aDocuments[i].DocType = dtQuote   then Inc(aQuotes)
    else if aDocuments[i].DocType = dtOrder   then Inc(aOrders)
    else if aDocuments[i].DocType = dtInvoice then Inc(aInvoices);
  end;
end;

procedure PrepData(var aDocuments: TDocuments);
var
  i: Integer;
begin
  aDocuments := nil;
  SetLength(aDocuments, cDocs);

  for i := 0 to cDocs - 1 do
  begin
    aDocuments[i].ID := i + 1;
    aDocuments[i].DocType := TDocType(Random(3));
  end;
end;

procedure RunTests;
var vDocuments: TDocuments;
    vSW: TStopWatch;
    q, o, i: integer;
begin
  PrepData(vDocuments);

  vSW := TStopwatch.StartNew;
  CountAllItems(vDocuments, q, o, i);
  Writeln(Format('3x iterate:         %d ms (%d %d %d)', [vSW.ElapsedMilliseconds, q, o, i]));

  vSW := TStopwatch.StartNew;
  CountAllItems2(vDocuments, q, o, i);
  Writeln(Format('1x iterate (case):  %d ms (%d %d %d)', [vSW.ElapsedMilliseconds, q, o, i]));

  vSW := TStopwatch.StartNew;
  CountAllItems3(vDocuments, q, o, i);
  Writeln(Format('1x iterate (if):    %d ms (%d %d %d)', [vSW.ElapsedMilliseconds, q, o, i]));

end;

begin
  Randomize;
  RunTests;
  Readln;
end.

 

[Stefan Glienke 2002]

Any branching (if, case) is expensive - especially when it cannot be predicted because you have a random pattern.

 

Here is how it's done fast:

 

procedure CountAllItems4(const aDocuments: TDocuments; var counts: array of Integer);
var i: integer;
begin
  counts[0] := 0;
  counts[1] := 0;
  counts[2] := 0;
  for i := Low(aDocuments) to High(aDocuments) do
    Inc(counts[Ord(aDocuments[i].DocType)]);
end;

var
  counts: array[TDocType] of Integer;
begin
  ...
  CountAllItems4(vDocuments, counts);
  q := counts[dtQuote];
  o := counts[dtOrder];
  i := counts[dtInvoice];

 

Edited May 31, 2021 by Stefan Glienke

[Fr0sT.Brutal 900]

11 hours ago, Stefan Glienke said:

Any branching (if, case) is expensive - especially when it cannot be predicted because you have a random pattern.

 

Here is how it's done fast:

+1

Small modification:

 

Counts: array[TDocType] of Cardinal

..zeroize the array...

for i := Low(aDocuments) to High(aDocuments) do

  Inc(counts[aDocuments[i].DocType]); 

 

Edited June 1, 2021 by Fr0sT.Brutal

[Mike Torrettinni 198]

11 hours ago, Stefan Glienke said:

Here is how it's done fast: 

Very clever, thanks!

 

I can have this fast count run right after data import and then just return the result, based on requested data type. No more counting on demand!

[Mike Torrettinni 198]

1 hour ago, Fr0sT.Brutal said:

Small modification:

 

Counts: array[TDocType] of Cardinal

Interesting.

 

I implemented like this:

 

type TCounts = array[TDocType] of Cardinal;

procedure CountAllItems6(const aDocuments: TDocuments; var counts: TCounts);
var i: integer;
    dt: TDocType;
begin
  for dt := Low(TDocType) to High(TDocType) do
    counts[dt] := 0;

  for i := Low(aDocuments) to High(aDocuments) do
    Inc(counts[aDocuments[i].DocType]);
end;

 

And results (changed to 100mio doc lines):

 

 

[Fr0sT.Brutal 900]

2 hours ago, Mike Torrettinni said:

I implemented like this:

1) As long as you don't need input value of Counts, it's better to mark it "out" instead of "var"

2) When you declare a type for counts, you can zero it with "Default": "counts := Default(TCounts)"

Edited June 1, 2021 by Fr0sT.Brutal

[Mike Torrettinni 198]

2 hours ago, Fr0sT.Brutal said:

1) As long as you don't need input value of Counts, it's better to mark it "out" instead of "var"

2) When you declare a type for counts, you can zero it with "Default": "counts := Default(TCounts)"

Thanks, I didn't know that I can use Default for arrays. I use it for simple types and records, didn't know about arrays. Good!