Asymptotic complexity of a compiler

Posted by Meinersbur on Stack Overflow See other posts from Stack Overflow or by Meinersbur
Published on 2010-04-20T21:00:45Z Indexed on 2010/04/20 21:03 UTC
Read the original article Hit count: 436

Filed under:

compiler

|

asymptotic-complexity

What is the maximal acceptable asymptotic runtime of a general-purpose compiler?

For clarification: The complexity of compilation process itself, not of the compiled program. Depending on the program size, for instance, the number of source code characters, statements, variables, procedures, basic blocks, intermediate language instructions, assembler instructions, or whatever.

This is highly depending on your point of view, so this is a community wiki.

See this from the view of someone who writes a compiler. Will the optimisation level -O4 ever be used for larger programs when one of its optimisations takes O(n^6)?

Related questions:

When is superoptimisation (exponential complexity or even incomputable) acceptable?
What is acceptable for JITs? Does it have to be linear?
What is the complexity of established compilers? GCC? VC? Intel? Java? C#? Turbo Pascal? LCC? LLVM? (Reference?)

If you do not know what asymptotic complexity is: How long are you willing to wait until the compiler compiled your project? (scripting languages excluded)

© Stack Overflow or respective owner

Related posts about compiler

IDEA modular problem (jsp)

as seen on Stack Overflow - Search for 'Stack Overflow'
I have project in with 2 separate modules(frontend and backend, first depends on second). When I'm trying to access backend code from frontend code, things going fine. Things turn for the worse when I do the same from jsp. This is stacktrase for simple accessign bean <jsp:useBean id="mybean"… >>> More
Help with a compiler warning: Initialization from distinct Objective-C type when types match

as seen on Stack Overflow - Search for 'Stack Overflow'
Here is the function where I get the compiler warning, I can't seem to figure out what is causing it. Any help is appreciated. -(void)displaySelector{ //warning on the following line: InstanceSelectorViewController *controller = [[InstanceSelectorViewController alloc] initWithCreator:self]; … >>> More
Sometimes Java web app hang

as seen on Stack Overflow - Search for 'Stack Overflow'
The web app occasionally get hang for about 30 seconds when user request a web page, the server's CPU and memory usage are ok, and the jstack shows: "http-9999-3" daemon prio=6 tid=0x552f3400 nid=0xf40 runnable [0x578fc000] java.lang.Thread.State: RUNNABLE at org.eclipse.jdt.internal.compiler… >>> More
Need help regarding one LALR(1) parsing.

as seen on Stack Overflow - Search for 'Stack Overflow'
I am trying to parse a context-free language, called Context Free Art. I have created its parser in Javascript using a YACC-like JS LALR(1) parser generator JSCC. Take the example of following CFA (Context Free Art) code. This code is a valid CFA. startshape A rule A { CIRCLE { s 1} } Notice the… >>> More
Port Compiler Options (8 replies)

as seen on .NET 247 - Search for '.NET 247'
I currently own a license for Crossworks for ARM and would like to compile the port using it. With the code for the CLR now available, is it possible to compile the port with any ARM compiler or are we still restricted to the Keil ARM gcc compilers? >>> More

Related posts about asymptotic-complexity

Asymptotic complexity of a compiler

as seen on Stack Overflow - Search for 'Stack Overflow'
What is the maximal acceptable asymptotic runtime of a general-purpose compiler? For clarification: The complexity of compilation process itself, not of the compiled program. Depending on the program size, for instance, the number of source code characters, statements, variables, procedures, basic… >>> More
Indicates the Big-Theta g(n) and prove it [closed]

as seen on Stack Overflow - Search for 'Stack Overflow'
Indicates the Big-Theta g(n) for the function below and prove it (n^2 + 1)^10 I don not know how to prove it. >>> More
Proving that a function f(n) belongs to a Big-Theta(g(n))

as seen on Stack Overflow - Search for 'Stack Overflow'
Its a exercise that ask to indicate the class Big-Theta(g(n)) the functions belongs to and to prove the assertion. In this case f(n) = (n^2+1)^10 By definition f(n) E Big-Theta(g(n)) <= c1*g(n) < f(n) < c2*g(n), where c1 and c2 are two constants. I know that for this specific f(n) the… >>> More
C++ Asymptotic Profiling

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a performance issue where I suspect one standard C library function is taking too long and causing my entire system (suite of processes) to basically "hiccup". Sure enough if I comment out the library function call, the hiccup goes away. This prompted me to investigate what standard methods… >>> More
Throwing cats out of windows

as seen on Stack Overflow - Search for 'Stack Overflow'
Imagine you're in a tall building with a cat. The cat can survive a fall out of a low story window, but will die if thrown from a high floor. How can you figure out the longest drop that the cat can survive, using the least number of attempts? Obviously, if you only have one cat, then you can only… >>> More