Slow recursion

[UEZ]

I just want to add the results of our discussion in German forum.

Indeed recursion speed depends on the recursion code not to speed of AutoIt!

Here an example what I want to say:

expandcollapse popup

$n = 26

$bench_start = TimerInit()
ConsoleWrite(Fibonacci_i($n) & @CRLF)
$bench_end_i = Round(TimerDiff($bench_start), 4)

$bench_start = TimerInit()
ConsoleWrite(Fibonacci_r($n) & @CRLF)
$bench_end_r = Round(TimerDiff($bench_start), 4)

$bench_start = TimerInit()
ConsoleWrite(Fibonacci_r2($n) & @CRLF)
$bench_end_r2 = Round(TimerDiff($bench_start), 4)

ConsoleWrite(@CRLF & "Iterative : " & $bench_end_i & " ms")
ConsoleWrite(@CRLF & "Recursive : " & $bench_end_r & " ms")
ConsoleWrite(@CRLF & "Recursive2: " & $bench_end_r2 & " ms" & @CRLF)

ConsoleWrite(@CRLF & "Diff_IR : " & Abs($bench_end_i - $bench_end_r) & " ms !")
ConsoleWrite(@CRLF & "Diff_IR2: " & Abs($bench_end_i - $bench_end_r2) & " ms !")
ConsoleWrite(@CRLF & "Diff_RR2: " & Abs($bench_end_r2 - $bench_end_r) & " ms !")
ConsoleWrite(@CRLF & @CRLF)


Func Fibonacci_i($f)
    If $f = 0 Then
        Return 0
    ElseIf $f = 1 Then
        Return 1
    Else
        $arr_fib_n0 = 0
        $arr_fib_n1 = 1

        For $i = 2 To $f
            $arr_fib = $arr_fib_n1 + $arr_fib_n0
            $arr_fib_n0 = $arr_fib_n1
            $arr_fib_n1 = $arr_fib
        Next

        Return $arr_fib
    EndIf
EndFunc

Func Fibonacci_r($f)
    If $f < 2 Then Return $f

    Return Fibonacci_r($f - 1) + Fibonacci_r($f - 2)
EndFunc


; ************* Fibonacci R2 ******************
Func Fibonacci_r2($f)
    If $f < 2 Then Return $f

    Return Fibonacci_r2_(1, 1, $f)
EndFunc

Func Fibonacci_r2_($f1, $f2, $fn)
    If $fn < 3 Then Return $f2

    Return Fibonacci_r2_($f2, $f1 + $f2, $fn - 1)
EndFunc
; ************* Fibonacci R2 ******************

As you can see the optimized Fibonacci recursion is much faster than the originally posted code Fibonacci_r1 because when you look at the recursion tree you can see that Fibonacci_r1 calculation is exponential!

UEZ

Edited January 30, 2010 by UEZ

[Xand3r]

Another way for the fibonacci is to store the results in an array first run

iterative

expandcollapse popup

$n = 92
Dim $arr[$n+1]
Dim $arr2[$n+1]
ConsoleWrite("First run..." & @CRLF)
$bench_start = TimerInit()
Fibonacci_i($n,$arr2)
$bench_end_i = Round(TimerDiff($bench_start), 4)

$bench_start = TimerInit()
Fibonacci_r($n,$arr)
$bench_end_r = Round(TimerDiff($bench_start), 4)
ConsoleWrite(@CRLF & "Iterative: " & $bench_end_i & " ms" & @CRLF & "Recursive: " & $bench_end_r & " ms" & @CRLF & "Diff: " & Round($bench_end_i / $bench_end_r,10) & "" & @CRLF & @CRLF)

ConsoleWrite("Second run..." & @CRLF)
$bench_start = TimerInit()
Fibonacci_i($n,$arr2)
$bench_end_i = Round(TimerDiff($bench_start), 4)

$bench_start = TimerInit()
Fibonacci_r($n,$arr)
$bench_end_r = Round(TimerDiff($bench_start), 4)
ConsoleWrite(@CRLF & "Iterative: " & $bench_end_i & " ms" & @CRLF & "Recursive: " & $bench_end_r & " ms" & @CRLF & "Diff: " & Round($bench_end_i / $bench_end_r,10) & "" & @CRLF & @CRLF)

ConsoleWrite("Third run..." & @CRLF)
$n+=100
ReDim $arr[UBound($arr)+100]
ReDim $arr2[UBound($arr2)+100]
$bench_start = TimerInit()
Fibonacci_i($n,$arr2)
$bench_end_i = Round(TimerDiff($bench_start), 4)

