Created attachment 282377 [details]
All optimizations mentioned in the bug description as a single patch
(This was previously filed 2011-03-28 as an email I sent to the tools-portage emailing list. By request, I now post it here as well, with an update about my lack of time..)
I have an improvement suggestion in the form of a patch for the revdep-rebuild tool in the gentoolkit package. It was written against version 0.3.0_rc11-r3.
First some high-level explanation:
I optimized two different code paths, namely the steps "Assigning files to packages" (when not using the -e flag) and "Assigning files to ebuilds" (when using the -e flag). Thus only either of the optimizations kicks in during an invocation of the tool.
Below I present the results I got for the execution times for the optimized code paths ONLY (i.e. the total time of running the script took a lot longer). When running the tests, all necessary file contents had gotten cached into the Linux file cache during earlier runs. The 3_broken.rr file which works as input for the optimized code contained 122 files in my case.
Before After Speedup
"Assigning files to packages" 8 minutes 4.5 seconds ~100x
"Assigning files to ebuilds" 20 seconds 4.0 seconds ~5x
I was able to isolate the changes almost entirely to one function, by changing its interface a little bit. I renamed it in an attempt to make it better match the service it provides.
The main thing in the "Assigning files to packages" optimization is avoiding scanning all the /var/db/pkg/**/CONTENTS files once for every entry in the 3_broken.rr file. Instead, the CONTENTS files are scanned for ALL the entries in one go, and storing all matches in a temporary file. Then, to maintain the ability to detect missing entries, the script still iterates through all entries one by one, but uses the temporary file as input instead of the CONTENTS files, thus completing in almost no time.
The "Assigning files to ebuilds" code path (e.g. when using -e) included an innocent-looking piece of code that run very slowly at least for me - took 17 seconds to evaluate using 100% of one cpu core. I replaced it with a sed equivalent which completes in a fraction of a second.
The "-e" code path lacked a call to "clean_trap", so I added that.
Two bugfixes #196460 and #280341 that had been implemented in the script were implemented in such a way that they did not work properly when the -e switch was specified. I improved the fixes to work both with and without -e.
In summary, I have tried my best to maintain the exact functionality of the script including the handling of missing files and files not owned by a package.
The new interface of the function that was mostly rewritten also makes it easy to later add the same kind of reporting of files not owned by any package into get_exact_ebuilds() (used when using -e) as get_packages() (used when not using -e) was already implementing, without performance loss.
It might be possible to split the patch into two, but I am unfortunately not able to put any effort into this in the near future.
Thank you for a great tool and your efforts towards making Gentoo what it is :)
Jonas "xkr47" Berlin