On Fri, 2010-08-06 at 12:08 -0700, Roland McGrath wrote:
> Since you detect the cycle, could you use the smallest cycle
> instead of zero? Meaning, after X steps following this ref (in some
> specific order), you find yourself again. That assumes that DIEs you
> want to detect equal have the same circular reference structure.
I thought about something like that before. It certainly merits more
thought. But at the moment, it just makes my head hurt. I do know that
we have cases where things don't have exactly the same physical
structure, but they are equivalent, due to different amounts of sharing.
I thought I gave an example of that earlier. Yes, I did. See
Yes, I saw that example. I need to figure out where/how this is handled
in practice in the current scheme. Do you happen to have an actual
example of when this kind of situation arises?
It seems to me that if we can somehow embed/hash in the structure/cycles
better the number of comparisons we need to do to find duplicate
subgraphs should decrease a lot. But I probably need to do some more
testing. What would be some good representative samples to look at?
Something I was thinking about with respect to this. We want to find
subtrees that are equal. But can two subtrees that are part of different
larger subgraphs actually be similar? Since subtrees embedded into
different larger graphs will have a different contexts. Or am I
visualizing things wrongly?