[jit] Optimize alias analysis #20899
Conversation
pytorchbot
added
oncall: jit
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
2 times, most recently
from
f19d577 to
d33d47c
Compare
|
This looks good, but the PR is pretty big. Seems like a good opportunity to check out ghstack, our emulation of phabricator diff stacking. Can you put each of items 1-4 on their own stacked PR? |
suo
left a comment
suo
left a comment
There was a problem hiding this comment.
see above comment. Also remember to clang-format :)
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
from
d33d47c to
380dc05
Compare
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
3 times, most recently
from
a4582fc to
c3bf65d
Compare
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
from
c3bf65d to
4be1efb
Compare
suo
left a comment
suo
left a comment
There was a problem hiding this comment.
Looks good so far! Few comments inline.
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
from
2547097 to
f38ea25
Compare
|
@pytorchbot rebase this please |
|
I just realized - wouldn't this be a good use of bloom filters? The primary bottleneck is memory allocation, which bloom filters solve. Intersection/union can also be implemented as bit operations (which would be even faster than what we have now, since they could be sense). The only issue is that bloom filters are only probabilistically correct for membership queries. If an element is in the set it's guaranteed to return true. If it's not, then with arbitrarily high probability (depending on memory usage) it'll return false. Also, we never need to remove elements from the set. We've mentioned that we might want to remove edges, but regardless, we'd need to retraverse our DAG |
It could be, but I'd prefer to bottom out on how well we can do without going probabilistic first. |
…to optimizeAliasAnalysis
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
from
5f6f5c1 to
4549d42
Compare
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
from
7c3f3be to
1272912
Compare
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
from
5798c2d to
99674d1
Compare
suo
left a comment
suo
left a comment
There was a problem hiding this comment.
lgtm except for some name bikeshedding
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
2 times, most recently
from
010543f to
04484fc
Compare
|
@pytorchbot rebase this please. |
Chillee
force-pushed
the
optimizeAliasAnalysis
branch
from
fc993fa to
b044739
Compare
facebook-github-bot
left a comment
facebook-github-bot
left a comment
There was a problem hiding this comment.
@Chillee is landing this pull request. If you are a Facebook employee, you can view this diff on Phabricator.
6 participants
Overall Improvements
unordered_setto sparse bitset.flat_hash_mapinstead ofunordered_mapin some places.Benchmarks (somewhat approximate, best of a couple runs)
I use the
sparse bitsettaken from https://llvm.org/doxygen/SparseBitVector_8h_source.html. I had to make some modifications to use__builtin_popcountland instructions like that instead of other transitive clang dependencies.Some notes on our graph topologies
In general, our graphs are very sparse, and most of the components aren't connected. For GoogleNet, we have 200k nodes, we do 2k
mayAliasqueries, and the sum of magnitudes of sets at each node is 500k (ie: every node, on average, reaches 2.5 leaves).PS: Holy crap macbooks throttle an insane amount with the default fan settings.