Georges Aaron Randrianaina

Djamel Eddine Khelladi

Olivier Zendra

Mathieu Acher
email: mathieu.acher@irisa.fr

Towards Incremental Build of Software Configurations

Keywords: Highly configurable system, Build system, Incremental build

Building software is a crucial task to compile, test, and deploy software systems while continuously ensuring quality. As software is more and more configurable, building multiple configurations is a pressing need, yet, costly and challenging to instrument. The common practice is to independently build (a.k.a., clean build) a software for a subset of configurations. While incremental build has been considered for software evolution and relatively small modifications of the source code, it has surprisingly not been considered for software configurations. In this vision paper, we formulate the hypothesis that incremental build can reduce the cost of exploring the configuration space of software systems. We detail how we apply incremental build for two real-world application scenarios and conduct a preliminary evaluation on two case studies, namely x264 and Linux Kernel. For x264, we found that one can incrementally build configurations in an order such that overall build time is reduced. Nevertheless, we could not find any optimal order with the Linux Kernel, due to a high distance between random configurations. Therefore, we show it is possible to control the process of generating configurations: we could reuse commonality and gain up to 66% of build time compared to only clean builds.

CCS CONCEPTS

• Software and its engineering → Software configuration management and version control systems.

INTRODUCTION

Building software is a crucial activity in every non-trivial software project. Different artifacts are assembled, compiled, tested, and eventually deployed, hopefully with success. The rise of continuous integration (CI) has amplified this trend with build services integrated into major code platforms (e.g., Github, GitLab). Their interest is to continuously ensure the quality of a project, both in terms of functional and non-functional properties (e.g., security, execution time). Techniques such as distributed builds and parallelization of build tasks have been developed to speed-up builds. Although widely adopted, building software is increasingly complex and expensive in terms of time and other resources [START_REF] Beller | Oops, My Tests Broke the Build: An Explorative Analysis of Travis CI with GitHub[END_REF][START_REF] Edge | The costs of continuous integration[END_REF][START_REF] Hilton | Trade-offs in continuous integration: assurance, security, and flexibility[END_REF][START_REF] Lebeuf | Understanding, debugging, and optimizing distributed software builds: A design study[END_REF].

Software configurations add further complexity. Different variants of the artefacts can be assembled due to e.g., conditional compilation directives #ifdef in the source code. Different external libraries can be compiled and integrated as well. How the build is realized can also change e.g., with different compiler flags. Developers and maintainers want to ensure that, throughout evolution, all or at least a subset of software configurations build well. It is no surprise that many organizations build several software configurations of their projects as part of their CI. For instance, initiatives like KernelCI or 0-day build thousands of default or random Linux configurations each day [START_REF]KernelCI[END_REF]. Another example is JHipster, a popular Web generator that builds dozens of configurations at each commit, involving different technologies (Docker, Maven, grunt, etc) [START_REF] Halin | Test them all, is it worth it? Assessing configuration sampling on the JHipster Web development stack[END_REF].

The common practice is to independently build a subset of configurations i.e., in a fresh environment. In this paper we propose and explore an approach, called incremental build of configurations: instead of starting from scratch and cleaning the build artefacts, a configuration can be (incrementally) built from an existing and already completed configuration build. While incremental build has been considered for software evolution with small code edits, it has surprisingly not been considered for software configurations. The idea is to reuse artefacts of previous configurations builds and thus save some computations, hence resources, including time. Behind this idea, the real question is to quantify how much and where it can gain or lose compared to a more conventional build, in addition of already existing techniques such as distributed build. Moreover, this approach has risks: an incremental build might not work or might be incorrect compared to a conventional build, for example the build system might forget to recompile some necessary artefacts. Another unknown remains about the strategy to schedule the incremental build of configurations. Given a set of configurations, numerous possible orderings exist, possibly with different effects on correctness and overall build cost (e.g., CPU time). Does incremental build pay off whatever the ordering and the "distance" among configurations? Is it worth finding an optimal ordering? Our goal in this vision paper is to bridge the worlds of software build and configurable software. In particular, to push for an in-depth exploration of the above hypothesis and address, to the best of our knowledge, new open unaddressed questions: (RQ1, efficiency) Does incremental build outperform clean build? (RQ2, correctness) Is the result of incremental build the same as a clean build? (RQ3, optimality) Is there an order of configurations that brings an optimal (overall) incremental build time?

