[NVFuser] make comparators obey strict weak ordering by davidberard98 · Pull Request #75713 · pytorch/pytorch

davidberard98 · 2022-04-12T23:53:57Z

Stack from ghstack:

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering
https://en.cppreference.com/w/cpp/named_req/Compare

In particular comp(a, a) == false was failing on lower_loops.cpp.

Differential Revision: D35599653

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. [ghstack-poisoned]

facebook-github-bot · 2022-04-12T23:54:03Z

🔗 Helpful links

🧪 See artifacts and rendered test results at hud.pytorch.org/pr/75713
📄 Preview Python docs built from this PR
📄 Preview C++ docs built from this PR
❓Need help or want to give feedback on the CI? Visit our office hours

💊 CI failures summary and remediations

As of commit ddd7dcd (more details on the Dr. CI page):

💚 💚 Looks good so far! There are no failures yet. 💚 💚

This comment was automatically generated by Dr. CI (expand for details).

Please report bugs/suggestions to the (internal) Dr. CI Users group.

Click here to manually regenerate this comment.

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. ghstack-source-id: 660898e Pull Request resolved: #75713

davidberard98 · 2022-04-12T23:56:39Z

@davidberard98 has imported this pull request. If you are a Facebook employee, you can view this diff on Phabricator.

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. Differential Revision: [D35599653](https://our.internmc.facebook.com/intern/diff/D35599653) [ghstack-poisoned]

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. ghstack-source-id: e3cfd10 Pull Request resolved: #75713

davidberard98 · 2022-04-13T01:08:43Z

@davidberard98 has imported this pull request. If you are a Facebook employee, you can view this diff on Phabricator.

jjsjann123 · 2022-04-13T19:29:05Z

torch/csrc/jit/codegen/cuda/lower_expr_sort.cpp

      const auto& dependencies_1 = concrete_id_dependencies_.at(concrete_id_1);
      // if id1 depends on id0 it means id0 is inside id1, so id1 < id0
-      return !dependencies_1.count(concrete_id_0);
+      if (dependencies_1.count(concrete_id_0)) {


This doesn't look right... We can only return false after this point. In the old code, we could return true if dependencies_1.count(concrete_id_0) == false

this is my understanding, but lmk if something seems wrong here:

this looks like it's basically trying to do a toposort, where, if a depends on b, then we want a to go before b in the final sorted order. afaik, the typical comparator for this is "if a path a->b exists, then comp(a, b) = true. Otherwise comp(a, b) = false". Or in this case, if a maps to a set containing b, then return comp(a, b) = true. In particular, if there's no relationship between a and b, then comp(a, b) and comp(b, a) should both be false (unless you have some other way to break ties in this case)

if this the type of sort I was describing above, then dependencies_1.count(concrete_id_0) == false is a case where we don't necessarily have any dependence between dep_1 and dep_0; in other words, 0 -> 1 (dep_0 maps to dep_1) implies we should return true; and 0 -> 1 implies 1 -/-> 0; but 1 -/-> 0 doesn't imply 0 -> 1, so 1 -/-> 0 doesn't necessarily mean we should return true.

This sounds very reasonable to me (without knowing much about the actual implementation).

I'd argue in that instance, the entire block inside could just be removed, since it only returns false inside and that is the default behavior after the true block.

pytorch/torch/csrc/jit/codegen/cuda/lower_expr_sort.cpp

Lines 699 to 706 in 9b49a26

if (concrete_id_dependencies_.find(concrete_id_1) !=

concrete_id_dependencies_.end()) {

const auto& dependencies_1 = concrete_id_dependencies_.at(concrete_id_1);

// if id1 depends on id0 it means id0 is inside id1, so id1 < id0

if (dependencies_1.count(concrete_id_0)) {

return false;

}

}

Having said that, I'm waiting on someone who actually knows what this does to respond. cc'ing @csarofeen @naoyam

yeah, that's true - I can delete those blocks if we decide this change is okay

Thanks @davidberard98. I believe the fix makes sense and is indeed a nice catch.

great, thanks for the help reviewing @naoyam @jjsjann123

I removed the false blocks like @jjsjann123 suggested

jjsjann123 · 2022-04-13T19:29:11Z

torch/csrc/jit/codegen/cuda/lower_loops.cpp

      const auto& dependencies_1 = concrete_id_dependencies_.at(concrete_id_1);
      // if id1 depends on id0 it means id1 is inside id0, so id0 < id1
-      return dependencies_1.count(concrete_id_0);
+      if (dependencies_1.count(concrete_id_0)) {


IIUC, the first block and the second block are checking the same thing from different perspective and that's what strict weak ordering checks as well. So even though it looks slightly strange from the code diff, they are still correct.

I'm stamping it.

jjsjann123 · 2022-04-13T19:35:11Z

Fort this check comp(a, a) == false

Maybe we can add a quick short cut where we just return false when both things are pointing to the same value?! cc'ing @csarofeen

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing on lower_loops.cpp. Differential Revision: [D35599653](https://our.internmc.facebook.com/intern/diff/D35599653) [ghstack-poisoned]

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. ghstack-source-id: 9f8b1a6 Pull Request resolved: #75713

jjsjann123

LGTM

jjsjann123 · 2022-04-14T07:06:44Z

torch/csrc/jit/codegen/cuda/lower_loops.cpp

      const auto& dependencies_1 = concrete_id_dependencies_.at(concrete_id_1);
      // if id1 depends on id0 it means id1 is inside id0, so id0 < id1
-      return dependencies_1.count(concrete_id_0);
+      if (dependencies_1.count(concrete_id_0)) {


IIUC, the first block and the second block are checking the same thing from different perspective and that's what strict weak ordering checks as well. So even though it looks slightly strange from the code diff, they are still correct.

I'm stamping it.

csarofeen · 2022-04-14T13:53:47Z

Thanks @davidberard98 let me check this quickly today and will get back to you on the changes.

csarofeen · 2022-04-14T17:18:34Z

Thanks again, @davidberard98. I was just trying to confirm some properties of this sorting. So what they're actually doing is a "topo sort" of "loop nests". I naively assumed when I wrote that code that there was a single unique ordering of loop nests, but in fact it makes sense that in certain kernels that's not the case, and multiple orderings can be correct. As long as both orderings are consistent (perfectly reversed actually), then we should be fine. concrete_id_1 and concrete_id_2 in both of these blocks should have the same exact information, we just want sorting order to be exactly reversed.

So the block in lower_expr_sort the old logic was:

  if(id0 dependent on id1)
    id0 < id1
  else if(id1 dependent on id0)
    id0 >= id1
  else
    id0 < id1

and in lower_loops:

  if(id0 dependent on id1)
    id0 >= id1
  else if(id1 dependent on id0)
    id0 < id1
  else
    id0 < id1

With your updated logic I believe it's in lower_expr_sort:

  if(id0 dependent on id1)
    id0 < id1
  else
    id0 >= id1

and in lower_loops:

  if(id0 dependent on id1)
    id0 >= id1
  else
    id0 < id1

So a few things. I agree there's an issue with unstable sorting. What I think we should do is in lower_loops put exactly what's in lower_expr_sort and reverse the sorted list used in lower_loops.cpp. Does that make sense @davidberard98 and @naoyam?

naoyam · 2022-04-14T17:30:59Z

Reversing the order generated in lower_expr_sort seems better as it removes the logic duplication.

Re:

and in lower_loops:

  if(id0 dependent on id1)
    id0 >= id1
  else
    id0 < id1

I think what the PR does is to check if id1 depends on id0, and only in that case returns true.

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing on lower_loops.cpp. Differential Revision: [D35599653](https://our.internmc.facebook.com/intern/diff/D35599653) [ghstack-poisoned]

davidberard98 · 2022-04-14T18:59:06Z

@davidberard98 has imported this pull request. If you are a Facebook employee, you can view this diff on Phabricator.

naoyam · 2022-04-14T19:42:05Z

torch/csrc/jit/codegen/cuda/lower_utils.h

+
+  const std::unordered_map<IterDomain*, std::unordered_set<IterDomain*>>&
+      concrete_id_dependencies_;
+  const ComputeAtMap compute_at_map_;


nit: this can be a const reference.

whoops, meant to do that - thanks for noticing this!

naoyam · 2022-04-14T19:42:41Z

Thanks again @davidberard98 . The update looks good to me. Just added a minor comment.

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing on lower_loops.cpp. Differential Revision: [D35599653](https://our.internmc.facebook.com/intern/diff/D35599653) [ghstack-poisoned]

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. ghstack-source-id: e3b44f5 Pull Request resolved: #75713

csarofeen

Thanks so much for the help!

davidberard98 · 2022-04-14T20:31:11Z

@davidberard98 has imported this pull request. If you are a Facebook employee, you can view this diff on Phabricator.

davidberard98 · 2022-04-14T21:41:06Z

@pytorchmergebot merge this

github-actions · 2022-04-14T21:43:00Z

Hey @davidberard98.
You've committed this PR, but it does not have both a 'release notes: ...' and 'topics: ...' label. Please add one of each to the PR. The 'release notes: ...' label should represent the part of PyTorch that this PR changes (fx, autograd, distributed, etc) and the 'topics: ...' label should represent the kind of PR it is (not user facing, new feature, bug fix, perf improvement, etc). The list of valid labels can be found here for the 'release notes: ...' and here for the 'topics: ...'.
For changes that are 'topic: not user facing' there is no need for a release notes label.

Summary: Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. Pull Request resolved: #75713 Approved by: https://github.com/jjsjann123, https://github.com/csarofeen Test Plan: contbuild & OSS CI, see https://hud.pytorch.org/commit/pytorch/pytorch/d21082c98222b69f53d428e0c199d4d37491d155 Reviewed By: mehtanirav Differential Revision: D35599653 Pulled By: davidberard98 fbshipit-source-id: 5b51cdf61d7112bdb17270f32a7e9d2a87791a82

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. Pull Request resolved: pytorch#75713 Approved by: https://github.com/jjsjann123, https://github.com/csarofeen

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. Pull Request resolved: pytorch#75713 Approved by: https://github.com/jjsjann123, https://github.com/csarofeen Co-authored-by: David Berard <dberard@fb.com>

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. Pull Request resolved: pytorch#75713 Approved by: https://github.com/jjsjann123, https://github.com/csarofeen

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. Pull Request resolved: pytorch/pytorch#75713 Approved by: https://github.com/jjsjann123, https://github.com/csarofeen

Internally there is an at-runtime assert that was failing. The assert is checking to make sure that comparators obey strict weak ordering https://en.cppreference.com/w/cpp/named_req/Compare In particular `comp(a, a) == false` was failing. Pull Request resolved: pytorch/pytorch#75713 Approved by: https://github.com/jjsjann123, https://github.com/csarofeen Co-authored-by: David Berard <dberard@fb.com>

facebook-github-bot added the cla signed label Apr 12, 2022

facebook-github-bot added the oncall: jit Add this issue/PR to JIT oncall triage queue label Apr 12, 2022

davidberard98 requested a review from jjsjann123 April 13, 2022 15:41

jjsjann123 requested changes Apr 13, 2022

View reviewed changes

davidberard98 requested review from eellison and jjsjann123 April 14, 2022 00:43

jjsjann123 approved these changes Apr 14, 2022

View reviewed changes

davidberard98 mentioned this pull request Apr 14, 2022

[testing] -D_GLIBCXX_ASSERTIONS #75766

Closed

naoyam reviewed Apr 14, 2022

View reviewed changes

csarofeen approved these changes Apr 14, 2022

View reviewed changes

pytorchmergebot closed this in d21082c Apr 14, 2022

davidberard98 added the topic: not user facing topic category label Apr 14, 2022

jjsjann123 mentioned this pull request Apr 17, 2022

[NVFuser] make comparators obey strict weak ordering csarofeen/pytorch#1590

Merged

facebook-github-bot deleted the gh/davidberard98/89/head branch April 18, 2022 14:17

	if (concrete_id_dependencies_.find(concrete_id_1) !=
	concrete_id_dependencies_.end()) {
	const auto& dependencies_1 = concrete_id_dependencies_.at(concrete_id_1);
	// if id1 depends on id0 it means id0 is inside id1, so id1 < id0
	if (dependencies_1.count(concrete_id_0)) {
	return false;
	}
	}

Conversation

davidberard98 commented Apr 12, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

facebook-github-bot commented Apr 12, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

🔗 Helpful links

💊 CI failures summary and remediations

Uh oh!

davidberard98 commented Apr 12, 2022

Uh oh!

davidberard98 commented Apr 13, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

davidberard98 Apr 13, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jjsjann123 commented Apr 13, 2022

Uh oh!

jjsjann123 left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

csarofeen commented Apr 14, 2022

Uh oh!

csarofeen commented Apr 14, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

naoyam commented Apr 14, 2022

Uh oh!

davidberard98 commented Apr 14, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

naoyam commented Apr 14, 2022

Uh oh!

csarofeen left a comment

Choose a reason for hiding this comment

Uh oh!

davidberard98 commented Apr 14, 2022

Uh oh!

davidberard98 commented Apr 14, 2022

Uh oh!

github-actions bot commented Apr 14, 2022

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

davidberard98 commented Apr 12, 2022 •

edited

Loading

facebook-github-bot commented Apr 12, 2022 •

edited

Loading

davidberard98 Apr 13, 2022 •

edited

Loading

csarofeen commented Apr 14, 2022 •

edited

Loading