Bug 19355

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.

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.

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.

The string interning task now has it's own enhancement request at #19427.  So we can track it separately.

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.

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.