To investigate these questions, we detail how we apply incremental build for two real-world application scenarios (1) ordering over a fixed set of configurations; (2) generation of configurations in such a way the incremental build is efficient. We conduct a preliminary evaluation on two case studies, namely x264 and Linux Kernel. For x264, we found that an optimal ordering of random software configurations exists and reduces overall build time. A caveat is that the correctness of the incremental build is sometimes not ensured for certain pairs of x264 configurations and thus poses some challenges. In contrast to x264, we could not find any optimal order with the Linux Kernel due to a high distance between configurations. Nonetheless, we show it is possible to control the process of generating configurations: we could reuse commonality and gain up to 66% of build time compared to only clean builds. In addition, we ensure that the generated configurations of Linux change as much as possible.

WHY INCREMENTAL BUILD?

This section introduces our vision, before presenting two real-world scenarios of incremental build of configurations

Incremental build of configurations

When testing a configurable system, developers often build a set of configurations. The common workflow is to build each of them from scratch. A build typically has a cost, such as CPU time, energy consumption, billed when done in a paid cloud service, etc. In the rest of the paper, we take as an example the cost function of CPU time. Figure 1a illustrates three configurations 𝑐 1 , 𝑐 2 and 𝑐 3 of the same configurable software system, and their build from scratch times (respectively 10, 15 and 20 minutes).

The black node can be seen as an initial state, or a clean directory to launch the build task from. The edge from the initial state to the configuration represents the build task and the time it takes. Building these three configurations, to check if they compile or for testing, takes 45 minutes as shown on Figure 1a 1 .

However, configurations of the same software system can share similarities: build rules, source files and even object files. Our hypothesis is that these similarities could lead to sharing: the files produced during the build of a configuration can be reused by other configurations built after. This is the main point of incremental build: avoiding redundant builds and processing only the required build rules to be efficient. Figure 1b shows a possible order to build the three configurations presented above: first build 𝑐 1 which takes 10 minutes; then compile 𝑐 2 and 𝑐 3 without going back to the initial state (e.g. without cleaning the directory) but reusing the compiled files from 𝑐 1 's build. This reuse reduces build times for 𝑐 2 and 𝑐 3 from 15 and 20 min to 10 min. In the end, three configurations were built in 30 minutes instead of 45.

Therefore, an incremental build is intended to be efficient compared to a classic clean build. This efficiency could be measured by CPU load or energy consumed during the build.

However, incremental build may not always be recommended, due to correctness issues for some systems. Indeed, reusing files built for other configurations could introduce improper files into the configuration being built. Hence, the result of the incremental build could be different compared to a clean build for the same configuration. Hence, the correctness of incremental build of configurations must be ensured. To do so, the produced output of a clean build and an incremental build of the same configuration should verify an equivalence, according to a correctness criterion. Such a criterion can be two binaries having the same size or same number of symbols and the same name for each one of these symbols. It also can be a bit by bit comparison or a binary diff program which compares the binaries control flow graph. 1 These 3 builds can be built in parallel (e.g., using distributed resources).

[Scenario 1 (S1)] Improving overall build of a fixed set of configurations

When testing highly configurable systems, one usually has a set of configurations to build. This set contains either default standard configurations that represent the frequent configurations or a mix of random configurations. Instead of being built from scratch they could be built incrementally as in Figure 1b, benefiting from their similarities. Nevertheless, not all configurations share similarities. Some can be different up to the point that the build system cannot reuse any artefact from a previous build.

To detect beforehand if two configurations have some files in common that their builds could reuse, knowledge on the system is necessary. This knowledge is used to order the (incremental) build of the configurations in a way such that each incremental build performed uses as much materials from previous builds as possible. The previous build artefacts could be either the build directory or a dedicated cache. However, the goal remains the same: maximising the reuse of materials produced by previous builds and improving overall build time compared to only clean builds. With our set of configurations {𝑐 1 , 𝑐 2 , 𝑐 3 }, we can consider the minimum possible build time is 30 minutes (Figure 1b). This best build time is obtained because 𝑐 1 is built first, then 𝑐 2 and 𝑐 3 both benefiting from some 𝑐 1 artefacts. Knowledge of the system helps computing a heuristic to automatically find this order of builds, maximise artefacts reuse, and improve total build time. Starting with configuration 𝑐 2 then 𝑐 1 and 𝑐 3 , the impact on total build time might be different.

One of the main challenges in this scenario is how to construct this knowledge (e.g., a heuristic) so as to find an optimal ordering of incremental builds for a given set of configurations.

