Closed Bug 33390 Opened 25 years ago Closed 25 years ago

memory exhausted with javascript array

Categories

(Core :: JavaScript Engine, defect, P1)

Product:
Core
Component:
JavaScript Engine
Type:
defect

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla0.8

People

(Reporter: wrobell, Assigned: brendan)

References

(Blocks 1 open bug)

Details

(Keywords: js1.5)

Attachments

(14 files)

zipped html file illustrating the problem
301.93 KB, application/octet-stream
Details
Standalone JS testcase (to be run in JS shell)
203 bytes, text/plain
Details
testcase generator that uses new Array; and x[i][j] = ...
189 bytes, text/plain
Details
testcase generator that uses array initializers
182 bytes, text/plain
Details
proposed fix
50.42 KB, patch
Details | Diff | Splinter Review
better fix, avoid O(n**2) in JS_ARENA_GROW too
56.47 KB, patch
Details | Diff | Splinter Review
argh, JS_ARENAMETER had a bogus old variance calc from '95
57.70 KB, patch
Details | Diff | Splinter Review
final proposed patch (for now)
66.16 KB, patch
Details | Diff | Splinter Review
Argh, last patch over-left-shifted jsarena.h code in vi to expand tabs
66.01 KB, patch
Details | Diff | Splinter Review
diff -wu of last (final, really final) patch
57.69 KB, patch
Details | Diff | Splinter Review
Recycle function and var nodes too; rename JS_ArenaRealloc
71.23 KB, patch
Details | Diff | Splinter Review
Same as last patch, but I fully fixed the unindentation damage in jsarena.h
68.82 KB, patch
Details | Diff | Splinter Review
updated patch to apply to top of cvs trunk
66.31 KB, patch
Details | Diff | Splinter Review
let's try that again.... this is the one to review
65.79 KB, patch
Details | Diff | Splinter Review
From Bugzilla Helper: User-Agent: Mozilla/4.71 [en] (X11; I; Linux 2.3.47 i586; Nav) BuildID: 2000032309 Script below generates HTML file with JavaScript script, which creates table with $j*$i elements. When $j equals to 25 (at $i=256) then mozilla grows to about 48MB. Increasing $j to ie. 255 causes mozilla to exhaust system memory (if limits are unlimited of course). The same thing is with netscape. I know about this bug from my friend Robert Kurowski. --------------------------------------- #!/usr/bin/perl $j=256; print <<END; <html> <head> <title>JavaScript Test</title> <script type="text/javascript"><!-- END while ($j--) { $i=256; while ($i--) { print "x[$j][$i]='".$i*$j."';\n"; } } print <<END; </script> </head> <body> <p> OK! </p> </body> </html> END ------------------------------------- Reproducible: Always Steps to Reproduce: Look at description field. Actual Results: Memory system exhausted. Expected Results: Show "OK" string.
I get this too (linuxppc buildid 2000041919). Memory usage went all the way up to 135Megs then I ran out and the system locked up. Netscape on the other hand gets by with a svelte 13Megs no sweat. This looks pretty bad. Someone with enough priveledges should change platform/OS to "all" and confirm it. I'm not gonna attach the generated file because it's way too big (1.2megs) although I will attach a zipp'ed version for those of you without perl (I pity you... :) ).
cc'ing me
change Platform and OS to "All" (bug was found on windows at all)
OS: Linux → All
Hardware: PC → All
Confirming, as several people have seen it. Gerv
Status: UNCONFIRMED → NEW
Ever confirmed: true
still get it with 2000042708
Phil, can you see if this is still happening? I know brendan's done some work in this area...
Assignee: rogerl → pschwartau
Changing QA contact to me -
QA Contact: rginda → pschwartau
I don't see memory increase as before. Using the the linux build from 08/14/2000.
Changing component to Browser-General (see comments below)
Assignee: pschwartau → asa
Component: Javascript Engine → Browser-General
QA Contact: pschwartau → doronr
Using commercial binary 2000092320 on WinNT; comparing to optimized JS shell built from source 2000-09-21 on WinNT. If I run the standalone JS shell testcase above, here is what I find. Beginning with memory usage of 91M/259M, my memory usage proceeded: 91M ---> 115M ---> 91M --> 94M (linearly) The downturn in memory usage happened when the outer loop variable had decremented from 256 to approximately 50. Suddenly I could see memory being freed and going down to 91M again, and then increasing. With the browser, however, the memory usage was like this: 103M ---------------------------------> 259M (non-linearly) Memory usage climbed without pause, and accelerated in a non-linear way. The page never finished loading, and I got a warning from the Windows OS that memory had been exhausted. These results show, I believe, that this bug is a problem not of the JS engine itself, but of the browser embedding of the engine. Therefore reassigning to Warren for further analysis - perhaps this bug is even a duplicate of another; I was unable to find it, however.
Assignee: asa → warren
=> jband
Assignee: warren → jband
No no no. This has nothing to do with large arrays. No arrays get created. The first line of the test case causes a JS error. The problem here is that the compiler (in the JS engine) is choking on the content of the 64k lines of input. It is deep in jsemit.c allocing like crazy when it passes the 200meg mark. Phil, you misinterpreted the initial code sample. This was perl code to generate JS source. It was not intended to be translated into JS, but run to generate JS code. See the zipped html file that Gwyn Judd attached. Strip off the html parts at the front and back and run that in jsshell and see what you get! I ran it in xpcshell and got the same memory explosion as in the browser. Brendan & Roger, do we consider this something that ought to be fixable, or just a "don't do that!" sort of thing? I'm wondering things like: Can the parse tree be ripped up as we go? (currently all in one arena, right?) AND Isn't this a pretty darn uniform pattern of code that ought to be rather optimizable down to a much smaller bytecode array?
Assignee: jband → brendan
Component: Browser-General → Javascript Engine
jband is correct. When I run Gwyn's testcase at 2000-04-27 01:00 above, I run out of virtual memory in Mozilla and in the standalone JS shell. The N4.7 browser, however, handles it without any apparent problems.
Status: NEW → ASSIGNED
Keywords: js1.5, mozilla0.9
Target Milestone: --- → mozilla0.9
js1.5 => p1. /be
Priority: P3 → P1
Target Milestone: mozilla0.9 → mozilla0.8
Keywords: mozilla0.9 → mozilla0.8
Looks like this person ran into the same problem... http://www.deja.com/%5BST_rn=ps%5D/getdoc.xp?AN=706292446 He's seeing a crash with... Data = new Array ( (new Array("2197","745185","34")), (new Array("6591","1858354","34")), // and so on for something like 2500 lines );
Several bad things: jsemit.c has code that grows two kinds of arena-based allocations (bytecode, srcnotes) by a constant increment, resulting in O(n**2) space growth; jsparse.c didn't recycle parsenode so as to avoid growing its arenas. Patch coming up, but first, I'll attach my perl testcase generators, the first based on wrobell's perl, the second an improvement of it that results in fewer than half the bytecodes as the first. /be
Here comes the patch that reduces memory for the output of the first attached testcase generator (the one that uses new Array and x[i][j] = ...) as follows: Before patch: Parser growth: 26480640 (526086 nodes, 23147784 bytes) Code-gen growth: 299008 (984842 bytecodes, 329222 srcnotes) After patch: Parser growth: 315392 (526086 nodes, 9 max, 1 unrecycled) Code-gen growth: 0 (984842 bytecodes, 329221 srcnotes) The growth is bytes measured by sbrk(0); the "Before patch" line for Parser growth shows the total node count and consequent size (net of arena header and rounding), given 44 bytes per JSParseNode. Here is the output of a patched js shell given input generated by the second (array initializer) testcase-generator patch: Parser growth: 3620864 (65797 nodes, 65797 max, 1 unrecycled) Code-gen growth: 0 (460297 bytecodes, 66308 srcnotes) I didn't do a "Before patch" measurement because there isn't be much improvement in Parser growth, as the giant array initializer is one big expression, and I have not yet taught the compiler to emit code incrementally and recycle nodes within a single expression statement. I'm not sure I will go that far, because 3.6M growth given a 587K .js file (~6x blowup from source to in-memory data) is not as terrible as the problem this bug reports. Jband, I'm not at all sure what is causing the nested Array constructor call case you found in that deja.com posting. I need a testcase. Anyone have one? /be
Attached patch proposed fix — — Splinter Review
Proposed fix's cvs commit log message: - Optimize compile (parse+emit) operation to generate code for each top-level statement or function in turn, recycling JSParseNodes as we go for greatly reduced footprint. - Fix O(n**2) growth problems in bytecode and srcnote generation. - Add js_ParseTokenStream entry point to compiler, for tree-generation without code-generation. Move JSOP_EVAL instruction selection from code-generator to parser, to match other such specializations and enable js_ParseTokenStream. - Clean up bracing, multi-line conditions, and overlong lines. /be
Keywords: patch, review
r=mccabe. jsemit.c:2741 * accomodate either the first or second byte of additional storage * required by this 3-byte offset. */ - if ((cg->noteCount + 1) % SNINCR <= 1) { + if (((cg->noteCount + 1) & cg->noteMask) <= 1) { if (!GrowSrcNotes(cx, cg)) return JS_FALSE; sn = cg->notes + index; could this be a check against 0 with a different bit operation? Does 'top level statement' mean top level within the js script? If some function contains many statements, do we still bloat? I've long wondered if something like this wouldn't help Rhino compile speed.
Oops, my first attachment (http://bugzilla.mozilla.org/showattachment.cgi?attach_id=15683) has a 'var' before x, which results in one extra unrecycled node. Just delete that var, defined METER_PARSENODES in jsparse.c, and you should get numbers about the same as the ones I posted. mccabe writes: >- if ((cg->noteCount + 1) % SNINCR <= 1) { >+ if (((cg->noteCount + 1) & cg->noteMask) <= 1) { > if (!GrowSrcNotes(cx, cg)) > return JS_FALSE; > sn = cg->notes + index; > >could this be a check against 0 with a different bit operation? it can't without signed modulus, which requires an extra branch of a full-on divmod instruction to handle the negative case. We must handle the case where cg->noteCount is 63, cg->noteMask is 63, and we need to grow cg->notes to fit two more bytes (at indexes 63 and 64, resulting in a noteCount of 65). Note that we must use a relational op, equality can't do the range test we need. Note also how adding two and testing <= 2 won't work: it will wrongly grow the notes vector when noteCount is 62. I'm still not entirely happy with the way this code now allocates power-of-two sized pieces from an arena: it seems too easy to overflow an arena, waste cycles on a copy, and leave the old piece unusable. I think malloc/realloc are likely to work better than arena-pools here, for any power of two > 32 or so. More measurements in a bit. /be
Yup, JS_ARENA_GROW was evil: it grew "in place" (found more to accomodate the new size in the nominally pool->arenasize arena) only about 1 in 6 calls. This makes for yet another O(n**2) space explosion. I fixed it to realloc the arena if the allocation being grown consumed the arena's entire payload (minus slop for alignment). Now the numbers look really good, with arena stats dumped after (JS_ARENAMETER defined and JS_DumpArenaStats(stdout) called from jsparse.c after the last METER_PARSENODES printf): Parser growth: 40960 (526086 nodes, 9 max, 1 unrecycled) Code-gen growth: 0 (984842 bytecodes, 329221 srcnotes) temp allocation statistics: number of arenas: 16 number of allocations: 533 number of free arena reclaims: 0 number of malloc calls: 16 number of deallocations: 0 number of allocation growths: 0 number of in-place growths: 0 number of extending growths: 0 number of released allocations: 0 number of fast releases: 0 total bytes allocated: 18112 mean allocation size: 33.9812 standard deviation: 206.291 maximum allocation size: 4096 note allocation statistics: number of arenas: 1 number of allocations: 1 number of free arena reclaims: 0 number of malloc calls: 1 number of deallocations: 0 number of allocation growths: 13 number of in-place growths: 2 number of extending growths: 11 number of released allocations: 0 number of fast releases: 0 total bytes allocated: 524288 mean allocation size: 524288 standard deviation: 524288 maximum allocation size: 524288 code allocation statistics: number of arenas: 1 number of allocations: 1 number of free arena reclaims: 0 number of malloc calls: 1 number of deallocations: 0 number of allocation growths: 12 number of in-place growths: 2 number of extending growths: 10 number of released allocations: 0 number of fast releases: 0 total bytes allocated: 1048576 mean allocation size: 1.04858e+06 standard deviation: 1.04858e+06 maximum allocation size: 1048576 stack allocation statistics: number of arenas: 0 number of allocations: 0 number of free arena reclaims: 0 number of malloc calls: 0 number of deallocations: 0 number of allocation growths: 0 number of in-place growths: 0 number of extending growths: 0 number of released allocations: 0 number of fast releases: 0 total bytes allocated: 0 mean allocation size: 0 standard deviation: 0 maximum allocation size: 0 gc-arena allocation statistics: number of arenas: 1 number of allocations: 748 number of free arena reclaims: 0 number of malloc calls: 1 number of deallocations: 0 number of allocation growths: 0 number of in-place growths: 0 number of extending growths: 0 number of released allocations: 0 number of fast releases: 0 total bytes allocated: 5984 mean allocation size: 8 standard deviation: 0 maximum allocation size: 8 gc-arena allocation statistics: number of arenas: 0 number of allocations: 1007 number of free arena reclaims: 0 number of malloc calls: 1 number of deallocations: 0 number of allocation growths: 0 number of in-place growths: 0 number of extending growths: 0 number of released allocations: 0 number of fast releases: 0 total bytes allocated: 8056 mean allocation size: 8 standard deviation: 0 maximum allocation size: 8 Note that now, all non-in-place growths are "extending" growths, which means realloc calls. That frees the old arena in the case that in-place growth in the malloc heap is not possible, and malloc then recycles the old arena's space quite well, as the "Parser Growth" figure shows (41K, down from 315K!). Even the second testcase-generator's output (using array initializers) improves from 3.62M to 3.48M due to better malloc recycling of the evacuated realloc space. The "extends" case really makes an arena pool useful as a malloc/realloc device where the pool keeps track of all allocations and can free them _en masse_ or LIFO. It's not the cheapest way to so track memory, at 16 bytes per arena header, but it's cheap enough and it unifies mechanism to fix JS_ARENA_GROW to handle this "extends" case and not purvey an O(n**2) hazard. Revised patch coming up. /be
mccabe also wrote: >Does 'top level statement' mean top level within the js script? If some >function contains many statements, do we still bloat? No bloat -- top-level statements in a function body are emitted one at a time. The top-level test is whether the statement-info stack is empty (wherefore the removal of the redundant TCF_TOP_LEVEL flag, whose bit was reclaimed by the new TCF_COMPILING flag in JSTreeContext -- this new flag tells us we can safely downcast tc to (JSCodeGenerator *) and emit as we go). I think the last patch is "it", for now. If someone thinks that we really need finer-grained code-gen/parser interleaving, a separate bug with testcase should be filed. Looking for fresh r= and sr= from someone (shaver or jband). /be
Fear not: I just removed this line +#define METER_PARSENODES /* XXXbe don't check me in! */ from jsparse.c. Sorry for leaving it in the patches. /be
Oops, I lied: functions containing gazillions of statements will parse into whole trees, which are then walked by the code generator. This is required for now by several data dependencies in jsemit.c (e.g., pn_tryCount), but I think I can fix those to cope with TCF_COMPILING. Might do one more patch, please feel free to r= anyway. /be
I think something's slightly busted about the patch; I get } else { \ p = (type) JS_ArenaGrow(pool, p, size, incr); \ } \ } else { \ p = (type) JS_ArenaGrow(pool, p, size, incr); \ } \ in jsarena.h
n/m, I see how the curlies line up. Pesky tabs.
Yeah -- I expanded tabs in the macro bodies I touched, just to keep my sanity. See last two patches. /be
r=mccabe JS_ArenaExtend and JS_ArenaGrow sound a little too synonymous; maybe a comment? Or are there more descriptive names? I'm not sure I understand the new js_PushStatement pairs near TOK_TRY and TOK_FINALLY.
Those JS_Arena* functions are not to be called directly, but I'll noodle on better names. The missing Push/PopStatement brackets meant that those calls to Statements from top-level try and finally blocks thought they were at top level (!tc->topStmt), which means when TCF_COMPILING is set, emit code as we go -- which scrambles the try block's code with its JSOP_TRY (which comes out after instead of before the try block code), e.g. /be
Still craving that ever-lovin' sr=jband or sr=shaver. New patch coming up, trivial change to keep track of previously declared consts (or functions or vars, in case strict and for the TCF_FUN_VS_VAR deoptimization required by ECMA) without holding onto unrecyclable JSParseNodes. The previous patches know in RecycleTree to return early after recycling a function's body, or a variable list, to avoid recycling the function node or var list node itself. By keeping a JSOp in the tc->decls atom-list, instead of the whole darn JSParseNode, we can recycle node trees uniformly, without special cases, recursively calling RecycleTree according to node arity. /be
Ok, *now* I'm done. Reviewers please review! /be
I'm guessing nsnull isn't defined in .c code. This is cool reading. + if (nallocs != 0) { is there a reason not to use if (nallocs) [i'm guessing some wierd clarity] if (((uintN)index & cg->noteMask) == 0) { if (!left || !right) which is more expensive, that or if (!(left && right)) ? does the cost change for longer expressions: if (!fp || fp->varobj != chain || fp->scopeChain != chain)
>+ if (nallocs != 0) { >is there a reason not to use if (nallocs) [i'm guessing some wierd clarity] Usually I don't test scalars against zero implicitly, but sometimes I'm lazy. In this case I'm being explicit, as nallocs is neither boolean nor a pointer. > if (((uintN)index & cg->noteMask) == 0) { Did you have a question about this line? > if (!left || !right) >which is more expensive, that or if (!(left && right)) ? Let the optimizing compiler decide. It can do De Morgan's theorem as well as we can, and it knows the instruction schedule and instruction costs better. >does the cost change for longer expressions: >if (!fp || fp->varobj != chain || fp->scopeChain != chain) Only in terms of what you think is the most likely to be true (which short-circuits || -- or false for short-circuiting &&). The most likely to be true clauses should be at the front, if performance is critical. Usually (as is the case here) it's not critical, but clarity and readability are. /be
Applied patch (id=22207) on Linux and ran the test suite against both the debug and optimized JS shells. No regressions were introduced -
OK, finally finished reading a patch before /be posted a new one. =) sr=shaver, now that I understand the js_ArenaRealloc caller-reports-OOM behaviour. Out of curiosity, how much of a win is this?
Keywords: review
shaver: my comments dated 2000-12-27 16:13 show the win: from 27MB process data segment growth down to ~315K, for the big bad array init testcase. /be
Fix checked in, thanks to reviewers. /be
Status: ASSIGNED → RESOLVED
Closed: 25 years ago
Resolution: --- → FIXED
Keywords: mozilla0.8
Blocks: 45343
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: