[gambit-list] Algorithmic complexity of clang

Marc Feeley feeley at iro.umontreal.ca
Tue May 1 09:47:02 EDT 2012


Concerning the algorithmic complexity of clang, I am forwarding to the list an analysis I did in January to better understand the build times of Gambit when compiled with gcc.

Marc

Begin forwarded message:

> From: Marc Feeley <feeley at iro.umontreal.ca>
> Subject: Re: gambit-c
> Date: 24 January, 2012 10:38:28 AM EST
> To: Jeremy Huddleston <jeremyhu at macports.org>
> Cc: Jeremy Lavergne <jeremy at lavergne.gotdns.org>, Bradley Lucier <lucier at math.purdue.edu>
> 
> 
> On 2012-01-23, at 7:36 PM, Jeremy Huddleston wrote:
> 
>> Ok, I see the issue now.  I've also created gcc-preprocessed versions for comparison with gcc (since gcc doesn't like clang's preprocessed sources).  Recent clang trunk compiles _thread.c much faster than XCode 4.2's, but it's not nearly as fast as gcc and llvm-gcc.  Now that I've been able to reproduce this, I've passed it along to our compiler team for analysis.  There are really 2 issues here, however: one is the compilation time, and one is the resulting performance of the built executable.
>> 
>> I think the bug report that I filed will be focusing on the compilation speed.  I think we should hold off on the performance of the executable until after the compiler issues are worked out since they will certainly have an impact on the executable itself.
> 
> I agree.
> 
>> Thanks for your help,
>> Jeremy
>> 
>> $ time /Developer/usr/bin/clang -c -O1 -Wno-parentheses clang-preprocessed/_thread.preproc.c 
>> 
>> real	0m28.851s
>> user	0m22.885s
>> sys	0m0.728s
>> 
>> $ time /opt/local/bin/clang-mp-3.1 -c -O1 -Wno-parentheses clang-preprocessed/_thread.preproc.c 
>> 
>> real	0m18.909s
>> user	0m17.001s
>> sys	0m0.778s
>> 
>> $ time /Developer/usr/bin/llvm-gcc-4.2 -c -O1 gcc-preprocessed/_thread.preproc.c 
>> 
>> real	0m4.798s
>> user	0m3.976s
>> sys	0m0.127s
>> 
>> $ time /opt/local/bin/gcc-apple-4.2 -c -O1 gcc-preprocessed/_thread.preproc.c 
>> 
>> real	0m3.558s
>> user	0m3.062s
>> sys	0m0.167s
> 
> I repeated my experiment to compare clang 2.0 (from an old installation of Xcode), clang 3.0 (from Xcode 4.2) and clang 3.1 (built from the LLVM sources, installed in my /usr/local/bin).  I did a "CC=the_c_compiler ./configure --enable-single-host;time make" for each C compiler.  The transcript of each build is attached below.  Here are the respective build times:
> 
> % tail -3 transcript-clang-*
> ==> transcript-clang-2_0.txt <==
> real	16m4.946s
> user	15m48.710s
> sys	0m15.776s
> 
> ==> transcript-clang-3_0.txt <==
> real	107m2.396s
> user	106m30.343s
> sys	0m31.707s
> 
> ==> transcript-clang-3_1.txt <==
> real	16m9.004s
> user	15m52.962s
> sys	0m15.684s
> 
> As you can see clang 3.0 has a much longer build time than clang 2.0 and clang 3.1 (which are very close).  I'm convinced this is due to the use of very high complexity algorithms in the clang 3.0 compiler.  To verify this conjecture I looked at the compile time for _io.c and _thread.c for clang 2.0 and clang 3.0.  The times in seconds are:
> 
>            clang 2.0    clang 3.0
>  _io.c      287.0        1948.0
>  _thread.c    8.8          21.6
> 
> In terms of lines of code in the host C function, _io.c is about 3.1 times bigger than _thread.c .  These numbers can be used to estimate the algorithmic complexity of the algorithms in these two compilers.
> 
> Notice that for clang 2.0 the compile times of _io.c and _thread.c are related by a *cubic* function on the relative size of the host C function:
> 
>    8.8 * 3.1^3 = 262 (which is close to 287)
> 
> For clang 3.0 the compile times of _io.c and _thread.c are related by a *quartic* function on the relative size of the host C function:
> 
>   21.6 * 3.1^4 = 1994 (which is close to 1948)
> 
> So if n is the size of the code, for large n, clang 2.0 is O(n^3), which is terrible, and clang 3.0 is O(n^4), which is outright catastrophic for compiling machine generated code.  To be practical (for machine generated code) the complexity should be O(n^2) at most.  For the record, with GNU gcc the same experiment gives a ratio of 6.3 between the compile times of _io.c and _thread.c, which is less than O(n^2), it is roughly O(n^1.6).
> 
> I hope something can be done about this.
> 
> Marc
> 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: transcript-clang-2_0.txt
Url: http://webmail.iro.umontreal.ca/pipermail/gambit-list/attachments/20120501/980a5b28/attachment-0003.txt 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: transcript-clang-3_0.txt
Url: http://webmail.iro.umontreal.ca/pipermail/gambit-list/attachments/20120501/980a5b28/attachment-0004.txt 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: transcript-clang-3_1.txt
Url: http://webmail.iro.umontreal.ca/pipermail/gambit-list/attachments/20120501/980a5b28/attachment-0005.txt 
-------------- next part --------------
> 



More information about the Gambit-list mailing list