[RELAY][BUG]type inference is slow

[Meteorix]

For a large model, tvm compilation is really slow. I perf it and find that type inference costs most of the time.

# Children      Self  Command  Shared Object                         Symbol
# ........  ........  .......  ....................................  .....................................................................................................................................................................
#
    93.18%     0.00%  python   libtvm.so                             [.] tvm::relay::PatternRewriter::Rewrite
            |
            ---tvm::relay::PatternRewriter::Rewrite
               |
                --93.17%--tvm::relay::InferTypeWithModule
                          |
                           --93.05%--tvm::transform::Pass::operator()
                                     tvm::transform::PassNode::operator()
                                     tvm::transform::ModulePassNode::operator()
                                     tvm::runtime::PackedFunc::operator()<tvm::IRModule, tvm::transform::PassContext>
                                     std::function<void (tvm::runtime::TVMArgs, tvm::runtime::TVMRetValue*)>::operator()
                                     std::_Function_handler<void (tvm::runtime::TVMArgs, tvm::runtime::TVMRetValue*), void tvm::runtime::TypedPackedFunc<tvm::IRModule (tvm::IRModule, tvm::transform::PassContext)>::AssignTypedLambda<tv
                                     void tvm::runtime::TypedPackedFunc<tvm::IRModule (tvm::IRModule, tvm::transform::PassContext)>::AssignTypedLambda<tvm::relay::transform::InferType()::{lambda(tvm::IRModule, tvm::transform::PassCont
                                     |
                                      --93.03%--tvm::relay::transform::InferType()::{lambda(tvm::IRModule, tvm::transform::PassContext const&)#1}::operator()
                                                |
                                                |--79.48%--tvm::relay::TypeInferencer::Infer
                                                |          |
                                                |          |--49.03%--tvm::relay::TypeInferencer::GetType

From my understanding, PatternRewriter rewrite every function in a module, then each time PatternRewriter calls InferType to infer every function. It should be incremental. Is there any reason why this incremental inference is commented? https://github.com/apache/tvm/blob/main/src/relay/transforms/type_infer.cc#L805

[t-vi]

#6900 is my attempt at getting incremental type inference into the PyToch frontend. It will need some serious cleanup, but I think it is useful. It removes the N² thing of re-checking everything in a linearly growing model and empirically reduces the translation time for BERT by ~3x.

[Meteorix]

@t-vi Thanks, I have read your PR and discuss thread. But when I use relay.build, it still calls c++ build pipeline then c++ type inference.

[jroesch]

@Meteorix the type inferencer in its current form has some issues being incrementalized, the reason it is so slow is people are using it in a N^2 with number of nodes way like @t-vi mentioned. It wasn't originally designed to be used this way and probably needs to be refactored but doing that is relatively complicated. There are some other issues I would like to address at same time and probably won't happen until q1 2021.

[junrushao]

If there is no actionable item, I suggest we merge this particular issue to relay improvements, and close this thread.