Sunday, February 1, 2009

Ch4, Ex3

Following code fragment can be used to measure the time elasped
for N in 1..40 do 
local T1 T2 R in
T1 = {Property.get 'time.total'}
R = {Fib N}
T2 = {Property.get 'time.total'}
{Show fib(num:N result:R timeTaken:(T2-T1))}
end
end


Results with Sequential definition of Fib:
fib(num:10 result:55 timeTaken:0)
fib(num:11 result:89 timeTaken:0)
fib(num:12 result:144 timeTaken:0)
fib(num:13 result:233 timeTaken:0)
fib(num:14 result:377 timeTaken:0)
fib(num:15 result:610 timeTaken:0)
fib(num:16 result:987 timeTaken:0)
fib(num:17 result:1597 timeTaken:0)
fib(num:18 result:2584 timeTaken:0)
fib(num:19 result:4181 timeTaken:16)
fib(num:20 result:6765 timeTaken:0)
fib(num:21 result:10946 timeTaken:0)
fib(num:22 result:17711 timeTaken:15)
fib(num:23 result:28657 timeTaken:16)
fib(num:24 result:46368 timeTaken:15)
fib(num:25 result:75025 timeTaken:63)
fib(num:26 result:121393 timeTaken:31)
fib(num:27 result:196418 timeTaken:31)
fib(num:28 result:317811 timeTaken:93)
fib(num:29 result:514229 timeTaken:1123)
fib(num:30 result:832040 timeTaken:233)
fib(num:31 result:1346269 timeTaken:296)
fib(num:32 result:2178309 timeTaken:515)
fib(num:33 result:3524578 timeTaken:1963)
fib(num:34 result:5702887 timeTaken:2447)
fib(num:35 result:9227465 timeTaken:3554)
fib(num:36 result:14930352 timeTaken:5579)
fib(num:37 result:24157817 timeTaken:9398)
fib(num:38 result:39088169 timeTaken:15413)
fib(num:39 result:63245986 timeTaken:26198)
fib(num:40 result:102334155 timeTaken:42329)

Results with Concurrent definition of Fib:
fib(num:10 result:55 timeTaken:0)
fib(num:11 result:89 timeTaken:0)
fib(num:12 result:144 timeTaken:16)
fib(num:13 result:233 timeTaken:0)
fib(num:14 result:377 timeTaken:0)
fib(num:15 result:610 timeTaken:0)
fib(num:16 result:987 timeTaken:0)
fib(num:17 result:1597 timeTaken:0)
fib(num:18 result:2584 timeTaken:0)
fib(num:19 result:4181 timeTaken:138)
fib(num:20 result:6765 timeTaken:0)
fib(num:21 result:10946 timeTaken:16)
fib(num:22 result:17711 timeTaken:30)
fib(num:23 result:28657 timeTaken:47)
fib(num:24 result:46368 timeTaken:76)
fib(num:25 result:75025 timeTaken:1139)
fib(num:26 result:121393 timeTaken:200)
fib(num:27 result:196418 timeTaken:324)
fib(num:28 result:317811 timeTaken:538)
fib(num:29 result:514229 timeTaken:1662)
fib(num:30 result:832040 timeTaken:2847)
fib(num:31 result:1346269 timeTaken:4417)
fib(num:32 result:2178309 timeTaken:25378)
fib(num:33 result:3524578 timeTaken:10957)
fib(num:34 result:5702887 timeTaken:17760)
*** Warning: Mozart: virtual memory exhausted.
.......It couldn't even go beyond 34.

Conclusion:
It is evident from above results that as N goes high the concurrent version becomes slower and slower. The reason is the threads overhead, moreover significantly more active memory needed to run the concurrent version and gc needs to do alot of work.

Number of Threads created by concurrent Fib:
Number of threads created by {Fib N}
= 1 + threads created by {Fib N-1} + threads created by {Fib N-2}

N = 3, threads = 1
N = 4, threads = 1 + created by {Fib 3} + created by {Fib 2}
= 1 + 1 + 0 = 2
similarly
N = 5, threads = 1 + 2 + 1 = 4
N = 6, threads = 1 + 4 + 2 = 7
N = 7, threads = 12
N = 8, threads = 20
.....
....
Number of threads created by {Fib N} = {Fib N} - 1

Note: {Show arg} shows arg on buffer *Oz Emulator* and not in Oz Browser.

No comments:

Post a Comment