From Bugzilla Helper: User-Agent: Mozilla/5.0 (X11; U; Linux 2.2.15-4mdk i686; en-US; m18) Gecko/20001013 BuildID: 2000101309 the standard way of string concatenation in JavaScript (as far as I know) is to use the + operator. However, doing this with a large number of operations is very slow in Mozilla. I think even VB beats it. :( During long string concatenations, Mozilla appears to simply lock up and actually crashed a number of times while I was putting together my test case. If you use the += operator, the string concatenation is actually rather quick. However, I don't see this method being used very often in web sites. Reproducible: Always Steps to Reproduce: Open the test case I'll submit Click on the "Slow" button. Time with lunar calendar Click on the other button. Notice the speed difference Actual Results: String concatenation is very slow using the normal way of doing things. String concatenation isn't bad if you use the weird work-around Expected Results: I would expect the two methods to have similar performance, especially doing something as simple as 500 operations like my test case does. I found this while I was developing/using a javascript XML parser. During one of my DOM runs, I parse the tree and create a whole lot of DIVs and then use the innerHTML property to display them appropriatly. As the DOM tree got larger, Mozilla would begin to hang/crash. After debugging, I found out it was because I used the + operator to concatenate my strings. Changing the concatenation method made the system work reasonably well. IE handles the test case fine in both instances. This is more a "Mozilla-the platform" bug than a netscape bug, but it would be nice to get in for Mozilla 1.0. It would even be nicer of course to get into Netscape 6, of course :)

Confirmed with 110204 mozilla trunk build. We are significantly slower than 4.7.

Attaching a variant of the above testcase, with duly declaration of loop counter as a local variable. For 500 loops on my PIII-550, timer shows about 40 secs with the first method, and less than half a second with the second one (fast and shortcut :-). Look at the hard disk activity : isn't that weird ?

Roughly identical results with NN4.76. Don't ask for MSIE-5.5...

Does this contribute to the rather slow DHTML performance of Mozilla /Netscape 6?

See also bug 40391, which focuses on the DoS/freeze aspect of this problem.

cc'ing Brendan -

First, let me pleasantly assert that x += y; is not weird -- it's the right way to code x = x + y; in any C-like language worthy of that provenance. The reason += runs faster is simple: the loop body concatenates y and z to make a 117-character string, which is then appended to the ever-growing string in x. With the x = x + ...; form, the increasingly large string (>> 117 characters) in x is concatenated six times with relatively short strings in y and z, piling up stupendous amounts of intermediate-string-concat-results that are just garbage to be collected. Each temporary string lives in the malloc heap until the next GC, which won't happen till the 4096th backward branch and/or return statement (see nsJSContext::DOMBranchCallback in dom/src/base/nsJSEnvironment.cpp). With x += y+z+y+z+y+z; and ignoring the space cost of computing the right-hand side, we have 117*loop*(loop+1)/2 or 14.7M of growth, most of it garbage. With x = x + y+z+y+z+y+z, we can't ignore the cost of computing y+z+y+z+y+z, because its terms successively left-associate, first with the x on the right of the assignment to compute x+y, then x+y+z, then x+y+z+y, etc. As x grows, these intermediates become as significant as the final append to x in each iteration of the loop. We have to compute: sum[i from 1 to 500] of i * (sum[j from 1 to 6] of i+(j%1?32:7)) sum[i from 1 to 500] of i * (6*i + 117) (sum[i from 1 to 500] of 6*i*i) + 117 * (sum[i from 1 to 500] of i) 6 * (sum[i from 1 to 500] of i*i) + 14.7M Notice that the linear sum is now dominated by the sum of squares. The sum of squares from 1 to n is n*(n+1)*(2*n+1)/6, so the result is n*(n+1)*(2*n+1) + 14.7M for n=500 or a horrendous 265M! The run-time is terrible in Mozilla, about 20 times worse than in the JS shell (build that over in js/src using Makefile.ref on Unix, js.mak on Windows) due to mozilla's larger working set size after the first window is up and you're ready to run the test. The disk grinding you hear is the VM system thrashing as the process grows its data segment to cope with the O(n**2) growth. Reference counting (which I believe MS's JScript engine uses) makes this all better. I'll take this bug and work on a fix, an optimization that doesn't totally undo the JS engine's use of garbage collection, but which makes this sort of code run about as fast as if ref-counting were used. /be

