[GitHub] [tvm] zhangyicole commented on pull request #12761: [TIR, analysis] Add expr hash sort in ExprDeepEqual

[GitBox <gi...@apache.org>]

zhangyicole commented on PR #12761:
URL: https://github.com/apache/tvm/pull/12761#issuecomment-1248891043

   > Hello!
   > 
   > Thank you for the discussion and the PR. Just a few thoughts here:
   > 
   > * **1.** Indeed, we knew that the existing `Analyzer::Simplify()` would not deal with commutativity, because it does not implement a normalization procedure that is guaranteed to converge towards the normal form (which would indeed imply sorting sub-terms, etc). Rather, all it does is it tries to "do its best" by rewriting some known patterns, with no guarantees to converge to a normal form. For this reason, they could not deal with commutativity in `Simplify()`, because that would indeed lead to non-terminating rewrite sequences (or more realistically return junk, as in practice they stop to rewrite after N rewrites are done). It often works fairly well in practice, but there is no guarantee of being complete (it behaves like a heuristic). However, it really must be correct (i.e, the result of simplify() must rely be equivalent to its input with algebraic laws).
   > * **2.** Before trying to make `Analyzer::Simplify()` able to deal with with commutativity, it could be useful to **see if people are in practice facing the issue where a lot of redundant computations appear, but written differently due to the commutativity of some operators (like + and *)**. If so, it would be cool to see such concrete examples. To be honest, I don't even think that that many people are turning ON the already existing `bool identify_equiv_terms` of the CSE pass `Pass CommonSubexprElimTIR`, which uses `Analyzer::Simplify()`, which itself does what it can with associativity, neutral elements, etc. These things are probably pretty rare, and commutativity is probably too.
   > 
   > Although I designed the pass in a way that it can potentially identify terms that are equivalent [according to any equivalence relation](https://github.com/apache/tvm/blob/main/src/tir/transforms/common_subexpr_elim_tools.cc#L730-#L750) (instead of just the syntactical equality `ExprDeepEqual`), it might not necessary be often needed in practice. This design that allows to use a custom equivalence relation did not cost much more, so I went for it, in case it could become useful to someone one day for a particular case, so that it would not be needed to write another CSE pass for dealing with that. But I don't necessary think that we should do comparisons modulo equivalence often, and this is why by default `bool identify_equiv_terms` of the `Pass CommonSubexprElimTIR` is set to false.
   > 
   > * **3.** If we decide that `Analyzer::Simplify()` (or another new Analyzer!) should deal with commutativity, then it should itself deal with commutativity, rather than baking commutativity into `ExprDeepEqual` which is supposed to be just a deep **syntactical** equality, and is used as such in many many places of TVM's codebase (not just the CSE). So clearly it should not being changed (as @tqchen noted too).
   > * **4.** Remember that normalizing terms properly in order to deal with commutativity (which indeed includes sorting sub-terms) will likely be computationally expensive, which will make compilation of ML models longer. Actually, just the smaller work that `Analyzer::Simplify()` does is already time consuming, and that's probably why people leave the `bool identify_equiv_terms` of the CSE pass set to false (which is the default behavior, as I wrote earlier). It might make people want even less to turn ON this `bool identify_equiv_terms`. Perhaps the pseudo-normalization that `Analyzer::Simplify()` does is not too bad as a compromise: still usable in practice when needed (i.e does not take too long), and deals with most simplifications needed (although not commutativity).
   > * **5.** If all the other algebraic properties (associativity, simplification of neutral elements, etc) are still done by the **pseudo**-normalization `Analyzer::Simplify()` that is not guaranteed to find a normal form, I am not sure that a "normalizer for commutativity" built on top would be complete -even just in regard to commutativity. Is it worth it to then make `Analyzer::Simplify()` slower while still being incomplete?
   > 
   > Thanks!
   
   Hi，@FranckQC，thanks for the questions and comments。
   I quite agree with what you said about the complexity of the `Analyzer::Simplify()`, the overhead of the `Analyzer::Simplify()` is very expensive, changes to the `ExprDeepEqual` will not improve the function and may slow down its performance, so, as suggested by tqchen, make it as A subclass, maybe a good approach.
   
   The source of this submission is that in my previous use, there was a size judgment for the input and output size of the operator containing the reshape operation, and I rewrote deep equal to meet my needs. After seeing your issue, I think this part of the rewrite is helpful, so submit this PR.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org