$bench_start = TimerInit()
Fibonacci_r($n,$arr)
$bench_end_r = Round(TimerDiff($bench_start), 4)
ConsoleWrite(@CRLF & "Iterative: " & $bench_end_i & " ms" & @CRLF & "Recursive: " & $bench_end_r & " ms" & @CRLF & "Diff: " & Round($bench_end_i / $bench_end_r,10) & "" & @CRLF & @CRLF)

Func Fibonacci_i($f,ByRef $arr_fib)
    If $arr_fib[$f] Then Return $arr_fib[$f]
    $arr_fib[0] = 0
    $arr_fib[1] = 1
    $k=2
    While $arr_fib[$k]<>0
        $k+=1
    WEnd
    For $i = $k To $f
    $arr_fib[$i] = $arr_fib[$i-1] + $arr_fib[$i-2]
    Next
    Return $arr_fib[$f]
EndFunc

Func Fibonacci_r($f,ByRef $arr)
    If $f = 0 Then Return 0
    If $f = 1 Then Return 1
    If $arr[$f] Then
        Return $arr[$f]
    Else
        $arr[$f]= Fibonacci_r($f - 1,$arr) + Fibonacci_r($f - 2,$arr)
        Return $arr[$f]
    EndIf
EndFunc

First run...

Iterative: 0.4886 ms
Recursive: 2.3939 ms
Diff: 0.2041020928

Second run...

Iterative: 0.0142 ms
Recursive: 0.0131 ms
Diff: 1.0839694656

Third run...

Iterative: 0.6018 ms
Recursive: 3.4384 ms
Diff: 0.1750232666

[Mat]

Or use binets formula... I've done it here. Not sure how it will compare with lower numbers, but it should be faster than the higher ones

[UEZ]

Or use binets formula... I've done it here. Not sure how it will compare with lower numbers, but it should be faster than the higher ones

Thanks for the Math.au3!

But my issue was not calculating Fibonacci numbers - it was about recursion and its speed with AutoIt! And what I figured out is that "optimized" recursion code is not so slow as I thought when I started this thread.

UEZ

[Mat]

But my issue was not calculating Fibonacci numbers - it was about recursion and its speed with AutoIt! And what I figured out is that "optimized" recursion code is not so slow as I thought when I started this thread.

I understand It would be interesting to see exactly how AutoIt compares to c++ when it comes to a simple while ... wend loop.

[monoceres]

I understand It would be interesting to see exactly how AutoIt compares to c++ when it comes to a simple while ... wend loop.

That's a pretty meaningless test. For example, this code returned instantly when I compiled and ran it.

int i=0; 
while (i<1000000000)
 i++

Edited February 4, 2010 by monoceres

[Xand3r]

#include<iostream>
#include <time.h>

using namespace std;

int main()
{
    clock_t init, final;
    init=clock();
    int i=1;
    while (i<10000000)
    {
        i++;
    }
    final=clock()-init;
    cout << (double)final / ((double)CLOCKS_PER_SEC) <<"\n";
    return 0;
}

0.09 sec

$start = TimerInit()
$max=10000000
$i=1
While $i<$max
    $i=$i+1
WEnd
ConsoleWrite(TimerDiff($start) & @CRLF& @CRLF & @CRLF & @CRLF )

15 sec

$max = 10000000
$start = TimerInit()
For $i=1 To $max
Next
ConsoleWrite(@CRLF & @CRLF & TimerDiff($start)/1000 & @CRLF)

0.8 sec

Edited February 5, 2010 by Xand3r

[Mat]

Thats what I wanted to know thanks Thats quite a big difference

[czardas]

Interesting thread. I'm not sure what these tests are telling us though. How are these comparable?

$start = TimerInit()
$max=10000000
$i=1
While $i<$max
    $i=$i+1
WEnd
ConsoleWrite(TimerDiff($start) & @CRLF& @CRLF & @CRLF & @CRLF )

15 sec - While loop (involving an argument) and then a calculation.

$max = 10000000
$start = TimerInit()
For $i=1 To $max
Next
ConsoleWrite(@CRLF & @CRLF & TimerDiff($start)/1000 & @CRLF)

0.8 sec - For loop doing nothing at all.

I'm just a bit confused.

[Mat]

Interesting thread. I'm not sure what these tests are telling us though. How are these comparable?

$start = TimerInit()
$max=10000000
$i=1
While $i<$max
    $i=$i+1
