Last Comment Bug 348627 - O(N^2) or worse algorithm in error console
: O(N^2) or worse algorithm in error console
Product: Toolkit Graveyard
Classification: Graveyard
Component: Error Console (show other bugs)
: Trunk
: x86 Linux
-- normal (vote)
: ---
Assigned To: timeless
Depends on: 348836
  Show dependency treegraph
Reported: 2006-08-14 11:00 PDT by Boris Zbarsky [:bz] (still a bit busy)
Modified: 2016-06-29 11:02 PDT (History)
6 users (show)
See Also:
QA Whiteboard:
Iteration: ---
Points: ---

patch (1.72 KB, patch)
2006-08-14 11:02 PDT, timeless
bzbarsky: review+
bzbarsky: superreview+
Details | Diff | Splinter Review
just some tests (1.29 KB, text/plain)
2006-08-30 09:03 PDT, timeless
no flags Details
per neil (1.80 KB, patch)
2006-08-30 09:04 PDT, timeless
no flags Details | Diff | Splinter Review
per Seno Aiko (1.80 KB, patch)
2006-09-06 18:44 PDT, timeless
neil: review+
neil: superreview+
Details | Diff | Splinter Review

Description User image Boris Zbarsky [:bz] (still a bit busy) 2006-08-14 11:00:08 PDT

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.



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 User image timeless 2006-08-14 11:02:24 PDT
Created attachment 233594 [details] [diff] [review]
Comment 2 User image Aiko 2006-08-14 12:54:51 PDT
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 User image timeless 2006-08-14 15:38:20 PDT
Comment on attachment 233594 [details] [diff] [review]

mozilla/xpfe/components/console/resources/content/consoleBindings.xml 	1.26
mozilla/toolkit/components/console/content/consoleBindings.xml 	1.14
Comment 4 User image timeless 2006-08-14 15:38:49 PDT
that seems like a bug.
Comment 5 User image Aiko 2006-08-15 02:17:20 PDT
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 User image 2006-08-15 16:28:43 PDT
Hmm... didn't the original loop count from 1 to col-1?
Comment 7 User image Boris Zbarsky [:bz] (still a bit busy) 2006-08-15 16:42:29 PDT
Er... yeah, it did.  Reopening.  timeless, fix the indexing?

Requesting blocking because now we have a functionality regression...
Comment 8 User image Boris Zbarsky [:bz] (still a bit busy) 2006-08-15 16:47:17 PDT
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 User image 2006-08-16 02:25:02 PDT
I can't actually get reasonable error source with a line of > 253 characters.
Comment 10 User image 2006-08-16 02:27:58 PDT
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 User image 2006-08-16 07:01:30 PDT
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 User image timeless 2006-08-30 09:03:24 PDT
Created attachment 236082 [details]
just some tests
Comment 13 User image timeless 2006-08-30 09:04:36 PDT
Created attachment 236083 [details] [diff] [review]
per neil
Comment 14 User image Aiko 2006-08-30 12:32:04 PDT
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 User image timeless 2006-09-06 18:44:57 PDT
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.
Comment 16 User image 2006-09-16 16:12:50 PDT
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 User image timeless 2006-09-19 05:22:03 PDT
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

Note You need to log in before you can comment on or make changes to this bug.