From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 661B23858C3A; Fri, 21 Jan 2022 14:08:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 661B23858C3A From: "gprocida at google dot com" To: libabigail@sourceware.org Subject: [Bug default/28005] abidiff: compares the same types and declarations many times Date: Fri, 21 Jan 2022 14:08:15 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: libabigail X-Bugzilla-Component: default X-Bugzilla-Version: unspecified X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: gprocida at google dot com X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Resolution: X-Bugzilla-Priority: P2 X-Bugzilla-Assigned-To: dodji at redhat dot com X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://sourceware.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 21 Jan 2022 14:08:15 -0000 https://sourceware.org/bugzilla/show_bug.cgi?id=3D28005 --- Comment #4 from gprocida at google dot com --- Hi Dodji. Note: This issue remains lower priority for us than anything relating to ab= idw 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 understandi= ng 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 he= lp, but this may lose some change_kinds if recursion is stopped sooner than bef= ore. 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 prope= rly. 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. --=20 You are receiving this mail because: You are on the CC list for the bug.=