Jump to content
Sign in to follow this  
Mike Torrettinni

Micro optimization: Counting items: 1 vs multiple iterations

Recommended Posts

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.

 

image.thumb.png.3433a137fcad154cd6dda63434d49f3f.png

 

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.

 

Share this post


Link to post

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 by Stefan Glienke
  • Like 5
  • Thanks 1

Share this post


Link to post
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 by Fr0sT.Brutal
  • Thanks 1

Share this post


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

Share this post


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

 

image.thumb.png.fc3797340181bb746b9e14212f64314c.png

 

  • Like 1

Share this post


Link to post
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 by Fr0sT.Brutal
  • Like 1
  • Thanks 1

Share this post


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

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
Sign in to follow this  

×