89011 - Exponential string concatenation hangs Mozilla

Status: VERIFIED DUPLICATE of bug 56940

(Core :: JavaScript Engine, defect)

Description

[reining]

From Bugzilla Helper:
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.2) Gecko/20010628
BuildID:    2001062823

the system first is going very slowly and then the hole system hangs up, so that
I can't switch to console etc. Maybe 'cause of the Newsticker there made with
Javascript?

Reproducible: Always
Steps to Reproduce:
1.just go to the page
2.
3.

Actual Results:  system hangs up

Expected Results:  show the page :o)

Comment 1

[Junk_HbJ]

Alse seeing this with 2001070204 / Win98SE.

After loading this page, Mozilla starts to allocate memory without reason; at
the end, System Monitor showed that the lizard consumed over 150 MB of RAM.

Shouldn't happen, I'd say...

Comment 2

[Dwayne]

Confirming on 2001-06-28-04.

OS should be changed to all.  Over to Javascript engine?

Comment 3

[Conor Lennon]

Changing OS to all.

I think the problem comes down to the following javascript:

               c+=" "+c;

This is inside a loop while is looped 15 times.  The function that contains the
loop is repeatly executed through setTimeout().
While I can see what is being attempted, I think it is being done wrong.
I can see how the above command could cause memory problems.

Comment 4

[Matthias Versen [:Matti]]

Thos doesn't crash my win2k but I have 512MB RAM.
Mozilla use many RAM with this page:

Mozilla:
40MB - 110MB - 180MB - 240 MB - 40MB........ 1s     2.      3s.     4s.     
5s.........

NS 4.77DE

10MB - 15MB - 30Mb - 10MB ......

200Mb is very much.....
and your system hangs because it's out of RAM

-> JS engine (one of the best Mozilla QAs will look at this bug :-)

Comment 5

[Matthias Versen [:Matti]]

grr, bugzilla destroyed my little table :-(

40MB/1s , 110MB/2s ....

Comment 6

[Phil Schwartau]

The ticker() function at the site is as follows:

var d,e=0; 
function ticker() 
{ 
  var a,b,c; 
  c="  07.07.-08.07. UKW-Contest "
  b=(400/c.length)+1; 
  for(a=0;a<=b;a=a+1) c+=" "+c; 
  document.laufschrift.ticker.value=c.substring(e,e+400); 
  if(e++==400) e=0; 
  d=setTimeout("ticker()",1000/5); 
} 

Comment 7

[Phil Schwartau]

> I think the problem comes down to the following javascript:
>
>                   c += " " + c;
>
> This is inside a loop while is looped 15 times (actually 16, = 0 to 15)


Conor is right: this is what causes memory to run out. The string
concatenation is exponentional. The string c starts out with 28 characters,
but grows to 1,900,543 characters! Then the ticker() function is called 
recursively and we start all over again. 


This reduced testcase exhausts all memory on my WinNT box:

var c = 'xxxxxxxxxxxxxxxxxxxxxxxxxxxx';
test(); 

function test() 
{ 
 for(var i=0; i<=15; i++) {c += c;}
 test();
}

Comment 8

[Phil Schwartau]

This is a duplicate bug 56940:
"O(n**2) and O(n**3) growth too easy with JS string concat"

Compare bug 40391, bug 64589, which are also dupes of bug 56940.

Personally, I would like to think that the current bug is invalid.
If you make a string of 1,900,543 characters, don't complain if you
run out of memory! Especially with no idea of the user's hardware.
There are other ways to make the marquee effect here without doing this!

However, IE4.7 handles the give site without any problem whatsoever
on my WinNT box. NN4.7 handles it, bug not as well.


*** This bug has been marked as a duplicate of 56940 ***

Comment 9

[Phil Schwartau]

Marking Verified Duplicate -