Object Intersection Captures on Interactive Apps to Drive a Crowd-sourced Replay-based Compiler Optimization

More and more of our computing needs rely on smart mobile devices. With active users now more than 5.2 billions [9], smartphones are the defining computing medium of our era. Nevertheless, mobile devices are severely limited, both in terms of processing power and battery life. Aggressive performance and energy optimizations are necessary for maintaining the user’s Quality of Experience, supporting novel capabilities, and providing reasonable levels of autonomy. What we get instead is poorly optimized software. Even the preeminent mobile platform, Android, relies on a compiler with just 18 distinct optimizations, an order of magnitude less than what traditional optimizing compilers offer [28]. As a result, immense amounts of performance and energy are wasted, impacting the smartphone user’s experience.

A major hurdle with extracting performance from mobile systems is evaluating optimization decisions. Whether it is about comparing competing implementations, tuning compiler heuristics, or applying iterative compilation [35], we need to determine whether each choice will be beneficial or not. We could evaluate all choices on the same representative mobile system, program, and input and then assume that good choices on that setup will always be beneficial. With a multitude of processor designs, system capabilities, software stacks, operating environments, and usage patterns [52], this is a hard assumption to make. In any case, creating any kind of program input that induces the same application behavior every time while causing no side-effects is a non-trivial endeavor for interactive applications.

Evaluating optimizations online, on the target system while the user is interacting with the application, could be a solution if it did not introduce a whole new set of problems. Making confident decisions is hard when the execution context is constantly changing. The operating environment, the application state, and the input will be different each time the application is executed. Their effect on latency can easily be more important than the effect of any optimization decision. A very large number of evaluations for each decision might be required before we are confident about its merit [22]. Many of these decisions can easily be suboptimal, severely affecting the user experience. Statistical approaches can limit this negative impact at the cost of an even slower process [14] but in a low-latency environment even rare slowdowns that are noticeable by the users are unacceptable [52]. In any case, when tested optimizations lead to erroneous results, something relatively common with optimizing compilers,¹ no online approach is acceptable.

To make it easy to choose the right mobile optimizations, we need a way to evaluate them that combines the benefits of offline and online approaches: adapted to each device and each application, driven by actual user input but at the same time fast, unrestricted, and invisible to the user. Our work introduces a novel way for achieving this by driving offline optimization with real input collected online. We build our approach around a lightweight capture and replay mechanism. While the user is interacting with the device, we identify important code regions and capture the state accessed by them. Later, we are able to restore the saved state and re-execute the code region in the exact same way it was originally executed. By replaying this execution under different optimization decisions but the same environment, we can directly compare optimizations using the time it took to execute the region.

Traditional capture mechanisms [11, 48, 55, 57] are not well suited to this task, especially in terms of introduced latency. Capture happens online and may affect the user, so it is critical to keep its overhead low. Our input capture mechanisms were developed with this aim. Our previous work, leverages the kernel Virtual Memory subsystem to automate and accelerate the capture. Using memory protection we monitor, with little overhead, the pages accessed while a targeted region runs. Future replays will only need to access these pages, a small fraction of an application’s memory. For those pages, we need their original state before they are modified by the application. Instead of copying them preemptively in user space [11], we use the Copy-on-Write (CoW) mechanism to do it on-demand in kernel space. When the region’s execution ends, we only have to store the original version of each accessed page in the phone’s storage. In this work we reduce the capture sizes even further, without requiring any additional overhead. We identify the heap objects that are reachable by the region’s code and intersect them with the accessed heap pages. Any unreachable data in those pages are not needed for a replay, so we erase them. We also introduce an alternative approach that favors a simpler and more lightweight runtime operation over capture sizes. All of our approaches have unnoticeable runtime overheads.

We fused capture and replay into a novel iterative compilation system that optimizes mobile applications for the actual environment and context they are being used in. We use genetic search to explore the space of compiler optimizations. We evaluate each optimization decision by applying it on the targeted code and replaying the captured execution with the new binary. We rank and select optimizations based on the time each replay took, apply genetic operations, and continue the process with another generation. We select the best performing decision over the whole search and we apply it on the online version of the application, the one the user interacts with.

