<p>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 time on any thread, and side-effect-free functions which don't need to share data can be computed in separate threads at the same time.</p>
<p>However, these optimisations all have some overhead: lazy evaluation usually requires some kind of branching on whether or not a result has been computed yet, memoisation typically requires lookups in a hashtable (and the same branching), and starting threads isn't generally cheap. So they should only be applied when the computation itself is sufficiently slow.</p>
<p>What analyses or heuristics can a compiler use to estimate the runtime cost of a function or expression, relative to the overhead costs of these optimisations?</p>
<p><sup>(There is also no benefit to lazily evaluating an expression which will definitely be evaluated, no benefit to memoising a function that will be called at most once, or so on; but determining those things is out of scope for this question.)</sup></p>
<hr />
<p>From the other direction, some expressions may be eligible for <a href="https://en.wikipedia.org/wiki/Constant_folding" rel="nofollow noreferrer">constant folding</a> but would not be worth computing at compile-time; in an extreme case, a combinatorial search program might take months to complete, but its observable behaviour would be equivalent to printing a constant. In these cases we want to know that it's sufficiently <em>fast</em> before attempting to optimise it, but the analysis is the same (i.e. we want to estimate the running time).</p>

<optimization><static-analysis><memoization>
How to estimate which parts of a program will be slow?
CC BY-SA 4.0
2023-06-13T23:05:27.120Z
PGO (profile-guided optimization) may be an answer to the title, but the body seems to ask for something else. Also "runtime cost of an expression" is uncomputable in general, so any implementation of such an estimate will be a mere heuristic at best, and whenever you see a nontrivial while loop, you're screwed.
Bubbler
CC BY-SA 4.0
2023-06-13T23:07:39.980Z
@Bubbler The title can never convey the entirety of a question; I chose the title to summarise the question and make it more likely to be found by others looking for similar information. I'm aware that the answer is going to involve heuristics and estimates, and I wrote that in the question. (I'm not looking for a solution to the halting problem.)
kaya3
CC BY-SA 4.0
2023-06-14T13:33:41.867Z
Two downvotes ─ I've been getting a lot of those in the past few days. Is there something unclear about the question, or have people just started downvoting questions they aren't personally interested in?
kaya3
<p>A combination of abstract interpretation, aggressive inlining and partial specialisation can provide a lot of additional insight into what have a potential to be a bottleneck. E.g., if you have a loop body that you know can have high upper bounds (from abstract interpretation), everything called from inside that loop body is a potential target for optimisations - including attempts to specialise the calls to different kinds of the argument values that may repeatedly happen during the loop. Think of cases like <code>for( auto i in ... ) { slowfunction(i % 10, ...); }</code> - where you may want to create 10 specialisations of slowfunction, each with a constant value of the first argument.</p>
<p>The key in such optimisations is to be able to backtrack - e.g., if in the example above specialising <code>slowfunction</code> does not result in a faster code you just backtrack and leave it as it is.</p>
<p>Some rudimentary form of it exist in even the mainstream compilers - if some computation was moved out of a loop body, it can later be re-materialised back if compiler can see that the register pressure introduced by hoisting it is more costly than just repeating the computation every loop iteration.</p>
<p>So, to summarise - if you can backtrack, you can do a lot more than with even the smartest heuristics, you just try optimisations, see if they are beneficial, and backtrack if they are not.</p>

CC BY-SA 4.0
2023-06-14T09:32:53.017Z
2023-06-14T09:32:53.017Z
SK-logic
<p>Well, there's a whole CS research and engineering field devoted to almost exactly this question: <a href="https://en.wikipedia.org/wiki/Worst-case_execution_time" rel="nofollow noreferrer">Worst-Case Execution Time (WCET) analysis</a>. The Wikipedia article provides links to several survey and particular methods papers, as well as competitions and some tools. Though in practice WCET analysis works only for real-time embedded systems (Airbus is famous for employing it) where programs get written in a very restricted (subset of a) language. While compiler don't really use it, relying on heuristics instead.</p>

