Loop Iteration Speed Test

[Martin_fr]

To do alignment use

Code: Pascal  [Select][+][-]

1. {$CodeAlign Loop=$20 Proc=$20}

Mind you, with all the "smart buildin micro optimizations" of modern cpu, in most cases you will not see a difference.

But, I have personally seen some of the few cases, where it made a difference. And a noticeable 20%.


If you put each loop into a proc of its own then you can:

- Do some warm up runs, where you discard the times
- Run each loop several times getting fastest and avg times (e.g. doing 20 runs for each bench)
- For more complex scenarios,
  - reorder the function in code (in case it affects caching - code or data / well yours don't have data to cache)
  - change the order in which you test them

Also you did not specify which optimization you compiled with. And the exact version of FPC. That can change results.



As for loop, the following are equal (the begin end are optional, but they don't generate code / at least they should not)
You could play with = vs > vs <> ...

Code: Pascal  [Select][+][-]

1. for i := 0 to maxint-1 do begin
2. end;

Code: Pascal  [Select][+][-]

1. i := 0; while i < maxint do begin
2.   inc(i);
3. end;

Code: Pascal  [Select][+][-]

1. i := 0; repeat
2.   inc(i);
3. until i = maxint;

Do those you can then add any other workload such as your timing condition.

However, your check for the time will likely take much more time than the loop iteration itself. So you will not see any difference. If actually there is one.

But further more, the compiler optimizes in some cases the result of the loop and contained code. So which loop is faster may change depending on what you actually do in the loop.

One thing can be told, if the upper bound (in your case maxint) was something like "SomeContainer.Count - 1" and if calling Count was slow, then the for loop will be faster. Simply because it calls count only once, and caches the result.

On the other hand, for the same reason the for loop will fail, if the count changes during the loop.



As I said in each version of FPC the loops may compare differently.

And as the compiler gets better at optimizing there likely will be less of a difference (if there is any to start with).

That is except for the functional differences:
- for: only one evaluation of the upper bound
- repeat: no check before the first iteration

E.g. if you have an inner loop, that is being STARTED a million times, but each time only runs between 1 and 3 iterations, and you know it will always be at least 1, then when you use repeat, you have one comparison less. One for each of the million times that it gets started.
However, for that to make a difference, the loop itself must not take much time in the iterations. Because 1 comparison is hardly any time. And if the loop spend much time doing something inside it, then you still only save 0.00001%.

[AlanTheBeast]

said stuff ...

I suggest:

1 -Use GetTickCount64 to measure time, less CPU than the FP TDateTime and those calculations.
     (64 bit integer (int64) or QWord).

2- Do your test within a procedure or function with -O2 optimization so the control variables in the proc/function VAR section  end up in registers.
    (If the test control variables are in globals they will bias your performance computation).

3- measure how many loops can go in t time (as other(s) point out):

Code: Pascal  [Select][+][-]

1. U := GetTickCount64;
2. Q := U + 10_000_000;  //ms
3. Repeat T := GetTickCount64 until T<>U;    // line up at the start of a millisecond <- important.
4. Repeat
5.           <Stuff>;
6.           inc(n); //if needed
7.           T := GetTickCount64;
8. Until T>=Q;
9. <Compute rates here>;
10.  

On a multi core machine you could put the "target exercise" in one thread and the surveillance code in a separate thread or FG thread.  Not much extra work to do.

But of course you have no idea how much pre-emption, interrupts, etc.  take place during your run, so after many runs or a very, very long run you would have a likely bit of stats for the load case of the computer at the time of the test.

And GetTickCount64 is not razor sharp either (nor is "now").

Such exercises done on OS-less platforms (RTL, etc.) yield far more reliable stats (when conducted correctly and optimally with interrupts from a h/w timer) to count the ticks - ... and apply to that environment.  (That said, the RTL I sometimes use also does pre-emption, interrupts, so there's that).

[gues1]

If you want to measure the time (I try only in Windows, but should works in Linux too) with resolution less then 1 microsecodns, you can use the unit attached.

It was an old unit that use 0,1 microseconds resolution hardware present in the modern systems.

BE CAREFULL that 0,1 microseconds is the RESOLUTION !!! The accuracy (I mean the "measures" that you do) is not the same of course.

The beauty of this is that you can simply use it multiple "instances" so you can have in very simple mode more then one timer.

I don't know how was the original file name, I call it in this way 'cause Delphi has the same functionality in the same unit. This implementation is different from Delphi side.

How to use:

Code: Pascal  [Select][+][-]

1. var tim: TStopWatch; //you can have more then one, be carefull that they use resources, don't abuse.
2. tim := TStopWatch.StartNew;
3. //things to do
4. tim.Stop;
5. ShowMessage(Tim.ElapsedMilliseconds.ToString); //Time in milliseconds
6. ShowMessage((Tim.ElapsedTicks div 10).ToString); //Time in microseconds
7.  
8. tim.Reset;
9. tim.Start;
10. //another time
11. .....
12.  

[Gustavo 'Gus' Carreno]

Hey gues1,

If you want to measure the time (I try only in Windows, but should works in Linux too) with resolution less then 1 microsecodns, you can use the unit attached.

This is awesome, THANKS!!!

I've been drooling on the Stop Watch concept for quite a while, so I'm glad someone port it to Free Pascal!!!

Cheers,
Gus

[gues1]

Hey gues1,

If you want to measure the time (I try only in Windows, but should works in Linux too) with resolution less then 1 microsecodns, you can use the unit attached.

This is awesome, THANKS!!!

I've been drooling on the Stop Watch concept for quite a while, so I'm glad someone port it to Free Pascal!!!

Cheers,
Gus

It's not works of mine, I have found it somewhere sometimes ago. I only use it to compare some test that I do form Delphi vs. Lazarus

[Gustavo 'Gus' Carreno]

Hey gues1,

It's not works of mine, I have found it somewhere sometimes ago. I only use it to compare some test that I do form Delphi vs. Lazarus

That's not a problem!! And I thank you for your honesty !!
Nonetheless, I've been wanting something like this for a while and this is very welcomed, whatever the origin !!

Cheers,
Gus

[LV]

To do alignment use

Code: Pascal  [Select][+][-]

1. {$CodeAlign Loop=$20 Proc=$20}

Mind you, with all the "smart buildin micro optimizations" of modern cpu, in most cases you will not see a difference.

That's right.

And if the loop spend much time doing something inside it, then you still only save 0.00001%.

This is exactly what we're talking about for those who work with CFD. The application execution time can take 10, 20, or more hours. Therefore, for such tasks, the measurement accuracy of up to ms or μs is not very relevant.

Oh yeah, FPC 3.2.2 with -O3 optimization.

[Martin_fr]

And if the loop spend much time doing something inside it, then you still only save 0.00001%.

This is exactly what we're talking about for those who work with CFD. The application execution time can take 10, 20, or more hours. Therefore, for such tasks, the measurement accuracy of up to ms or μs is not very relevant.

But the savings (if any, if any...) are neither.

The given example test ignores actual documented differences, such as  "for" saves time on recalculating the upper bound. Because "maxint" is a constant. It takes no time.

What the given example tests, is if the compiler generates internally different asm, which may have different speed for different loop statements.
Ignoring that those differences (if they exist at all) may not exist with all fpc versions....

Those assumed/alleged differences will at best be tiny. They only matter
- once, maybe when the loop is being initialized. That is a tiny fraction of the execution, unless the loop does nothing inside itself, and is called millions of time by an outer loop. A very uncommon case.
- for each iteration for the inc and compare.

That later, does mainly differ in speed if the loop counter (and bound to compare)  can be in registers or not. But that depends on how registers are used by the code inside the loop. The loop itself does not decide that.

So even if the empty loop runs at different speed, as soon as you go real app, and have content in the loop, the rankings may be the exact opposite....

But also, even if the empty loops get 1% or 2% of speed difference. The amount of time that the "loop code" has of the overall app will itself be less than 1% => Even if you only have the most extreme short near-empty loops, then it may be more. But that is unlikely.

1% of 1% is 0.01% And if your app runs an hour, then that saves ONE second or less?

[LV]

Thank you, @Martin_fr, for your clear and professional explanation.

[Martin_fr]

Just to put my responses into the correct light. I don't wont to dismiss the idea of those benchmarks, but...

As an exercise benchmarking those loops may be fun. But it should be understood that the results of this wont help you speeding up any of your code.


There is a lot to say about benchmarking (and following optimization of code...).

And I have myself gone down that road, and certainly made my "mistakes" (or spent time that professionally wouldn't have been worth it). And probably (actually: certainly) there are further pitfalls ahead that I will fall into. Despite the experience I think to have build by now.

To speed up you code, you have to benchmark that code. And if you want to try different types of loops, though with exception of "for caches the upper bound, if that is an expensive function call", you will most likely not get much of a gain. (Well your gain will be experience in benchmarking, if you understand why the results are as they are).

[paweld]

Hello @paweld what was the error? Please show me what I did wrong? And what you did to fix things please.

You inserted for..in into the repeat..until loop, which causes the for..in loop to always execute all of it no matter the elapsed time. I changed as below (I used a list instead of an array):

Code: Pascal  [Select][+][-]

1.   // FOR..IN loop
2.   il := TIntegerList.Create;
3.   for I := 1 to 100000000 do il.Add(i);
4.   Count := 0;
5.   StartTime := Now;
6.   for I in il do
7.   begin
8.     if MilliSecondsBetween(Now, StartTime) >= 1000 then
9.       break
10.     else
11.       Inc(Count);
12.   end;
13.   il.Free;
14.   memoResults.Lines.Add('FOR..IN loop:         ' + IntToStr(Count) + ' iterations');