Speedup get_op_ids_in_path
Speedup get_op_ids_in_path

Summary:
Perf bug report: https://www.facebook.com/groups/1405155842844877/permalink/1617904561570003/

Diagnosis:

I've done some digging into this and here's what I've found:
(1) In this use case, the call is disallowed_op_ids = get_op_ids_in_path(ssa, blob_versions, [], inputs)) where inputs = ['res4_22_sum'] is the last blob produced by the res4 stage of a ResNet101 model.
(2) get_op_ids_in_path has exponential running time in the number of blocks in the res4 stage of ResNet. This is based on empirical running times. This call should complete in 4.5 days on my devgpu.
(3) I haven't familiarized myself enough with the IR and SSA code in core.py to understand the algorithmic fix yet, but surely there's a more efficient algorithm to compute the same thing.

Reviewed By: Yangqing

Differential Revision: D4446278

fbshipit-source-id: 8bd147f92d62b865dc355d5802a53e92d64b6e21

pietern/caffe2,xzturn/caffe2,sf-wind/caffe2,pietern/caffe2,Yangqing/caffe2,bwasti/caffe2,davinwang/caffe2,bwasti/caffe2,Yangqing/caffe2,davinwang/caffe2,xzturn/caffe2,bwasti/caffe2,sf-wind/caffe2,sf-wind/caffe2,Yangqing/caffe2,davinwang/caffe2,Yangqing/caffe2,sf-wind/caffe2,sf-wind/caffe2,davinwang/caffe2,xzturn/caffe2,davinwang/caffe2,xzturn/caffe2,bwasti/caffe2,pietern/caffe2,caffe2/caffe2,xzturn/caffe2,pietern/caffe2,Yangqing/caffe2,bwasti/caffe2,pietern/caffe2