Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: poset dominates method only testing reachability #33971

Closed
zdjones opened this issue Aug 30, 2019 · 8 comments
Closed

cmd/compile: poset dominates method only testing reachability #33971

zdjones opened this issue Aug 30, 2019 · 8 comments

Comments

@zdjones
Copy link
Contributor

@zdjones zdjones commented Aug 30, 2019

What version of Go are you using (go version)?

$ go version
go version devel +8c5de667d3 Fri Aug 30 08:28:40 2019 +0000 darwin/amd64

The gc compiler's partially ordered set, uses a method dominates to determine whether two nodes are partially ordered. dominates does a depth-first search of the DAG and returns true as soon as it finds a path between the given nodes. Because there may be multiple paths between the nodes (its a DAG, not a tree):

 n1    
|  \  
A   B
|  /
 n2 

finding that path A exists isn't sufficient to say that n1 dominates n2.

Fortunately, as best I can tell, reachability is logically correct everywhere dominates is currently used in poset.go.

I would like to change the name of the method (dominates -> reaches) and update all the comments in the file accordingly.

@dominikh @rasky @Merovius

@rasky

This comment has been minimized.

Copy link
Member

@rasky rasky commented Aug 30, 2019

@dr2chase

I find "dominates" clearer. I might be rusty on graph theory, but the fact that is a DAG (and not an oriented graph) should conflate the concepts of domination and reachability, as far as I can tell. In the context of this poset, I would say that "n1 dominates n2" means "I can prove n1 < n2", which is the property we are focusing on.

Maybe I didn't fully understand your comment though....

@zdjones

This comment has been minimized.

Copy link
Contributor Author

@zdjones zdjones commented Aug 30, 2019

It sounds like you've got my comment right. I totally agree with what you're saying, and admit that my understanding of dominance/reachability is based mostly on wikipedia and Go compiler code.

The difference has become meaningful, for me, when I'm considering the poset and the SSA/CFG in the same sitting. Handling the SSA, dominance, in the strict graph theory sense, is important and requires attention. Then I switch to thinking about the current state of the poset, and I need to switch to a different meaning of the term.

So, I suppose the benefit of the change would be in reducing the cognitive overhead of handling both the SSA and poset at once. The difference is subtle, and the precision in naming would help me, and possibly others. That being said, if both cases are actually expressing dominance (which I'm not sufficiently qualified to judge), then there isn't really more precise terminology available, and I'll have to manage.

I should mention... I'm in awe of the code/logic in poset.go, it's been great to read, use, and think about. Thanks for that!

@Merovius

This comment has been minimized.

Copy link

@Merovius Merovius commented Aug 30, 2019

@rasky As I understand the definition, "X dominates Y" means every path from the root to Y goes through X. So in the DAG in the original comment (assuming n1 is the root), A does not dominate n2 - the path n1 -> B -> n2 does not pass through A. Likewise, B does not dominate n2. But n1 dominates n2 (even if we assume that the root is "further up", as long as it reaches n1 and does not introduce new paths into the diamond). IMO, the definition is fairly clear and pretty clearly not the same as reachability.

I don't quite understand what you mean by a DAG and not an "oriented" graph. Do you mean that it's a DAG and not a general directed graph (i.e. that it's the acyclic nature that means the two are identical)? Because that still doesn't quite work. Confusingly, the "acyclic" in DAG means "there are no directed cycles", which still allows undirected cycles (the diamond is cyclic as an undirected graph, but if the arrows flow from top to bottom, you can't "follow" that cycle).

The two are conflated in (directed) trees and forests though. In an undirected tree, there is exactly one path from any node to any other node. Hence, in a directed tree, if there is one path Root -> … -> A -> … -> B, then every path from the Root to B must pass through A (there is at most one such path, after all). The difference between a DAG and a directed forest is exactly that the DAG allows diamonds as in the original comment.

I'm fairly confident that the two concepts are different and that what you care about in poset.go is reachability, not dominance. If it helps, one of the Wikipedia examples of a partially ordered set is "The vertex set of a directed acyclic graph ordered by reachability" so it stands to reason that if the DAG is supposed to model a partial order, reachability is what you're interested in :)

Also, FWIW, I met @zdjones at GopherCon UK via a discussion about the poset.go stuff and when I read the implementation I got pretty confused :) I am not super familiar with graph theory myself, so I had to consult the definition myself. And couldn't, for the live of me, figure out why dominance is important (and thought that there must be a super clever trick behind this data structure that I'm not seeing). When I figured out that the dominates method actually checks reachability (doing a DFS and aborting once you find the node is a pretty standard way to check for reachability), things clicked and I stopped looking for hidden magic :)