All evaluation replays happen offline, when the phone is idle and charged. That gives us tighter control of the execution environment, reducing the measurement noise. Since all replays process the same state under the same environment, we are highly confident in the ranking of the evaluated optimizations. Since this is the same device the user interacts with and these inputs were produced during the normal operation of the application, we are highly confident that optimizations performing well during replay will perform well online, too.

To accelerate the offline evaluations, we have implemented a crowd-sourcing module to this system. It allows us to perform a collaborative search amongst different users, splitting between them the cost of evaluating candidate optimizations. By leveraging the accumulated evaluation data, participating users can now discover better genomes at a fraction of the time when compared to individual user searches. The more users that collaborate the better, enabling deeper searches with less effort from each user.

This framework is compiler-agnostic: Any compiler that can process Dalvik code [6] and generate code for Android devices can be plugged in. It can also be applied to different Operating Systems (OSes) and even for non-mobile environments. For Android, currently there is only one Dalvik toolchain, the default one, and it has a very limited optimization space with 18 distinct optimizations. We overcame this limitation by creating a new Android backend ² based on LLVM, which offers a far more expansive and interesting optimization space.

We used Android apps, both benchmarks and interactive ones, to evaluate our approach. With profiling and static bytecode analysis we identify code that can be accurately replayed and is worth optimizing. Our online captures run a handful of times per day and are imperceptible to the user. Our Page and Intersection approaches minimize stored data and require an average overhead of less than 15 ms, while our capture Everything approach requires less than 5 ms. Powered by capture and replay, our iterative compilation approach searches for good optimizations without exposing users to slow or erroneous binaries. We achieve on average 44% whole program speedups over Android and 35% over LLVM -O3, significantly improving the user experience. Our joint search delivers speedups within 5% of those achieved by individual searches, which is impressive considering that only a fraction of a user’s evaluation effort is now required. With 10 users, we were able to accelerate the search by 7\(\times\) for the user that had the biggest workload and by 12\(\times\) for the same user when compared to the average. Furthermore, we were able to get near optimal results for new users after as little as a few minutes of participation in the search.

The main contributions of this article are as follows:

This article is organized as follows. Section 2 describes the motivation behind our work, followed by Section 3 that describes our crowd-sourced iterative compilation framework. The experimental setup is on Section 4, followed by Section 5 that presents our results. Section 6 discusses related work, and Section 7 offers some concluding remarks.

Iterative compilation [35] is an optimization technique that can outperform a compiler’s default presets. It searches for different code transformations and their parameters, evaluates them for performance and at the end keeps the best performing binary. There are multiple techniques for searching: random, through genetic search, and statistical [49] or machine learned models [38]. Despite the significant performance benefits of iterative compilation, it has not been applied in a general way on mobile systems.

Offline Compiler Optimization. Regardless of how we optimize an application offline, we rely on some kind of a representative evaluation system (hardware and software) and a deterministic and representative input.³ By repeatedly executing an app with a deterministic input under different optimizations, we can directly compare them and choose the best one. With a representative system and inputs, we can be confident that our choice will work well online, too.

This simple methodology has proved hard to adapt to mobile systems. There is no representative system where we can optimize an app once for every other system. We need to optimize for each one individually. Even then, it is hard to create inputs without explicit support from the app. Mobile apps tend to have complex inputs, including user events, sensors, system state, and network data. Packaging all these for offline usage in a neat deterministic input that introduces no undesirable side-effects is a non-trivial problem. Making sure that they are representative is even harder. Expecting most mobile developers to put the effort required to support offline performance evaluation is unrealistic.

Online Optimization Is Risky. An alternative approach is to evaluate optimization decisions online on the program version the user interacts with. This removes the problem of identifying representative systems and inputs: They are representative by definition. While a workable solution in some cases, online optimization creates a new set of problems.

There is no hard guarantee that optimizations will not introduce errors. Figure 1 shows what happens when we apply random LLVM optimizations on FFT [50]. Only 60% of the cases lead to a correct binary. Fifteen percent crash or timeout the compiler, but this is manageable. The remaining 25% is not, as it leads to runtime errors: program crashes or timeouts or even a wrong output. Offline approaches simply reject such binaries with no other side-effect. But in an online setup, broken optimizations are visible to the user and affect the user experience. Even worse, silent errors that change the program behavior can result in corrupted data with long-term consequences for the user. This is an unacceptable risk.