[Scenario 2 (S2)] Beyond building fixed configurations: exploring a larger space

In addition to building and improving total build time for a fixed set of configurations, we propose to generate configurations to explore and test a larger configuration space. Indeed, one of the best way to test a configurable software is to build variants of it 2 . The more configurable a software system is, the larger its configuration space, hence the more configurations have to be tested. We want to have high diversity of configurations in order to cover a configuration space as large as possible. In this scenario, for all picked configurations, we try to generate variant configurations "around them" in order to improve also what we call the local diversity in the configuration space. This way, given a starting configuration, close configurations can be generated such that the incremental build of the variants always outperform clean builds. We present this scenario in Figure 1c. We first build configurations such as 𝑐 1 , 𝑐 2 , 𝑐 3 . Then, from e.g., 𝑐 2 we derive other configurations 𝑐 21 , 𝑐 22 ,. . . Then, we incrementally build these configurations from 𝑐 2 . To accelerate even more this configuration space exploration, we can execute the incremental build of each generated configurations in parallel.

This technique is thus not only about mutating a configuration or generating new ones from a seed. We must ensure that the incremental build of the generated configurations from the original outperform clean builds and remains correct. For instance, we can control that the build of each generated configuration in Figure 1c takes 2 minutes. Instead of 3 clean builds in 45 minutes (Figure 1a), we can build 9 configurations in 42 minutes. Our main goal is to have a proper strategy to mutate the configurations in order to get correct incremental builds that outperform clean builds and can diversify enough to explore the configuration space.

PRELIMINARY RESULTS

We present in this section our preliminary results on experimenting incremental build of configurations over x264 (scenario S1) and Linux (scenarios S1 and S2).

[S1] Ordering configurations of x264

x264 is a software system for video encoding written in C. It has about 115.243 lines of code and 50 possible compile-time options (or features). We built two batches with 20 random generated configurations each. In this way, we perform 2 * 20 clean builds and 2 * (20 * 19) = 760 incremental builds, i.e., 760 pairs of configurations (𝑐1, 𝑐2) where c1 is built with a clean build, and c2 incrementally build after c1. Thus, a total of 800 builds. To generate the random configurations, we use the random product generator in the Fea-tureIDE framework [START_REF] Meinicke | Mastering software variability with FeatureIDE[END_REF].

For the first batch, 7 out of 20 cases of incremental build were slower than clean build. For these cases, we recommend a simple clean build. We also had one case only where the binary produced by incremental build was not consistent with the binary supposed to be produced by a clean build: it did not have the same binary size. Nevertheless, with a combination of correct and most efficient pairs of incremental builds, we could still deduce an optimal order. Total CPU time using only clean builds was 747,99 seconds, whereas total CPU time relying on incremental builds in the optimal order plus clean build (for incorrect incremental builds) was 747,26 seconds, representing a non-significant gain of 0.10% of build time.

For the second batch, for each of these 20 configurations, we found an incremental build that outperforms its clean build. We further checked their correctness w.r.t. the criteria on the binaries and found that incremental build was always correct. After that, based on the most efficient pairs of incremental builds, i.e., the fastest observed incremental build, we could deduce an optimal order. The total CPU time using only clean builds was 754.92 seconds, whereas the total time of the incremental build in the optimal order was 666.12 seconds, representing a gain of 11.6% of build time.

It is thus possible to order a set of configurations such that incremental build combined with clean builds gives a better performance than only clean builds.

[S1] Ordering configurations of Linux

In order to extend our results to a bigger software system, we replicated it on Linux. Linux is a kernel of operating system written in C. Linux is considered as the most complex configurable software system with over 15.000 features and about 28 millions of lines of code. We generated two batches of 20 configurations each and conducted the same experiment as x264. The configurations were generated using the Linux Kernel command line utility randconfig, which generates random configurations. Though the correctness holds, we could not find any pair of configurations in which incremental build was faster than clean build. After investigation, we found out that there was too much difference between two randomly generated configurations, with up to a thousand options added or removed. In addition, the strategies of the build system (Make) can also fail to reuse files and do redundant builds (see, e.g., [START_REF] Zhang | ABC: Accelerated Building of C/C++ Projects[END_REF]).

It is thus not straightforward to find an optimal incremental build ordering for a given set of random configurations due to high difference between them.

[S2] Local diversity of Linux configurations

