CODEWITHSUNDEEP
ccompilation
rktavi
rktavi

Reputation: 782

Is it possible to achieve infinite compilation time in C (i.e. without templates)?

So, the title. It is generally known that it is possible to write C++ program, which would require infinite time to compile (in theory). But is it possible to write such program in plain C? Or is there a way to slow down compilation time to at least several minutes with a small program?

Upvotes: 0

Views: 375

Answers (3)

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

Experimentally, if you ask a recent GCC or Clang/LLVM to compile with optimizations some C code containing a single (or very few) C function(s) with many thousands of statements, the compilation time is growing a lot.

By experience, compilation with gcc -O2 of a single function with many thousand C statements requires a time proportional to the square of the number of statements (more exactly number of Gimple statements after preprocessing & gimplification).

The intuition explaining that is that the algorithms for register allocation, instruction scheduling, and middle-end optimizations are often worse than O(n) ; naive non-optimizing C compilers like tinycc, nwcc, 8cc etc don't have such time behavior (but generate code really worse than gcc -O2...)

BTW, you could play (on Linux) with my manydl.c program (which generates some more or less random C code, then compile it and dlopen it, to show that you can dlopen many hundred thousands of shared objects). Read its source code, it will illustrate my point.

More seriously, I did (in the past) experiment the same issue in old versions of MELT, which generates C++ code suitable for extension of GCC. I had to split in several routines some huge sequential initialization code.

You might compile with gcc -ftime-report -O2 such a huge function to understand more precisely in which optimization passes is the compiler spending its time.

At last, if you want a small source code, you can cheat by asking it to #include "some-huge-file.c" but I believe that does not count.

Upvotes: 1

jxh
jxh

Reputation: 70472

Include recursively

#include __FILE__

Most compilers will probably bail out early, but theoretically, this would cause infinite compilation.

Include (or compile directly, or link against) a device instead of a file

#include "/dev/tty"

On systems that support it, this causes the compiler to wait for input. Similarly, you could use a named pipe.

Find a bug in the compiler

It is possible the compiler has a logic error that will cause it to loop forever.

Upvotes: 1

JS1
JS1

Reputation: 4767

Here is the example you asked for, with exponentially increasing macros.

#define FOO  i++  // Substitute any statement here for i++
#define FOO1 FOO ; FOO
#define FOO2 FOO1 ; FOO1
#define FOO3 FOO2 ; FOO2
#define FOO4 FOO3 ; FOO3
#define FOO5 FOO4 ; FOO4
#define FOO6 FOO5 ; FOO5
// Keep going however much you want
...
#define FOO40 FOO39 ; FOO39

volatile int i;

int main(void)
{
    FOO40;  // This expands to 2^40 statements.
}

I used FOO18 for a timing test to see what would happen. I tested both the preprocessor time and the compilation time separately:

(Preprocessor phase)
time gcc -E foo.c -o foo.i
1.7 seconds

(Compilation phase)
time gcc foo.i -o foo
21 seconds

Out of curiosity I kept trying bigger and bigger values. Unfortunately, at some point the compiler ran out of memory (the preprocessor was fine). I got this error:

cc1: out of memory allocating 16842751 bytes after a total of 403505152 bytes

At FOO16 with -O2, I was able to get 2:23 compilation time without running out of memory. So if you want to get an even longer compilation time, first find out many many statements you can put into a single function without running out of memory (FOO16 for me). Then make several functions, like this:

int main(void)
{
    FOO16;
}

void bar1(void)
{
    FOO16;
}

void bar2(void)
{
    FOO16;
}

// etc...

Upvotes: 1

Related Questions