Monday, August 20th, 2007

How stacked are you?

Category: JavaScript

Mark Wubben, of sIFR fame, had to write a depth-first tree iterator and was wondering what the call stack limitations were for the various browsers, so he wrote:

javascript

  1. function Foo() {
  2.     Foo.count++;
  3. }
  4.  
  5. Foo.count = 0;
  6. Foo.prototype.invoke = function() {
  7.     new Foo().invoke();
  8. };
  9.  
  10. setTimeout(function() {
  11.     document.body.innerHTML = "Maximum call stack size: " + Foo.count;
  12. }, 1000);
  13.  
  14. new Foo().invoke();

which resulted in:

  • Safari 2.04: 100
  • Firefox 2.0.0.6: 1001
  • Internet Explorer 7: 1789
  • Opera 9.22: 3340

Posted by Dion Almaer at 4:36 am
16 Comments

+++--
3.4 rating from 21 votes

16 Comments »

Comments feed TrackBack URI

Opera rules.

Comment by Pierre X. — August 20, 2007

Safari is to be blamed for its small call stack size.

“Maximum call stack size exceeded” exception first causes my application’s normal function being terminated and leaving in a buggy status. And later my javascript runs in infinite loop because of former buggy status and then hangs the whole Safari browsers with 100% CPU usage.

I do hope this bug can be fixed when Safari 3 is to be released. But I feel sad to see that this bug is left unfixed for more than 2 years, according to the bug history at http://bugs.webkit.org/show_bug.cgi?id=4045

Comment by Zhou Renjian — August 20, 2007

I did the very same thing once to check the maximum cookie size in different browsers… It seems that trial and error is the only way.

Comment by ch__ — August 20, 2007

I would add that Swift got 1000, IE6 had 893, but FF3 has change nothing.

Comment by mefisto — August 20, 2007

To be clear, in Safari 3.0.3 beta this test yields the result “Maximum call stack size: 100”

Comment by Gudbergur — August 20, 2007

Why do you people even care about Safari when IE5 gets barely mentioned? (these two currently have equal market share – 1.5%) Is it a new / old thing? Just asking..
my source: http://www.w3schools.com/browsers/browsers_stats.asp

Comment by yct — August 20, 2007

Yeah, this got me a couple times when doing some very (seemingly) basic JSON serializations in Ext. What a huge pain.

Comment by Steve — August 20, 2007

We’ve run into this problem with safari, too. We have an animation that is basically a classic node and edge graph, which we process recursively in javascript. It breaks on reasonably large datasets in safari. Turns out there’s both a ticket for it, and a patch
http://bugs.webkit.org/attachment.cgi?id=13359&action=edit
Both are oooold, but the patch has not been accepted. What’s up?

There is a super easy solution to this, of course- build your own stack (just and array), replace all recursive calls with stack pushes, and in a while loop pop elements from the stack and process until stack is empty.

At first our team thought the stack limit was for security reasons- limits to the number of popunders or remote scripting attacks. But wouldn’t such attacks just use a while loop, or the three line recursion limit fix above?

Webkit- we love you. Please fix this bug!

-j

Comment by jason — August 20, 2007

One thing is interesting to me is that the maximum stack size in Opera is not fixed, you may reduced that number to pretty small with some JS syntax. F

For example ( which is a extreme case )

Foo.prototype.invoke = function() {
try{ try{ try{ try{ try{
try{ try{ try{ try{ try{

new Foo().invoke()

}catch(e){}}catch(e){}}catch(e){}}catch(e){}}catch(e){}
}catch(e){}}catch(e){}}catch(e){}}catch(e){}}catch(e){}
}

//In my Opera 9.22
//Maximum call stack size: 773

Comment by Hedger Wang — August 20, 2007

javascript:(function(){function Foo(){Foo.count++}Foo.count=0;Foo.prototype.invoke=function(){new Foo().invoke()};setTimeout(function(){document.body.innerHTML=”Maximum call stack size: “+Foo.count},1000);new Foo().invoke()})()

Comment by OneLiner — August 20, 2007

See also this oldie-but-goodie:

http://blogs.msdn.com/ericlippert/archive/2005/08/01/442606.aspx

Comment by David Golightly — August 20, 2007

http://w3future.com/weblog/2006/02/28.xml#tailCallEliminationInJavascript

Comment by carmen — August 20, 2007

Publicity helps :)

It seems that they have fixed the bug a moment ago:
http://trac.webkit.org/projects/webkit/changeset/25161

Comment by Sebastian Werner — August 21, 2007

You can wipe your call stack clean using setTimeout, though of course then you’ll need some kind of callback mechanism. (setTimeout is also nice to use if a library calls your functions and discards any exceptions thrown.)

Comment by Tim Cooijmans — August 21, 2007

Brendan Eich chimed in on my original post, the 1000 call count limit is going to be removed: http://novemberborn.net/javascript/callstack-size#c000873

Comment by Mark Wubben — August 21, 2007

I just installed Safari 3 and was very disappointed to see the call stack limit is still 100.

Comment by Matt Sielski — October 19, 2007

Leave a comment

You must be logged in to post a comment.