<p>Is there any research on quantifying the cost of a procedure, with regard to compiler optimization?</p>
<p>I.e. assigning some kind of cost in terms of CPU time or memory to a procedure, either so the programmer can decide wether the operation, forexample a precomputation, is worth doing, or to help a compiler make optimizing decisions.</p>
<p>I would assume any non-trivial precise costing would be undecidable due to <a href="https://en.wikipedia.org/wiki/Rice%27s_theorem" rel="nofollow noreferrer">Rice's Theorem</a>, but there could be good heuristics - a more systematic and formal form of the analysis programmers makes themselves.</p>

CC BY-SA 4.0
2022-09-22T10:29:44.290Z
There is a lot of work on this. For example when deciding whether to inline a procedure call, the compiler uses some heuristic to evaluate if it is worth it. It is very important in cryptography, b/c you need to make your code free from data-dependent timing.
Martin Berger
CC BY-SA 4.0
2022-09-22T10:30:58.500Z
Then there is all the work on Resource Aware ML, that came from Jan Hoffmann's PhD work, see e.g. https://www.cs.cmu.edu/~janh/publications/
Martin Berger
CC BY-SA 4.0
2022-09-22T10:32:34.853Z
There is also work on verified performance, starting, I think, with the paper *Verifying Program Performance* from 1976: https://dl.acm.org/doi/pdf/10.1145/321978.321987 by Ben Wegbreit.
Martin Berger
CC BY-SA 4.0
2022-09-22T10:33:51.267Z
Getting *precise* performance bounds is hard, because modern processors are complex beasts that are based on many prediction engines (e.g. branch prediction) that are typically not well-modelled by compilers.
Martin Berger
<reference-request><optimization><compilers>
Quantifying the cost of procedures
Ari Fordsham
# Quantifying the cost of procedures

(Asked by: username_0 on 2022-09-21)

Is there any research on quantifying the cost of a procedure, with regard to compiler optimization?

I.e. assigning some kind of cost in terms of CPU time or memory to a procedure, either so the programmer can decide wether the operation, forexample a precomputation, is worth doing, or to help a compiler make optimizing decisions.

I would assume any non-trivial precise costing would be undecidable due to [Rice's Theorem](https://en.wikipedia.org/wiki/Rice%27s_theorem), but there could be good heuristics - a more systematic and formal form of the analysis programmers makes themselves.

**Tags:** reference-request, optimization, compilers

> **Comments:**
> **username_1**: There is a lot of work on this. For example when deciding whether to inline a procedure call, the compiler uses some heuristic to evaluate if it is worth it. It is very important in cryptography, b/c you need to make your code free from data-dependent timing.  
> **username_1**: Then there is all the work on Resource Aware ML, that came from Jan Hoffmann's PhD work, see e.g. https://www.cs.cmu.edu/~janh/publications/  
> **username_1**: There is also work on verified performance, starting, I think, with the paper *Verifying Program Performance* from 1976: https://dl.acm.org/doi/pdf/10.1145/321978.321987 by Ben Wegbreit.  
> **username_1**: Getting *precise* performance bounds is hard, because modern processors are complex beasts that are based on many prediction engines (e.g. branch prediction) that are typically not well-modelled by compilers.  

---

## 0 answers

