[Fixbug] Fix graph metadata hash

[KTong821]

Same graphs should have the same hash. Graph node traversal used in generating hash is non-deterministic, leading to different hashes for the same graph.

This can prevent graph runs from using the fast path, since dispatch tables cannot be found for the current (different) hash!

[yaoyaoding]

Very interesting!

Is there any example to reproduce the behavior of producing different hashes?

[KTong821]

@yaoyaoding I am able to observe this on my resnet app branch, with >30 layers. Was not able to observe on smaller graphs.

graph_analyze in graph_impl.py runs a topological sort using iteration over unordered data structure (set, dict), causing this behaviour.

[yaoyaoding]

Will this line produce different string when the topological order is different?

[KTong821]

Yes, I think anything that relies on graph.nodes will cause this.

[vadiklyutiy]

@KTong821 What is the reason of Graph node traversal used in generating hash is non-deterministic?

[yaoyaoding]

using iteration over unordered data structure (set, dict), causing this behaviour.

Good catch! We might need to avoid iterating set when we construct the topological order of nodes of flow graph.
Using dict is fine because "Dictionaries preserve insertion order." from https://docs.python.org/3/library/stdtypes.html#mapping-types-dict

@vadiklyutiy for your question, we used set and iterate it when we compute a topological order of our computation graph.

[KTong821]

@yaoyaoding yes, making the topological ordering one-to-one is a better solution than sorting the hash input string. We might make different graphs have the same hash by sorting here. Will update PR.

[yaoyaoding]

Thanks! @KTong821