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.
We did very little work on performance in V1. In particular, function overhead is very heavy in V1 but we are working on improving this in V2.
Hi
Both the function and the filter is called recursively – you are just passing the input in two different ways – argument or pipeline. In fact, function and filter are just syntactical sugar for the same. These two definitions are the same:
function test1{ process { $_ } }
filter test2{ $_ }
Try to do a type function:test2 and see the output.
Best regards
Per
http://www.msgoodies.com
Is the delay explained as simply as:
function – filter = parameter binding
?
Yes, yes … functions and filters are the same thing … that wasn’t my point. My point was that the filter was being recursed via a pipeline.
In fact, if I understand things correctly … the filter method should have pretty much the same overhead as the function, plus the overhead of running that mini pipeline?