# Slowdown of Flat attributed function

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} *)

1. 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.

• Just want to note, that if you remove OneIdentity attribute, then you will get quite different results. I think here is key of the problem. – user18792 Nov 7 '14 at 10:06
• @user18792 No, as explained in the document of Flat: "when functions that are Flat are used in pattern matching, they often also require the attribute OneIdentity", so removing OneIdentity will make the function ill defined. Even if OneIdentity is removed, the slowdown of f@@A is still there. My question is about the slowdown due to the Flat attribution. I don't think OneIdentity plays any role in this phenomenon. – Everett You Nov 7 '14 at 10:17
• Just an observation that you may or may not be aware of is that the order of the definition of the downvalues of f is important and it may be what causes the more/less efficient evaluation of f for different ordered arguments. For instance, if you exchange the first two definitions, f@@B is -2 whereas f@@A still 0. – gpap Nov 7 '14 at 12:12
• @gpap Thanks for your comment. The ordering of downvalue definitions indeed matters. Also f@@B evaluates to -2 is a bug. I do not expect the result to change. I found one has to enforce the condition i != j in the definition of f[i_, j_] in order to get the right result. But usually having defined f[i_, i_], f[i_, j_] is assumed to take different i and j. But I don't understand why it does not behave as expected here. – Everett You Nov 7 '14 at 19:03

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.

• The changing of the result is another bug that I do not understand. The result 0 is not expected to change for any ordering (because f is modeling an Abelian group multiplication). I have to enforce the condition f[i_, j_] /; i != j to get the correct result, which is usually unnecessary given the definition of f[i_, i_] already. I do not understand the behavior here either. – Everett You Nov 7 '14 at 19:13
• I think the only way to shed a bit of light is to analyze carefully Trace[] output. – user18792 Nov 7 '14 at 19:44
• I did looked into the Trace, but I did not gain much insight. It seems that the pairing process is not shown in the Trace output. – Everett You Nov 7 '14 at 19:49