Optimising speed of loops

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

Optimising speed of loops

Postby bi1iruben » Apr 18, 2017 1:16

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

Re: Optimising speed of loops

Postby SARG » Apr 18, 2017 14:17

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
Posts: 1922
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Optimising speed of loops

Postby MrSwiss » Apr 18, 2017 14:20

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

Re: Optimising speed of loops

Postby dodicat » Apr 18, 2017 14:24

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
Posts: 2977
Joined: Aug 07, 2007 23:20
Location: Maryland, USA
Contact:

Re: Optimising speed of loops

Postby vdecampo » Apr 18, 2017 17:50

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

Re: Optimising speed of loops

Postby counting_pine » Apr 18, 2017 19:43

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

Re: Optimising speed of loops

Postby marcov » Apr 18, 2017 19:57

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

Re: Optimising speed of loops

Postby Stonemonkey » Apr 18, 2017 23:04

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

Re: Optimising speed of loops

Postby deltarho[1859] » Apr 19, 2017 3:17

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

Re: Optimising speed of loops

Postby deltarho[1859] » Apr 19, 2017 15:04

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
Posts: 7097
Joined: May 28, 2005 3:28
Location: Germany

Re: Optimising speed of loops

Postby D.J.Peters » Apr 19, 2017 21:08

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

Re: Optimising speed of loops

Postby deltarho[1859] » Apr 19, 2017 22:44

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
Posts: 102
Joined: Feb 04, 2011 20:34
Location: Ontario, Canada

Re: Optimising speed of loops

Postby Boris the Old » Apr 22, 2017 3:48

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

Return to “Beginners”

Who is online

Users browsing this forum: No registered users and 3 guests