[qvti] Cache operation results

[eclipse-qvtd-bot]

| --- | --- | | Bugzilla Link | 491264 | | Status | RESOLVED FIXED | | Importance | P3 normal | | Reported | Apr 07, 2016 12:03 EDT | | Modified | Sep 01, 2016 13:23 EDT | | Depends on | 500519 | | Reporter | Ed Willink |

Description

Instrumenting Adolfo's 101Companies example highlights that some operation calls are re-evaluated many times.

For interpreted execution, we could just intercept OperationCallExp evaluation to short circuit re-evaluation. But for which operations? Caching all String / Integer / Collection and perhaps more generally DataType-sourced operations could be expensive. (Testing for re-invocation requires a hash computation of all arguments.)

For CGed execution, many operations are inlined so the call suppression point has been optimized away. Selected operations could be reified as classes similar to mapping classes so that much of the Mapping suppression logic could be re-used.

However the Operation call suppression should use a weak cache so that memory is freed up to help the GC out.

Selective reification of operations by classes suggests we need a call tree analysis to identify those operation calls that may benefit from caching.

? an operation with more than one caller is cached. Call within a loop using a loop variable is a single caller. For multiple callers we can compare argument expressions so that clearly distinct arguments disable caching.

How much of this could be in OCL? An ExpressionInOCL can be pre-analyzed to formulate a smarter evaluation strategy. Perhaps QVTiTransformationAnalysis extends ExpressionInOCLAnalysis.

[eclipse-qvtd-bot]

By Ed Willink on Jun 15, 2016 06:54

Cache added to all CGed QVT Function calls for now.

Adding this to all operations could be really bad, for instance Collection::size() etc can be computed quickly, but if cached, the caching requires a hashcode computation thereby converting a constant execution time to proportionate. Conversely caching Collection::closure() is probably good.

This is presumably only soluble by an estimator for the computation time.

[eclipse-qvtd-bot]

By Ed Willink on Jun 15, 2016 10:24

Although true OCL operations are side effect free and so MAY-BE_CACHED, more general execution may have (benign) side effects; e.g. a symbol name allocator that counts names MUST-BE-CACHED. Bad side effects MUST-NOT-BE-CACHED. UML's Operation.isQuery could be rescued to define MUST-BE-CACHED.

[eclipse-qvtd-bot]

By Ed Willink on Jun 15, 2016 12:41

Cached operations do not play well with the operation dispatch API.

Short-circuit interpreted evaluation of e.g. BooleanAndOperation.dispatch defers evaluation of the second argument until the easy first argument cases have been handled. The CGed evaluation has yet to be upgraded to exploit dispatch short-cirtcuiting.

Caching requires that all arguments are evaluated to identify the cache entry.

The following are declared to be validating:\ Boolean::and/implies/or\ Collection::exists/forAll\ OclAny::oclIsInvalid/oclIsUndefined\ ?? Boolean::not/xor ??

All are quick so prohibiting caching on validating operations should not be a problem.

Conversely losing the short circuit capability on ordinary operations may be a simplification.

[eclipse-qvtd-bot]

By Ed Willink on Jun 17, 2016 16:39

Caching requires a polymorphic treatment of source+argyments so revising the evaluation API to use a boxedSourceAndArguments Object[] avoids reformatting and simplifies once all the deprecations can be removed.

Rearranging the EvaluationVisitor.visitOperationCallExp to populate an Object[] then direct to Executor.internalExecuteOperationCallExp allows the executor to choose dispatch strategy /caching. Just Functions for now to demonstrate the principle.

Lightweight (not-cached) operations can be identified by volatile or validating; just need to add a volatile keyword to OCLstdlib.

More generally an Operation (call) can be uncached if all calls of the Operation have unique arguments. In practice probably means a single caller. Inputs of Mappings/Operations with mutally non-conformant types are distinct. Loops over Sets may extend the domain of uniqueness with further mutually distinct types.

[eclipse-qvtd-bot]

By Ed Willink on Aug 30, 2016 07:25

Auto-determination of whether to cache is not as sensitive as might appear.

If\ B = the cost of executing the function/operation body\ C = the cost of creating a cached result\ R = the cost of re-using a cached result\ N = the number of re-uses that actually occur (not knowable without profiling)

The critical comparison is R < B. There is no point caching if re-use (a hash calculation, a map get and a hit check) is more expensive than a re-computation. C is probably less than 2R, so if we cache unnecessarily we incurred a B+C cost rather than a B. But B>R, so at worst we incur an extra 2R cost on a B cost. Cannot be worse than 200% overhead for operations where R is similar to B. No overhead for R > B. Steadily reducing overhead as B >> R.

For the interpreter B incurs interpreted overheads whereas R does not so B > R for quite modest functions. Probably cache everything that is not explicitly uncacheable.

[eclipse-qvtd-bot]

By Ed Willink on Sep 01, 2016 01:58

(In reply to Ed Willink from comment #5)

For the interpreter B incurs interpreted overheads whereas R does not so B > R for quite modest functions. Probably cache everything that is not explicitly uncacheable.

For the interpreter there is also an analysis cost to determine if B > R. This is overwhelming for typical occasional OCL usage.

Therefore for inrterpreted usage (In reply to Ed Willink from comment #0) For interpreted execution, we could just intercept OperationCallExp evaluation to short circuit re-evaluation.

Not quite so simple. Must also intercept IterationManager dispatching.

Probably just want to re-implement ConstrainedOperation.evaluate etc to cache. Simple library operations will not cache and so incur zero new overhead.

[eclipse-qvtd-bot]

By Ed Willink on Sep 01, 2016 08:22

(In reply to Ed Willink from comment #6)

Not quite so simple. Must also intercept IterationManager dispatching.

No. An IterationManager iterates body expressions not operations.\

Probably just want to re-implement ConstrainedOperation.evaluate etc to cache. Simple library operations will not cache and so incur zero new overhead.

This seems to work rather well.

If an operation implementation overrides evaluate, it is invoked directly without overhead.

Else if it overrides basicEvaluate, it inherits a version of evaluate that attempts to re-use a cached entry before reverting to a basicEvaluate to initialize the cache.

All tests pass with ConstrainedOperation, EObjectOperation, EInvokeOperation, StringTokeneizeOperation cached. (After repairing the tutorial examples to create new queries after modifying the model, else they re-use a stale cache. And after fixing an ambiguity regression in the CG tests.)

[eclipse-qvtd-bot]

By Ed Willink on Sep 01, 2016 13:23

Pushed to master for M2