As ordering a fixed set of configurations seems to be difficult to find with Linux, we decided for another approach. Instead of picking all the configurations randomly, we extract knowledge from the source code to generate new configurations.

The Linux Kernel build system is composed of multiple makefiles at each directory level. Obviously, these makefiles contain build rules which compile and link files together. By enabling or disabling an option, the modification impacts the addition or not of build rules, hence, the compilation of some files and their dependency.

To determine before compilation which files will be compiled if an option is enabled (or disabled), we built a dependency graph (DG) between options according to their implementation at the file level. If two options are implemented in the same file, we link them with an edge in the DG. With this representation, we could over approximate the amount of files to recompile when an option is modified from the configuration. Then, we sort options according to the amount of files they would recompile if they were enabled or disabled. With this information, we can deduce which options can be progressively added to increase diversity by small increments, instead of building from scratch every configuration.

We picked a random configuration and built it from scratch. Then we generated 9 configurations from it with the technique described before using the DG. The number of different options between each generated configuration and the original varies from 7 to 183. Total CPU time using only clean builds was 4.864,26 seconds, whereas total CPU time relying on one clean build of the initial configuration then incremental builds of the others was 1.648,87 seconds, representing a gain of approximately 66% of build time.

Thus, the generation of configurations to be built incrementally can be guided with knowledge from the system in order to outperform clean build.

RELATED WORK

Build systems. Many works exist on (incremental) build systems [START_REF]A fast, scalable, multi-language and extensible build system[END_REF][START_REF] Cao | Forecasting the duration of incremental build jobs[END_REF][START_REF] Erdweg | A sound and optimal incremental build system with dynamic dependencies[END_REF][START_REF] Stuart | Make -a program for maintaining computer programs[END_REF][START_REF] Hammer | Incremental computation with names[END_REF][START_REF] Konat | Scalable incremental building with dynamic task dependencies[END_REF][START_REF] Maudoux | Correct, efficient, and tailored: The future of build systems[END_REF][START_REF] Mitchell | Shake before building[END_REF][START_REF] Schwanke | Smarter Recompilation[END_REF][START_REF] Walter | Smart Recompilation[END_REF] but they focus on code changes through the evolution of software (e.g. commits) rather than configurations. Cserep et al. [START_REF] Cserép | Integration of Incremental Build Systems Into Software Comprehension Tools[END_REF] introduce how to detect only the necessary files to build with incremental parsing of the codebase. Maudoux et al. [START_REF] Maudoux | Bringing incremental builds to continuous integration[END_REF] show that incremental build could help speed up builds of continuous integration (CI), and Gallaba et al. [START_REF] Gallaba | Accelerating Continuous Integration by Caching Environments and Inferring Dependencies[END_REF] that caching can accelerate CI. An open issue is to adapt these techniques over distant software configurations that may have very different impacts on the files to build. Several empirical studies on build systems have been performed (e.g., [START_REF] Hilton | Trade-offs in continuous integration: assurance, security, and flexibility[END_REF][START_REF] Hilton | Usage, costs, and benefits of continuous integration in open-source projects[END_REF][START_REF] Lawall | JMake: Dependable Compilation for Kernel Janitors[END_REF][START_REF] Lebeuf | Understanding, debugging, and optimizing distributed software builds: A design study[END_REF][START_REF] Maudoux | Correct, efficient, and tailored: The future of build systems[END_REF][START_REF] Maudoux | Lessons and Pitfalls in Building Firefox with Tup[END_REF][START_REF] Zhao | The impact of continuous integration on other software development practices: a large-scale empirical study[END_REF]). Beller et al. [START_REF] Beller | Oops, My Tests Broke the Build: An Explorative Analysis of Travis CI with GitHub[END_REF] performed an analysis of builds with Travis CI on top of GitHub. About 10% of builds show different behaviour when different environments are used. In our case, we are considering different software configurations rather than environments.

