[Webkit-unassigned] [Bug 74170] DFG's interpretation of rare case profiles should be frequency-based not count-based

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=74170





--- Comment #2 from Filip Pizlo <fpizlo at apple.com>  2011-12-09 02:11:11 PST ---
Well this is interesting.  What I was trying to say is that we want a test like:

rateOfFailure / rateOfExecution >= threshold

to determine if we should assume the worst for this instruction.  But that's not quite right.  Consider the following code:

for (var i = 0; i < 10000; ++i)
    doSomethingThatTakesSlowPathOneInEveryLoopIterations()

In this case, rateOfFailure = rateOfExecution/10.  So it seems like we can assume that it rarely fails and then compile the code as such.

But this would be wrong!  Our goal is not to maximize the probability of a single speculation check succeeding; it is instead to maximize the probability that the function completes without any speculation failures.  Thus if we have a 1/10 chance that any iteration of the loop fails, and the loop executes 10,000 times, then the probability that we will fail at some point during the execution of this loop is essentially 1.  Formally, it is something like:

1 - (1 - rateOfFailure / rateOfExecution) ^ 10000

or more broadly:

1 - (1 - rateOfFailure / rateOfExecution) ^ (rateOfExecution / numbeOfFunctionInvocations)

We have two choices.  We can either perform the formal computation, or we can be clever.  Consider that we do not count the total number of executions of an operation (rateOfExecution) but we do count the number of times the function executes and test:

rateOfFailure / numberOfFunctionExecutions >= threshold

then oddly, we get something much closer to the more general formulation, in terms of its behavior when you plot it for varying inputs.  This is actually great news, because it means that we don't even have to track the execution rate of basic blocks - all we need is the total number of times that a code block executed.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.