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

RESOLVED FIXED

Status

RESOLVED FIXED
13 years ago
3 years ago

People

(Reporter: bzbarsky, Assigned: timeless)

Tracking

Trunk
x86
Linux

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 3 obsolete attachments)

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

13 years ago
Posted patch patch (obsolete) — Splinter Review
Attachment #233594 - Flags: superreview?(bzbarsky)
Attachment #233594 - Flags: review?(bzbarsky)
(Reporter)

Updated

13 years ago
Attachment #233594 - Flags: superreview?(bzbarsky)
Attachment #233594 - Flags: superreview+
Attachment #233594 - Flags: review?(bzbarsky)
Attachment #233594 - Flags: review+

Comment 2

13 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

13 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

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

Comment 5

13 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.
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).
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...

Updated

13 years ago
Depends on: 348836
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

13 years ago
Posted file just some tests
(Assignee)

Comment 13

13 years ago
Posted patch per neil (obsolete) — Splinter Review
Attachment #236083 - Flags: superreview?(neil)
Attachment #236083 - Flags: review?(neil)

Comment 14

13 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

13 years ago
Posted patch per Seno Aiko (obsolete) — Splinter Review
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 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

13 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

13 years ago
Status: REOPENED → RESOLVED
Last Resolved: 13 years ago13 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.