Optimising speed of loops

[bi1iruben]

Are there any difference in the speed of executing a loop in the compiled code between:
a) A manual loop with a counter incremented by +1 and using an IF count < max THEN GOTO start_loop
b) Using a FOR... NEXT loop or
c) DO ... LOOP ?

[SARG]

Hi,

Very very low benefit to do/loop :
for/next 2.42
do/loop 2.35
custom 2.38

The better is the most easy to code / to read..... So your choice.

Code: Select all

Dim As Double tt

tt=Timer
For i As Ulongint =1 To 1000000000
Next

Print Timer-tt


tt=Timer
Dim As ULongInt  i=0
Do 
   i+=1
Loop until i=1000000000

Print Timer-tt

tt=Timer
i=0
here:
   i+=1
If i<>1000000000 Then GoTo here
Print Timer-tt


Sleep

[MrSwiss]

Well, I'd say: don't use a) at all (use of GoTo is discouraged, as long, as there are alternative options)

The Do ... Loop is probably fastest (as long as there are no complex Start/End conditions) e.g.:

• Do While (Boolean) var = TRUE -- or --
  Loop Until Len(InKey()) or similar stuff

In For ... Next Loop the used variable (Loop-Counter) is influencing on speed, e.g.:

• fastest is UInteger (can be used in both compilers 32/64, without modifying source)
  but, it has limits too: only step-size of +/-1 or other integer values (aka: integer stepping,
  not 0.5 or similar here, you'd need Single/Double as counter)
  and, on down counting Loop's only down to 1 (blows if count goes lower)

If you need to go to zero (or below) use Integer instead of UInteger.

BTW: there is also: While ... Wend Loop available ...

[dodicat]

Just try it out.
64 bit , no optimizations:

Code: Select all

 1.334196794545278          for
 0.7249080961337313         do
 1.16963249060791           while

 2.336079527856782          for
 0.7183756754966453         do
 1.173688134993427          while

 2.33496980345808           for
 0.7196304887766019         do
 1.165945727843791          while

 2.335170669364743          for
 0.7151450528763235         do
 1.198257770156488          while

 2.360170096158981          for
 0.7188615861814469         do
 1.168725000810809          while

Press any key to continue . . . 

32 bit gas:

Code: Select all

  1.365903843711578          for
 1.18790171048704           do
 1.178744344918187          while

 2.363004461872151          for
 1.210046582384962          do
 1.182412629293424          while

 2.365101406498866          for
 1.1845951217162            do
 1.185610401451697          while

 2.369157050771605          for
 1.195089084236827          do
 1.183272896808035          while

 2.366699437188117          for
 1.18553819924449           do
 1.176286389004019          while

Press any key to continue . . . 

test code:

Code: Select all

dim as long limit=500000000

dim as double t=timer

do
    
    
for n as long=1 to limit
next
print timer-t,"for"

sleep 50
dim as long inc
t=timer
do
    inc+=1
loop until inc=limit
print timer-t,"do"
inc=0


sleep 50
t=timer
while inc<limit
    inc+=1
wend
print timer-t,"while"
print



loop until len(inkey)

 

So it depends on which compiler.
Win 10 here.

[vdecampo]

The best speed optimization for loops is to unroll them. Do as many calculations per loop as you can. For example, instead of counting from 1 to 100 doing a calculation each iteration, step by 5 and do 5 calculations per loop.

-Vince

[counting_pine]

It can be difficult to predict which code will produce the fastest results. It may even change depending on the compiler settings, or the computer it's run on.
In 64-bit mode, fbc compiles the code to a barely-readable but valid C program, and lets the GCC compiler optimise it. In the above example, with 'fbc -O 3', the gcc backend is smart enough to remove the 'while' loop entirely, returning a time of 0 seconds.
I have some theories, perhaps something to do with the subtle differences between 'while <' and 'until =', but I couldn't say why exactly.

Optimisation can be a very interesting question to ponder, but writing optimal code takes a lot of programmer time, e.g.
- thinking about how to optimise
- trying to write optimised code
- profiling the code to work out where to optimise, which code is *actually* the fastest and how much time is saved

And later down the line, you or other people might have to:
- trying to understand the optimised code to work out what it does or how it does it
- make changes to optimised sections
- track down bugs within it

In many cases I think more time will be lost trying to read and write optimal code than is ever saved in the running of the program.

[marcov]

It might also be best to use only local variables for for loops.

Using a global variable in the main program might trigger some special case for global variables (specially if global variables are e.g. automatically volatile)

[Stonemonkey]

As suggested, some unrolling can help, but look to see what can be removed or altered in loops.

If a variable doesn't change within a loop but is used to divide inside the loop then calculate the reciprocal outside the loop and multiply by that instead

Code: Select all

c=some_value
for i as integer=0 to 999
  result(i)=my_array(i)/c
next

'will be faster like this:

c=some_value
reciprocal_c=1.0/c
for i as integer=0 to 999
  result(i)=my_array(i)*reciprocal_c
next

or if a value that does change within a loop is used to divide in several calculations then calculate the reciprocal once and multiply by that instead of dividing several times.

[deltarho[1859]]

One way to speed up loops is to use a register for the counter.

Code: Select all

tt=Timer
Asm
 mov edi, 1
End Asm
repeat_loop:
' Code
Asm
inc edi
cmp edi, 1000000001
jb repeat_loop
End Asm
 
Print Timer-tt

My machine is a little bit faster than SARGs but I get this

Code: Select all

for/next 1.91
do/loop 1.86
custom 1.89
register 0.26

However, I must question what we are doing here. With a loop of 1000,000,000 the time taken to execute a handful of BASIC statements within the loop may render the 'flyback' time as academic, relatively. With a loop that big I would be seriously thinking about converting the BASIC to assembler. For very much smaller loops the 'flyback' time will be academic. For a loop of 1000 the 'flyback' is in the nanosecond domain.

In many cases I think more time will be lost trying to read and write optimal code than is ever saved in the running of the program.

Quite so.

[deltarho[1859]]

I have been waiting for someone to mention that my ASM is unsafe.

This is safe:

Code: Select all

tt=Timer
Asm
 mov edi, 1
 push edi
End Asm
repeat_loop:
' Code
Asm
  pop edi
  inc edi
  cmp edi, 1000000001
  push edi
  jb repeat_loop
  pop edi ' Tidy up
End Asm
Print Timer-tt

And here is some code with BASIC twixt the ASM blocks; 1 To 20 using ecx, the classical register used for counting in ASM.

Code: Select all

' With BASIC
Print
Dim As Long x = 1
Asm
 mov ecx, 1
 push ecx
End Asm
repeat_loop1:
' Code
print x;
x += 1
Asm
  pop ecx
  inc ecx
  cmp ecx, 21
  push ecx
  jb repeat_loop1
  pop ecx ' Tidy up
End Asm

Needless to say the safe code is slower but still faster than the other methods. It did not need a proof: Using a register variable should be faster then using a memory variable.

Not exactly readable, is it? In fact, it is positively ugly.

For me I'd use the most readable method that does the job. If For/Next works then I would go for that - the intent cannot be any clearer.

use of GoTo is discouraged, as long, as there are alternative options

GoTo comes into its own for error trapping. Alternative options exist but they are not as simple as a GoTo and the intention is very clear provided we use a meaningful label to jump to.

[D.J.Peters]

offtopic not really :-)

