504881 - Consider dealing better once we hit MAX_BRANCHES

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Boris Zbarsky [:bzbarsky]]

See bug 504829 comment 11 and preceding.  Basically, once we hit MAX_BRANCHES for a tree, if we keep trying to execute it and exiting on the same branch exit things end up really slow.

Comment 1

[Boris Zbarsky [:bzbarsky]]

I guess what really bothers me here is that we're basically guarding on a loop invariant.  If we could reliably detect that and hoist the guard to before even calling into the jitted code, that could be a win.

Comment 2

[David Mandelin [:dmandelin]]

I want to second this bug: this is one of the most common causes of severe performance problems in TM. A few ideas to consider:

- Increase MAX_BRANCHES. It won't solve the problem in principle, but it might help. Or it might hurt--so we should also consider making MAX_BRANCHES adaptive.

- We were just talking about using a better data structure to select the type-matching tree when the number of trees gets bigger. (Currently we always search a list.)

- Do something smarter when we reach MAX_BRANCHES. If perf is going to be worse than interpreter at a certain point, then even just blacklisting the loop is a win. To be smarter, we could try to recompile the loop in some way to reduce the branchiness. For example, if there is one point that is causing most of the branching, we should deoptimize at that point.

Comment 3

[Graydon Hoare :graydon]

Another heuristic: throw out the least-recently-taken branch when you hit branch #32, not the one you're currently building.

(IOW bake-in the assumption that not all branches are taken with equal probability, and that sorting them is better than not.)

Comment 4

[Luke Wagner [:luke]]

TM was removed.