WEnd
ConsoleWrite(TimerDiff($start) & @CRLF& @CRLF & @CRLF & @CRLF )

15 sec - While loop (involving an argument) and then a calculation.

$max = 10000000
$start = TimerInit()
For $i=1 To $max
Next
ConsoleWrite(@CRLF & @CRLF & TimerDiff($start)/1000 & @CRLF)

0.8 sec - For loop doing nothing at all.

I'm just a bit confused.

Well you could argue that a for loop is just a simpler syntax for the while loop as shown. The bit I was interested in was the c++ vs AutoIt, where there was actually a huge difference for the same/similar code.

[czardas]

Well you could argue that a for loop is just a simpler syntax for the while loop as shown. The bit I was interested in was the c++ vs AutoIt, where there was actually a huge difference for the same/similar code.

Yeah I noticed.

[Valik]

$i = $i + 1? Somebody needs to learn about operator +=.

[monoceres]

$i = $i + 1? Somebody needs to learn about operator +=.

And somebody needs to implement $i++

Just kidding, I know it's not going to happen

Edit: The word not is important

Edited February 5, 2010 by monoceres

[Xand3r]

$i = $i + 1? Somebody needs to learn about operator +=.

lol... i know about the f'ing

+=

-=

*=

/=

&= operators

lol... i had no ideea that

$i+=1 is faster than $i = $i + 1

[monoceres]

lol... i had no ideea that

$i+=1 is faster than $i = $i + 1

If you think about it, it makes perfectly sense.

$i = $i + 1

Need to lookup $i twice and $i is probably being copied at least once since the answer is overwriting the $i variable.

$i+=1 on the other hand can directly manipulate the $i without any copies or temporary storage.

[Richard Robertson]

$i+=1 on the other hand can directly manipulate the $i without any copies or temporary storage.

To an extent. The low level workings still make a copy. In the very least this copy is the data loaded from memory to a register.

[monoceres]

To an extent. The low level workings still make a copy. In the very least this copy is the data loaded from memory to a register.

Yes of course, but that's just on integer. A copy of the autoit variant will probably trigger some kind of copy constructor that will most certainly do some work.

[czardas]

Why is there no ^= operator, or is there?

Nevr mind - I can live without it.

Edited February 7, 2010 by czardas

[UEZ]

#include<iostream>
#include <time.h>

using namespace std;

int main()
{
    clock_t init, final;
    init=clock();
    int i=1;
    while (i<10000000)
    {
        i++;
    }
    final=clock()-init;
    cout << (double)final / ((double)CLOCKS_PER_SEC) <<"\n";
    return 0;
}

0.09 sec

$start = TimerInit()
$max=10000000
$i=1
While $i<$max
    $i=$i+1
WEnd
ConsoleWrite(TimerDiff($start) & @CRLF& @CRLF & @CRLF & @CRLF )

15 sec

$max = 10000000
$start = TimerInit()
For $i=1 To $max
Next
ConsoleWrite(@CRLF & @CRLF & TimerDiff($start)/1000 & @CRLF)

0.8 sec

In my opinion the comparison is wrong with While/WEnd and For/Next because While/WEnd is calculating and For/Next not!

To compare correctly you have to add also a simple calculation to For/Next:

$start = TimerInit()
$max=10000000
$i=1
Do
$i+=1
Until $i>=$max
ConsoleWrite(Round(TimerDiff($start), 0) & " ms" & @CRLF)

$start = TimerInit()
$max = 10000000
$j=0
$start = TimerInit()
For $i=1 To $max
    $j+=1
Next
ConsoleWrite(Round(TimerDiff($start), 0) & " ms" & @CRLF)

Nevertheless For/Next is faster than While/WEnd or Do/Until!

UEZ

Edited February 5, 2010 by UEZ

[Beege]

so I just applied what monoceres and WeaponX were talking about with using _WinAPI_BitBlt() vs _GDIPlus_GraphicsDrawImageRect() to a recent script I was doing to try and learn some graphics stuff and WOW did it make a difference. If you have a sec run this Scrolling Line Graph example that I put together. Notice how much less CPU Time _WinAPI_BitBlt() uses, and most important, how much smoother it looks!

expandcollapse popup

#include <GuiConstantsEx.au3>
#include <GDIPlus.au3>
#include <WindowsConstants.au3>

Global $Width = 800, $Height = 250
Global $hGUI = GUICreate("Scrolling Line Graph", $Width, $Height)
Global $Steps = 250, $StepSize = Int($Width / $Steps), $Shift_Distance = $Width-$StepSize

