In 2022 at the conference on Programming Language Design and Implementation (PLDI 2022), Prime Video published a paper entitled Differential cost analysis with simultaneous potentials and anti-potentials. It showed how we have introduced a technique to compute a bound for changes in cost due to code modifications (where the word cost captures the generic notion of a resource, such as run-time or memory usage).
Efficiency is important for Prime Video because not only do developers need to provide code that runs fast with very tight bounds on start-up time, but they also need to pay attention to memory usage and other resources such as disk usage or number of threads. Indeed, the Prime Video application needs to run and provide a uniform user experience (UX) on a range of devices, some of them with very limited memory and processing power.
One way to address this concern is to use efficient architectures and programming languages. Another approach is more fine-grained and consists in making sure that the code developed is efficient in the first instance, and that code changes do not introduce performance regressions.
The Differential cost analysis with simultaneous potentials and anti-potentials paper, developed as part of an internship project on the Prime Video Automated Reasoning team with Ðorđe Žikelić, shows how it is possible to simultaneously compute a polynomial function both for the maximum or minimum amount of resources required to run two program versions. These polynomial functions are respectively called the potential and the anti-potential functions of a program. By taking the difference between the potential function of the modified program and the anti-potential function of the original program, it is therefore possible to compute a threshold that bounds the difference in cost between two versions.
By working on a representation of the program based on transition systems and by employing the results of Handelman’s theorem, we show in our paper how the computation of the difference is computed efficiently and reduced to a set of linear constraints that can be solved by existing off-the-shelf linear solvers.
In our experiments, we employed benchmarks in C from the literature, and we have been able to compute tight bounds in 14 out of 19 examples. Based on these results and on the efficiency of the approach, our plan for the future is to introduce a cost analyzer bot, enriching the set of techniques already available through the BugBear code review bot.
For more information about this paper, see the Calculating the differential cost of code changes article on the Amazon Science website.