O(N^2) or worse algorithm in error console

RESOLVED FIXED

Status

Toolkit Graveyard
Error Console
RESOLVED FIXED
11 years ago
a year ago

People

(Reporter: bz, Assigned: timeless)

Tracking

Details

Attachments

(1 attachment, 3 obsolete attachments)

1.29 KB, text/plain
Details
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.
(Assignee)

Comment 1

11 years ago
Created attachment 233594 [details] [diff] [review]
patch
Attachment #233594 - Flags: superreview?(bzbarsky)
Attachment #233594 - Flags: review?(bzbarsky)
Attachment #233594 - Flags: superreview?(bzbarsky)
Attachment #233594 - Flags: superreview+
Attachment #233594 - Flags: review?(bzbarsky)
Attachment #233594 - Flags: review+

Comment 2

11 years ago
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.
(Assignee)

Comment 3

11 years ago
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
(Assignee)

Comment 4

11 years ago
that seems like a bug.
Status: NEW → RESOLVED
Last Resolved: 11 years ago
Resolution: --- → FIXED

Comment 5

11 years ago
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.

Comment 6

11 years ago
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
Flags: blocking1.9?
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).

Comment 9

11 years ago
I can't actually get reasonable error source with a line of > 253 characters.

Comment 10

11 years ago
In fact, when the source line exceeds 253 characters I often get a "negative" error column - unfortunately it's stored in a PRUint32...

Updated

11 years ago
Depends on: 348836

Comment 11

11 years ago
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);
(Assignee)

Comment 12

11 years ago
Created attachment 236082 [details]
just some tests
(Assignee)

Comment 13

11 years ago
Created attachment 236083 [details] [diff] [review]
per neil
Attachment #236083 - Flags: superreview?(neil)
Attachment #236083 - Flags: review?(neil)

Comment 14

11 years ago
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?
(Assignee)

Comment 15

11 years ago
Created attachment 237045 [details] [diff] [review]
per Seno Aiko

there's no protection against that. the result is a very very uncomfortable asynchronous infinite loop.
Attachment #236083 - Attachment is obsolete: true
Attachment #237045 - Flags: superreview?(neil)
Attachment #237045 - Flags: review?(neil)
Attachment #236083 - Flags: superreview?(neil)
Attachment #236083 - Flags: review?(neil)

Comment 16

11 years ago
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.
Attachment #237045 - Flags: superreview?(neil)
Attachment #237045 - Flags: superreview+
Attachment #237045 - Flags: review?(neil)
Attachment #237045 - Flags: review+
(Assignee)

Comment 17

11 years ago
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
(Assignee)

Updated

11 years ago
Status: REOPENED → RESOLVED
Last Resolved: 11 years ago11 years ago
Resolution: --- → FIXED
Product: Firefox → Toolkit
Product: Toolkit → Toolkit Graveyard
You need to log in before you can comment on or make changes to this bug.