Optimizing further

6 Optimizing further

We here describe a simple transformation on join definitions, which does not rely on a full semantical analysis (such as name usage analysis), but only on a simple, local, syntactical analysis of join-patterns.

Let us take a simple example:

let S(x) | m_1(y) = P_1(x,y)
and S(x) | m_2(y) = P_2(x,y)
  ....
and S(x) | m_n(y) = P_n(x,y)
;;

In this example, a match occurs only when there are messages pending both on S and on one of the methods m₁, m₂,…Thus, from the synchronization point of view, all the methods are equivalent. And indeed, we can regroup them into one, single method channel m by transforming this join definition into:

let S(x) | m(p,y) = P[p] (x,y);;
let m_1(y) = m(1,y);;
let m_2(y) = m(2,y);;
 ....
let m_n(y) = m(n,y);;

Where P is the vector of processes [P₁,P₂,...,P_n].

Methods m₁ m₂,…are now simple wrappers. Method m_i now calls m with an additional i argument, which basically is the index of P_i in array P. At this point, we must emphasize that we describe this technique as a source to source transformation only for clarity. However, the produced source code may not be correct with respect to the join type system, when the types of methods are different. Anyhow, this optimization is implemented using ad hoc mechanisms, this both improves efficiency and solves the typing problem.

Currently, this optimization is performed by the jocaml compiler. This leads to a new interpretation of name indexes by the “join” library. The least significant bits in name indexes still encode names that actually take part to synchronization (here S and m), while their most significant bits (which were previously unused) now encode the extra i argument. This yields two benefits. First, the number of status checks decreases, as the number of matching statuses decreases. Second, the number of channels that can be defined in one definition can now exceed the hosting system integer size, provided some names can be grouped together for synchronization.

In the join compiler, this technique might be used to reduce automata size, since it lowers the number of non-matching statuses, by reducing the number of synchronizing names. Code entries for methods m₁, m₂,…would still be contained in the definition structure, they would only stack the index of the process to fire, and then call the code for method m. Moreover, they do not need to be updated after each transition of the automaton.

Finally, this technique can also be applied to more complex synchronizations. Given a definition that defines names x₁, x₂, …, x_n, using patterns J₁, J₂, …J_m. We say that two names are equivalent, when swapping them in the patterns yields the same set of patterns. We then replace equivalent names by a single name, plus an index.

Consider the following definition

let S_1(x) | m_1(y) = P_1(x,y)
and S_1(x) | m_2(y) = P_2(x,y)
and S_2(x) | m_1(y) = P_3(x,y)
and S_2(x) | m_2(y) = P_4(x,y)
;;

Then the set of defined names {S₁, S₂, m₁, m₂} can be partitioned into {S₁, S₂} and {m₁, m₂}. Then, the above program can be transformed into:

let S(p,x) | m(q,y) = P[p,q] (x,y);;
let m_1(y) = m(1,y);;
let m_2(y) = m(2,y);;
let S_1(y) = S(1,y);;
let S_2(y) = S(2,y);;

(with P[1,1] = P₁, P[1,2] = P₂, P[2,1] = P₃ and P[2,2] = P₄)