622670 - js::Bindings::findDuplicateArgument is O(n**2)

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jeff Walden [:Waldo]]

Attachment: Shell testcase to (begin to) demonstrate non-linear blowup

We check for duplicated argument names when a function is strict mode code and when JSOPTION_STRICT is set.  The check uses a dead-simple O(n**2) algorithm to check, which works fine for small argument counts but blows up if there are lots of arguments.

The attached testcase starts to demonstrate the complexity blowup.  Since the loop here is so thin it's not obvious how much worse the complexity is than non-linear.  But in any case, this tail of output definitely starts to show that 1.5x argument count isn't triggering quite the same 1.5x time:

1066: 2ms
1599: 7ms
2398: 14ms
3597: 31ms
5395: 66ms
8092: 145ms
12138: 327ms
18207: 705ms
27310: 1591ms
40965: 3672ms
61447: 9364ms
/home/jwalden/moz/inflight/dup-arg.js:15: SyntaxError: too many function arguments

Comment 1

[Jeff Walden [:Waldo]]

Fixed by bug 630332.