Online Optimization Affects the User Experience. Broken optimizations are just one part of the wider problem of our search being visible to the user. Even for optimizations that lead to valid binaries, there is a good chance that the binary will be noticeably slower than normal. Figure 2 shows the performance of 50 correct FFT binaries generated by applying random sequences of LLVM optimizations. Performance is relative to that achieved by the Android compiler. All binary versions are slower than it, from 15% to as much as 8\(\times\) slower. Even if this is an initial exploration of the optimization space and later choices improve performance, the user will still have experienced unacceptable levels of slowdown. As we will show in Section 5, suboptimal binaries are common even in later stages of an otherwise profitable optimization process. Such behavior might lead to the user removing the app or disabling the optimizer.

Online Optimization Is Slow. Even if we managed to work around these limitations, a fundamental problem remains: We have no control over the context in which optimizations are being evaluated, especially input. We have to use whatever input happens to be fed to the program. This is not always a problem. But in the general case, we cannot directly compare optimizations that have been evaluated on different inputs that take different amounts of time to process. The only safe way to do it is to evaluate each optimization a large number of times. If all optimizations are evaluated on a similar sample of inputs, then direct comparisons of average execution times will be statistically meaningful. The problem is this can be a very lengthy process.

Figure 3 shows such an approach where we try to estimate the speedup of LLVM -O1 over -O0 for FFT with an increasing number of evaluations each with an input drawn from a uniform distribution. The evolution of a single speedup estimation is presented as a line. Areas are ranges of likely outcomes. While -O1 is almost 2\(\times\) better than -O0, our online estimation varies wildly, from almost 2\(\times\) slowdown to 8\(\times\) speedup. It is not until the 22nd evaluation when we decide that -O1 is better than -O0. It takes another 20 evaluations for the estimation to start stabilizing. This behavior is not an outlier. The 75% probability area shows a similar evolution: Twenty-five evaluations to decide that -01 is better and more than 1,000 evaluations to have less than 10% uncertainty in the speedup estimation. In contrast, there is very little variation with offline evaluation. Even a single measurement might be enough (though not statistically safe).

This scenario points toward a 100–1000\(\times\) increase in evaluation time compared to an offline approach to get a comparable level of confidence in our optimization decisions. This is very likely an underestimation. Other sources of experimental noise that we cannot control online, such as frequency scaling, thermal throttling, and resource contention affect our confidence. Skewed distributions of input processing times may reduce our confidence even further. Seen in the context of an iterative compilation system like the one in Section 5, this would translate into millions of evaluations for each optimized program. For FFT, this means tens of hours of repeated experiments. This is unfeasible. Mobile applications are typically active for only a few tens of minutes every day and are updated every few weeks. There is just not enough evaluation time for an online approach.

Beyond Online and Offline Optimization. What we ideally need is something that combines the best of both worlds. Both a system that can repeatedly use the same inputs to quickly search the optimization space without affecting the user experience and a system where developers do not need to manually build and maintain sets of representative inputs.

In this section, we describe how we aggressively optimize Android applications, with an offline optimization search driven by user-transparent input captures, taken online, requiring no developer effort. Section 3.1 describes how we detect hot regions of Android applications that are worth optimizing. Section 3.2 describes our page capture mechanism, followed by Section 3.3, which introduces our replay mechanism. Section 3.4 explains how we extract information from captures for optimization and automatic code correctness verification, followed by Section 3.5 that describes two additional capture mechanisms. In Section 3.6, we detail our LLVM backend implementation for Android that enables us to use LLVM to optimize Android code. It is followed by our genetic search engine, which explores the space of compiler optimization decisions in Section 3.7. Section 3.8 shows, how we integrate all these components to build an iterative compilation system that is transparent to the user and the developer but still manages to produce highly optimized program binaries. Finally, Section 3.9 presents a crowd-sourcing module built into our iterative compilation system that enables a deeper search in less time.

We have implemented a prototype system and evaluated our approach with a set of experiments on Google Pixel 4 devices running Android 10. Its processor unit is a Qualcomm SDM855 Snapdragon 855. It consists of eight Kryo 485 cores each configured with a different maximum clock frequency, from 1.78 GHz to 2.84 GHz. To reduce measurement noise during replays we keep all cores online and fix their frequency to the maximum. We only replay while the phone is fully charged, so the increased power consumption does not affect device autonomy. At any other time, the OS has full control of the cores’ operating states and frequencies.

