Slowdown of Flat attributed function

Question

I was trying to write an associative function f using the attribute Flat.

Remove[f];
SetAttributes[f, {Flat, OneIdentity}];
f[0, i_] := i;
f[i_, 0] := i;
f[i_, i_] := 0;
f[i_, j_] /; i != j := 6 - i - j;

To test the performance, I first generate two test sets A and B. They are of the same lengths and just differed by the patterns.

n = 20;
{A, B} = Flatten /@ {Transpose@#, #} &@ConstantArray[{0, 1, 2, 3}, n]
(*{{0, 0, ..., 1, 1, ..., 2, 2, ..., 3, 3, ...}, 
   {0, 1, 2, 3, 0, 1, 2, 3,...}}*)

I would expect f@@ acting on them to have the similar efficiency. But to my surprise, I found f@@A is about 40 times slower than f@@B on my computer (Mathematica 10, Mac OS X). This slowdown ratio will continue to increase with the size $n$ of the problem, following a quadratic power law, i.e. $t_A/t_B\sim O(n^2)$, where $t_A$ or $t_B$ is the time to evaluate f@@A or f@@B respectively.

Timing[f @@ A] (* {0.041280, 0} *)
Timing[f @@ B] (* {0.001190, 0} *)

However, if instead of using the Flat attribute, and forcing the function f to be evaluated in sequential pairings, then f@@A and f@@B do have similar performance (f@@A is even slightly faster, and both are faster than the best performance using the Flat attribute).

Remove[f];
f[0, i_] := i;
f[i_, 0] := i;
f[i_, i_] := 0;
f[i_, j_] /; i != j := 6 - i - j;
f[i_, j_, k__] := f[f[i, j], k];
Timing[f @@ A] (* {0.000507, 0} *)
Timing[f @@ B] (* {0.000610, 0} *)

It seems to me that for Flat attributed functions, Mathematica is seeking to arrange the pairing in an optimal way, but unfortunately this arrangement actually slowdown the performance prominently.

So my question is how does Mathematica actually arrange the pairing when evaluating Flat attributed functions? In particular, why is f@@A evaluated much slower than f@@B with a $O(n^2)$ slowdown ratio in the former example?

---

1. Ordering of downvalue definitions matters.

As @gpap mentioned in the comment below, the order of the definition of the downvalues of f matters a lot. For example, I found the following arrangement gives an extreme contrast of $10^3$ times slowdown!

Remove[f];
SetAttributes[f, {Flat, OneIdentity}];
f[i_, i_] := 0;
f[0, i_] := i;
f[i_, 0] := i;
f[i_, j_] /; i != j := 6 - i - j;
Timing[f @@ A] (* {0.123521, 0} *)
Timing[f @@ B] (* {0.000071, 0} *)

2. f[i_ ,j_] without the condition i != j is not working as expected.

The multiplication table for the monoidal (associative and has identity) function f is like: $$\begin{array}{c|cccc} f & 0 & 1 & 2 & 3\\ \hline 0 & 0 & 1 & 2 & 3\\ 1 & 1 & 0 & 3 & 2\\ 2 & 2 & 3 & 0 & 1\\ 3 & 3 & 2 & 1 & 0\\ \end{array},$$ which actually forms an Abelian group (but I do not want to impose the attribute Orderless in my definition). Due to this Abelian property, the result f@@A (or f@@B) is not going to be affected by the ordering of the elements in A (or B), and it is also expected that f@@A == f@@B to be True. However it is found by @user18792 and @gpap that the result does change with the ordering of the elements as well as the ordering of downvalue definition of f, if f[i_, j_] /; i != j is not defined with the condition i != j. Usually given the definition of f[i_, i_] already, f[i_, j_] is expected to only match the cases with different i and j. However this expectation is not working here. I would also like to know why.

Answer 1

This is not actually an explanation, just some insights. In order to see whats going here I modified your code in the following way:

Remove[f];
SetAttributes[f, {Flat, OneIdentity}];
f[0, i_] := i /; (Print[{0, i}]; True)
f[i_, 0] := i /; (Print[{i, 0}]; True)
f[i_, i_] := 0 /; (Print[{i, i}]; True)
f[i_, j_] := 6 - i - j /; (Print[{i, j}]; True)

For test lets take smaller lists

{A, B} = {{0, 1, 2, 3,0}, {0, 2, 1, 3}}

Then

f @@ A

{2,3}
{1,1}
{2,3}
{4,0}
{2,3}
{1,1}
{2,3}
{0,4}
{2,3}
{1,1}
{2,3}
{4,0}
{2,3}
{1,1}
{2,3}

Out[15]= 4

and

f@@B
{1,3}
{2,2}
{1,3}
{0,2}
{1,3}
{2,2}
{1,3}
Out[16]= 2

If you will repeat the same with

Remove[f];
f[0, i_] := i /; (Print[{0, i}]; True)
f[i_, 0] := i /; (Print[{i, 0}]; True)
f[i_, i_] := 0 /; (Print[{i, i}]; True)
f[i_, j_] := 6 - i - j /; (Print[{i, j}]; True)
f[i_, j_, k__] := f[f[i, j], k] /; (Print[{i, j, k}]; True)

You will see that number of computation steps will be less. This is especially well seen if you slightly increase data lists. Moreover the results differ, as was noted on comment of user gpap.

Here is how Trace output looks like (for function with Attributes Flat and OneIdentity )

Trace[f@@A]

{{A,{0,1,2,3,0}},f@@{0,1,2,3,0},f[0,1,2,3,0],f[1,2,3,0],f[1,2,3],6-1-f[2,3],{-1,-1},{{f[2,3],6-2-3,{-2,-2},{-3,-3},6-2-3,1},-1,-1},6-1-1,4}

I interpret it in the following way (unfortunately Trace[ ] cannot show action of Attributes, because these are evaluated before any rules)

f[0,1,2,3,0]-> f[0,f[1,2,3,0]] (OneIdentity attribute)-> f[1,2,3,0] (rule f[0, i_] := i) -> f[0,1,2,3] (?Flat Attribute)-> f[0,f[1,2,3]](?OneIdentity attribute) -> f[1,2,3] (rule f[0, i_] := i) -> f[1,f[2,3]] (?OneIdentity attribute)-> 6-1-f[2,3] (rule f[i_, j_] := 6 - i - j) -> 6-1 -(6-2-3) (rule f[i_, j_] := 6 - i - j)-> 4

This interpretation, however, is too simple compared to Print[rule] tests. Seems Flat attribute works much harder than shown in Trace[].

The calculation order of function without attributes is different.