Status
()
People
(Reporter: khyperia, Assigned: khyperia)
Tracking
Firefox Tracking Flags
(firefox66 fixed)
Details
Attachments
(1 attachment)
The parser calls FoldConstants in the middle of parsing, on a couple different subnodes. We should not do that, as we'll constant fold the thing again in the outerlevel constant fold pass. Some statistics for *the startup path of the shell* (which I'm using as a test thing): I made a singleton object that lasts the entire length of the process, then every time FoldConstants::visit() is called, I record in the set `(ptr, kind)`. If it already exists, then we're *probably* visiting the same node twice. (`kind` is there in hopes it catches reuse of memory, it will probably hopefully be a different kind). I then count the number of times this set has a new tuple added to it, and how many times a tuple is already there. Before my patch: Unique nodes visited: 45253 Duplicate visits: 2469 After my patch: Unique nodes visited: 45253 Duplicate visits: 0
Assignee  
Comment 1•6 months ago


Assignee  
Comment 2•6 months ago


A good question is "but why? why are we doing this?" and I think we've just had those calls in for years, originally created when the code was *dramatically* different, and never removed them. I traced back through what felt like at least 10 reformatting changes and found this, which is a patch that adds a call to foldconstants in the middle of the parser. https://bugzilla.mozilla.org/show_bug.cgi?id=648526
Comment 3•6 months ago


Thanks for the investigation & diagnostic work, that's very helpful. I think we still need the particular constantfolding call that was added in bug 648526. Try it: js> [1]; dis(); If you see an `object` opcode, good; if you see `newarray` and `initelem`, that's bad. JSOP_OBJECT is an optimization that's enabled only if every field/element of an object/array literal is a constant expression (sideeffectfree and always produces the same value). We currently track that at parse time, so we have to know at parse time if a ParseNode is constant. For the UnaryExpression `1` we solve this by doing constantfolding. There are other things we could do instead. * give up on identifying stuff like `2**16` as constant, but specialcase negative numbers (lame) * compute the HasNonConstInitializer bit during constantfolding, not during parsing * don't compute it at all; instead just do another pass over the fields/elements during the BytecodeEmitter pass to see if the optimization is valid
Comment 4•6 months ago


OK, reviewed. Thanks for doing this; we really should never mention constant folding at all in Parser.cpp. That'll be a good day.
Comment 5•6 months ago


If this was really O(2^n) in source size, it should be possible to produce small strings `s` such that `parse(s)` sits there constant folding for a very long time. I wasn't able to construct one, so I think we must have some kind of countermeasure for this already. It would be nice to know what it isnow we can remove it!
Assignee  
Comment 6•6 months ago


Okay, I just spent probably too long looking into the exact O(?)
behavior of a specific test case in the old system.
I counted the number of times ParseNodeKind::Number
was hit in the constant folder during an eval
of an expression (throughout all calls of the constant folder).
The expressions used:
"[Math.sqrt(2),Math.sqrt(2)]
" > "[[Math.sqrt(2),Math.sqrt(2)],[Math.sqrt(2),Math.sqrt(2)]]
" etc. (growing a binary tree)
"[Math.sqrt(2),Math.sqrt(2)]
" > "[Math.sqrt(2),Math.sqrt(2),Math.sqrt(2),Math.sqrt(2)]
" etc. (growing a list, for control test)
and I compared the number of times PNK::Number
was hit, per each expression, as the depth got larger. The number of Math.sqrt
nodes are depth**2
, so that's the number of times it should be called. Indeed, that's the case for the list. However, the number of times it's called for the binary tree is (depth**2) * (depth + 1)
. If I'm doing my math right, if we let n
be the number of Math.sqrt
calls, that's O(n*log(n))
.
With this patch applied, both the list version and the binary tree version are O(n). Yay!
(I think there are test cases with higher O(?)
runtimes, but I've spent enough time on this already)
Pushed by ahauck@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/585a078ac5b3 Do not constantfold the same nodes more than once. r=jorendorff
Comment 8•6 months ago


bugherder 
Description
•