Our compiler toolchain uses the Android 10 compiler to generate HGraph nodes, the LLVM backend from Section 3.6 to transform it into LLVM IR, and LLVM tools. LLVM was based on version 10. In particular, we use opt to optimize with a total of 197 passes and 710 parameters and flags, and llc to compile with 90 CPU-specific and 569 generic options.

The GA searches through this enormous space over 11 generations, the first randomly generated, the other 10 driven by genetic search. Each generation has 50 genomes. In the first one, we may try up to three times to replace each genome that leads to worse performance than both LLVM -O3 and Android. This biases the algorithm toward the more profitable areas of the transformation space. In the first generation, we also remove redundant passes to keep the genomes short. The probability that we mutate a genome and the mutation probability per gene are both 5%. At 100 identical binaries we halt the algorithm. Each tournament selection round considers 7 candidates with a 90% probability.

For our experiments we use Android applications that fall into three types, as listed in Table 1. The first is the Scimark benchmark suite. The second, named Art, contains benchmarks that have been used in the past by Google or third parties for the evaluation of the Android compiler. The third, named Interactive, contains nine regular Android applications. In our future work (see Section 7), we aim to test the proposed approach on a wider range of source codes, as there might be some artificiality on this application list.

We collect execution times for the final reported speedups outside the replay environment to guarantee that our results are not an artifact of the replay environment. We use the best performing binary discovered by the GA earlier using replay but we otherwise execute the application interactively. We disable any random initialization so that applications start in approximately the same state throughout the experiments and perform similar work. This makes it easier to estimate the speedup with any kind of certainty. For benchmark applications, this is straightforward as the inputs are fixed. For interactive ones, we try to follow the logic of each application to bring its state to a similar point each time, including manually interacting with the application.

For the execution time measurements of interactive applications deciding the start and the end point of the measurement is a balancing act. We want a fair and representative measurement that includes the code surrounding the hot region, i.e., code we have not optimized. At the same time we want all time measurements to capture similar behaviors. A longer execution is more likely to be affected by random high impact events, like GC, or by deviating system and user behavior. As a compromise, we measure a certain number of iterations of the conceptual main loop of the application. This number is different for each application and was selected empirically. For games this conceptual loop was one player round and it generally ranged from 0.7 s to 3 s. Even for a small number of apps, this was tedious process. It only reinforced our conviction that deterministic and repeatable evaluations without replaying require significant effort.

During search, each transformation is evaluated 10 times through replay, unless it is substantially slower than the baseline. For those cases, we perform only two evaluations. We perform outlier removal on the collected runtime measurements using median absolute deviation. Then, we determine the relative merit of two sets of transformations with a two-side Student’s t-test. Reported speedups are also based on 10 evaluations per transformation but without outlier removal. Finally, our plots include 95% confidence intervals where applicable.

For our joint GA search we used a fixed initial population of 200 to ensure that the same amount of points in space are visited on each run. The algorithm runs remotely and stores the evaluation data in a document store. We evaluated this architecture using 10 Google Pixel 4 devices. Each device represented a different user and each user had a different input. For the interactive apps we generated new inputs using manual interactions, and for the benchmarks we altered the region’s problem sizes. Once we captured all user inputs for each app, we programmed the phones to participate collaboratively, in a realistic way. Studies have shown that most users charge their phones overnight [25], when devices are also conveniently idle. Using sleep data [13], we created a user availability schedule, as shown by Figure 9. Users joined and exited the search at different times and had different availability. User7 had the least participation, as the device initially joined for a brief period, followed by a break, before joining again for a few more hours.

To evaluate our approach we performed six sets of experiments. The first shows our performance gains on the apps of Table 1 and demonstrates the potential of our approach. The second shows why we need an intelligent search of the optimization space and why we should not do it online. The third compares the online overheads of the proposed input capture mechanisms and the fourth one compares their storage requirements. Two of the approaches focus on minimizing the capture sizes, being applicable even on low-end devices, while an alternative one focuses exclusively on minimizing the runtime overhead. We demonstrate that all approaches have transparent online operation from the users. The last two experiments showcase the offline GA search acceleration when crowd-sourcing the findings from several users.