My patch in progress (not ready for attachment) is too big to rush into 0.8. I'll do it in 0.9 for js1.5 final (js1.5 RC3 should be the same as mozilla0.8's JS source). /be

*** Bug 64589 has been marked as a duplicate of this bug. ***

*** Bug 74918 has been marked as a duplicate of this bug. ***

Slipping, but I want to get my half-done changes in for 0.9.1 and js1.5 final. /be

There is a workaround for this problem that improves performance on Mozilla and IE. Instead of building the string via concatenation, i.e. x = x + y or even x += y, save the pieces of string in an array. Then when you need the full string, do a join on the array. It helps the performance quite a bit in both browsers.

I have the patch for this still half-done in one of my trees, but there is no way I can justify rushing it to completion for 0.9.1. Sorry -- too much time was spent on super-review, staff@mozilla.org administrivia, politics... I'm gonna hide at home and hack more for 0.9.2. /be

*** Bug 89011 has been marked as a duplicate of this bug. ***

Moving out, but this should happen soon in order to make js1.5. /be

*** Bug 95119 has been marked as a duplicate of this bug. ***

Moving out. With FastLoad behind me, I will get to this in the 0.9.5 milestone. /be

Using the provided testcase, the first method takes 260 sec and the second 0.8 sec using todays nightly. (WinNT ran out of virtual memory and swapped like hell). It would be great to see performance improved here.

Any chance of this for 0.9.5?

Moving out -- the half-done patch is on my old laptop, there is no way this will make the 0.9.5 train. /be

Shouldn't this be Platform All and OS All? I've observed this problem on Win2K and comments say that it is Linux too. Mac?

XP -> Plat/OS All/All

Comment on attachment 53406 [details] [diff] [review] proposed fix, please test and review -- this cures all ills and passes the js testsuite I caught a few nits, fixing in a new patch. /be

Tired, I'm crashing soon. All patches passed the JS testsuite, but only the third should have -- we need some string concatenation tests that grown the string to > 65535 chars, then feed it back as left operand of +. Tomorrow I'll hack a better scheme to overlay (start,length) on JSString.length, so even long strings that have short start offsets (say, 0, as all left operands to + will after becoming dependent on the + result) can take the realloc path and avoid quadratic or cubic growth problems. /be

I checked around, and am willing to bet that Mozilla platforms all ensure 0 mod 4 alignment of pointers returned by malloc. So I'm looking for r= and sr= on the latest patch (attachment 53492 [details] [diff] [review]) from the usual suspects. /be

I asked around today too, and while every was quick to point out how strong their C-standard-fu was by telling me I couldn't count on it, nobody could dig up a platform that broke. De facto trumps de jure! I'll review the patch tomorrow, hopefully.

0 mod 4 (or more) is normal (but most certainly not mandated by ANSI) on most 32-bit-or-more-system allocators. We could add that as a requirement, perhaps even check it in configure. However, this is something someone trying to port it to such a system would hit moderately fast. Do we have a web page detailing issues for people who want to port to a new target? nsSmallVoidArray (nee nsCheapVoidArray) requires nsIFoo * objects live on 0 mod 2 boundaries, BTW.

