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, but there could be good heuristics - a more systematic and formal form of the analysis programmers makes themselves.

  • $\begingroup$ 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. $\endgroup$ Commented Sep 22, 2022 at 10:29
  • $\begingroup$ Then there is all the work on Resource Aware ML, that came from Jan Hoffmann's PhD work, see e.g. cs.cmu.edu/~janh/publications $\endgroup$ Commented Sep 22, 2022 at 10:30
  • $\begingroup$ There is also work on verified performance, starting, I think, with the paper Verifying Program Performance from 1976: dl.acm.org/doi/pdf/10.1145/321978.321987 by Ben Wegbreit. $\endgroup$ Commented Sep 22, 2022 at 10:32
  • $\begingroup$ 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. $\endgroup$ Commented Sep 22, 2022 at 10:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.