_GDIPlus_Startup()
Global $hGraphic = _GDIPlus_GraphicsCreateFromHWND($hGUI)
Global $hBitmap = _GDIPlus_BitmapCreateFromGraphics($Width, $Height, $hGraphic)
Global $hBackbuffer = _GDIPlus_ImageGetGraphicsContext($hBitmap)
Global $hPen = _GDIPlus_PenCreate(0xFF00FF00, 1)
Global $ScreenDc=_WinAPI_GetDC($hGUI)

GUISetState()

$start = _GetProcessTimes()
For $i = 1 to 250
    _UpdateGraph(Random(1, 99)*.01, False)
    Sleep(20)
Next
$end = _GetProcessTimes()
ConsoleWrite(@CRLF & 'CPU Time = ' & ($end-$Start) & ' using _GDIPlus_GraphicsDrawImageRect() ' & @CRLF)

_Clear()
Sleep(1000)

$start = _GetProcessTimes()
For $i = 1 to 250
    _UpdateGraph(Random(1, 99)*.01)
    Sleep(20)
Next
$end = _GetProcessTimes()
ConsoleWrite('CPU Time = ' & ($end-$Start) & ' using _WinAPI_BitBlt() ' & @CRLF)

_Exit()

Func _UpdateGraph($iValue, $bBitBlt = True)

    Static $Y_Last = 0

    If Not $Y_Last Then
        $Y_Last = Int($Height-($iValue * $Height))
        Return
    EndIf

    Local $Y = Int($Height-($iValue * $Height))

    Local $hClone = _GDIPlus_BitmapCloneArea($hBitmap, $StepSize, 0, $Shift_Distance, $Height);
    _GDIPlus_GraphicsClear($hBackbuffer, 0xFF000000);
    _GDIPlus_GraphicsDrawImageRect($hBackbuffer, $hClone, 0, 0, $Shift_Distance, $Height)
    _GDIPlus_GraphicsDrawLine($hBackbuffer, $Shift_Distance, $Y_Last, $Width-1, $Y, $hPen)

    If $bBitBlt Then
        $gdibitmap=_GDIPlus_BitmapCreateHBITMAPFromBitmap($hBitmap)
        $dc=_WinAPI_CreateCompatibleDC($ScreenDc)
        _WinAPI_SelectObject($dc,$gdibitmap)
        _WinAPI_BitBlt($ScreenDc,0,0,$Width,$Height,$dc,0,0,$SRCCOPY )
        _WinAPI_DeleteObject($gdibitmap)
        _WinAPI_DeleteDC($dc)
    Else
        _GDIPlus_GraphicsDrawImageRect($hGraphic, $hBitmap, 0, 0, $Width, $Height)
    EndIf

    _GDIPlus_ImageDispose($hClone)
    $Y_Last = $Y

EndFunc   ;==>_UpdateGraph

Func _Clear()
_GDIPlus_GraphicsClear($hBackbuffer, 0xFF000000);
_GDIPlus_GraphicsDrawImageRect($hGraphic, $hBitmap, 0, 0, $Width, $Height)
EndFunc

Func _Exit()
    _GDIPlus_PenDispose($hPen)
    _GDIPlus_GraphicsDispose($hGraphic)
    _GDIPlus_Shutdown()
    _WinAPI_ReleaseDC($hGUI, $ScreenDc)
    Exit
EndFunc   ;==>_Exit

Func _GetProcessTimes()
    Static $hScripthandle = _WinAPI_GetCurrentProcess()
    Static $PCreationTime = DllStructCreate($tagFILETIME), $PExitTime = DllStructCreate($tagFILETIME), $PKernelTime = DllStructCreate($tagFILETIME), $PUserTime = DllStructCreate($tagFILETIME)
    DllCall('Kernel32.dll', "int", "GetProcessTimes", "hwnd", $hScripthandle, "ptr", DllStructGetPtr($PCreationTime), "ptr", DllStructGetPtr($PExitTime), "ptr", DllStructGetPtr($PKernelTime), "ptr", DllStructGetPtr($PUserTime))
    Return DllStructGetData($PKernelTime, 1)+DllStructGetData($PUserTime, 1)
EndFunc   ;==>_ProcessCalc

CPU Time = 61562500 using _GDIPlus_GraphicsDrawImageRect() 
CPU Time = 15468750 using _WinAPI_BitBlt()