There are scattered porting docs on mozilla.org (http://www.mozilla.org/projects/xpcom/porting/, e.g.) but nothing central/complete. The assertions I've added will stop a porter cold, which is the usual way one transports Mozilla: hack it till it compiles, then hack more till it stops crashing/asserting. Some new (or old -- word-addressed PDP-10, anyone?) architecture could align all types on a "byte" boundary, leaving no low bits free for tagging. Such platforms will have to relocate the JSSTRFLAG_BITS elsewhere, probably to the high order bits in JSString.length. I don't want to put them there now for all platforms, because that imposes greater costs than the current low-order bit tagging scheme requires. /be

rogerl, any hope of an r=? Anyone on the cc: list trying the latest patch? /be

odd comment "String descriptors are GC'ed while string their chars" [line 44, jsstr.h] [way picky...] use of 'JSSTRDEP_LENGTH' in jsstr.c conflicts with comment in jsstr.h : "Always use the JSSTRING_LENGTH and JSSTRING_CHARS accessor macros!" I understand that you're factoring out the test, but won't the optimizer do that? Or maybe a macro that acquires both? There are reference to str->chars in 'js_AtomizeString', jsatom.c line 574,575 (and other references in that file). Are these all safe? If I read the changes in jsexn.c correctly, you've changed the order of file & line number output in exn_toSource. Does rginda rely on the existing format? (Not that that makes the change bad). Is it worth adding a macro wrapper for 'js_UndependString' to avoid the call overhead for non-dependent strings? In js_MinimizeDependentStrings, what happens if the accumulated start position exceeds JSSTRDEP_OFFSET_MAX?

Thanks for that garbled comment catch -- I deleted "string" and rewrapped to format well. >use of 'JSSTRDEP_LENGTH' in jsstr.c conflicts with comment in jsstr.h : >"Always use the JSSTRING_LENGTH and JSSTRING_CHARS accessor macros!" >I understand that you're factoring out the test, but won't the optimizer do >that? Or maybe a macro that acquires both? We want to factor the test there, and a bit later (and in similar places). I've made that jsstr.h comment less militant. >There are reference to str->chars in 'js_AtomizeString', jsatom.c line 574,575 >(and other references in that file). Are these all safe? Yes, check the ATOM_TMPSTR flag usage. >If I read the changes in jsexn.c correctly, you've changed the order of file & >line number output in exn_toSource. Does rginda rely on the existing format? >(Not that that makes the change bad). I didn't reorder anything, but I did declare and set variables to hold JSSTRING_LENGTH(message), etc. >Is it worth adding a macro wrapper for 'js_UndependString' to avoid the call >overhead for non-dependent strings? It's used so rarely, I don't think so. >In js_MinimizeDependentStrings, what happens if the accumulated start position >exceeds JSSTRDEP_OFFSET_MAX? See jsstr.c line 94 -- if start doesn't fit, str is left dependent. /be

Comment on attachment 53788 [details] [diff] [review] updated to merge other js/src changes, and to fix a comment in jsstr.h Fixed comments, new patch in a second. /be

It sucks a little that the 0 mod 4 alignment of str->chars applies to external strings too. I can imagine someone wanting to build external strings from differently aligned char data. I'm thinking that a JS_ASSERT in JS_NewExternalString might help embedders with early detection if they violate this new constraint.

Sorry if I'm being dense, but I don't understand how you can be safely mucking with the internals of strings at runtime (e.g. in js_UndependString) without locking.

jband: right, assertion added. Do you and shaver have external string cases in mind where 4-byte alignment might not be guaranteed? Thread safety, what's that? Ahem. Patch coming up. /be

cc'ing scc on this string question. Well, the one use of JS_NewExternalString now it's passed: const nsSharedBufferHandle<PRUnichar> *handle; handle = readable.GetSharedBufferHandle(); .... str = JS_NewExternalString(cx, NS_CONST_CAST(jschar *, NS_REINTERPRET_CAST(const jschar *, handle->DataStart())), handle->DataLength(), DOMStringFinalizerIndex); It's not obvious, but I don't see anything in string that forces mDataStart to be on a 0,4 aligned boundary. Can we check alignment and allocate a new buffer if the alignment isn't 0,4?

Ok, two-pronged attack: 1. Give up using small integer immediates when testing JSSTRING_IS_*: use the high two bits of JSString.length to flag DEPENDENT and PREFIX. This will allow JSString.chars to have any alignment. 2. Distinguish strings whose buffer and header can't be mutated (those potentially accessible to more than one thread) from those we can mutate, by adding a new GC-thing-type. Atoms own immutable strings, because any thread can access a string-keyed atom. Objects whose scope converts from lock-free to lock-full must have their string-valued slots promoted to immutable GC-thing-type, and any new string-valued property assigned to a lock-full object must have the value string "promoted". js_ConcatStrings reallocs left and morphs it only if it's mutable (otherwise it copies). Step 2 avoids imposing costs on every property get (#gets >> #sets), and on the thread-safe/single-threaded cases that dominate (see bug 54743). Comments? /be

This sounds good to me. Sorry for the reality check :) I was willing to live with the alignment issue, but like seeing it become a non-issue to embedders. I'm with you in thinking that reducing the length limit isn't going to hurt in the real word. I like the scheme for retaining the non-locked fast path for the bulk of strings. I'm trying to think of other possible string references - other than as JSObject properties - where we (or native clients) would need to ensure their immutability.

This detailed sub-plan has been on my mind, and it should address jband's last concern, which I share: GCX_MUTABLE_STRING is the new GC-thing type, and we make mutable strings only in js_ConcatStrings, for the result. We morph back to GCX_STRING in Undepend, so API users see a flat, nul-terminated string that won't move behind their backs. The JS_New*String* APIs make immutable strings as always. /be

My last comment implied that js_UndependString would morph the GC thing type back to GCX_STRING from GCX_MUTABLE_STRING, but I decided to factor that semantic out of Undepend and into js_GetStringChars, called by JS_GetStringChars. The same "undepend" vs. "morph to immutable" distinction is made in jslock.c, with the MAKE_STRING_IMMUTABLE macro, for least call overhead (hmm, I think I'll hoist the JSSTRING_IS_DEPENDENT(str_) out of js_UndependString into that macro, should have done that already [rogerl was prescient'). /be

Comment on attachment 54509 [details] [diff] [review] dig it: lock-free mutable/growable/dependent strings, immutable once multithreaded next patch hoists JSSTRING_IS_DEPENDENT test to callers of js_UndependString in jslock.c (as promised), and adds a JSSTRING_BITMASK variant of JS_BITMASK that's 64-bit size_t safe. /be

I compiled and started running the tests. It crashed right away running... ecma/Array/15.4.2.1-2.js It is in js_CompareStrings The string looks like: - str1 0x00427010 length 0xc0000fa9 + chars 0x00427018 "?" But JSSTRING_LENGTH returned: l1 0x40000000 It looks like JSSTRDEP_LENGTH is clearly broken: #define JSSTRDEP_LENGTH(str) (JSSTRDEP(str)->length \ & (JSSTRING_IS_PREFIX(str) \ ? JSSTRING_LENGTH_MASK \ : JSSTRDEP_LENGTH_MASK))

jband: what's str1? I don't see this, obviously. Hmm, I'll look for you on IRC. /be

Comment on attachment 54596 [details] [diff] [review] dig it more: lock-free mutable/growable/dependent strings, immutable once multithreaded Never mind, I'm an idiot. Slight error in JSSTRING_BITMASK... new patch coming up. /be

I added a printf("oink! %u <%s>\n", n, js_GetStringBytes(str)); call just above the #ifdef DEBUG code in js_UndependString, ran mozilla (optimized), and loaded this bug's second attachment, clicking on the two buttons. The output was: oink! 2 <50> oink! 2 <75> oink! 2 <90> oink! 3 <100> oink! 3 <120> oink! 3 <150> oink! 3 <200> oink! 1 <5> oink! 1 <7> oink! 1 <9> oink! 1 <z> oink! 1 <1> oink! 1 <0> oink! 1 <2> oink! 17 <done in 0.01 sec.> oink! 18 <done in 0.011 sec.> oink! 18 <done in 0.009 sec.> Notice that after some startup cruft (small strings, attribute values?) the only flattened dependent strings were those generated by the native alert code's calls to JS_GetStringChars. Hoping for review (rogerl, khanson) and super-review today (jband and shaver), don't make me beg! /be

I pointed out to jband that JSSTRDEP_LENGTH was a fine macro (its outer expression is a binary-& operator joining JSSTRDEP(str)->length with a right operand that's a ternary expression selecting the right bitmask -- the parens and indentation show the correct precedence). But JSSTRING_BITMASK was mistakenly defined as JSSTRING_BIT should have been! Both macros are there now, in case size_t is 64 bits. The only other change in the last patch was to elaborate jsapi.[ch] with comments, JS_NewMutableString, and JS_MakeStringImmutable. /be

Comment on attachment 54760 [details] [diff] [review] final patch, I swear -- passes js testsuite (why didn't I rerun the tests before the last patch? augh) >+ tmplen = JSSTRING_LENGTH(str); >+ js_strncpy(&chars[nchars], JSSTRING_CHARS(str), tmplen); >+ nchars += tmplen; tmplen is overindented. >+ if (JSSTRING_LENGTH(message) != 0) { >+ length = JSSTRING_LENGTH(name) + JSSTRING_LENGTH(message) + 2; > cp = chars = (jschar*) JS_malloc(cx, (length + 1) * sizeof(jschar)); > [...] >+ js_strncpy(cp, JSSTRING_CHARS(name), JSSTRING_LENGTH(name)); >+ cp += JSSTRING_LENGTH(name); > *cp++ = ':'; *cp++ = ' '; > [...] >+ js_strncpy(cp, JSSTRING_CHARS(message), JSSTRING_LENGTH(message)); >+ cp += JSSTRING_LENGTH(message); Cache the JSSTRING_LENGTH values in locals, now that they're not simple loads, or leave it to the compiler? >+ /* XXXbe js_strtod shouldn't require NUL termination */ >+ bp = js_UndependString(cx, str); >+ if (!bp) Indeed. File a bug on that? >+ /* XXXbe js_strtointeger shouldn't require NUL termination */ >+ bp = js_UndependString(cx, str); As above. >- cstr = js_DeflateString(cx, str->chars, str->length); >+ cstr = js_DeflateString(cx, JSSTRING_CHARS(str), JSSTRING_LENGTH(str)); Misindented. >- cstr = js_DeflateString(cx, str->chars, str->length); >+ cstr = js_DeflateString(cx, JSSTRING_CHARS(str), >+ JSSTRING_LENGTH(str)); And again. > ren2 = NewRENode(&state, >- (len == 1) ? REOP_FLAT1 : REOP_FLAT, (void *)cp); >+ (len == 1) ? REOP_FLAT1 : REOP_FLAT, >+ (void *)cp); Ibid. > if (opt) { >+ s = JSSTRING_CHARS(opt); >+ for (i = 0, n = JSSTRING_LENGTH(opt); i < n; i++) { >+ switch (s[i]) { Encore! >+ if (JSSTRING_IS_DEPENDENT(str) && !js_UndependString(NULL, str)) >+ return NULL; >+ >+ *js_GetGCThingFlags(str) &= ~GCF_MUTABLE; Doesn't (shouldn't?) js_UndependString do the flag-twiddling? >+/* >+ * May be called with null cx by js_GetStringChars, above; and by the jslock.c >+ * MAKE_STRING_IMMUTABLE file-local macro. >+ */ >+const jschar * >+js_UndependString(JSContext *cx, JSString *str) >+{ > [...] >+#ifdef DEBUG >+ { >+ JSRuntime *rt = cx->runtime; Doesn't that have us crashing if #DEBUG and null cx? >+ /* >+ * ECMA extension: if the property has not been set already (possibly >+ * to a user-defined value), return as its value the character at the >+ * given index. Don't use resolve, which penalizes all string method >+ * calls and other property accesses. Let the property attributes be >+ * the default, so the user can override, enumerate, etc. and get the >+ * expected results. >+ */ >+ if (JSVAL_IS_VOID(*vp) && (size_t)slot < JSSTRING_LENGTH(str)) { >+ str1 = js_NewDependentString(cx, str, (size_t)slot, 1, 0); >+ if (!str1) >+ return JS_FALSE; >+ *vp = STRING_TO_JSVAL(str1); Neat. How does this interact with the mutability of the string, though? Can the contents of the returned string, as seen by script, change through mutation of the underlying string? My gut says "no", but I can't quite convince myself. >+ /* Windows says sqrt(0.0) is "-1.#J" (?!) so we must test. */ >+ sigma = (var != 0.) ? sqrt(var) : 0.; That's so lovely. De-nit it, and convince me of the flag-twiddling correctness, and we're good to go.

>tmplen is overindented. Nope, it's just expandtab vs. old pre-vim code I wrote that uses tabs. If you like, I'll expand a bunch of tabs there, and make the final patch diff -wu. Same goes for your later claims that I misindented code (/me wouldn't overtly misindent, ya know!). >Cache the JSSTRING_LENGTH values in locals, now that they're not simple >loads, or leave it to the compiler? Did that later, must've blown these off in my haste. Compiler can't do it, cuz of the function calls out of scope that might modify memory. Fixed. >Indeed. File a bug on that? Ok -- bug 106495. It's low priority, IMHO. >Doesn't (shouldn't?) js_UndependString do the flag-twiddling? No, as I commented here (and now in jsapi.h), flattening a string (giving it a NUL backstop at the same time) and making a string mutable are separate and composable operations. Consider native methods (such as those js_strtod callers) who want to pass a string to single-threaded code as a flat jschar[]. Why should they have to pay the immutability tax? >Doesn't that have us crashing if #DEBUG and null cx? Duh. Fixed, thanks. >Neat. How does this interact with the mutability of the string, though? >Can the contents of the returned string, as seen by script, change through >mutation of the underlying string? Nope, cuz we're returning this value via the default getter, and the value never goes into a property slot (no slot is ever allocated if the user has not assigned a non-void value to s[0] for some string object s). Search for the default_val variable and its block in js_GetProperty. This means that not only can one-char strings be mutable dependents (single-threaded _ab initio_, they will be promoted if ever stored in a multi-threaded object), but that such strings are recreated on each access. I'm ok with that -- the old resolve/resolve1/enumerate code was more code bloat and resolve hurt performance across the board. An alternative would be to define properties as we find non-void slot values being accessed, here in str_getProperty. Let's continue this in bug 61987, but I don't see why this part of the patch can't go in now. Great review, thanks again. Final (diff -wu) patch coming up. /be

Urk, I meant "immutable" here: >No, as I commented here (and now in jsapi.h), flattening a string (giving it a >NUL backstop at the same time) and making a string mutable are separate and ^^^^^^^ /be

shaver wrote: >Neat. How does this interact with the mutability of the string, though? >Can the contents of the returned string, as seen by script, change through >mutation of the underlying string? And I misstook his meaning. He was thinking that GCX_MUTABLE_STRING means the chars in the string's buffer might change. It does not. It means only that the string descriptor's members (in particular, the "start" offset in a dependent string -- see js_MinimizeDependentStrings) might mutate, and that the buffer might be realloc'd (but its contents up to the former length not changed). I crave a better word that MUTABLE that's short enough. Anyone have one? If not, I'll just comment the heck out of jsapi.h and jsgc.h, which introduce the "mutable" word to the public and private engine-internal friends. /be

I am gonna go with GROWABLE. It doesn't capture the "you can mutate the start offset" meaning, but it doesn't mislead (in conjunction with my ancient failure to const-ipate JSString.chars or its precursor) API users into thinking that they can change the characters in a "mutable" string (which as shaver's comment feared would break any strings dependent on that string). /be

More thinking, less submitting! Growable is better in the new API entry point: JS_NewGrowableString, not JS_NewMutableString (which might mislead casual users to change characters in the buffer). But I'm sticking with GCF_MUTABLE/GCX_MUTABLE_STRING, because that flag and type does mean that the GC-thing itself (the JSString descriptor struct) is mutable, both for growable (realloc changes the chars pointer if it has to move the allocation to grow it) and dependent (start might change when minimizing dependencies) strings. Final^2 patch in a moment. /be

The only things that are bugging me are: 1) Do we break anyone in the places where we vend the result of js_NewDependentString? Your warning in jsapi.h is good. You should at least also post something to the newsgroup. Is that good enough? 2) shouldn't this be >= ? + if (length > JSSTRING_LENGTH_MASK) { + JS_ReportOutOfMemory(cx); + return NULL; + } 3) I'm a little worried about threadsafety of calls to js_UndependString. In general the internal uses seem reasonable. But what about interaction with (or between) the external callers? Being in a request does not give safety. It may be that no other threads are even going to have access to these strings - and that this is a non-issue. But I have not convinced myself of that. Otherwise, I'm ready with a sr=. Thoughts?

>1) Do we break anyone in the places where we vend the result of >js_NewDependentString? Your warning in jsapi.h is good. You should at least also >post something to the newsgroup. Is that good enough? I think so, because I'm not exposing dependent strings' (backstop-less) character storage via the old API. Barring OOM errors, we're API compabitle. >2) shouldn't this be >= ? > + if (length > JSSTRING_LENGTH_MASK) { + JS_ReportOutOfMemory(cx); + return NULL; + } Nope, MASK is MAX, not LIMIT (the "do not exceed" number, not the "fencepost"). >3) I'm a little worried about threadsafety of calls to js_UndependString. There isn't any -- that call cannot be made safely on a string already available to multiple racing threads. As designed, it's still useful for users who need an independent (flat, backstopped) character array. >In >general the internal uses seem reasonable. But what about interaction with (or >between) the external callers? Apart from buggy external (API client) calls on strings already wrongly "published" to multiple threads via, e.g., storing a ref in a member of a multi-threaded native data structure, I don't see the problem. >Being in a request does not give safety. True, but the JS_UndependString API is for single-threaded strings only. We don't have a bit in the string with which to assert that the string is still ST (we could assert that it's GCF_MUTABLE, but that overconstrains single-threaded users, where the string may be ST but immutable already for other reasons). >It may >be that no other threads are even going to have access to these strings - and >that this is a non-issue. But I have not convinced myself of that. How do other threads get access to a newborn string? Either (a) via an atom keyed by it; (b) via a slot in an MT object; (c) via a native ref in an MT data structure. (a) is handled by making immutable strings by default, and in particular for all atom keys. (b) is covered by the MAKE_STRING_IMMUTABLE calls in jslock.c. (c) is "caveat API user", and worth a newsgroup post for sure. API docs, ugh. Anyway, I still need double sr= to get this in. /be

Comment on attachment 54913 [details] [diff] [review] really-final (unless jband finds something) patch sr=jband I'm happy

r=rogerl. I also black-boxed it - concat's & substrings etc. running with Purify, nothing bad to report.

Fix is in, what a rush -- my baby is back from the fat farm! Well, if you ignore the scope double hashing bug.... /be

I have reviewed the code changes. I was curious about the necessity for JSSTRDEP_RECURSION_LIMIT. I wrote some test programs to check and verify the correctness of strings consturcted with repeated left and right concationation. I found no descrapancies. As expected strings with repeated concatenations to the end ran several times faster. Repeated concatenation to the beginning of the string showed no improvement. Both results expected. Clever solution. =Kenton=

JSSTRDEP_RECURSION_LIMIT may need to be tuned. It's my SWAG at what should be a safe level of recursion for js_MinimizeDependentStrings, a nested function with only a few args and locals. Some platforms run out of stack faster than others; running out of stack is a crash bug on all platforms I know of. We have bugs (or khanson has one, at least :-) on the parser or the code generator running out of stack on long chained + expressions (and we had || and &&, but kenton and I fixed those). Time for operator precedence parsing? /be

Marking VERIFIED FIXED. Using Mozilla trunk builds 20011026xx on WinNT, Linux, Mac. In the testcases above, there is now virtually no difference in performance between the two buttons. In addition, on my WinNT box, each button performs faster than it does in IE4.7. The "Slow" button in particular is MUCH faster now in Mozilla than in IE4.7 I also want to record the astonishing improvements the fix for this bug has made in the performance testcases of bug 105219. Using Mozilla trunk binary 20011026xx on my WinNT box: (All times in seconds) BEFORE 56940 FIX AFTER 56940 FIX Reduced testcase #1 220 7.5 Reduced testcase #2 210 6.5 Reduced testcase #3 105 1 Similar improvements on my Linux and Mac as well. Bravo!!!

Re-reviewing my own checked in patch, what kind of kook am I? The js_MarkGCThing switch was lax, it used the same case code for GCX_STRING and GCX_MUTABLE_STRING, but only the latter may have a dependency to mark. So now we assert for the GCX_STRING case that str is independent. Similarly, atomized strings are independent and immutable, so we don't need JSSTRING_CHARS and JSSTRING_LENGTH in CHECK_FOR_FUNNY_INDEX in jsobj.c. I took the liberty of suffixing _ to macro locals, rather than prefixing it and invading the standard C namespace. I'm probably gonna check this in with hypothetical review and super-review, unless someone is watching his bugmail and feeling generous. /be

Checking in regress-56940-01.js; /cvsroot/mozilla/js/tests/js1_5/String/regress-56940-01.js,v <-- regress-56940-01.js initial revision: 1.1 done RCS file: /cvsroot/mozilla/js/tests/js1_5/String/regress-56940-02.js,v done Checking in regress-56940-02.js; /cvsroot/mozilla/js/tests/js1_5/String/regress-56940-02.js,v <-- regress-56940-02.js initial revision: 1.1

(In reply to comment #76) these checkins caused invalid entries. I've sent an email to sysadmins to see how to fix it.

admittedly, my BigO calcs are somewhat bogus, but on Windows only I see O(N^2) behavior for sizes up to 10,000 in the testcases. On a Pentium M 1.7Ghz box I get: <http://test.bclary.com/tests/mozilla.org/js/js-test-driver-standards.html?test=js1_5/String/regress-56940-01.js;language=language;javascript> BUGNUMBER: 56940 STATUS: String concat should not be O(N**2) STATUS: (1000, 10); (2000, 40); (3000, 150); (4000, 220); (5000, 331); (6000, 631); (7000, 851); (8000, 1102); (9000, 1452); (10000, 1832); STATUS: Order: 2 FAILED!: BigO 2 < 2 FAILED!: Expected value 'true', Actual value 'false' FAILED!: <http://test.bclary.com/tests/mozilla.org/js/js-test-driver-standards.html?test=js1_5/String/regress-56940-02.js;language=language;javascript> BUGNUMBER: 56940 STATUS: String concat should not be O(N**2) STATUS: (1000, 10); (2000, 90); (3000, 190); (4000, 190); (5000, 461); (6000, 641); (7000, 791); (8000, 1102); (9000, 1402); (10000, 1802); STATUS: Order: 2 FAILED!: BigO 2 < 2 FAILED!: Expected value 'true', Actual value 'false' FAILED!: Plotting these values out seems to confirm a quadratic curve over the range of values I tested.

Note to self: Brendan thinks the O(N^2) behavior on Windows is due to O(N^2) behavior in Window's realloc. Not our bug.