Closed Bug 348627 Opened 14 years ago Closed 14 years ago
O(N^2) or worse algorithm in error console
STEPS TO REPRODUCE: 1) Have an error in JS at the end of a line a few hundred KB long (e.g. unterminated string literal). 2) Open the error console. ACTUAL RESULTS: hang EXPECTED RESULTS: not hang timeless and I suspect the code in <method name="repeatChar">, since all the time is spent in GC and string concatenation. The seamonkey console has the same problem.
I don't know if you care but for string lengths > 10000 the Array.prototype.join trick is far slower than doubling the string (str += str) until it has the right length.
Comment on attachment 233594 [details] [diff] [review] patch mozilla/xpfe/components/console/resources/content/consoleBindings.xml 1.26 mozilla/toolkit/components/console/content/consoleBindings.xml 1.14
Attachment #233594 - Attachment is obsolete: true
that seems like a bug.
Status: NEW → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED
array_join_sub calls realloc once per array element and at least under Windows realloc can be O(N^2), too. Blame it on Microsoft if you want, but 500K realloc calls to build a 500K string doesn't look like a good algorithm to me, no matter which OS. Optimising array_join_sub is already filed as bug 200505, btw.
Hmm... didn't the original loop count from 1 to col-1?
Er... yeah, it did. Reopening. timeless, fix the indexing? Requesting blocking because now we have a functionality regression...
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
And as far as that goes, we still hang with that patch, so we should probably go with comment 5. The profile for that hang looks like: Total hit count: 353031 349619 array_join_sub breaking down as: 137238 _end 135272 JS_GetElement 21279 realloc 12327 mremap Length-doubling seems like a better approach. Or more to the point, write aCol-1 in binary, and then assemble that string, starting from the small end (so we don't realloc the big chunk a bunch of times).
I can't actually get reasonable error source with a line of > 253 characters.
In fact, when the source line exceeds 253 characters I often get a "negative" error column - unfortunately it's stored in a PRUint32...
Typical doubling algorithm: if (--aCol <= 0) return ""; for (var i = 2; i < aCol; i += i) aChar += aChar; return aChar + aChar.substr(0, aCol - aChar.length);
Better use slice instead of substr, just in case bug 179628 ever gets fixed. It could be funny if the console tries to report its own strict warnings, or is there some sort of protection against that?
there's no protection against that. the result is a very very uncomfortable asynchronous infinite loop.
Comment on attachment 237045 [details] [diff] [review] per Seno Aiko Note: as it happens, the error text appears to be limited to ~255 columns. In 1.7 and previous, the error text and column would be independently truncated to fit within the range. In 1.8 the error column would be calculated relative to the truncated error text. Unfortunately that column could easily be to the left of the text, which doesn't work well when the column is an unsigned value :-( That has now since improved so that if the error column is not within the error text then it is not reported.
Comment on attachment 237045 [details] [diff] [review] per Seno Aiko mozilla/toolkit/components/console/content/consoleBindings.xml 1.15 mozilla/xpfe/components/console/resources/content/consoleBindings.xml 1.27
Attachment #237045 - Attachment is obsolete: true
Status: REOPENED → RESOLVED
Closed: 14 years ago → 14 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.