Exponential string concatenation hangs Mozilla

VERIFIED INVALID

Status

()

VERIFIED INVALID
17 years ago
16 years ago

People

(Reporter: rb, Assigned: rogerl)

Tracking

Trunk
x86
Windows 2000
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Reporter)

Description

17 years ago
From Bugzilla Helper:
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.0rc2)
Gecko/20020510
BuildID:    2002051006

Mozilla 1.0 RC2 allocates large amounts of memory when running the attached
JavaScript-Code (some kind of JavaScript-Ticker). Sometimes the page comes up,
mostly not. The Windows Task-Manager says that Mozilla allocates up to 200 Meg
of RAM rapidly increasing.

Reproducible: Always
Steps to Reproduce:
1. Load the page
2. watch Windows swapping ;-)


<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

<html>
<head>
	<title>Untitled</title>

  <script language="JavaScript">
  <!--
  <!-- Begin
  // THESE VARIABLES CAN BE CHANGED //
  
  var myMainMessage="  Test  ***";
  var speed=150;
  var scrollingRegion=85;
  
  // END CHANGEABLE VARIABLES //
  var startPosition=0;
  function mainTextScroller() {
      if (myMainMessage)
        {
          var mainMessage=myMainMessage;
          var tempLoc=(scrollingRegion*3/mainMessage.length)+1;
          if (tempLoc<1) {tempLoc=1}
          var counter;
          for(counter=0;counter<=tempLoc;counter++)
             mainMessage+=mainMessage;
  
document.mainForm.mainTextScroller.value=mainMessage.substring(startPosition,startPosition+scrollingRegion);
          startPosition++;
          if(startPosition>scrollingRegion) startPosition=0;
          setTimeout("mainTextScroller()",speed); }
        }
  //  End -->
  //-->
  </script>

</head>



<body onload="mainTextScroller();">

<form name="mainForm">
<SCRIPT LANGUAGE=JavaScript>
    
if (myMainMessage) {
  document.write('<center> \n');
  document.write('<input type="text" name="mainTextScroller" size="39"
style="height: 20px; font-size: 9px; line-height: 14px; width: 327px;
border-style: solid; border-color:#3A9FEF;"> \n');
  document.write('</center> \n');
}
</SCRIPT>

</form>

</body>
</html>

Comment 1

17 years ago
Created attachment 84662 [details]
Reporter's HTML testcase

Comment 2

17 years ago
We're going to have to mark this one invalid. The testcase cannot be
loaded by IE6 any better than Mozilla trunk 2002052008. All available
memory gets exhausted on my WinNT box (128M RAM), with either browser.


Here is the reason why:

      for(var counter=0; counter<=tempLoc; counter++)
        mainMessage += mainMessage;


This is not the way to code a ticker! Don't concatenate the message string
with itself repeatedly; you create exponential string growth that way.

I was able to safely load the testcase in Mozilla by saving it locally
and setting a future breakpoint in 

      Tools > Web Development > JavaScript Debugger 


I found that:

tempLoc
$[0] = [double] 24.181818181818183

counter
$[1] = [void] void
mainMessage.length
$[2] = [integer] 11

counter
$[2] = [integer] 1
mainMessage.length
$[3] = [integer] 22

counter
$[2] = [integer] 2
mainMessage.length
$[3] = [integer] 44


And so on. This means, since the max value of |counter| is 24, that
we're headed for a string of length 11* 2^24 = 184,549,376 characters !!!
This simply uses up all the memory on your computer. 

Compare the same mistake made in bug 89011. In that case, the string
got up to 1,900,543 characters.  

We (and IE6) are able to handle that page, because of the fix for 
bug 56940, "O(n**2) and O(n**3) growth too easy with JS string concat".
But neither we nor IE6 can handle the testcase here, because the final
string is nearly 100 times bigger. Again, neither that site nor this
testcase is coding the ticker in a sensible way. 

For an example of other ways of doing it, see
  http://devedge.netscape.com/evangelism/examples/stock-ticker/
Status: UNCONFIRMED → RESOLVED
Last Resolved: 17 years ago
Resolution: --- → INVALID
Summary: 1.0 RC2 allocates large amounts of memory → Exponential string concatenation hangs Mozilla

Comment 3

17 years ago
Marking Verified. 

Roland, thank you for this report, and for providing a testcase.
This question often comes up. Note there are other ways of doing
the ticker besides the example I quoted at 

  http://devedge.netscape.com/evangelism/examples/stock-ticker/

For example, just take the message string and keep removing the
first character away from the beginning and add it to the end.
That keeps the size of the message string constant, while 
translating the message from right to left. 

I believe in the devedge example above, they put the message string
into a <div>, and move the <div> instead of changing the string.
It is an interesting technique -
Status: RESOLVED → VERIFIED

Comment 4

16 years ago
*** Bug 166770 has been marked as a duplicate of this bug. ***
You need to log in before you can comment on or make changes to this bug.