Chris Smowton
2013-Dec-31 14:17 UTC
[LLVMdev] [Patch][Review Request][llvm-link] Fix One Performance Bug
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>
Wan, Xiaofei
2014-Jan-02 03:02 UTC
[LLVMdev] [Patch][Review Request][llvm-link] Fix One Performance Bug
This patch has been merged already by Rafael in r181104 Thanks Wan Xiaofei From: Chris Smowton [mailto:chris.smowton at gmail.com] On Behalf Of Chris Smowton Sent: Tuesday, December 31, 2013 10:18 PM To: LLVM Developers Mailing List; Wan, Xiaofei Subject: Re: [Patch][Review Request][llvm-link] Fix One Performance Bug 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/20140102/a6237e40/attachment.html>