Huddled Masses
Posts Tagged ‘Timing’
February 4th, 2008 | 
Author: So, I posted a story about Fibonacci sequences and noticed that the recursion in PowerShell is really rather slow. But I also noticed something interesting — I had expected that recursing using a function would be a little cheaper (and faster) than recursing using the pipeline, and it turns out that it’s not. At all.
I’d love to hear some thoughts on why I got the speed results I got here. At first I thought it was something about type coercion, but as you can see, I tried casting everything to no avail. There’s no difference if I don’t output anything, and in fact, the non-recursive algorithm can trivially output every Fibonacci number in the sequence without affecting it’s time (I actually altered it so it didn’t to keep the output clean).
Obviously I expected the recursive algorithms to be slow and scale badly because of the amount of work involved, but how is it that the pipeline-recursive “filter” outperforms the plain old recursive function (albeit by an infinitesimal fraction)?
[08]: function fibfunction([int]$i){ if($i -lt 2) { 1 }else{ [int](fibfunction ($i-1)) + [int](fibfunction ($i-2)) } }
[09]: filter fibfilter{ if($_-lt2){1}else{[int]([int]$_-1|fibfilter)+[int]([int]$_-2|fibfilter)}}
[10]: [int]$size = 18
[11]: fibfunction $size
4181
[12]: $size | fibfilter
4181
[13]: [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
4181
[14]: get-history -count 3 | fl CommandLine,@{l="Duration"; e={$_.EndExecutionTime - $_.StartExecutionTime}}
CommandLine : fibfunction $size
Duration : 00:00:02.4764040
CommandLine : $size | fibfilter
Duration : 00:00:02.2137255
CommandLine : [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
Duration : 00:00:00.0048825
[15]: [int]$size = 21
[16]: fibfunction $size
17711
[17]: $size | fibfilter
17711
[18]: [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
17711
[19]: get-history -count 3 | fl CommandLine,@{l="Duration"; e={$_.EndExecutionTime - $_.StartExecutionTime}}
CommandLine : $null = fibfunction $size
Duration : 00:00:10.5764715
CommandLine : $null = $size | fibfilter
Duration : 00:00:09.6282900
CommandLine : $null = [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
Duration : 00:00:00.0058590
P.S.: The numbers in braces with the colon (like [18]: ... ) is my prompt.
Posted in Huddled | 
Tags: Fibonacci, Performance, PowerShell, Recursion, Scripting, Timing | 
4 Comments »