Possible approaches to improving the performance/memory of XRA

[ThomasHaas]

Problem: Our relation analysis represents the may/must-sets of all relations explicitly, which results in huge (possibly prohibitive) memory consumption on larger benchmarks. Since relations can be quadratic in the unrolled program size, it is not uncommon to have may/must-sets with millions of edges.

External solution:
The possibly easiest solution is to just use a Datalog engine like Soufflé which can handle billions of variables and supports parallelization out-of-the-box. Obvious disadvantages are the lack of control and the third-party dependency. One would need to prototype a simple RA with Soufflé to understand it better though.

Internal solutions:
Most of the following points are related to improved representation of the relations.

(1) We can exploit the fact that must \subset may and as such avoid storing edges in the may-set if they are already in the must-set. This, however, makes code that iterates over may-edges harder to write.

(2) We should have explicit, implicit, semi-explicit, and semi-implicit/hybrid representations. Let me explain what I mean by those:

• Explicit: The set of edges is stored explicitly just like we do now (possibly with the optimization from (1)).
• Implicit: The set of edges is computed on demand so that the storage is O(1). For static base relations this is easy to imagine (e.g, ext) but for derived relations this is harder. For, e.g., a union c = a | b, we could represent c implicitly by dispatching containment/iteration operations to a and b. This comes with some overhead. That overhead is too big for composition c = a;b and transitive closures and may likely get large if multiple implicit relations are nested.
  Furthermore, implicit representations are hard to handle inside recursive definitions and generally for the whole propagation framework (solutions to this later).
• Semi-explicit: A semi-explicit representation does not depend on other relations like the implicit one, but it also avoids storing all edges explicitly. For example, the transitive closure c = b+ can be represented by computing the transitive closure (or even transitive reduction) after merging all SCCs. Especially in huge transitive closures that span over almost all events, merging SCCs might trivialize the representation.
• Semi-implicit/hybrid: A semi-implicit/hybrid representation combines implicit and explicit representation. A part of the relation is represented implicitly and a set deviations (edge-additions or deletions) are stored explicitly. For example, after performing XRA on c = a & b, acyclic(c), it is likely that the may-set of c is strictly smaller than the intersection of the may-sets of a and b, so we cannot represent the set fully implicitly anymore. Instead, we have may(c) = (may(a) & may(b)) +- Delta where the Delta is explicit.
  More generally, we can provide a representation of the form S + Delta where S does not necessarily need to be implicitly represented.

Since it is not always clear which representation to choose, we should be able to decide dynamically (possibly mid-computation) which relation is represented in which way. Even just among the explicit representation, there can be multiple options like sparse matrices and dense matrices.

Computation/Propagation: While implicit representations are memory-efficient, they are not suitable for representing data in a propagation-based algorithm. I suggest to do the computation in stages and represent the changes made in the current stage explicitly. In other words, the hybrid representation S + Delta is used throughout with S being the result of the previous computation stage.
After a stage, we can do a compactification that merges the representation into S' = S + Delta for the next stage.
What is a stage?: A stage would be a top-down + bottom-up computation.
The algorithm would look like this

• Do an initial bottom-up computation without propagation (only inside recursion, where this is necessary). Since all relations get computed from scratch, we can directly compute implicit representations where possible.
• Start a new stage where we do a top-down (XRA) followed by a bottom-up propagation (all explicit). After that stage, do compactification and start a new stage.

Alternative computation target: All the above discussion is about computing just the may/must sets of relations. However, there are also the active sets.
For a CAAT-based encoding, we only ever need to compute the active sets of base relations, which are not a big deal.
For the eager encoding, we need to compute a lot more. Now, it would be theoretically possible to interleave the may/must-set computation with the active set computation to avoid computing may/must-edges that are never active.
This a whole different story, so I will leave it at that for now.

I welcome any other suggestions and/or ideas for improving (X)RA.

[hernanponcedeleon]

Now that #743 has been merged, can we close this?

If we ever have problems again related to this, we can reopen.

[ThomasHaas]

Sure