Closed
Bug 2235
Opened 26 years ago
Closed 26 years ago
String catenation in JavaScript has non-linear memory/time usage
Categories
(Core :: JavaScript Engine, defect, P1)
Core
JavaScript Engine
Tracking
()
M3
People
(Reporter: mff, Assigned: mike+mozilla)
Details
This JavaScript program exhibits non-linear (usually quadratic)
time/memory usage. Try arg0 values of 10, 100, 1000, 10000, etc.
Eventually, you will get a out-of-memory error from JS_malloc (jsapi.c).
I have tested this using JavaScript v1.4-2 (12-13-98 tarball)
on both Linux and SPARC platforms. It crashes on both.
The easiest way to see the quadratic memory usage is
to run "top" during successively larger test cases.
var s = "";
s = "abcd";
for (i = 0; i < arguments[0]; i++) {
s += s;
}
print(i);
I think the bug is somewhere in str_concat (jsstr.c),
but haven't had a chance to find it. It seems that
JS_free isn't being called, possibly on a temporary
variable. If I figure it out tonight, I'll mail in a patch.
I searched the bug archives, but didn't find anything similar.
Sorry if this is a repeat.
Thanks,
Mary
WHOOPS! Wrong program. Here's the one I meant to send you!
var s = "";
x = "abcd";
for (i = 0; i < arguments[0]; i++) {
s += x;
}
Assignee | ||
Comment 2•26 years ago
|
||
Thanks for the great report!
This bug seems similar to one we have filed against 4.51 in the internal bug
system. I'd move the bug report to bugzilla so that I we could refer to it
here, but I think that would confuse the 4.51 guys, who are a little behind on
the open-source curve.
The gist of the bug is that opening javascript scripts with extremely long lines
exhibits quadratic time/memory usage. One way to demonstrate this is to try to
open a javascript url, e.g.:
javascript:'cccccccccccccccc ... ' // repeated 300k times
A first look at the problem showed it to be in collecting the current line in a
buffer in jsscan.c, which never gets freed when it's expanded.
I'm slated to look at a fix, but it'd be nice if this were another facet of the
same problem you're looking at.
-- Mike
Assignee | ||
Comment 3•26 years ago
|
||
Thanks for the great report!
This bug seems similar to one we have filed against 4.51 in the internal bug
system. I'd move the bug report to bugzilla so that I we could refer to it
here, but I think that would confuse the 4.51 guys, who are a little behind on
the open-source curve.
The gist of the bug is that opening javascript scripts with extremely long lines
exhibits quadratic time/memory usage. One way to demonstrate this is to try to
open a javascript url, e.g.:
javascript:'cccccccccccccccc ... ' // repeated 300k times
A first look at the problem showed it to be in collecting the current line in a
buffer in jsscan.c, which never gets freed when it's expanded.
I'm slated to look at a fix, but it'd be nice if this were another facet of the
same problem you're looking at.
-- Mike
Here's one last observation :
Note that in js_NewString.c (jsstr.c), a new tagged GC thing is alloc'd
(a 2 word struct). NewString initializes str->chars (the first word)
to its chars argument. This chars argument is (almost always) the result of
a call to JS_malloc (non-GC'd heap!) (see the call that's causing my
problem is on line 1805 in jsinterp.c). After reading most of the GC code,
I'm pretty convinced that this malloc'd chars value will *never* be freed.
One problem is that the GC will only be invoked when *its* heap fills up
(not when malloc's heap fills up). Even if you force the GC to run,
I don't see where the JS_malloc'd values stored in String things will
be freed. That's my guess. Thanks for the quick reply. mff
Assignee | ||
Updated•26 years ago
|
Status: NEW → ASSIGNED
Assignee | ||
Comment 5•26 years ago
|
||
Character strings associated with String objects and primitives get freed when
the associated GC-thing is collected; when the string is finalized,
js_FinalizeString gets called and frees the associated heap-allocated string.
Maybe the garbage collector is never being called inside the loop in your test?
If you're using the js standalone shell, does adding a GC() call inside the loop
help? If this does, I wonder if there isn't someplace in the interpreter loop
that we could add a GC check to without incurring too much overhead in the
common case... any suggestions?
GC() is definitely not being called inside the loop.
I don't know how to invoke it from the interpretor --
and can't find how to do it. Pls let me know how & I'll try that.
I will try to add a GC() call in jsinterp & see what that does.
thx mff
Assignee | ||
Comment 7•26 years ago
|
||
Any progress on this one? Last I talked to you (email) you were looking at
something like removing some of the heuristic aspects of deciding when to
collect and putting a counter in the allocator instead. It you have what looks
like a stable fix, it'd be great to get it in.
The 300K string issue I mentioned is almost certainly a different issue than
this one, as it turns out. The cause of the non-linearity is probably the same
- frequent copies + memory never freed, but it occurs in the scanner. That
problem was resolved by changing the string-growth increment to increase if the
string is grown more than once.
Mike
Comment 9•26 years ago
|
||
per leger, assigning QA contacts to all open bugs without QA contacts according
to list at http://bugzilla.mozilla.org/describecomponents.cgi?product=Browser
Assignee | ||
Updated•26 years ago
|
Status: ASSIGNED → RESOLVED
Closed: 26 years ago
Resolution: --- → DUPLICATE
Assignee | ||
Comment 10•26 years ago
|
||
This memory blowup durned out to be a flaw with the js.c standalone interpreter
(or possibly jsj, the liveconnect-enabled interpreter.) Most applications using
js, such as the browser, register a 'branch callback' function that gets called
whenever the javascript interpreter makes a branch. Usually this includes a
check to see whether the garbage collector needs to be called. Without this
check, the garbage collector is called in loops like the one below only when the
system runs out of memory or triggers some other heuristic check.
At least, that's my understanding.
I'm making a new (low-priority!) bug against js.c and setting this bug to be a
dup of that.
*** This bug has been marked as a duplicate of 3649 ***
Comment 11•26 years ago
|
||
Marking Verified.
Comment 12•26 years ago
|
||
Changing component to "Javascript Engine". "Javascript" component is being
retired.
You need to log in
before you can comment on or make changes to this bug.
Description
•