Skip to main content

Questions tagged [optimization]

Use this tag for questions about efficient compilation or execution of a programming language, including in a virtual machine, or language features that facilitate more efficient code generation or execution for interpreters

Filter by
Sorted by
Tagged with
29 votes
4 answers
5k views

What are the ways compilers recognize complex patterns?

This answer is an example of a compiler recognizing that a complex expression is equivalent to a single operation: ...
CPlus's user avatar
  • 8,813
0 votes
0 answers
165 views

Do any notable languages today *not* seek to define away non-trivial optimization problems?

Many real-world problems have a prioritized set of requirements, some of which might be satisfied in multiple different ways. For example, one might have a function ...
supercat's user avatar
  • 1,904
0 votes
0 answers
118 views

How can transpilers benefit from compiler optimizations which are compatible with semantics, if other "optimizations" in the target language aren't?

Consider the following function: ...
supercat's user avatar
  • 1,904
0 votes
4 answers
476 views

How to design a programming language that can simplify/optimize algorithms?

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 ...
minseong's user avatar
  • 125
5 votes
1 answer
350 views

How does link-time function inlining work?

I am familiar with traditional linking concepts (static and dynamic linking, relocation, PIE) and with traditional compiler optimizations (such as static expression evaluation, loop unrolling and ...
Borisav Živanović's user avatar
3 votes
6 answers
499 views

Are there languages or compilers having optimizations to deallocate variables early?

In a scope that defines two variables a and b, the code firstly does things only on a. Then <...
user23013's user avatar
  • 2,608
9 votes
0 answers
240 views

How can a compiler optimise persistent data structures to use mutable data structures "under the hood"?

Consider for a motivating example a copy-on-write array, which implements a persistent (i.e. immutable) array data type. As an optimisation at runtime, a reference counter can be used to avoid the ...
kaya3's user avatar
  • 20k
1 vote
0 answers
198 views

Global value numbering implementation

I wrote a global value numbering algorithm according to this paper and I would like to verify if certain behaviour of the algorithm is correct. My implementation as is performs the following code ...
chrysante's user avatar
  • 778
0 votes
1 answer
196 views

How to minimize total size of static data?

I am implementing a WASM backend and I hope to optimize the size. I have collected a series of static data. After erasing the type, it can be simply considered as ...
Aster's user avatar
  • 3,238
3 votes
1 answer
239 views

How to assign unique names to variables within a function?

I want to promote all variables within the function to the top level of the function, make it more cache-friendly and reduce size bloat caused by alignment fill. In other words, it will roughly ...
Aster's user avatar
  • 3,238
2 votes
1 answer
379 views

Pros and cons of treating endless loops as "anything can happen" UB, versus allowing limited reordering

Many programming languages, including C89, specify that the behavior of a program in terms of sequentially executed steps, whose behavior is in turn defined in terms of the program's state when the ...
supercat's user avatar
  • 1,904
4 votes
1 answer
328 views

Determining the most optimized data type for the platform with type inference

For my programming language, I have built an engine that goes after the parser and before the compiler. This engine analyzes, validates, and simplifies the AST. During the analasys, it determines as ...
Hg0428's user avatar
  • 173
6 votes
1 answer
359 views

Optimization algorithm using conditional invariants

I am looking for an optimization algorithm that would make use of invariants in regions of code. For example if (n == 0) f(n); should be changed to ...
chrysante's user avatar
  • 778
15 votes
3 answers
834 views

Towards a better default listlike datastructure for functional languages

In most functional languages I know of, linked lists are the default datastructure of choice for many operations. The benefits are clear - they're clearly encoded with ADTs, and can be utilised easily ...
blueberry's user avatar
  • 2,587
6 votes
2 answers
211 views

How to ensure coherent choices of representatives in an e-graph?

E-graphs are a neat intermediate representation for program transformations and optimisations, which group program terms into equivalence classes (e-classes). An optimising compiler can then select ...
kaya3's user avatar
  • 20k
10 votes
1 answer
1k views

What are the tradeoffs between using sea of nodes, CFG of basic blocks, and egraphs for compiler optimizations?

I've heard of "sea of nodes" intermediate representations mostly in the context of just-in-time compilation (JVM, V8, Graal) whereas intermediate representations such as LLVM IR are used in ...
Troy Sargent's user avatar
39 votes
6 answers
5k views

How to ensure that an optimising compiler will terminate?

An optimising compiler typically applies some set of rewrites to some intermediate representation of the program, replacing terms with other terms which are supposed to be equivalent but more ...
kaya3's user avatar
  • 20k
4 votes
1 answer
232 views

Can analysis of periodic loop behaviour be generalised to unstructured control flow?

The basic form of a loop is as follows: loopvars := init body: loopvars := f(loopvars) done := term(loopvars) br done, end, body end: Suppose we've recognised ...
Moonchild's user avatar
  • 897
5 votes
2 answers
319 views

Why would external iteration require lots of code inlining relative to internal iteration?

In Graydon Hoare's blogpost The Rust I Wanted Had No Future, they state that: Iteration used to be by stack / non-escaping coroutines, which we also called "interior" iteration, as opposed ...
JennyJams's user avatar
  • 667
7 votes
2 answers
750 views

Empirically, what are the implementation-complexity and performance implications of "unboxed" primitives?

I'm designing a Python-like language: bytecode-compiled, brace-free syntax, reference semantics for variables. Among many differences from Python, I want to support a limited form of static typing. I ...
Karl Knechtel's user avatar
23 votes
4 answers
4k views

Pros and cons of "anything-can-happen" UB versus allowing particular deviations from sequential program execution

Some language specifications invite compilers to make certain assumptions, and behave in completely arbitrary fashion if such functions are violated, even if the code in question would have ...
supercat's user avatar
  • 1,904
8 votes
2 answers
401 views

How to optimize non-tail recursion?

Tail recursion, where a function calls itself as the last step, is straightforward to optimize as to prevent unbounded stack growth: tail call optimization applies. However, this doesn't apply to ...
Bbrk24's user avatar
  • 9,137
5 votes
0 answers
225 views

Why has there been little recent work on GPU compiler phase optimization?

While GPU compiler phase optimization has been shown to improve performance significantly (e.g. https://link.springer.com/chapter/10.1007/978-3-319-75178-8_35), there has been very little follow-up ...
Amrit Baveja's user avatar
8 votes
3 answers
611 views

Tail-recursive detection and conversion

Motivation I have implemented the tail recursion optimization for my language, where a return statement calls itself by goto ...
Aster's user avatar
  • 3,238
-4 votes
1 answer
257 views

What are the disadvantages of including foreach loops? [duplicate]

Yes, FOR loops. Those great things. There are good for shortening code. But there may be downsides I'm not aware of. I'm referring to Python style FOR loops. So, what are the disadvantages of ...
Starship's user avatar
  • 1,336
6 votes
1 answer
192 views

Automatic copy to move promotion

I'm designing a language that has move semantics similar to C++. To make it more efficient and to prevent the need for explicit moves I want to automatically promote copies to moves if the compiler ...
chrysante's user avatar
  • 778
17 votes
7 answers
3k views

What are the pitfalls of using an existing IR/compiler infrastructure like LLVM?

Using something like LLVM when designing a compiler has a lot of advantages, since tons of work can be saved by using an existing optimizer and code generation for a variety of platforms. Even large, ...
Rydwolf Programs's user avatar
20 votes
1 answer
700 views

What is the relationship between STG and RVSDG?

GHC is an optimizing Haskell compiler. Since Haskell is lazy and mutation is rare, control flow and data flow are often very closely aligned. Therefore, it is often most useful to think about ...
Alexis King's user avatar
  • 9,156
4 votes
3 answers
944 views

What are some common ways to optimise an interpreter?

Optimization is getting things to work faster with less resources. What are some ways to optimize an interpreter?
Starship's user avatar
  • 1,336
3 votes
3 answers
208 views

What are the downsides, if any, of using implicit function purity in an impure language?

An idea I had for one of my languages recently was this: function purity makes it easier to do certain optimizations. However, the language I'm designing is an impure imperative language that has an ...
Seggan's user avatar
  • 2,753
3 votes
2 answers
246 views

What are the disadvantages of automatically inlining all functions?

Function inlining is when the function called is directly substituted in the calling code. This avoids the overhead of setting up the call stack, managing any relevant pointers that need to be tracked ...
FireTheLost's user avatar
  • 1,613
4 votes
2 answers
189 views

How to estimate which parts of a program will be slow?

Many modern compilers are sophisticated enough to determine that some functions or expressions can be computed lazily, memoised, or parallelised. For example, pure functions can be computed at any ...
kaya3's user avatar
  • 20k
10 votes
1 answer
274 views

Syntax options for providing branch prediction information

Branch prediction information can affect performance. Languages to provide programmers with ways to provide branch prediction hints to improve performance of code. One option is C++ ...
CPlus's user avatar
  • 8,813
5 votes
2 answers
972 views

Why was C implemented with a register preservation convention that seems to be far less efficient than its predecessor's?

In original implementations of the B language, the caller was responsible for saving and restoring any registers it cares about before calling a function. But in the C language, the called function is ...
Ray Butterworth's user avatar
6 votes
2 answers
386 views

Are there any disadvangates to requiring sincos() type functions?

sincos() is just a way to compute sin() and cos() at once, possibly at improved performance ...
CPlus's user avatar
  • 8,813
7 votes
2 answers
420 views

How to implement dynamic scoping?

How to implement dynamic scoping? Dynamic scoping is useful for forms of dependency injection, error handling and alternatives to thread local storage. Some examples of dynamic scoping include React's ...
Ms. Molly Stewart-Gallus's user avatar
5 votes
1 answer
188 views

Which functions should a compiler cache outputs for?

Because a bare function object might not have constant time complexity, and because the function object might be called with the same argument repeatedly, I thought it might be good to cache its ...
Dannyu NDos's user avatar
4 votes
1 answer
226 views

Implementing a number to string semantics efficiently in a C-style language?

In C our options for converting numbers to strings and adding them to a string are limited to: Write your own function. sprintf() to a buffer. Either way, one ...
CPlus's user avatar
  • 8,813
13 votes
2 answers
665 views

Which calling convention should my compiler use?

The LLVM-IR Reference Manual's section on Calling Conventions lists as many as 15 supported calling conventions. These vary in ways including whether they support tail call optimization, how many and ...
Rydwolf Programs's user avatar
15 votes
7 answers
832 views

How can a programming language support vectorization portably?

C and C++ have no vector types or operations but many compilers offer their own non-portable extensions such as __attribute__((__ext_vector_type__())). The issue is ...
CPlus's user avatar
  • 8,813