[LLVMdev] [Patch][Review Request][llvm-link] Fix One Performance Bug

[Chris Smowton]

Regarding the patch request quoted below, was this code or something 
related ever merged? If not then I strongly encourage doing so.

I came across the same problem using the ld LTO plugin via Clang, 
linking programs that use the QT library, and thus can often consist of 
hundreds or thousands of translation units. With Wan's patch the time to 
link a program using QtCore and QtGui fell from 10 minutes to 3 minutes, 
thanks to not rerunning TypeFinder over the composite module every time 
a new module was linked in.

Regarding feedback given to the original patch request, the "running 
total" of types used in a module probably should be maintained by the 
Linker class rather than forming part of Module; however this requires 
that Linker's composite Module is not modified other than by calling 
Linker's LinkIn... methods, otherwise the running total may become 
inconsistent with the Composite Module, and I'm unsure whether that's 
always true.

FWIW my hurriedly hacked-up version of Wan's patch is attached, but at 
least the restriction that Composite and any supplied type set must be 
kept in sync would need to be documented. The variable names and 
comments are likely inaccurate as I'm not clear whether it is named 
struct types, all struct types or all types which are relevant.

Chris
> From: <Wan>, Xiaofei <xiaofei.wan at intel.com  <http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits><mailto:xiaofei.wan at intel.com  <http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits>>>
> Date: Sunday, 28 April, 2013 1:43 AM
> To: "llvm-commits at cs.uiuc.edu  <http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits><mailto:llvm-commits at cs.uiuc.edu  <http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits>>" <llvm-commits at cs.uiuc.edu  <http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits><mailto:llvm-commits at cs.uiuc.edu  <http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits>>>
> Subject: [Patch][Review Request][llvm-link] Fix One Performance Bug
>
> Background:
> Our business need to link many BC files together to generate a final big BC file; we noticed that the linking time increase significantly(more than linearly) with the increase of the BC file number, our biggest case (with ~8000 BC files ) takes > 1 hour time on XEON server which is unbearable to users.
>
> Profiling and Analysis:
>
> a.       From profiling data, it was observed that TypeFinder() consumes 98% of total time; TypeFinder() is not a key activity in llvm-link, it is just used to filter out all "Named Structure Types" in a module
>
> b.       In current llvm-link, when linking all BC files, the BC file is linked one by one; for example, link bc1, bc2, bc3, bc4, bc5, bcN, the workflow is that, link bc1 & bc2 to bc12, then link with bc3 to bc123, then link with bc4 to bc1234, ..., finally bc12345...N.
>
> The "Named Structure Types" in destination module is calculated in each linking; with the size increase of destination module, TypeFinder() will consume more and more time, this explains why the linking time increase is more than linearly
>
> Solution & Fix & Result:
>
> a.       "Named Structure Types" can be maintained in an incremental way in destination module, when linking a new module, just need to add new "Named Structure Types" into destination module to keep it most up-to-date
>
> b.       The fix is very small, just add a collection in module to keep all "Named Structure Types" in destination module for link. See attachment for details.
>
> c.       After this fix:
>
> For our biggest case, the linking time decrease from 70 minutes to 35 seconds.
>
> ForXalan in SPEC2006, the linking time decrease from 30 seconds to 2 second
>
> Please review, thanks!
>
> --
> Best Regards
> Wan Xiaofei (xiaofei.wan at intel.com  <http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits><mailto:xiaofei.wan at intel.com  <http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits>>)
> Intel Corporation, Shanghai, China
> MCG, Android Runtime & Compiler Team
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131231/7a59b7dd/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: linker.patch
Type: text/x-patch
Size: 6543 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131231/7a59b7dd/attachment.bin>