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@iro.umontreal.ca Subject: Re: gambit-c Date: 24 January, 2012 10:38:28 AM EST To: Jeremy Huddleston jeremyhu@macports.org Cc: Jeremy Lavergne jeremy@lavergne.gotdns.org, Bradley Lucier lucier@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
Afficher les réponses par date