2

I've written a javascript to emulate WPF DockPanel Layout behaviour in HTML through the help of javascript.

Now i'm running into performance issues once i begin nesting those panels to a recursion level of 10. Oddly enough it's nothing more than ordinary recursion and on the deepest level the function in question is finishing in between 0,2 and 2ms.

Profiler Image

Now either i do have some ghost performance loss, or is there a massive cost in invoking recursion for javascript? I hope one of you knows.

If there's a cost the obvious solution would be recursion unrolling which would be rather sad.

I've read SO-Recursive function calling in JavaScript On this, but does that really mean that i may have to accept recursiondepth n = functioncost * (10^(n-1)) for every depth of recursion i'll go?

Also this (which refutes the idea of recursion beeing slower than iteration) SO - Is iteration faster than recursion, or just less prone to stack overflows?

And this Programmers: Performance: recursion vs. iteration in Javascript, which speaks for iteration beeing faster than recursion by a factor of 4 (sigh...)

This is a general question, independant of browser JS engine. If you know about it beeing slow in one but fast in another that information would be welcome too. I was assuming that it would be the same in all.

Wrapup information for visitors: The impact of recursion vs iteration is very significant. Iteration in general wins.

  • Factor FF30 : 5~
  • Factor Chrome 36: 40~
  • Factor Native IE8, WinXP: 10~
Community
  • 1
  • 1
Dbl
  • 5,634
  • 3
  • 41
  • 66
  • Which JavaScript engine are you using here? Safari, Chrome, Firefox and Internet Explorer all have completely different implementations. – tadman Jul 23 '14 at 16:10
  • @tadman added some information – Dbl Jul 23 '14 at 16:16
  • guess i'll investigate some with a custom test script until someone contributes to figure this out, since there's conflicting test results in the linked posts – Dbl Jul 23 '14 at 16:28
  • Each JavaScript engine is built with different performance optimization techniques and they behave quite differently on certain types of operations. There are some very general rules, but recursion itself isn't something that's normally benchmarked. – tadman Jul 23 '14 at 16:30

1 Answers1

6

Yes, the recursion has a very big impact on performance in JavaScript, always avoid it, use only iterative approach

A simple example of fibonacci function (recursion vs loop):

http://jsperf.com/fibonacci-recursive-or-iterative/4

Another example written by me some time ago (object navigation):

http://jsperf.com/object-navigation

var a = {
    b: {
        c: 'd'
    }
};

find(a, 'b/c'); // => 'd'

OP-Test: http://jsperf.com/iterative-vs-recursive-method-invocation/3

Dbl
  • 5,634
  • 3
  • 41
  • 66
micnic
  • 10,915
  • 5
  • 44
  • 55
  • 1
    jesus... a factor of almost 60 on my machine for both FF30 and chrome 36. Whats your change between revision 4->5 tho? It went from a factor of 60 to 2 now? – Dbl Jul 23 '14 at 16:46
  • is there a way to move this benchmark into setTimeout? apparently because of me having to close the "slow script" dialog i can't do a proper measurement in native IE 8 – Dbl Jul 23 '14 at 16:52
  • 1
    It's a bit unfair to use fibonacci because the recursion is exponential. This doesn't match the normal usage of recursion in JS. – fgb Jul 23 '14 at 16:56
  • @micnic in my particular case i have no memo information, thus #4 is more conclusive, which i modified with #8 for IE8 support. Thanks for your help. – Dbl Jul 23 '14 at 17:09
  • @AndreasMüller, check my updated answer with a "non-exponential" recursion, the result is the same: recursion is very expensive – micnic Jul 23 '14 at 17:59
  • @micnic ok... wow. that difference is even more significant and comes closer to my prod environment since i am storing data and switching context a lot. if it's that big with this little object structure it should be insane when there's like 50 nested properties. thanks again! – Dbl Jul 23 '14 at 18:27