Iterative compilation is a well-established technique [35]. Early approaches, focused on embedded systems [1, 10], were exhaustively searching simple optimization spaces. Later approaches avoided that, through random [17] or genetic search [16], and other self-adapting techniques [2, 4, 12, 23, 27, 30, 38]. While all of them improve the search quality, either with better optimizations or faster search, they assume offline evaluations, fixed inputs, and a controlled environment.

Fursin et al. [26] exploits performance stability to evaluate transformations online. However, this approach is susceptible to slow or erroneous evaluations. Additionally, the variable input and the operating noise require more evaluations for sound comparisons, to the point that is impracticable. Our approach allows bulk-evaluations without affecting the user, while inherently tackling noise, by operating at idle times and imposing an execution environment.

Capture and replay frameworks are also well studied. Many approaches use instrumentation [33, 34, 48, 57] to reduce the captured data. By capturing fine-grained events like variable reads or writes, they minimize the stored state. This causes significant overheads, since each event has to be instrumented. Other approaches [31, 54] avoid this low-level instrumentation; however they either modify the Java API or require instrumentation with external tools to use their custom APIs. CRIU [55] is a Linux-based system that avoids the overheads and limitations of previous approaches. It fully captures the memory, which fits its intended usage, but it is a poor match for replaying hot regions.

The closest existing approach, CERE [11], aims to accelerate large scientific applications by breaking them down into shorter code regions. It captures those using a page-based mechanism. As latency is not an issue for CERE, overheads are typically over 20%, some reaching 250%. Part of this is due to not using CoW. When a page is first accessed, execution stops until a copy is made, regardless of whether the page will be modified or not. CoW keeps this process in kernel space and only copies the modified pages, making our online operation unnoticeable from the users.

This article introduced a crowd-sourced optimization approach for mobile devices, transparent to developers and users. Offline approaches rely on representative inputs that are hard to reconstruct, especially for interactive apps. Online approaches use real inputs, but expose users to slow or erroneous executions. On top of that, input variability makes the robust comparison of optimizations an extremely lengthy process.

Our approach tunes interactive apps using real inputs without disrupting the users. With infrequent captures, we store the input for targeted regions with little overhead. Later, we can replay each region on-demand, using the same context but different optimizations to compare them and discover the best ones, while the device is idle and charged.

We implemented a prototype system on Android, including a novel LLVM backend to increases the optimization space. We capture inputs once per optimization run. Our Page and Intersection mechanisms require less than 15-ms overhead on average per capture, while Everything requires less than 5 ms.

For this almost imperceptible effect on users, we achieve average speedups of 44% over Android and 35% over the LLVM -O3. With crowd-sourcing we achieve just 5% less of that at a fraction of the evaluation time. With 10 users, the search was accelerated by 7\(\times\) for the user with the highest workload, while another user was able to extract near optimal results only within a handful of minutes.

This work has produced some exciting results but there are more untapped opportunities for optimization. In the future we aim to evaluate our approach on more code sources. One problem that might arise, is that some of the computationally-intensive codes of the more complicated apps are re-written in native code (i.e., JNI). While our approach does not currently consider JNI, it can help avoiding it altogether, as it brings fine-tuning (automated or not) to the Java/Kotlin languages directly, reducing development time and increasing productivity.

To address input variation that concerns the same user, we can optimize for multiple captures. When such input changes happen between different days, we can simply perform periodic captures and optimize the code overnight. When those changes happen during the same day, we can follow two approaches. The first is to consider multiple captures and optimize for the average case. The second is to generate multiple binaries and employ multi-versioning. For the latter, we can maintain a set of pre-optimized binaries for the most frequently encountered inputs, and at runtime use a lightweight input-classification algorithm to predict and use the code version that will yield the best performance.

The findings of our joint search suggest that the input was significant for many cases when it came to code optimization. Despite being able to do a joint search and specialize for individual users when needed, we noticed that a few deviated a lot from others. We are considering detecting those scenarios and do non-shared searches (at least to some extent) to address this. We will also extend our GA search to cluster over time different users according to the genomes that are most effective for them. This will encourage deeper exploration in areas that might be beneficial for particular user inputs.