Do not constant-fold the same nodes more than once

RESOLVED FIXED in Firefox 66



6 months ago
6 months ago


(Reporter: khyperia, Assigned: khyperia)



Firefox Tracking Flags

(firefox66 fixed)



(1 attachment)



6 months ago
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 outer-level 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 re-use 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

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.
Thanks for the investigation & diagnostic work, that's very helpful.

I think we still need the particular constant-folding 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 (side-effect-free 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 constant-folding.

There are other things we could do instead.

* give up on identifying stuff like `2**16` as constant, but special-case negative numbers (lame)

* compute the HasNonConstInitializer bit during constant-folding, 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
OK, reviewed. Thanks for doing this; we really should never mention constant folding at all in Parser.cpp. That'll be a good day.
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 is--now we can remove it!

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)

Comment 7

6 months ago
Pushed by
Do not constant-fold the same nodes more than once. r=jorendorff

Comment 8

6 months ago
Closed: 6 months ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla66
You need to log in before you can comment on or make changes to this bug.