Advisories/The EvalContext speed-up optimization may cause incorrect computed result


The problem

There is a feature in Analytica 4.6 that allows it to avoid certain computations when it can "prove" that the result will not be used in the final result. The feature exists to speed-up evaluation times, and was first introduced in Analytica 4.6. It has been discovered that a bug in the implementation of this optimization can cause some computations to return an incorrect result.

Products impacted

The problem reported here exists only in Analytica and ADE release 4.6.1.

The issue has been fixed in Analytica 5.0, and it does not exist in release 4.5 or earlier.

Does this impact your model?

Test it

To find out whether your own model is impacted by this issue, you should turn this speed-up feature off and compare your results to see if they change. Here's how:

  1. Launch two instances of Analytica
  2. Load your model into both.
  3. In the second Analytica instance:
    1. Press F12 to open the typescript window.
    2. Type: EnableEvalContextUse:0
  4. Evaluate your final result(s) in each instance, in the same order. Compare the final results to see if they differ.

If your final results change from turning off this speed-up optimization, then you should assume this problem impacts you. If the results don't change, then it is pretty safe to assume your model is not impacted.

Side note: There are some cases involving random-number generation where the bug is not present, but in which turning the optimization off could change the sequence of random numbers generated. Because of this, a change in your results does not absolutely prove that the bug is present, but we recommend you just assume you are impacted if you see your results change.

Frequency

As of the date of this advisory (23-Sept-2016), we know of only one model in use that is impacted by this problem. Several dozen models testing are not impacted, and in the 18 months since 4.6 was released, the issue was not discovered and reported to us by any of our users (until it was reported for this one model mentioned). Update (26-Jan-2018 -- second model discovered that was impacted).

Nevertheless, we feel it is important to treat this seriously, since it is hard to spot an incorrect result.

If, after this advisory is distributed, we receive reports from our end-users of other models are impacted, we will update this section.

What you should do

You should test your model to see if your model is impacted. If so, or if you just want to play it totally safe, you can turn off this speed-up optimization in your own model(s). The steps for turning off this optimization are:

  1. Open your model in Analytica
  2. Press F12 to open the Typescript window
  3. Type: EnableEvalContextUse : 0
  4. Save your model

Turning on the optimization locally

Since this is a speed-up optimization, turning off the optimization for your entire model may increase your model evaluation times. Please be aware that this increase be extremely minimal, so don't you should not go to any additional effort unless you see a significant slowdown.

If you do experience a significant slowdown from turning off this optimization, you can recover the benefits by turning the optimization on locally for a few select variables. Start by identifying which variables slowdown. You can do this in Analytica Enterprise or Optimizer as follows.

  1. Launch two instances of Analytica.
  2. Load your model into both
  3. In Typescript set EnableEvalContextUse:0 in one instance, and EnableEvalContextUse:1 in the other.
  4. Compute your model in both instances.
  5. In not already present, use File / Add Library.... / Performance Profiler / Embed to add the Performance Profiler to your model.
  6. Compare the CPU msecs between your two instances to find variables that have slowed down substantially.

For these few variables, you can re-enable the speed-up optimization locally for them by surrounding their definition with a call to SetEvaluationFlag as follows.

If your original definition is

Var x[I] := F(a,b);
Var y[I] := F2(a,b);
If y>0 Then G(x) / Sum( x, I ) Else 0

Change it to

SetEvaluationFlag( 'evaluationContext', true, 
    Var x[I] := F(a,b);
    Var y[I] := F(a,b);
    If y>0 Then G(x) / Sum( x, I ) Else 0
)

You should, of course verify that the result is still correct.

Technical details

The EvalContext speed-up optimization allows Analytica to avoid carrying out some intermediate computations if it can "prove" that the result of the intermediate computation does not impact the final result. By avoiding these unnecessary computations, faster evaluation may be achieved in some cases. The bug identified in this advisory arises because under a certain combination of conditions, its "proof" that the result will influence the final result is wrong, and hence it skips a computation that was actually necessary.

The following example illustrates this speed-up optimization as well as the bug:

Advisory1.png

The evaluation of F(A) by itself would involve three calls to F(), since F's parameter is atomic and the result of A has three cells. The result is an array indexed by I. But for the call to F(A) in the first cell of the table, only the I=1 slice of the result will be retained in the final result. The evaluation context speed-up optimization deduces that it needs to call the function F() only once, i.e., for F(3), thus saving two unnecessary calls to F(). Likewise, in the second cell it is able to save two squaring operations.

The bug identified in this advisory occurs when the third cell is evaluated. In this case, F(A) does need to be called three times, because Sum needs all three values for its result. The context logic deduces this case incorrectly, concluding that it only needs to evaluate F(7). The correct result for the third cell is 9+25+49 = 83, but with this bug it instead computes 49+49+49 = 147.

The bug in the logic occurs only when the following conditions all co-occur:

  • You have call to an array function that operates over an index, I. In the above example, this is the Sum function which operates over index I.
  • The call to this array function is a sub-expression nested within a larger expression, or it is in a User-Defined Function's definition. In the above example, Sum appears within a larger expression, the call to the Table function.
  • The expression passed to the array parameter of this function involves a computation that will be repeated for each slice along I (e.g., by array-abstraction). In the example, the computation of F(A) involves repeated calls to F() for each cell of A.
  • At the point where the array function appears, it must be possible to prove that only a single slice of the result along index I will be retained in the final result. This slice must be along the same index that the function operates over. In the example, you can prove that only the I=3 slice of the result of Sum will be retained, and Sum operates over index I.

See Also

Comments


You are not allowed to post comments.