@rasky

This comment has been minimized.

Copy link
Member

@rasky rasky commented Aug 30, 2019

Thanks, I now agree it makes sense to rename it. Feel free to send a CL and assign it to me.

@zdjones

This comment has been minimized.

Copy link
Contributor Author

@zdjones zdjones commented Aug 30, 2019

@Merovius, your comment has helped me think about this better. I see now that my original example wasn't great for this discussion. Should have been more like:

root 
|   \
n1   \  
|     B  
A    /
|   /
 n2 

Now, finding that path A exists isn't sufficient to say that n1 dominates n2.

I also see now that if you pretend n1 is a root of an independent DAG, then reachability = dominance for that new DAG (the root dominates all nodes in the DAG). I think the code in poset.go is actually doing that; dominates is calling the depth first search on a DAG rooted at n1, even if n1 isnt the root of one of the DAGS in the forest.

In other words, its a matter of context. In the context of the poset as a whole, dominates is not the right word for n1 -> n2. In the context of a DAG rooted at n1, dominates is correct, as it is the same as reachability. The implicit creation of the DAG rooted at n1 makes it more difficult to reason about, so I'm still for the change

@Merovius

This comment has been minimized.

Copy link

@Merovius Merovius commented Aug 30, 2019

@zdjones I feel that's a bit of a stretch as a justification :) The doc-comment say "Returns true if i1 dominates i2", not "in the subgraph obtained by using i1 as a new root" :) The comment near the top also says "It is implemented as a forest of DAGs; in each DAG, if node A dominates B, it means that A<B", which is not true (I mean, it is true. But IMO anyone would read this as an "if and only if", which is not true). Your observation is that asking if a root dominates another node is equivalent to asking if that other node is reachable, but TBH I'm certain that's not what's meant here :)

@zdjones

This comment has been minimized.

Copy link
Contributor Author

@zdjones zdjones commented Aug 30, 2019

Agreed, every time I read it, I read it as you say. CL is enroute.

@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Aug 30, 2019

Change https://golang.org/cl/192617 mentions this issue: cmd/compile: rename poset method dominates to reaches

@gopherbot gopherbot closed this in ba068c1 Aug 30, 2019
tomocy added a commit to tomocy/go that referenced this issue Sep 1, 2019
The partially ordered set uses a method named 'dominates' to determine whether
two nodes are partially ordered. Dominates does a depth-first search of the
DAG, beginning at the source node, and returns true as soon as it finds a path
to the target node. In the context of the forest-of-DAGs that makes up the
poset, dominates is not necessarily checking dominance, but is checking
reachability. See the issue tracker for a more detailed discussion of the
difference.

Fortunately, reachability is logically correct everywhere dominates is currently
used in poset.go. Reachability within a DAG is sufficient to establish the
partial ordering (source < target).

This CL changes the name of the method (dominates -> reaches) and updates
all the comments in the file accordingly.

Fixes golang#33971.

Change-Id: Ia3a34f7b14b363801d75b05099cfc686035f7d96
Reviewed-on: https://go-review.googlesource.com/c/go/+/192617
Reviewed-by: Giovanni Bajo <rasky@develer.com>
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
t4n6a1ka added a commit to t4n6a1ka/go that referenced this issue Sep 5, 2019
The partially ordered set uses a method named 'dominates' to determine whether
two nodes are partially ordered. Dominates does a depth-first search of the
DAG, beginning at the source node, and returns true as soon as it finds a path
to the target node. In the context of the forest-of-DAGs that makes up the
poset, dominates is not necessarily checking dominance, but is checking
reachability. See the issue tracker for a more detailed discussion of the
difference.

Fortunately, reachability is logically correct everywhere dominates is currently
used in poset.go. Reachability within a DAG is sufficient to establish the
partial ordering (source < target).

This CL changes the name of the method (dominates -> reaches) and updates
all the comments in the file accordingly.

Fixes golang#33971.

Change-Id: Ia3a34f7b14b363801d75b05099cfc686035f7d96
Reviewed-on: https://go-review.googlesource.com/c/go/+/192617
Reviewed-by: Giovanni Bajo <rasky@develer.com>
Run-TryBot: Giovanni Bajo <rasky@develer.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.