CC BY-SA 4.0
2023-06-14T17:10:36.177Z
2023-06-14T17:10:36.177Z
Alex Chichigin
# How to estimate which parts of a program will be slow?
Posted by: username_0 on 2023-06-13
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 time on any thread, and side-effect-free functions which don't need to share data can be computed in separate threads at the same time.

However, these optimisations all have some overhead: lazy evaluation usually requires some kind of branching on whether or not a result has been computed yet, memoisation typically requires lookups in a hashtable (and the same branching), and starting threads isn't generally cheap. So they should only be applied when the computation itself is sufficiently slow.

What analyses or heuristics can a compiler use to estimate the runtime cost of a function or expression, relative to the overhead costs of these optimisations?

(There is also no benefit to lazily evaluating an expression which will definitely be evaluated, no benefit to memoising a function that will be called at most once, or so on; but determining those things is out of scope for this question.)

---

From the other direction, some expressions may be eligible for [constant folding](https://en.wikipedia.org/wiki/Constant_folding) but would not be worth computing at compile-time; in an extreme case, a combinatorial search program might take months to complete, but its observable behaviour would be equivalent to printing a constant. In these cases we want to know that it's sufficiently *fast* before attempting to optimise it, but the analysis is the same (i.e. we want to estimate the running time).
**Tags:** optimization static-analysis memoization
> **Comments:**
> **username_1**: PGO (profile-guided optimization) may be an answer to the title, but the body seems to ask for something else. Also "runtime cost of an expression" is uncomputable in general, so any implementation of such an estimate will be a mere heuristic at best, and whenever you see a nontrivial while loop, you're screwed.  
> **username_0**: @Bubbler The title can never convey the entirety of a question; I chose the title to summarise the question and make it more likely to be found by others looking for similar information. I'm aware that the answer is going to involve heuristics and estimates, and I wrote that in the question. (I'm not looking for a solution to the halting problem.)  
> **username_0**: Two downvotes ─ I've been getting a lot of those in the past few days. Is there something unclear about the question, or have people just started downvoting questions they aren't personally interested in?  
---
## 2 answers
### Answer by username_2 on 2023-06-14. Score: 4
A combination of abstract interpretation, aggressive inlining and partial specialisation can provide a lot of additional insight into what have a potential to be a bottleneck. E.g., if you have a loop body that you know can have high upper bounds (from abstract interpretation), everything called from inside that loop body is a potential target for optimisations - including attempts to specialise the calls to different kinds of the argument values that may repeatedly happen during the loop. Think of cases like `for( auto i in ... ) { slowfunction(i % 10, ...); }` - where you may want to create 10 specialisations of slowfunction, each with a constant value of the first argument.

The key in such optimisations is to be able to backtrack - e.g., if in the example above specialising `slowfunction` does not result in a faster code you just backtrack and leave it as it is.

Some rudimentary form of it exist in even the mainstream compilers - if some computation was moved out of a loop body, it can later be re-materialised back if compiler can see that the register pressure introduced by hoisting it is more costly than just repeating the computation every loop iteration.

So, to summarise - if you can backtrack, you can do a lot more than with even the smartest heuristics, you just try optimisations, see if they are beneficial, and backtrack if they are not.
---
### Answer by username_3 on 2023-06-14. Score: 2
Well, there's a whole CS research and engineering field devoted to almost exactly this question: [Worst-Case Execution Time (WCET) analysis](https://en.wikipedia.org/wiki/Worst-case_execution_time). The Wikipedia article provides links to several survey and particular methods papers, as well as competitions and some tools. Though in practice WCET analysis works only for real-time embedded systems (Airbus is famous for employing it) where programs get written in a very restricted (subset of a) language. While compiler don't really use it, relying on heuristics instead.
---
