Re: dwarf_output overview

[Mark Wielaard <mjw at redhat dot com>]

On Fri, 2010-08-06 at 12:08 -0700, Roland McGrath wrote:
> > Since you detect the cycle, could you use the smallest cycle size
> > 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
> 	https://fedorahosted.org/pipermail/elfutils-devel/2010-July/001480.html

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?

Thanks,

Mark