The Blackfin DSP microprocessor developed by Analog Devices and Intel
has „Zero-overhead Loop Registers“ that means any assembler code
between the hardware loop commands are repeated without any time consumtion for a loop counter
or the test condition the repeating code are executed without a jump instruction !

What a cute tiny monster ;-)

Joshy

[deltarho[1859]]

I cannot compete with that but it reminded me of the count down method where we can eliminate 'cmp' and use a 'jnz'.

Here we are counting from 20 to 1

Code: Select all

Dim As Long x = 1
Asm
 mov ecx, 20
 push ecx
End Asm
repeat_loop1:

' Basic code
print x;
x += 1

Asm
  pop ecx
  dec ecx
  push ecx
  jnz repeat_loop1
  pop ecx ' Tidy up
End Asm

I'm stil not persuaded to use assembler though. <smile>

[Boris the Old]

In my experience, it's not worth the time and effort to worry about such trivial optimization details. It's a very rare program that will benefit from choosing between FOR/NEXT and DO/WHILE, etc.

Forty or fifty years ago there might have been some benefits. But today, with most functionality being performed by the operating system, graphics libraries, database libraries, etc, very little work is actually performed in user code.

For me, the overriding consideration is code clarity and ease of maintenance. So I always use standard language features in a way that makes it clear what the program is doing. So sometimes I'll use FOR/NEXT if a simple loop is required, but other times I'll use DO/WHILE if special end conditions need to be handled.

However, even though I was using Assembler language 45 years ago to drive telecommunications hardware, I never use it today to save a few cpu cycles in high level code. It's not an appropriate solution. Firstly, it has no effect in the great scheme of things. Secondly, it adds complexity to the code. Thirdly, it restricts the number of people who are capable of maintaining the code. And lastly, it assumes functionality in the high level code (eg: FB) that may not exist in the future.

Rod