Execution efficiency; complexity analysis

[AndreVanDelft]

There have been rewriting approaches to ACP before, such as in Toolbus and PSF. Those were not successful:

• One problem was IMO that Toolbus and PSF did not have a smooth coexistence with a normal programming language. SubScript and Free-ACP have that.
• PSF was very slow; I am not sure about Toolbus. Maybe the Free-ACP implementation in Scala is fast enough in many practical cases, but I doubt the scalability.

AFAIK SubScript VM's complexity is O(n), that is: execution overhead is proportional to the program size (code fragments, special elements, calls, operators).

I have the impression that Free-ACP will have complexity O(n^2) or worse.
Consider for instance k processes in a parallel composition, that each perform m actions in sequence. Say n = m*k.

Free-ACP will start with constructing a k-fold choice, namely: what process should start. Each choice contains a starting action, followed by another parallel composition, etc.
It seems that for each step you will have a k-fold overhead. So the complexity may be as bad as O(k*n) which is almost O(n^2).

Is that true? Or will complexity be worse or better?

[anatoliykmetyuk]

I have in mind a "lazy" approach for parallelism cases. Assuming the following axioms for ||:

ax || by = a(x || by) + b(ax || y)
ε || x = ε
δ || x = x

If you have k operands under ||, the first rewriting step will create k operands under +. But + is suspendable, as long as all its operands are suspendable. All of the operands of this particular + are of the form ax, so are suspendable too. Hence, no further rewritings of the newly created parallelism operators will happen, the suspension will happen instead.

Calculating complexity, the first rewriting will create a list of size k, and from then on we'll be working with the list of that fixed size. So, in the particular case of a k-ary parallelism operator with k sequential operands, the complexity will be O(k), independently of the size of these sequential operands.

[anatoliykmetyuk]

Ok, I think I get what you are talking about here. You say that for every action that happens in a parallelism operator, we'll need to do a rewriting of complexity O(k), where k is that parallelism operator's size. And, if we are to do every action from these n = m*k actions, we'll have to do an action of O(k) complexity for each of these n actions, which results in O(n*k) complexity.

Yes, you are completely right here. Further, there are other sequence-processing operations that happen during the rewritings that are proportional to the operators' size: this for example.

I was not keeping in mind the complexity of the program while developing this solution. However, I do not think this should be an immediate concern: definitely something to think about, but not likely to cause troubles in foreseeable future. Or were there troubles of some kind with Toolbus and PSF?

[anatoliykmetyuk]

By the way, following this logic, SubScript also does not have an O(n) complexity: it constantly sends messages from its leafs up through the graph, for each AA that happens. This makes the complexity depend on the average distance from the root to the leafs. If one stacks operators one on top of another, or makes too much nested script calls, or does recursive calls, this will also impact the performance.

Very roughly, the complexity of SubScript is O(r*n), where r is an average distance from the root to a leaf, and n is the number of these leafs.