From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id ABFAD3836012; Tue, 22 Jun 2021 08:17:35 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org ABFAD3836012 From: "gprocida at google dot com" To: libabigail@sourceware.org Subject: [Bug default/28005] New: abidiff: compares the same types and declarations many times Date: Tue, 22 Jun 2021 08:17:35 +0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: new 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: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter cc target_milestone attachments.created Message-ID: 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: Tue, 22 Jun 2021 08:17:35 -0000 https://sourceware.org/bugzilla/show_bug.cgi?id=3D28005 Bug ID: 28005 Summary: abidiff: compares the same types and declarations many times Product: libabigail Version: unspecified Status: UNCONFIRMED Severity: normal Priority: P2 Component: default Assignee: dodji at redhat dot com Reporter: gprocida at google dot com CC: libabigail at sourceware dot org Target Milestone: --- Created attachment 13510 --> https://sourceware.org/bugzilla/attachment.cgi?id=3D13510&action=3Ded= it archive containing two XML files for comparison The test case here was comparing two mostly vanilla Linux kernel ABI XML fi= les. The libabigail version was 1656f9dd7b09cfc5013b891b93fa6b4dc41a0b6b (predat= ing a known performance regression). The ABI files are attached. Profiling with callgrind and instrumenting the code reveals that the two functions: ir::types_have_similar_structure ir::equals (particularly the var_decl overload) are called thousands more times than there are pairs of types or declaratio= ns to be compared. Around 30% of runtime is estimated to be down these function calls. ir::types_have_similar_structure was called over 1 million times each for p= airs such as int, int and void, void. ir::equals was called more than 50 thousand times each for around 20 (membe= r) variables and more 30 thousand times each for at least 1000 different ones. There is a big caveat: I didn't check to see whether each call had the same context (state affecting the outcome of function call) at each call. In particular, these could be indirectly recursive calls where the same variab= le pair appears earlier in the call stack. From my experimentation with diff algorithms, I know it's not safe to always cache such pending comparisons. On the other hand, types_have_similar_structure cannot be recursing for arguments like int, int, so it's an obvious candidate for memoisation. Howe= ver, I think the repeated calls are a symptom of a deeper problem. My vague intuition is that the structural similarity check could be done with a sing= le pass or could be eliminated altogether by being more careful elsewhere. --=20 You are receiving this mail because: You are on the CC list for the bug.=