[Bug default/28005] abidiff: compares the same types and declarations many times

["gprocida at google dot com" <sourceware-bugzilla@sourceware.org>]

https://sourceware.org/bugzilla/show_bug.cgi?id=28005

--- Comment #4 from gprocida at google dot com ---
Hi Dodji.

Note: This issue remains lower priority for us than anything relating to abidw
XML output.

I originally reported findings against commit 1656f9dd. By the time we got to
commit 46b1ab08, things were significantly better. However, the following
commit 39ba8596 (found with git bisect) made run times even longer.

We noticed this with the ABI XML comparison I'm now attaching. Timings are in
user CPU seconds on my machine:

commit  5.8.{7,13}      A vs B
1656f9dd        165     170
46b1ab08        92      91
39ba8596        372     538

I haven't profiled again, but I can guess that there are going to be many
repeated comparisons as before.

Adding some caching of equality results may be possible, but my understanding
is that this needs to be done in a way that avoids caching incomplete (due to
infinite recursion avoidance) and possibly incorrect results.

Note that is it is always safe to cache results that say a difference was
found. In fact, with libabigail we see things go slower when they are more
differences, so some kind of memoisation of negative outcomes may really help,
but this may lose some change_kinds if recursion is stopped sooner than before.

It is also possible to write an ABI graph comparison algorithm so that each
pair of things is compared at most once - I outlined this a while ago - and the
ABIs here compare in about 1 second with that.

The RETURN_TRUE_IF_COMPARISON_CYCLE_DETECTED and related code in abg-ir.cc
looks like it's trying to do similar things, but I haven't studied it properly.

I do wish I could achieve comparable performance in libabigail without very
intrusive changes. At a minimum updating change_kind* k / change kind
propagation would need to be handled as part of this.

Lastly, libabigail also does canonicalisation, sharing some of the same
equality functionality. I've not attempted to try to extend my algorithm to
cover that, not even as a theoretical exercise.

Regards,
Giuliano.

-- 
You are receiving this mail because:
You are on the CC list for the bug.