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

Status: RESOLVED FIXED

(Toolkit Graveyard :: Error Console, defect)

Description

[Boris Zbarsky [:bzbarsky]]

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.

Comment 1

[timeless]

Attachment: patch

Comment 2

[Aiko]

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 3

[timeless]

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

Comment 4

[timeless]

that seems like a bug.

Comment 5

[Aiko]

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

[[e-mail]]

Hmm... didn't the original loop count from 1 to col-1?

Comment 7

[Boris Zbarsky [:bzbarsky]]

Er... yeah, it did.  Reopening.  timeless, fix the indexing?

Requesting blocking because now we have a functionality regression...

Comment 8

[Boris Zbarsky [:bzbarsky]]

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

[[e-mail]]

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

Comment 10

[[e-mail]]

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

Comment 11

[[e-mail]]

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);

Comment 12

[timeless]

Attachment: just some tests

Comment 13

[timeless]

Attachment: per neil

Comment 14

[Aiko]

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?

Comment 15

[timeless]

Attachment: per Seno Aiko

there's no protection against that. the result is a very very uncomfortable asynchronous infinite loop.

Comment 16

[[e-mail]]

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 17

[timeless]

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