class FactorCacheEvaluator(UnvalidatedForm, LogicEvaluator):
"""
Factors a program with a child factorizer, which defaults to Galley keeping
loop nests shallow, then evaluates each query it produces with a child
evaluator, caching the result of each query by the canonical form of what
it computes. A query which reads cached results can hit the cache too.
Results are cached by the identity of the tensors they read, so a tensor
must not change while its results are cached. A result is dropped when a
tensor it read dies, so cached results live as long as their inputs. The
results of a program may be shared with the cache.
"""
def __init__(
self,
evaluator: LogicEvaluator,
factorizer: Callable[[LogicLoader], LogicLoader] | None = None,
stats_factory: StatsFactory | None = None,
):
self.evaluator = evaluator
self.capture = LogicCapture()
if factorizer is None:
self.factorizer: LogicLoader = GalleyLogicFactorizer(
self.capture, optimizer="greedy", cost_model=LOOP_DEPTH_COST_MODEL
)
else:
self.factorizer = factorizer(self.capture)
self.stats_factory = (
DenseStatsFactory() if stats_factory is None else stats_factory
)
self.cache: dict[LogicNode, Tensor] = {}
# The keys which read each tensor, by id, to drop when it dies.
self.readers: dict[int, list[LogicNode]] = {}
def _ref(self, tns: Tensor) -> TensorRef:
if id(tns) not in self.readers:
self.readers[id(tns)] = []
weakref.finalize(tns, self._forget, id(tns))
return TensorRef(id(tns))
def _forget(self, ref: int) -> None:
for key in self.readers.pop(ref, ()):
self.cache.pop(key, None)
def lower(self, prgm: LogicNode, bindings: dict[Alias, Tensor] | None = None):
if isinstance(prgm, LogicExpression):
out = HardAlias("result")
stmt: LogicStatement = Plan(
(Query(Table(out, prgm.fields()), prgm), Produces((out,)))
)
elif isinstance(prgm, Plan):
stmt = prgm
elif isinstance(prgm, LogicStatement):
stmt = Plan((prgm,))
else:
raise ValueError(f"Invalid prgm type: {type(prgm)}")
# Galley reads relabels only on tables.
stmt, results = extract_tensors(push_relabels(stmt), bindings or {})
stats = {
var: self.stats_factory(
tns, tuple(Field(f"d{i}") for i in range(len(tns.shape)))
)
for var, tns in results.items()
}
self.factorizer(
stmt,
{var: tns.ftype for var, tns in results.items()},
stats,
self.stats_factory,
)
def read(node: LogicNode) -> LogicNode | None:
match node:
case Table(Alias() as alias, idxs):
return Table(Literal(self._ref(results[alias])), idxs)
case FillTable(Alias() as alias):
return Literal(results[alias].fill_value)
case DimensionTable(Alias() as alias, Literal(r)):
return Literal(np.intp(results[alias].shape[r]))
return None
factored = self.capture.last_prgm
assert isinstance(factored, Plan)
for body in factored.bodies:
match body:
# Galley starts a pointwise result from its fill, as the
# evaluator does itself.
case Query(lhs, Aggregate(Literal(ffuncs.overwrite), _, arg, ())):
body = Query(lhs, arg)
match body:
case Query(
Table(Alias() as alias, idxs), Table(Alias() as src, src_idxs)
) if idxs == src_idxs:
results[alias] = results[src]
case Query(Table(Alias() as alias, idxs), rhs):
key = query_key(
cast(LogicExpression, Rewrite(PostWalk(read))(rhs)), idxs
)
if key in self.cache:
results[alias] = self.cache[key]
continue
reads = {
var: results[var]
for var in PostOrderDFS(rhs)
if isinstance(var, Alias)
}
(results[alias],) = self.evaluator(
Plan((body, Produces((alias,)))), reads
)
# A result which is one of its inputs would keep itself alive.
if all(results[alias] is not tns for tns in reads.values()):
self.cache[key] = results[alias]
for tns in reads.values():
self.readers[self._ref(tns).id].append(key)
case Produces(args):
if isinstance(prgm, LogicExpression):
return TableValue(results[cast(Alias, args[0])], prgm.fields())
return tuple(results[cast(Alias, arg)] for arg in args)
case _:
raise ValueError(f"Unsupported statement: {body}")
raise ValueError("The factorized program produces nothing")