## Optimising speed of loops

New to FreeBASIC? Post your questions here.
bi1iruben
Posts: 1
Joined: Apr 18, 2017 1:08

### Optimising speed of loops

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
Posts: 794
Joined: May 27, 2005 7:15
Location: FRANCE

### Re: Optimising speed of loops

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 tttt=TimerFor i As Ulongint =1 To 1000000000NextPrint Timer-tttt=TimerDim As ULongInt  i=0Do    i+=1Loop until i=1000000000Print Timer-tttt=Timeri=0here:   i+=1If i<>1000000000 Then GoTo herePrint Timer-ttSleep`
MrSwiss
Posts: 1774
Joined: Jun 02, 2013 9:27
Location: Switzerland

### Re: Optimising speed of loops

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
Posts: 4146
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Optimising speed of loops

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          whilePress 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          whilePress any key to continue . . . `

test code:

Code: Select all

`dim as long limit=500000000dim as double t=timerdo        for n as long=1 to limitnextprint timer-t,"for"sleep 50dim as long inct=timerdo    inc+=1loop until inc=limitprint timer-t,"do"inc=0sleep 50t=timerwhile inc<limit    inc+=1wendprint timer-t,"while"printloop until len(inkey) `

So it depends on which compiler.
Win 10 here.
vdecampo
Posts: 2973
Joined: Aug 07, 2007 23:20
Location: Florida, USA
Contact:

### Re: Optimising speed of loops

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
Posts: 5751
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

### Re: Optimising speed of loops

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
Posts: 2317
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

### Re: Optimising speed of loops

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
Posts: 525
Joined: Jun 09, 2005 0:08

### Re: Optimising speed of loops

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_valuefor i as integer=0 to 999  result(i)=my_array(i)/cnext'will be faster like this:c=some_valuereciprocal_c=1.0/cfor i as integer=0 to 999  result(i)=my_array(i)*reciprocal_cnext`

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]
Posts: 423
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Optimising speed of loops

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

Code: Select all

`tt=TimerAsm mov edi, 1End Asmrepeat_loop:' CodeAsminc edicmp edi, 1000000001jb repeat_loopEnd Asm Print Timer-tt`

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

Code: Select all

`for/next 1.91do/loop 1.86custom 1.89register 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]
Posts: 423
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Optimising speed of loops

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

This is safe:

Code: Select all

`tt=TimerAsm mov edi, 1 push ediEnd Asmrepeat_loop:' CodeAsm  pop edi  inc edi  cmp edi, 1000000001  push edi  jb repeat_loop  pop edi ' Tidy upEnd AsmPrint 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 BASICPrintDim As Long x = 1Asm mov ecx, 1 push ecxEnd Asmrepeat_loop1:' Codeprint x;x += 1Asm  pop ecx  inc ecx  cmp ecx, 21  push ecx  jb repeat_loop1  pop ecx ' Tidy upEnd 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
Posts: 6980
Joined: May 28, 2005 3:28
Location: Germany

### Re: Optimising speed of loops

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]
Posts: 423
Joined: Jan 02, 2017 0:34
Location: UK

### Re: Optimising speed of loops

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 = 1Asm mov ecx, 20 push ecxEnd Asmrepeat_loop1:' Basic codeprint x;x += 1Asm  pop ecx  dec ecx  push ecx  jnz repeat_loop1  pop ecx ' Tidy upEnd Asm`

I'm stil not persuaded to use assembler though. <smile>
Boris the Old
Posts: 101
Joined: Feb 04, 2011 20:34

### Re: Optimising speed of loops

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