Software product line (SPL) and variability. The SPL community develops numerous methods and techniques to manage a family of variants (or products). Configurations are used to build or execute variants and are subject to intensive research. For instance, building variants is a necessary step before deriving performance prediction models [START_REF] Pereira | Learning Software Configuration Spaces: A Systematic Literature Review[END_REF][START_REF] Guo | Variability-aware performance prediction: A statistical learning approach[END_REF][START_REF] Jamshidi | Transfer learning for performance modeling of configurable systems: an exploratory analysis[END_REF][START_REF] Jamshidi | Learning to sample: exploiting similarities across environments to learn performance models for configurable systems[END_REF][START_REF] Lesoil | The interplay of compile-time and run-time options for performance prediction[END_REF]. Formal methods and program analysis can identify some classes of configuration defects [START_REF] Classen | Featured Transition Systems: Foundations for Verifying Variability-Intensive Systems and Their Application to LTL Model Checking[END_REF][START_REF] Thüm | A Classification and Survey of Analysis Strategies for Software Product Lines[END_REF], leading to variability-aware testing approaches (e.g., [12, 21-24, 29, 35, 36, 38, 42]). Static analysis and notably type-checking has been used to look for bugs in configurable software and can scale to very large code bases such as the Linux Kernel [START_REF] Kastner | Type-checking software product lines-a formal approach[END_REF][START_REF] Kenner | Type-Chef: Toward Type Checking #Ifdef Variability in C[END_REF][START_REF] Alexander Von Rhein | Variability-Aware Static Analysis at Scale: An Empirical Study[END_REF]. Though variability-aware analysis is relevant in many engineering contexts, our interest differs and consists in studying the practice of concretely building a sample of (possibly distant and diverse) configurations with an unexplored approachincremental build. Sampling configurations is subject to intensive research [START_REF] Pereira | Sampling effect on performance prediction of configurable systems: A case study[END_REF][START_REF] Jamshidi | Learning to sample: exploiting similarities across environments to learn performance models for configurable systems[END_REF][START_REF] Souto | Balancing soundness and efficiency for practical testing of configurable systems[END_REF][START_REF] Thüm | A Classification and Survey of Analysis Strategies for Software Product Lines[END_REF]: incremental build brings new challenges (see also next section). There are several empirical studies about the build of SPLs and configurable systems. For instance, Halin et al. [START_REF] Halin | Test them all, is it worth it? Assessing configuration sampling on the JHipster Web development stack[END_REF] report on the endeavour to build all possible configurations of the JHipster configurable software system. We are unaware of studies that consider or apply incremental build of configurations.

FUTURE WORK PLANS

A priori knowledge for ordering and generating configurations. As shown in Section 3, the brute force strategy of picking random configurations may not work in all cases. It is effective for x264. However, it does not bring benefits for Linux because of high differences among its random configurations. We plan to develop techniques to infer information about the system either from the source code analysis or directly from the build system, so as to deduce similarities among possible configurations and determine an a priori order to incrementally build them. In addition to configuration ordering, we plan to use inferred knowledge from the system to generate valid configurations while providing high diversity.

Correctness of build systems. The challenge is to obtain a binary produced from incremental build that is consistent with a binary obtained from a clean build. Section 3.1 reports on issues with some pairs of configurations. We aim to test existing build systems (e.g., Make, Maven, Bazel, Pluto, etc.) correctness while performing incremental build over configurations instead of code additions such as commits. The correction of build systems is a notoriously difficult problem and configurations add further complexity.

Multi-objective problem and tradeoffs. There are several criteria: (1) the cost of building; (2) the correctness of the build; (3) the diversity of the targeted configurations. We fall into a multi-objective optimisation problem. A conservative approach that would slightly modify one option at a time when incrementally building has good chances of reducing the cost while being correct. Yet the diversity of configurations and their distances would be weak, which has limited interest for testing diverse configurations or learning over the configuration space [START_REF] Pereira | Learning Software Configuration Spaces: A Systematic Literature Review[END_REF]. Otherwise, a more aggressive approach is to pick random configurations with high diversity. Yet, as shown in Section 3.2, incremental build can be as costly as a traditional build. A research direction is to apply multi-objective algorithms or find a tradeoff suited for the specific needs of the software project.

CONCLUSION

We presented a novel problem and a vision that consists in bridging incremental build with software configurations. Results of preliminary experiments over x264 and Linux Kernel show that incremental build can reduce the cost of building (e.g., a gain of 66% over Linux when controlling the generation of configurations). Yet there are several challenges ahead related to the correctness of build systems, the diversity of configurations, and the ordering of the incremental builds. Many software projects are concerned with the problem of building multiple configurations into their CI; we encourage the software engineering community to more widely explore the potential of incremental build.

  Local diversity with incremental build

Figure 1 :

 1 Figure 1: Incremental build scenarios

"The Linux Kernel does not have a test suite.[. . . ] The best thing you can ever do for us is: you just build the Kernel and tell us if you have a problem. That is our QA cycle. ". Greg Kroah-Hartman, at FOSDEM 2010.