[Bug default/19355] New: [PERF] Libabigail slow on the r300_dri.so binary

[Bug default/19355] New: [PERF] Libabigail slow on the r300_dri.so binary

[dodji at redhat dot com]

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

            Bug ID: 19355
           Summary: [PERF] Libabigail slow on the r300_dri.so binary
           Product: libabigail
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: default
          Assignee: dodji at redhat dot com
          Reporter: dodji at redhat dot com
                CC: libabigail at sourceware dot org
  Target Milestone: ---

Running abidw --abidiff on the r300_dri.so binary is really slow and takes ~
5.5GB of rame.

It's now taking bit less than 8 minutes on my X86_64 T450s laptop, for a
non-optimized build.  Bringing that time down would be extremely useful.

The binary can be downloaded from http://ssh.bencoyote.net/~ben/r300_dri.so.gz

Note that running r300_dri.so on the the dwz'ed r300_dri.so takes even more
time, so this needs to be dealt with.

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

[Bug default/19355] [PERF] Libabigail slow on the r300_dri.so binary

[dodji at redhat dot com]

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

dodji at redhat dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |19427

--- Comment #4 from dodji at redhat dot com ---
The string interning task now has it's own enhancement request at #19427.  So
we can track it separately.


Referenced Bugs:

https://sourceware.org/bugzilla/show_bug.cgi?id=19427
[Bug 19427] Intern the strings used in Libabigail
-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug default/19355] [PERF] Libabigail slow on the r300_dri.so binary

[dodji at redhat dot com]

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

--- Comment #2 from dodji at redhat dot com ---
The series of 5 patches which landed in the master branch of the libabigail
code repository, with the latest one being
https://sourceware.org/git/gitweb.cgi?p=libabigail.git;a=commit;h=5a8c000a8714d588346aaf290d7ccde9a1a46174
should somewhat address a number of the issues raised in this problem report.

abidw --abidiff r300_dri.so, on a dwz'ed version of r300_dri.so now takes 12
minutes.  This more than 4x speed increase.  And it doesn't abort anymore.

So now, abidw --abidiff on a compressed (with dwz) r300_dri.so is "only" 4
minutes slower compared to abidw --abidiff on a non compressed one.

The reason for such a difference lies in how we compute the logical parent of a
DIE that has been imported using DW_TAG_imported_unit.

Keep in mind that a given DIE (named D) can be imported several times at
several places of the translation unit.  To get the logical parent of D, we
need to find out where D has been imported.  Looking for that import point
takes a certain (non-constant) amount of walking the translation unit.

It's that walking time that explains the 4 minutes difference on the (huge)
r300_dri.so debug info.

To reduce that time further, an option would be to build the data structure
representing DIEs in such a way that getting the logical parent would be an
operation that is bounded in time, if not constant.  In the short term, that
would imply that libabigail builds its own representation of DIEs, rather than
relying on the DIE representation provided by elfutils.

Note that the time taken on by abidw --abidiff on non-compressed binaries
hasn't changed so far.

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

[Bug default/19355] [PERF] Libabigail slow on the r300_dri.so binary

[dodji at redhat dot com]

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

dodji at redhat dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

--- Comment #1 from dodji at redhat dot com ---
Let's provide more numbers and perspective to this one.

abidw --abidiff r300_dri.so, on a version of r300_dri.so that has been dwz'ed
is even slower.  On my system, it's taking ~ 53 minutes and it's aborting!!!

So the priority now is to reduce the time taken on the dwz'ed version.

Profiling showed that most of the time is taken during what we could call the
"decompressing phase".  Basically, getting the logical parent of a debug
information entry (aka DIE) that has been imported (using the
DW_TAG_imported_unit kind of DIE) is what's taking the most time.

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

[Bug default/19355] [PERF] Libabigail slow on the r300_dri.so binary

[dodji at redhat dot com]

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

--- Comment #3 from dodji at redhat dot com ---
I am keeping this bug open still, as I hope we can keep further improve these
times.

Profiling suggests that one area that is taking time now is string comparison,
especially during the type hashing necessary for emitting the native xml
representation out to disk.  My understanding so far is that we spend a
significant amount of time comparing (class) type names and qualified names.

Note that (interestingly), that string comparison doesn't show up as a hot spot
during type comparisons that are the core of libabigail's comparison engine.
This is because types are canonicalized and so comparing two types (in general)
amounts to comparing two pointers.  One exception to that is when we compare
two classes A and B, and when either A or B is a declaration-only class.  In
that case, that comparison involves comparing their names.

Thus, I think that interning those strings
(https://en.wikipedia.org/wiki/String_interning) would help speed up things
here.

So maybe we could try to come up with an abigail::intern_string type that would
have methods to inter-operate seamlessly with the current std::string which is
used throughout the code base.  We'd then make abigail::decl_base::get_name()
and abigail::decl_base::get_qualified_name() return abigail::intern_string,
adjust what needs adjusting and see what we get in terms of speed increase
there.

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

[Bug default/19355] [PERF] Libabigail slow on the r300_dri.so binary

[dodji at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19355
Bug 19355 depends on bug 19427, which changed state.

Bug 19427 Summary: Intern the strings used in Libabigail
https://sourceware.org/bugzilla/show_bug.cgi?id=19427

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

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

[Bug default/19355] [PERF] Libabigail slow on the r300_dri.so binary

[dodji at redhat dot com]

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

--- Comment #5 from dodji at redhat dot com ---
String interning landed in the master branch of libabigail a while ago.

I guess we should measure the time and space taken by abidw --abidiff on the
r300_dri.so binary, especially when the de-deduplication work lands.

Maybe that could help.

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

[Bug default/19355] [PERF] Libabigail slow on the r300_dri.so binary

[maennich at android dot com]

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

Matthias Maennich <maennich at android dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
                 CC|                            |maennich at android dot com
         Resolution|---                         |FIXED

--- Comment #6 from Matthias Maennich <maennich at android dot com> ---
The test files for this are not longer available and besides the optimizations
that are mentioned in the bug, there have been significant improvements to
abidw's processing speed in mid 2019.

Hence closing.

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