https://gcc.gnu.org/bugzilla/show_bug.cgi?id=121439
Bug ID: 121439
Summary: [IOCCC] а case with high time complexity and high RAM
usage
Product: gcc
Version: 14.2.1
Status: UNCONFIRMED
Keywords: compile-time-hog, memory-hog
Severity: normal
Priority: P3
Component: c
Assignee: unassigned at gcc dot gnu.org
Reporter: jpegqs at gmail dot com
Target Milestone: ---
Created attachment 62075
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=62075&action=edit
prog.c
An entry from the latest IOCCC 28 generates C code that can break compilers:
https://github.com/ioccc-src/winner/blob/master/2024/kurdyukov4/prog.c
Preparations:
$ cc -O2 prog.c -o prog
$ head -c1m /dev/urandom > random.bin
# alt method: dd if=/dev/urandom bs=1M count=1 of=random.bin
$ ./prog < random.bin > output.c
The generated code (output.c) will be about 4MB in size.
And now the actual test for the compiler:
$ time -p cc -O0 output.c -o test
This completes, but takes about an hour.
$ time -p cc -O2 output.c -o test
And this hangs for several hours after which the OS kills the process with OOM.
If there is enough RAM, then the memory consumption increases to 34.5 GB, and
the process hangs indefinitely, even 10 hours were not enough to complete.
At the same time, Clang and the EDG-based compiler cope with compilation,
without optimizations it even does it in a few minutes.
You could work around the problem and disable some high time complexity
optimizations after some threshold to limit compilation time to a reasonable
value and limit memory consumption.
Affected GCC versions: 11.5.0, 13.3.0, 14.2.1
Although this case is completely artificial - but other compilers handle it
better.
Also the IOCCC judges report:
https://www.ioccc.org/2024/kurdyukov4/index.html#large-input-size-issues
