ASTKernel.plan_cpu is not deterministic with Py3

[blechta]

Following example produces different code with Py2 and Py3. Note that both work as expected and are validated against other form compilers.

from ufl import *
from tsfc import compile_form
from coffee.plan import ASTKernel

element = FiniteElement("P", triangle, 1)
u, v = TrialFunction(element), TestFunction(element)
a = inner(grad(u), grad(v))*dx
c = compile_form(a)
a = ASTKernel(c[0].ast)
a.plan_cpu(dict(optlevel='O2'))
print(a.gencode())

[blechta]

This is subtle. Can see a nonzero diff with

• Py3.4.3 and @5d633c0843434703e2ab87bd0b649112ecc368d5,
• Py3.5.2 and @5d633c0843434703e2ab87bd0b649112ecc368d5,

there is zero diff on

• Py3.5.2 and @4b52eb9a40555f1c1fabf8baa05b68645d1e2895,

and following does not work

• Py3.4.3 and @4b52eb9a40555f1c1fabf8baa05b68645d1e2895.

Seems that @5d633c0843434703e2ab87bd0b649112ecc368d5 is not a good patch...

[blechta]

Mentioned patch probably does not play a role. The problem is that Py3 result is non-deterministic, provbably somewhere else than @5d633c0843434703e2ab87bd0b649112ecc368d5. Py2 seems to be fine.

[miklos1]

Did you verify that the issue (of non-determinism) isn't in TSFC?

[blechta]

Not really. But without the ASTKernel.plan_cpu non-determinism has not been observed when running the FFC regression tests locally and on Bamboo.

[blechta]

It's hash randomization in python interpreter, see https://docs.python.org/3/using/cmdline.html#cmdoption-R. With PYTHONHASHSEED=666666 the above program gives me on my system a determinate answer, same as Py2.

[miklos1]

Then it probably happens through the iteration of a dict or set (which do no preserve ordering) for a purpose that matters for code generation.

[FabioLuporini]

Yes, that's a very reasonable explanation. Ugh, that was subtle.

[miklos1]

Preliminary testing suggests that this patch may fix the issue:

diff --git a/coffee/rewriter.py b/coffee/rewriter.py
index de9710e..47753df 100644
--- a/coffee/rewriter.py
+++ b/coffee/rewriter.py
@@ -568,7 +568,7 @@ class ExpressionRewriter(object):
             self.licm('only_const').licm('only_outlinear')

         # Transform the expression based on the sharing graph
-        nodes, edges = sgraph.nodes(), sgraph.edges()
+        nodes = [n for n in nodes if n in sgraph.nodes()]
         if not (nodes and all(sgraph.degree(n) > 0 for n in nodes)):
             self.factorize(mode='heuristic')
             self.licm('only_const').licm('only_outlinear')