0
$\begingroup$

Can I design or implement a programming language (doesn't have to be general purpose) such that "suboptimal" code in the language will become optimal after compilation?

E.g., guaranteeing that

myvar = 5
for i in 1..10:
    myvar += i

will do

myvar = 60

instead because the second one is faster?

Or noticing that a developer wrote some code that achieves: sorting numbers, and "replacing" their bad code with a better but equivalent-state-afterwards sorting algorithm.

Maybe optimizing everything is impossible (why?), are there baby steps along the way that can be achieved, and how?

$\endgroup$
13
  • 6
    $\begingroup$ You might want to read up on the Halting Problem, Gödel's Incompleteness Theorems, and related topics. A lot depends on your definition of "optimal", but it will generally be posslbe to find a program which theoretically has a more optimal form, but where no general algorithm exists which can determine that optimal form. $\endgroup$
    – IMSoP
    Commented Apr 2 at 14:39
  • 5
    $\begingroup$ By "not necessarily general purpose" do you mean "not necessarily Turing-complete" ? $\endgroup$ Commented Apr 2 at 16:08
  • 2
    $\begingroup$ "optimal" is very hard to define on modern computers. Even in the case of pure algorithms, the tradeoff of memory space, memory usage, and cache usage and access patterns and instruction usage can have very complex effects (see stackoverflow.com/questions/11227809/… for an example of this) We have heuristics that can be good enough most of the time, but 'best' is a challenging research problem. $\endgroup$ Commented Apr 2 at 18:03
  • 3
    $\begingroup$ You migh tbe interested in the field of superoptimization: arxiv.org/pdf/1711.04422.pdf $\endgroup$ Commented Apr 2 at 18:05
  • 2
    $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$ Commented Apr 2 at 22:26

4 Answers 4

4
$\begingroup$

It is impossible in the general case

This is equivalent to the halting problem. As IMSoP states in their comment, it is always possible to find a program which may have a more optimized form, for which a general algorithm cannot find it. Even in your first example, the optimizer would have to figure out if the loop halts or not, which is equivalent to the halting problem. While in your case it is trivial, consider a while (true) loop with a break in the middle, or 5 mutually recursive functions. Indeed, if your theoretical optimizer was applied to the entire program, it would have to produce the result of your input program in finite time, which, again, is the halting problem.

$\endgroup$
3
  • 3
    $\begingroup$ yet existing compilers do perform optimizations like this. $\endgroup$
    – Barmar
    Commented Apr 2 at 20:08
  • $\begingroup$ @Barmar what i meant was the general case is impossible $\endgroup$
    – Seggan
    Commented Apr 3 at 2:27
  • $\begingroup$ It's not even clear what thay would mean -- can we define "optimal" rigorously? $\endgroup$
    – Barmar
    Commented Apr 3 at 16:11
1
$\begingroup$

They are already here, and you are already using it

Yes. They are already here. What you are asking for is essentially compiler optimization, which means that a compiler may transform your code into something semantically equivalent but more efficient.

What you described is called constant folding, which means that the compiler detects which variables are constant, and automatically compute them beforehand, as they are constant anyways. Almost every modern compiler is able to optimize your example program into myvar=60.

Moreover, modern compilers like GCC have over thousands of optimzations; basically, they do everything that you can imagine. Of course, as the other answers say, there is no programmatic way to decide if a program is "as optimized as possible", but modern compilers can do really well.

So, stop worrying and continue using your favorite programming language. If you are interested in those optimization algorithms, try any textbook on compilers: Appel's Modern Compiler Implementation in ML, or the classic Compilers: Principles, Techniques, and Tools (aka Dragon Book).

$\endgroup$
2
  • $\begingroup$ Huh, constant folding evaluates the effect of loops nowadays? $\endgroup$ Commented May 17 at 0:13
  • $\begingroup$ @KarlKnechtel the loop is clearly constant, so yes! $\endgroup$
    – xuq01
    Commented May 17 at 4:43
0
$\begingroup$

As others have commented optimization is generally processor specific and many compilers already implement a range of optimization strategies, some quite aggressive, for a a wide range of programming languages.

Perhaps what has not been expressed is that optimization is a compiler issue, not really a language issue - though some languages (or language features) can be more difficult to optimize.

Quite a few compiler optimizers rely on program analysis techniques like control-flow analysis, data-flow analysis and information-flow analysis to keep track of what a program is doing and how different parts of a function/procedure/program interact. Thus if you really wanted to pursue your stated goal you would probably want to make your programming language very amenable to such analysis techniques as a starting point.

Compilers also tend to separate optimization of the code model (an internal representation of the program) and target code generation - which can be very specific to the processor choice.

There can also be questions as to exactly what your optimization target is - typically target code execution time or target code size. For example loop-unrolling might improve execution time at the expense of larger code size (though current day processors have complex predictive branch execution and instruction cacheing which can make tight loops a better choice for execution time).

Multi-core and multi-thread processors also introduce interesting optimization choices - should your programming language incorporate features that express low-level parallelization of computations; or should it just provide simple partitioning of processing threads and leave it to the OS to schedule the individual threads to processor cores.

Code optimization is a very interesting subject with many complexities - so well worth a look at if you are starting out. Some of the basics can be achieved comparatively easily - and repeating the work already done by others provides interesting challenges as a learning exercise; but state of the art optimization is a much larger thing and is much more than designing a programming language.

$\endgroup$
0
$\begingroup$

Achieving a truly optimal solution is impossible. However, improving algorithms is often referred to as optimization.

Many people have wondered how macro optimizations can be applied, and a lot of research has been done; however, it would be hard to describe all of it in a single stack overflow answer.

Here are some things to look into especially: Interprocedural optimizations, loop optimizations and polyhedral (polytopal) optimization, function inlining and loop unrolling, function specialization, factoring, register allocation, constant folding, and instruction scheduling.

Optimizations often interplay with other optimizations. For your example, a compiler would likely unroll the loop, due to it being a small number of iterations, and then it would use constant folding and propagation combined with dead store elimination to turn it into the single assignment to MyVar.

You should probably learn to convert to and use SSA or an equivalent. Optimizations within a single block are easy in SSA. Function inlining of small functions can expose problems between functions to block optimizations. After inlining, factoring and reverse inlining can turn the code back into functions. However, we cannot simply inline all functions. See (What are the cons of inlining then optimizing and then reverse inlining?) Functions can also be specialized to call sites. An easy to implement type of specialization is partial evaluation. However, creating too many specializations can actually hurt performance.

Loop optimizations can significantly impact the overall algorithms used. Loops are often combined, broken apart, swapped, and so on in advanced compilers.

The Wikipedia page https://en.wikipedia.org/wiki/Optimizing_compiler has an overview, yet no information about how to implement, of most kinds of optimizations.

You said that you don't care if the programming language is general purpose. I have been working on a hobby programming language compiler in my free time (I am a high school student), and my solution is to design the language to make optimizations easy. The compiler inlines functions before optimization, and it reverse-inlines (is there a better name?) the code after optimizations to shrink the binary size and ease pressure on the instruction cache. To avoid loop optimizations and many forms of analysis, I have designed the language without loops or conditional statements. Array accesses can serve the purpose of conditionals unless output is conditionally done. Maps, filters, and folds can sometimes take the place of loops. If statements can later be inserted based on ternary statements and array accesses to simulate lazy evaluation (for efficiency). However, these constraints might make my language harder to use, and it certainly isn't turing complete, as looping is highly limited. I also chose to prohibit certain types of values from being passed to user-defined functions or some built-in functions. These restraints also make converting to SSA trivial.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .