Georges Aaron Randrianaina
email: georges-aaron.randrianaina@irisa.fr

Xhevahire Tërnava
email: xhevahire.ternava@irisa.fr

Djamel Eddine Khelladi
email: djamel-eddine.khelladi@irisa.fr

Mathieu Acher
email: mathieu.acher@irisa.fr

On the Benefits and Limits of Incremental Build of Software Configurations: An Exploratory Study

Keywords: Software and its engineering → Software product lines, Software configuration management, Incremental compilers, Configurable software systems, build systems, configuration build

Software projects use build systems to automate the compilation, testing, and continuous deployment of their software products. As software becomes increasingly configurable, the build of multiple configurations is a pressing need, but expensive and challenging to implement. The current state of practice is to build independently (a.k.a., clean build) a software for a subset of configurations. While incremental build has been studied for software evolution and relatively small changes of the source code, it has surprisingly not been considered for software configurations. In this exploratory study, we examine the benefits and limits of building software configurations incrementally, rather than always building them cleanly. By using five real-life configurable systems as subjects, we explore whether incremental build works, outperforms a sequence of clean builds, is correct w.r.t. clean build, and can be used to find an optimal ordering for building configurations. Our results show that incremental build is feasible in 100% of the times in four subjects and in 78% of the times in one subject. In average, 88.5% of the configurations could be built faster with incremental build while also finding several alternatives faster incremental builds. However, only 60% of faster incremental builds are correct. Still, when considering those correct incremental builds with clean builds, we could always find an optimal order that is faster than just a collection of clean builds with a gain up to 11.76%.

INTRODUCTION

Building software is a crucial activity for developers and maintainers of projects. Various artifacts are assembled, compiled, tested, and then deployed, presumably successfully. The emergence of continuous integration (CI) has accelerated this trend with the integration of build services into major code platforms (e.g., GitHub, GitLab). The goal is to continuously ensure some quality assurance of software products, whether in terms of functionality or non-functional properties (e.g., security, execution time). Although widely adopted, building software is increasingly complex and expensive in terms of time and 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 are adding further complexity to the problem of building software. Different variants of the artifacts can be assembled e.g., due to conditional compilation directives #ifdef-s in the source code. Different external libraries can be compiled and integrated as well. The way the build is realized can also change e.g., with the use of different compiler flags. Developers and maintainers of a project want to ensure that, throughout the evolution, all or at least a subset of software configurations build well. As most of today's software is configurable in order to fit constraints, functional and performance requirements of users, it is not surprising to observe that many organizations build different software configurations of their projects. For instance, initiatives like KernelCI or 0-day build thousands of default or random Linux configurations each day [START_REF] Kernelci | KernelCI[END_REF][START_REF] Martin | Transfer Learning Across Variants and Versions: The Case of Linux Kernel Size[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 current state of practice is to build independently a subset of configurations i.e., in a fresh and clean environment. This paper proposes and explores an approach, called incremental build of configurations. The idea is simple: instead of starting from scratch and cleaning the build's artifacts, a configuration can be built from an existing and already completed configuration build (incrementally). The hope is to reuse artifacts of previous configurations' build and thus save some computations, resources, and time. This is just a hunch; the real question is to quantify how much and when you can gain (or lose) compared to a more conventional build. Moreover, the approach is not without risk: an incremental build may not work or may be incorrect compared to a conventional, clean build. The build system may forget to recompile some necessary artifacts, for example. In fact, it is a hypothesis that needs inquiry. Another unknown is about the strategy to order the incremental build of configurations. Given a configuration to build, with which other configurations should the incremental build be carried out? Should incremental build be used all times? There are numerous possible orderings, possibly with different effects on the correctness and overall build time. Our goal is to explore these hypotheses and address, to the best of our knowledge, new open questions: (𝑹𝑸 1 ) Is incremental build simply possible in real-world configurable systems? (𝑹𝑸 2 ) Does incremental build outperform clean build? (𝑹𝑸 3 ) Is the result of incremental build the same as that of clean build? (𝑹𝑸 4 ) Is there an order of configurations that brings an optimal (overall) incremental build time?

Novelty. Surprisingly, while incremental build is supported and has actually been designed for relatively small edits, it has not been explored for software configurations. A possible reason is that the usual compilation workflow and build process targets small, local modifications (e.g., modification of one source file). Building several configurations involve large modifications that span numerous source files, thus challenging build systems. There are numerous works in the software product line community about variabilityaware analysis [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] Hwan | Reducing combinatorics in testing product lines[END_REF][START_REF] Hwan | SPLat: lightweight dynamic analysis for reducing combinatorics in testing configurable systems[END_REF][START_REF] Viet Nguyen | Exploring variability-aware execution for testing plugin-based web applications[END_REF][START_REF] Shi | Integration Testing of Software Product Lines Using Compositional Symbolic Execution[END_REF][START_REF] Alexander Von Rhein | Variability-aware static analysis at scale: An empirical study[END_REF]. The idea is to process the configurable code base, exploiting similarities among individual variants with the goal of reducing analysis effort. Incremental build shares the same principle and aims to leverage similarities among configurations' build. However, we are unaware of works that consider the actual build of configurations in an incremental way. To the best of our knowledge, investigating the benefits and limits of incremental build at the configuration level has not yet been considered.

Significance of the problem. The promise is to reduce the cost of building software, a stressing topic when you think about the environmental and financial costs that companies and public organizations should have to bear [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]. Society relies on software, but building software has an enormous cost: we aim to mitigate this trend. Beyond Linux and JHipster examples already mentioned, numerous real-world software projects are configurable and actually build several configurations. The build is a necessary step to check the correctness of the code, to dynamically test the system, to observe non-functional properties (e.g., execution time, security), to synthesize performance models [START_REF] Erdweg | A sound and optimal incremental build system with dynamic dependencies[END_REF][START_REF] Guo | Variability-aware performance prediction: A statistical learning approach[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] Nair | Finding faster configurations using FLASH[END_REF][START_REF] Sarkar | Cost-efficient sampling for performance prediction of configurable systems (T)[END_REF][START_REF] Schwanke | Smarter recompilation[END_REF][START_REF] Siegmund | Performance-influence models for highly configurable systems[END_REF][START_REF] Walter | Smart recompilation[END_REF]. Owing to the cost and the frequencies of software builds, any improvement is more than welcome for developers and organizations.

Practical scenarios. Incremental build is mainly intended to be part of a continuous integration. With each commit, rather than building configurations separately, an ordering strategy can be used to reduce build time or to build much more configurations given a budget. Once the (optimal) order of the configurations is established, the benefits can be obtained several times during the evolution of a software project. Of course, the ordering can be updated in case of major modifications. Out of an order, the distribution of incremental build of software configurations on different machines is also possible but out of the scope of the paper.

Methodology. This paper designs and performs the first study about incremental build of configurations: the purpose is to understand the challenges and practices in a real-world setting and to generate hypotheses about other, similar contexts [START_REF] Stol | The ABC of software engineering research[END_REF]. Our contribution is limited to the study of incremental build on existing and real projects. On the other hand, this study opens new perspectives and brings insights that can be used to design new build systems or scheduling heuristics. Our data set covers five subject systems, namely x264, sqlite, xz, curl, and xterm covering different domains, respectively, video encoding, database, compression utility, network communication, and terminal emulator. Though all written in C language, their build process highly differs (more details in the paper). We explore whether incremental build works (i.e., produces something without errors), whether an incremental strategy outperforms a sequence of clean builds, whether the result is correct w.r.t. clean build, and what an optimal ordering of configurations brings in terms of build time.

Significance of the results. Our results showed that incremental build is feasible in 100% of the times in four subjects and in 78% of the times in the xz subject. On average, 88.5% of the configurations could be built faster with incremental build while also finding several faster alternative incremental builds. However, only 60% of faster incremental build are correct. Still, when considering those correct incremental builds with clean builds, we could always find an optimal order that is faster than just a collection of clean builds with a gain up to 11.76%. Overall, our results suggest that incremental build of configurations can be beneficial. Owing to the importance and increasing cost of build systems in the field of software engineering, it is worth addressing the open issues for fully realizing the potential of incremental build.

The main contributions of this paper are:

(1) the idea of incremental build of configurations;

(2) the design of an exploratory study to investigate the potential benefits and pitfalls of incremental build; (3) a quantitative and qualitative analysis of empirical results; (4) a discussion on the impacts of our works on developers, build systems designers, and researchers in configurable system or continuous integration; (5) a link to our publicly available data set for reproducibility.

The rest of the paper is structured as follows. Section 2 gives some background about build systems and introduces incremental build. Section 3 describes the design of our experiments. Section 4 reports on empirical results and answers research questions. Section 5 discusses the impacts of our study and results. Section 6 reports on threats to validity. Section 7 reviews related work. Section 8 formulates research directions after a short summary.

BACKGROUND AND MOTIVATION

This section gives a background on the tools and the process that are commonly used to build a C-based, configurable software system, which are the subjects of this study. Then, we motivate our work with an example taken from the xterm terminal emulator subject.

Autotools

Installing a software package requires having its dependencies (e.g., utilities and libraries) available in the current environment. In addition, the package needs also to know which are the available features of the current operating system in order to be configured and built accordingly. With the high diversity of operating systems, their features and even local hacks by the users, it is impossible to manage the configuration script for every possible environment. For this reason, the GNU Project introduced the Autotools utility to automatically generate configuration and build scripts to fit to the machine it is built upon.

The presented C-based projects in this paper, as subjects, mainly use the GNU Autotools with the utilities of Autoconf [START_REF]Autoconf[END_REF] and Automake [START_REF]Automake[END_REF], as shown in Figure 1. Specifically, Autoconf takes as input a file configure.ac in which the developer has specified the packages to check and to determine which ones can be used or are missing. Then it generates a configure file, which contains a script to check the available packages and features of the current machine and a script to configure the project given the user's configuration. On the other hand, while writing a software with a large amount of files, it is complicated to keep track and specify how to build each one of them. Therefore, the developers of C-based projects mainly use a Makefile to describe how to build the project. But, the Makefile support is different, depending on the computer environment. This is why developers rely on the Automake utility. Specifically, a developer first specifies the structure of the current project and how to build it. Then, Automake generates a Makefile.in that has the previous build rules with compatibility on the current machine's environment. Once the configure and Makefile.in are generated, the user needs to run only the configure script in order to configure the project. The configure script can use different options from the user, which are well-known as compile-time options, and generates the Makefile accordingly. After this configuration step, the users need to run the make command in order to build the given project. This entire process is also sketched in Figure 1.

Usually, Autotools is installed on the developer's computer, but not on the user's environment. Thus, the configure, Makefile.am, and Makefile.in often are shipped within the compressed folder that contains the project's sources. In this case, the user simply needs to execute the configure && make && make install command in order to configure, build, and install that given project.

Make and incremental build

Make is a well-known build system [START_REF] Stuart | Make -a program for maintaining computer programs[END_REF]. Make reads Makefiles which contain the build rules to build the current software package. A Makefile can be either generated by using Autotools or written by the developers themselves. To show how Make works, Figure 2 gives an illustrative example of a Makefile for a toy project (its source files are not included here). It is a borrowed example from [START_REF] Mokhov | Build systems à la carte[END_REF], with the build rules presented in Listing 1.

In the lines 1-2 of Listing 1 is defined the rule util.o which depends on the header file util.h and util.c. In its line 2 is described how to build it by using a cc compiler: the flag -c and the From this Makefile, Make can build a dependency graph like the one shown in Figure 2 (left). During the compilation for the first time, as nothing has been compiled yet, Make will build each of the described rules in the Makefile in order to build the final product. Building a project from scratch and from its clean basis is well-known as a clean build.

But, if a developer modifies even a file, then Make will rebuild only the rules that depend on this file. To build only the necessary rules, Make checks their timestamp. A rule must be rebuild if one of its dependencies is more recent than it. For instance, if the developer modifies main.c, Make will only build the rule that depends on it, that is, the main.o rule. Then, the rule that depends on main.o, the main, and so on. As util.o does not depend on main.c, Make will not update it. These updated rules by Make are also highlighted in blue color in Figure 2 (right). This process, where the build system does only the minimum work without rebuilding the unmodified targets is well-known as the incremental build.

The incremental build process of Make is meant for file changes of a single software configuration. However, we can leverage it to apply on files changes that are triggered by different compile-time configurations options in a C-based system. Indeed, configuration options are enabled in the code through file addition or C preprocessor directives. Inclusion of more files in a rule forces its update. Moreover, additions of blocks of code through C preprocessor directives changes the file's timestamp to a more recent one, hence it forces again the rebuild of the targets depending on it. Thus, Make will only recompile the necessary targets during an incremental build of configurations.

Motivating example

Let us consider xterm, a standard terminal emulator for the X Window System. xterm has 63 compile-time options, which may lead to less than 2 63 configurations (the exact number is certainly lower due to constraints among options). Building all (or even a subset) of its configurations is costly and time-consuming. It is where incremental build can play a positive role. Table 1 shows the build results for four configurations randomly generated for xterm. The top of Table 1 gives the options of the four diverse configurations, and the bottom of Table 1 gives the build time for clean build of each configuration separately, and the incremental build of the four configurations 𝑐 1 → 𝑐 2 → 𝑐 3 → 𝑐 4 . Note that in the incremental build, the first configuration must be built from scratch with a clean build. Only then we can start building incrementally the rest of configurations. From Table 1, we observe that the total sum in time (seconds) of the clean builds of the four configuration is 45.90 𝑠𝑒𝑐𝑜𝑛𝑑𝑠. Whereas, the total sum in time of the incremental build is 41.42 𝑠𝑒𝑐𝑜𝑛𝑑𝑠, that is, the sum of the clean build of 𝑐 1 (hence the "-" for its incremental build) and of the incremental builds of 𝑐 2 to 𝑐 4 . This represents a total gain of 4.48 𝑠𝑒𝑐𝑜𝑛𝑑𝑠 and 9.76% of time difference. We also observe individual gain for every incremental build of the three last configurations, respectively 6.16% for 𝑐 2 , 15.30% for 𝑐 3 , and 18.23% for 𝑐 4 . This gain is only on four configurations and can potentially be more significant the bigger the number of configurations that need to be build. To the best of our knowledge, no study exists on exploring the benefits and limits of incremental build on configurable software. The rest of the paper designs and reports on our exploratory study.

EXPERIMENTAL APPROACH

This section details incremental build experimentation. We first present the used research questions to address the goal of our experiment. Then, we describe the used subject systems with their configurations, and the used build approach in our experimentation.

Research questions

The goal of this study is to explore the feasibility, efficiency, optimization, and correctness of incremental build in real-life configurable software systems. Hence, we define the following four research questions.

𝑅𝑄 1 -Feasibility: Is incremental build possible in each configurable system? We first explore whether the build status of each of our subject software systems is successful during the incremental build in its all considered set of configurations, in some of them, or in none of them.

𝑅𝑄 2 -Efficiency: Does incremental build outperform clean build? To this end, we propose a build approach to measure and compare the clean build and incremental build time of each subject system in its respective set of configurations.

𝑅𝑄 3 -Correctness: Is the result of incremental build the same as that of clean build? To this end, we compare whether the resulting executable binary size and its symbols are the same after the incremental and clean build of each respective configuration in five subject systems.

𝑅𝑄 4 -Optimal ordering: Is there an order of configurations that brings an optimal (overall) incremental build time? By using our build approach, we analyse whether it exists an order of configurations such that the system with a given configuration can be incrementally build faster while being correct.

Subject systems

The objects of this experiment are five real-life software systems (see Table 2). To select them, we had in consideration several criteria. Namely, the fact that the system is an open-source and available project, it has compile-time configuration options, is a popular project, and covers a different application domain. As a result, we selected five C-based software systems as subjects. We first selected the command-line video encoder of x264, which has been widely studied among the highly configurable systems [START_REF] Pereira | Sampling effect on performance prediction of configurable systems: A case study[END_REF][START_REF] Pereira | Learning Software Configuration Spaces: A Systematic Literature Review[END_REF][START_REF] Jamshidi | Transfer learning for performance modeling of configurable systems: an exploratory analysis[END_REF]. Then, we selected the widely used SQL database engine sqlite, the generalpurpose data compression software of xz, the library of curl, which supports a wide range of data transfer protocols with URLs, and xterm, which is the standard terminal emulator for the X Window System. To reason on a project's popularity, we mostly used as a proxy the recent number of stars (from 29 to 21.6k), commits (from 1300 to 27k), and contributors in its git repository.

Variables

Our experiment aims to study the incremental build of a given configurable system in contrast to its clean building. Hence, the incremental and clean build of configurations is the independent variable we controlled. To answer our research questions, we observed three dependent variables, namely: the build time of a configuration, the system's executable binary size, and the system's object files in its build resulting folder, after both the clean and incremental builds.

Build approach

To be able to explore the qualities of incremental build in configurable systems and answer our research questions, we design the following build approach, and apply it in the five subject systems. Given a configurable system 𝜓 with compile-time options 𝑂 𝜓 = {𝑜 1 , 𝑜 2 , ..., 𝑜 𝑚 }, where 𝑚 ∈ N, we first create a sample of configurations 𝐶 𝜓 = {𝑐 1 , 𝑐 2 , ..., 𝑐 𝑛 } for that system. Where 𝑛 = 20, in this study, and each 𝑐 𝑖 ∈ 𝐶 𝜓 has a varying size with a random list of generated options from 𝑂 𝜓 . In Figure 3 is given an overview of our build approach. First, it should be noted that each configurable system has a default configuration, to which we will refer in the following as the baseline configuration (𝑐 𝑏 ). The system with its is at the root of our build approach. Then, we apply two main build steps, named clean build and incremental build as in Figure 3.

Clean build. In this step, the baseline system is build with each configuration 𝑐 𝑖 ∈ 𝐶 𝜓 from scratch. During this clean build, we measure and record the dependent variables (𝑑𝑣 𝑖 ) of 𝑐 𝑖 , namely, the build time, the executable binary size, and the generated files.

Incremental build. Then, over each clean build configuration (cf. 𝑐 1 to 𝑐 𝑛 in Figure 3), we incrementally build the same configurations, except the current previous applied configuration during the clean build. For instance, over the clean build of 𝑐 𝑛 we incrementally build all other configurations from 𝑐 1 up to 𝑐 𝑛-1 except the 𝑐 𝑛 itself. We assume that the incremental build of 𝑐 𝑛 after its clean build will provide the same results, hence it will be insignificant to study.

Listings 2 and 3 show an illustrative example taken from the first subject system of x264 with two of its used configurations, called 𝑐 1 and 𝑐 2 . In Listing 2, the x264's baseline system is first build with 𝑐 1 (lines 2-4), that is, it is clean build, and then it is incrementally build with 𝑐 2 (lines 9-11) over the previous build. Similarly, in Listing 3, the system is first clean build with 𝑐 2 (lines 2-4) and then it is incrementally build with 𝑐 1 (lines 9-11). It should be noted that after the first build, in line 9 of Listings 2 and 3, instead of cleaning the directory with make clean, we directly configure the system to host the new configuration: this is what we refer to as an incremental build. Hence, we incrementally build the next configuration on top of the previous clean build configuration.

Further, during each clean and incremental build process, we measure the build time and the executable binary size of the system (lines 4-6 and 11-13). Moreover, we save the state of the build system's directory after each build. In this way, we can retrieve useful data such as the binary, configuration logs and object files for further analysis.

Experiments settings

By using the presented build approach, we conduct an experiment with the five subject systems. Specifically, we build each system by using two batches with 20 random generated configurations each. In this way, we perform 2 * 20 clean builds and 2 * (20 * 19) = 760 incremental builds, or in total 800 builds of each system. To correctly handle all of them, we used a local git structure where each system build is saved in a new git branch. The resulting git structure of a system with all its builds has the same view as in Figure 3.

To generate the random configurations, we use the random product generator in the FeatureIDE framework [START_REF] Meinicke | Mastering software variability with FeatureIDE[END_REF]. It should be noted that the range of options within the sample of configurations (cf. column 'Range' in Table 2) changes quite proportionally with the number of considered options among the subjects (cf. column '#Opt. ' in Table 2). Whereas, for their comparison, we take two batches q q q q qq q q q q 0 20 40 60 80 100 with 20 sample of configurations in all five subjects. Further, to ensure that the generated set of configurations is diverse enough, we looked at the distance between each pair of configurations within a batch. By distance, we mean the percentage of common options between configurations. Hence, the distance 0 between two configurations 𝑐 𝑖 , 𝑐 𝑗 ∈ 𝐶 𝜓 indicates that the sets of compile-time options in these two configurations are disjoint sets. Whereas, the distance of 1 indicates that 𝑐 𝑖 is the same or at least a subset of 𝑐 𝑗 . Figure 4 shows the overall calculated distribution of the distance between all pairs of configurations in our five subject systems. The median distance varies between 33.33% in the second batch (𝐵 2 ) of x264 and 48.57% in the second batch (𝐵 2 ) of xterm, indicating that in each subject the considered configurations within a batch are diverse for more than 50% on average. We also observed 82 configurations of 0 distance in x264 (𝐵 1 and 𝐵 2 ) and in sqlite (𝐵 2 ), that is, completely different. Then, in x264 (𝐵 1 and 𝐵 2 ) there are only three cases with distance 1, that is, entirely included in another one.

We conducted the experiments on a Linux workstation running Fedora 34 with Intel Core i7-10610U CPU and 15.3 GiB of memory. To prevent side effects, all experiments are run twice using Docker and sequentially, as the only processes in the workstation. Moreover, the Dockerfile of each subject system is made available 1 and can be used to reproduce the experiments. At the same place, we provide the build configurations in all systems with their generated data.

RESULTS

We now discuss the results with regard to our research questions.

Feasibility of incremental build (𝑅𝑄 1 )

In order to measure and compare the build time and system correctness after an incremental build, we first had to ensure that the system is successfully building during the clean build of its configurations, that is, it has a build status 0 and an executable file is created. In cases when the system threw an error during the clean build of a configuration, we analysed the dependencies between compile-time options and resolved the error by removing one of the conflicting options. For example, we encountered such option's dependencies in the configurations of xterm. As a result, in our experiment with five systems, the clean build of each of their configurations is successful. Put differently, in all our clean build cases, the system's build status is 0 and a system's executable file is created.

Despite the successful clean build of all configurations, we noticed that some configurations in some systems have a failed build status during their incremental build. Finding out whether the incremental build is feasible in a system or not was hard to deduce by simply inspecting its Makefile. Therefore, we incrementally build all pairs of configurations in five systems and observed their build status, including the presence of their executable file. As a result, all of the configurations in x264, sqlite, curl, and xterm are successfully incrementally build. But, there are 9 configurations in xz that have a failed build status during their incremental build. These cases are marked with a dash ( ′ -′ ) in Table 3 for batches 𝐵 1 and 𝐵 2 . For instance, by incrementally building xz with configuration 𝑐 3 over any other configuration, in 𝐵 1 , it resulted in a failed build status and without an xz's executable file.

Based on our experiments with five subjects, a successful clean build configuration is not necessarily build successfully during its incremental build. Our initial observations, based only on the build status and the created system's executable, are that the incremental build is feasible in 100% of configurations in 4 systems, namely in x264, sqlite, curl, and xterm. Whereas, the incremental build in xz is feasible in 78% of its configurations. This indicates that the rest 22% of configurations in xz always require to clean build. 𝑹𝑸 1 insights: Our results show that between 78% (in the case of xz) and 100% (in the case of x264, sqlite, curl, and xterm) of configurations can be built incrementally. Hence, instead of always clean building, the incremental build of configurations is feasible on highly configurable systems.

Incremental vs. clean build time (𝑅𝑄 2 )

To answer the second research question, we recorded the clean build time of each configuration and the incremental build time of their all paired combinations. For this purpose, we follow the described build approach in Section 3.4. In Table 3 is given the resulting clean and incremental build time of each configuration, for two batches 𝐵 1 and 𝐵 2 , in each subject system. All build times are expressed in seconds. Specifically, the row 𝐶𝐵(𝑡 𝑛 ) shows the obtained clean build time per configuration. For instance, the clean build time of 𝑐 10 in the 𝐵 2 of curl is 50.13 𝑠𝑒𝑐𝑜𝑛𝑑𝑠. The row 𝑚𝐼𝐵(𝑡 𝑛 ) shows the minimum incremental build time of configuration 𝑛, from its all paired incremental builds. For instance, the fastest time to incrementally build 𝑐 2 of 𝐵 1 in xz is 10.28 𝑠𝑒𝑐𝑜𝑛𝑑𝑠. The next row, 𝐼𝐵(𝑐 𝑚 ), shows which is the clean build configuration for which the incremental build of a given configuration is faster. In the case of xz, the 𝑐 2 in 𝐵 1 is incrementally build faster after the clean build of 𝑐 18 . To easily notice whether the incremental build of a given configuration is faster than its clean build, then the fastest Figure 5: The % of configurations per system that have a faster, slower, and failed incremental build, than clean build q q q q q q q 0 5 10 15 20 The number of configurations with a faster incremental build (IB) than clean build (CB) in each system incremental build is colored in green, given in the row of 𝑚𝐼 𝐵(𝑡 𝑛 ).

Otherwise, when it is slower, it is colored in red. For instance, the incremental build of 𝑐 1 in the 𝐵 2 of x264 is 37.95 𝑠𝑒𝑐𝑜𝑛𝑑𝑠, or 0.14 𝑠𝑒𝑐𝑜𝑛𝑑𝑠 faster than its clean build, therefore it is colored in green. On the contrary, the 𝑐 12 in the 𝐵 2 of x264 is 64.56 𝑠𝑒𝑐𝑜𝑛𝑑𝑠, or 0.12 𝑠𝑒𝑐𝑜𝑛𝑑𝑠 slower than its clean build, hence it is in red.

From Table 3, it can be observed that in four systems, namely, in x264 (𝐵 1 ), sqlite (𝐵 1 , 𝐵 2 ), curl (𝐵 1 , 𝐵 2 ), and xterm (𝐵 1 , 𝐵 2 ), there is always a pair combination of configurations for which the incremental build of a given configuration is faster. However, in x264 (𝐵 2 ) there are 7 from 20 configurations for which the incremental build is always slower than the clean build. Similarly, there are 7 from 20 cases in xz (𝐵 1 , 𝐵 2 ) that always have a slower incremental build than clean build. In Figure 5 is given the percentage of configurations per system that resulted in a faster, slower, or failed build during their incremental build. Specifically, 100% of the configurations in sqlite, curl, and xterm have at least one case where they are incrementally build quicker than during their clean build. Further, 82.50% of the configurations in x264 and 60.00% of the configurations in xz have a faster build during their incremental building. In average, for all five systems, 88.50% of the configurations are built faster during their incremental build than during their clean build. Then, only 7.00% of them are built slower, and 4.50% have a failed built during the incremental building. In cases when a configuration showed a quicker incremental build, we went further and wondered whether it has more than one pair combination for which it is faster than its clean build. For instance, 𝑐 1 in the 𝐵 1 of xterm is incrementally built over all other 19 clean build configurations, that is, over the clean build configurations of 𝑐 2 to 𝑐 20 . When it is built over 𝑐 3 , given in the row 𝐼𝐵(𝑐 𝑚 ), it is faster for 0.18 𝑠𝑒𝑐𝑜𝑛𝑑𝑠 than during its clean building. But, we noticed that there are also cases for which the 𝑐 1 is incrementally built faster, which cases are not shown in Table 3. Therefore, we count all these cases and show them summarized in Figure 6. It resulted that, except in two case in sqlite and curl, all their 20 configurations in two batches show a faster incremental build time in all 19 pair combinations with the other configurations. In the 𝐵 1 of x264, there are between 15 and 19 pair combinations for which 20 configurations are incrementally built faster. In the contrary, in the 𝐵 2 of x264 there are less, between 1 and 13 pairs of combinations. Quite similarly, in xz there are configurations that have faster incremental build in up to 3 and 8 pairs of combinations per batch, respectively. In xterm there is also a large number of cases for which a configuration can be incrementally build faster, up to 15 and 19 cases, per batch. Hence, in the majority of the cases, one can find more than one pair combination to incrementally build a configuration faster than in its clean build.

In addition, in cases when the incremental built configurations are faster, we then wondered for how much they are. In this way, we want to find out for how many minutes or seconds one can benefit by incrementally building instead of clean building a configuration. To analyse it, we calculated the difference between the clean build time and the fastest (the best) incremental build time of each configuration in all systems. The obtained results are shown in Figure 7. The gained time by incrementally building a configuration in x264 is between 0 and 1.34 𝑠𝑒𝑐𝑜𝑛𝑑𝑠. Quite similarly, in xz is between 0 and 10.82 𝑠𝑒𝑐𝑜𝑛𝑑𝑠. In xterm is the smallest gain, between 0.08 and 0.58 𝑠𝑒𝑐𝑜𝑛𝑑𝑠. Whereas, in sqlite is the largest gained time, between 54.44 𝑠𝑒𝑐𝑜𝑛𝑑𝑠 up to 1 𝑚𝑖𝑛𝑢𝑡𝑒 𝑎𝑛𝑑 45 𝑠𝑒𝑐𝑜𝑛𝑑𝑠. This seems to be related also with the taken time to build the system itself. For instance, xterm has the smallest build time, less than 12 𝑠𝑒𝑐𝑜𝑛𝑑𝑠 in all cases. Hence, the gained time during the incremental build is the smallest in xterm. The overall gained time for an incremental build configuration, in all systems, is between 0 (i.e., it is the same time as in the clean build) and almost 2 𝑚𝑖𝑛𝑢𝑡𝑒𝑠. These findings show several things. First, in the majority of the cases (88.50%), the incremental build of a system's configuration is faster than its clean build. A successful clean build configuration may have a fail incremental build (in 4.5% of the cases). Thirdly, in order to benefit on time during the incremental build, the order of build configurations may matter. Then, depending on the system, one can find more than one pair combination of configurations (between 1 and 19) to quickly build a given configuration. The gained time per configuration is quite large (from 0 𝑠𝑒𝑐𝑜𝑛𝑑𝑠 to 1 𝑚𝑖𝑛𝑢𝑡𝑒 𝑎𝑛𝑑 45 𝑠𝑒𝑐𝑜𝑛𝑑𝑠). Benefiting in terms of seconds can be significant, for example, in cases when the system needs to be often build and regarding several configurations. 𝑹𝑸 2 insights: The incremental build of a given configuration can outperform its clean build, but the gain depends on the configuration that was previously built. Our results show that, in average, 88.5% of configurations can be build faster with incremental build.

System correctness (𝑅𝑄 3 )

The observations in the second research question show that in the majority of cases the incremental build of a system's configuration is faster than its clean build. For instance, the clean build time of the configurations in sqlite is between 54.45 𝑠𝑒𝑐𝑜𝑛𝑑𝑠 and 1 𝑚𝑖𝑛𝑢𝑡𝑒 𝑎𝑛𝑑 45 𝑠𝑒𝑐𝑜𝑛𝑑𝑠, whereas their fastest incremental build time is always 0.01 𝑠𝑒𝑐𝑜𝑛𝑑𝑠. Similar examples can be observed also in xz and curl. Hence, we raised the question whether the resulting incremental build systems in these cases are also correct. That is, whether the system after the incremental build and clean build is exactly the same. To reason about a system's correctness, we first defined the correctness of an incremental build based on some properties of its produced binary. It should be noted that comparing the binaries of the same clean and incremental build configuration bit by bit can give inaccurate results. This happens because the incremental build is not expected to be an exact reproduction of the clean build in the binary level. Still, two binaries that are produced by the same configuration share some similarities, such as the binary size and symbol table. Hence, we chose these two properties of a binary (i.e., binary size and symbol table) to ensure the system correctness.

In the row of 𝐵𝑆 [𝑀𝐵] in Table 3 is given the executable binary size, in megabytes (MB), of each clean build system for each configuration. These values are summarized in the first four rows in Table 4. As it can be observed, we encountered the four possible cases. Specifically, 60% of configurations in all systems have a faster incremental build and the resulting system has the same exact binary size as in the clean build. Then, 7.50% of their configurations have a slower incremental build, but still their system has the same exact binary size. On the other hand, there are 32.50% of configurations in all systems that have a faster or slower incremental build, but their resulting system has always a different binary size. Hence, based on the binary size, in 67.50% of the cases the systems that are built incrementally are correct, whereas in 32.50% of the cases they are incorrect. These cases can also be easily identified in Table 3 by using the legend of the colors given in Table 4. Besides, we compared the system's executable symbols after the clean and incremental build of each configuration in all five subjects. The obtained results are summarized in the last two rows in Table 4. It can be observed that, x264 and xterm after each built configurations are correct, that is, in 100% of the cases they have the same binary size and symbols. In the other systems, sqlite, xz, and curl, there are less number of configurations (between 2% and 46%) that have the same symbols during their clean and incremental builds. In all systems, there are 48.03% of configurations for which the resulting system has the same symbols in both build scenarios.

Based on these results, in almost all incrementally build cases x264 and xterm are correct. After investigation, we noticed that the incremental build in these systems is actually not performed by design. In both cases, the configure script is generating a configuration file (config.h and xtermcfg.h, respectively) on which all the other files depend on. Hence, after each configuration, everything is rebuilt from scratch. Therefore, the incremental build that we were expecting is actually equivalent to a clean build in these two systems. In the contrast, in xz we had incremental build issues. We were getting a same specific linker error telling that some symbols are undefined in some libraries. The reason of the error is that some libraries were supposed to be rebuilt during the incremental build of a configuration, but they were not. Further, the reason for which curl and sqlite were incorrect is the same. Whenever two configurations shared the same files and generate the same object files then, even when the content in these files changes by a configuration, they are not rebuild and updated. Consequently, the incorrect builds in these systems return a warning message notifying that there is nothing to build. 𝑹𝑸 3 insights: After an incremental build of configurations, configurable systems are likely to be correct (in 57.80% of the cases), but not always. Specifically, the resulting binaries are correct w.r.t. their executable binary size for 67.50% of configurations and w.r.t. their symbol table for 48.03% of configurations.

Optimal ordering (𝑅𝑄 4 )

Now that we found that incremental build can be faster and correct, the question is to what extent can we leverage on that to outperform clean build of all configurations. To answer this research question, we use our whole data and not only the minimum time that we 𝑉 are all configurations and edges 𝐸 are incremental builds between configurations 2 . We add an edge only when the incremental build is successful and is correct. Each edge has as a weight the minimum time of incremental build. These information comes from Table 3. Then, we add a root vertex that is linked with all other vertices by edges weighted with their respective clean build times. This is essential for configurations that cannot be built incrementally. After that, we run a minimum spanning tree directed graph algorithm [START_REF] Harold N Gabow | Efficient algorithms for finding minimum spanning trees in undirected and directed graphs[END_REF].

In this way, we calculate the optimal order of configurations that leverages to the best possible time on incremental build. Table 5 shows our obtained results after running our algorithm on all incrementally build configurations for two batches on five subject systems. From the column Gain, we can observe that indeed we are able to find an optimal ordering that allows us to correctly build all configurations while being faster by performing incremental builds. The gain varies from 0.10% to 11.76%. Furthermore, we could observe that we were always reducing the required number of clean builds in a system, which vary from 1, 2, 7, 8, 13, 17 to 19 times. Where 1 meaning one necessary clean build upon which the rest of configurations are incrementally built, and 19 where only one incremental built was possible. In particular, xterm, x264, and curl did not need many clean builds and used several incremental builds contrary to sqlite and xz. For example, in the optimized order for xterm 𝐵 1 we had only 1 clean build and the rest was a tree of incremental builds for the rest of the configurations. Whereas, sqlite 𝐵 2 used only 3 incremental builds and 17 clean builds. 𝑹𝑸 4 insights: It is possible to find an order of configurations for which (1) all incremental build configurations in this order are correct; (2) the overall incremental build time (with few clean builds in the middle of the order) is always smaller than the overall time when configurations are only clean built.

DISCUSSION

This section discusses the impacts of our results on three actors. 2 The graphs are available in our companion page.

For developers. From our experiments, we observe that 𝑅𝑄 2 and 𝑅𝑄 4 highlight the benefits of incremental build, while 𝑅𝑄 1 and 𝑅𝑄 3 highlight its limits. Nonetheless, we see that the benefits overcome the limits, in particular, when finding the correct optimal ordering. Hence, developers can already benefit from incremental build. A current limitation is that the optimal order is specific to a set of configurations and deserves an upfront computational investment. However, there are several projects that have a predefined or fixed set of default configurations to build (e.g., JHipster [START_REF] Halin | Test them all, is it worth it? Assessing configuration sampling on the JHipster Web development stack[END_REF]). Furthermore, the investment can pay for itself with the frequency of commits and thus the use of incremental builds several times throughout the continuous evolution.

Besides, developers should take into account the specifics of their projects and possibly fix their build artifacts to fully realize the potential of incremental build. For instance, the case of xz (cf. Section 4.3) is challenging: a critical library on which the build of configurations depends must be forced to rebuild. Indeed, it is specified that the build rule related to the library must be rebuilt each time, allowing it to propagate the build to its dependency and update the new configuration. This rebuild is unnecessary, and the build could be done once and for all. Therefore, developers of configurable software can miss opportunities of relying on incremental build due to mismanagement of their build scripts.

For build system designers. Numerous build systems have been recently designed and developed to support the specific needs of organizations [START_REF] Bazel | A fast, scalable, multi-language and extensible build system[END_REF][START_REF] Buildgrid | RECC[END_REF][START_REF] Maven | A software project management and comprehension tool[END_REF][START_REF] Ninja | A Small Build System with a Focus on Speed[END_REF]. The design space of build system is still to be explored and the case of configurations adds a new dimension. Designers should give an interface between the build rules written by the developer and the build system's back-end which is building the project. In the case of Make, the issues observed when aiming to incrementally build in our case studies cannot be only spotted by the developer in charge of writing build rules. Hence, configurationsaware build systems are still to be designed and developed. We believe the limits and insights of our study can help.

For researchers. Our results call for more research on the topic of incremental build of configurations. Researchers can evaluate the incrementality of existing build systems: most have been designed to support variability in time (evolution), not variability in space (configurations). We encourage researchers to assess the feasibility, correctness, and performance of build systems with the novel scenario of building successive software configurations as we did in the study. In general, there is still a lack of evaluation on a wider scope of incremental build of configurations with various build systems [START_REF] Bazel | A fast, scalable, multi-language and extensible build system[END_REF][START_REF] Buildgrid | RECC[END_REF][START_REF] Maven | A software project management and comprehension tool[END_REF][START_REF] Ninja | A Small Build System with a Focus on Speed[END_REF]. Researchers can design further empirical studies (e.g., confirmatory studies) to gain further insights or validate some hypotheses of our work. A major specificity of incremental build of configurations is that there is an order to define. Intuitively, given a set of configurations, the order of their incremental build can be defined given according to their distance and closeness. However, this notion of distance has to be defined precisely. It can be based on the difference of activated options within configurations, or on the relation between options and their implementation, or even include the impact on the build. Therefore, understanding why certain pairs of configurations benefit more from incremental build is an immediate research direction. It would be interesting to propose heuristics to find an order before the actual build, based on configuration similarities and build rules. In other words, how can we automatically find the optimal orders in 𝑅𝑄 4 ? It is an open problem that deserves much more research (e.g.,, choice and definition of a metric, correlation of distance with build time, thorough evaluation).

THREATS TO VALIDITY

Internal validity. To measure the benefits and limits of incremental build, we had to build several pairs of configurations. To reduce the risk of interference with other running software, we isolated the build environment. To do so, we created one docker image per system with the needed build tools and only needed dependencies. The machine we used was dedicated to the experiment. However, some OS processes and services were still running on the computer that can bring measurements noises. Nevertheless, as we dockerized similarly every run of our experiments, we expect that the noises would be similar, in particular, that we did not launch any other task in parallel. We only run twice the experiments owing to the cost of computations. Moreover, there is a threat related to the sampling used to generate configurations. We deliberately used random sampling to diversify our data sets of configurations. However, we observe from Figure 4 that our configurations are relatively disjoint. Nevertheless, for each sample batch, we repeat the experiment process 2 times. Finally, to check for the correctness of an incremental build, we compared the size and symbols of the produced binary with the one produced with a clean build.

External validity. We experimented on five subjects that are Cbased configurable software systems with the Make build system. Although we think that the incremental build would be applicable in other build systems and software technologies, we cannot generalize our results. Further experimentation is necessary.

Conclusion validity. Our experiments showed promising results

for incremental build of configurations by accelerating the build time. We also show limits when it comes to correctness. Even though, we could still find faster and correct incremental builds, which we used to find the optimal ordering of configurations. To have more insights and statistical evidence, further evaluation is needed on more subject systems and larger set of configurations.

RELATED WORK

Build systems. Many works exist on incremental build systems (e.g., [START_REF] Bazel | A fast, scalable, multi-language and extensible build system[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 without handling a set of configurations. In Cao et al. [START_REF] Cao | Forecasting the duration of incremental build jobs[END_REF], the authors forecast the duration of incremental build jobs for over 2 thousand of commits in GLib (library) and VTK (Visualisation ToolKit). While incremental build jobs vary in terms of duration, they propose a tooled approach, BuildMÉTÉO, to forecast how long a job will take based on the dependency graph extracted from a first clean build using MAKAO [START_REF] Adams | Design recovery and maintenance of build systems[END_REF]. BuildMÉTÉO can estimate the build time of a project after some modifications in its files. However, it is considering only the evolution of one configuration of the project and not diverse ones like our preliminary study. In Cserép and Fekete [START_REF] Cserép | Integration of incremental build systems into software comprehension tools[END_REF], they introduce a way to detect only the necessary files to build by parsing the whole codebase. Instead of parsing every file from scratch each time, which takes an important amount of time, they use incremental parsing.

In addition, they also check the build rules modifications associated with the files. Hence, a file to rebuild is a file that has been either modified or for which a build rule has changed. By doing so, they do not check the binaries' metadata, such as timestamps like Make does, and thus avoid issues we present in Section 4.3. Maudoux and Mens [START_REF] Maudoux | Bringing incremental builds to continuous integration[END_REF] present in their paper that incremental build helps to save time on local builds. However, it is not available yet on continuous integration (CI) platforms. Indeed, incremental build is not brought on CI because of some factors such as the correctness of the produced binary. In our paper, we show that the correctness of incremental build with real-world projects based on GNU Build System is not ensured due to the Make's strategy to perform incremental build over configurations. Further, Konat et al. provide a DSL to increase the effectiveness of writing build scripts by using their proposed language of PIE [START_REF] Konat | Scalable incremental building with dynamic task dependencies[END_REF][START_REF] Konat | Precise, efficient, and expressive incremental build scripts with PIE[END_REF]. With such expressive build scripts, analysis and error detection could be prevented beforehand. They also introduce a build system that takes track of files and focus only on the part that changed, to avoid having too much information in memory and perform strictly the minimum while being effective.

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] 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]). For instance, a case study at Google reported a large corpus of builds and build errors mainly focusing on static compilation problems [START_REF] Seo | Programmers' build errors: A case study (at Google)[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 behavior when different environments are used. In our case, we are considering different configurations rather than environments. To the best of our knowledge, incremental build for software configurations has received little attention.

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 variants and are subject to intensive research. Formal methods and program analysis can identify some classes of configurations' 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., [START_REF] Fischer | Testing of highly configurable cyber-physical systems -A multiple case study[END_REF][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] Hwan | Reducing combinatorics in testing product lines[END_REF][START_REF] Hwan | SPLat: lightweight dynamic analysis for reducing combinatorics in testing configurable systems[END_REF][START_REF] Lima | Learning-based prioritization of test cases in continuous integration of highly-configurable software[END_REF][START_REF] Viet Nguyen | Exploring variability-aware execution for testing plugin-based web applications[END_REF][START_REF] Shi | Integration Testing of Software Product Lines Using Compositional Symbolic Execution[END_REF][START_REF] Alexander Von Rhein | Variability-aware static analysis at scale: An empirical study[END_REF]). The general principle is to exploit the commonalities among variants, mainly at the code level. For instance, variability-aware execution [START_REF] Austin | Multiple facets for dynamic information flow[END_REF][START_REF] Hwan | Reducing combinatorics in testing product lines[END_REF][START_REF] Viet Nguyen | Exploring variability-aware execution for testing plugin-based web applications[END_REF] instruments an interpreter of the underlying programming language to execute the tests only once on all the variants of a configurable system. Nguyen et al. implemented Varex, a variability-aware PHP interpreter, to test WordPress by running code common to several variants only once [START_REF] Viet Nguyen | Exploring variability-aware execution for testing plugin-based web applications[END_REF]. Reisner et al. use a symbolic execution framework to evaluate how the configuration options impact the coverage of the system given a test suite [START_REF] Reisner | Using symbolic evaluation to understand behavior in configurable software systems[END_REF]. 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 (representative) configurations with an unexplored approach -incremental build.

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 endeavor to build all possible configurations of an industry-strength, open source configurable software system JHipster, a popular code generator for web applications. We are unaware of studies that consider incremental build of configurations.

CONCLUSION

In this paper, we conducted a novel study investigating the benefits and limits to incrementally build software configurations, as opposed to always cleaning as in conventional build. By considering five real-life configurable software systems, we explored whether incremental build works, outperforms a sequence of clean builds, is correct w.r.t. clean build, and can be used to find an optimal ordering of building configurations. Our results suggest that incremental build of configurations can reduce build time without trading correctness. Developers and maintainers can already benefit from this simple approach. Owing to the frequencies of build in continuous integration and their increasing cost, we encourage the software engineering community (build system designers, researchers, etc.) to further investigate incremental build of configurations.

As a future work, we plan to replicate our study with other build systems and more batches of configuration samples. We also plan to investigate the possibility of having a heuristic for finding automatically the optimal ordering. This is challenging as it requires to infer a priori the unknown distances among configurations. Finally, we aim to synthesize knowledge of patterns and anti-patterns of incremental build to increase benefits and reduce limits.

Figure 1 :

 1 Figure 1: The workflow of Autotools utility

Figure 2 :

 2 Figure 2: File dependency (left) and incremental build (right)

Listing 2 1 / 3 - 5 >> 0m20.262s 6 >> 8 / 1 / 3 - 8 /

 213568138 x264's clean build with 𝑐 1 and incremental build with 𝑐 2 * Clean build with c1 */ 2 [x264]$ ./configure --disable-interlaced --bit-depth=8 \ -chroma-format=444 --disable-bashcompletion 4 [x264]$ time make ; ls -l x264 -rwxr-xr-x 1904936 x264 7 * Incremental build with c2, after the clean build with c1 */ 9 [x264]$ ./configure --disable-asm --disable-gpl \ 10 --disable-thread --disable-interlaced 11 [x264]$ time make ; ls -l x264 12 >> 0m2.256s 13 >> -rwxr-xr-x 2423016 x264 Listing 3 x264's clean build with 𝑐 2 and incremental build with 𝑐 1 * Clean build with c2 */ 2 [x264]$ ./configure --disable-asm --disable-gpl \ -disable-thread --disable-interlaced 4 [x264]$ time make ; ls -l x264 5 >> 0m2.422s 6 >> -rwxr-xr-x 2423016 x264 7 * Incremental build with c1, after the clean build with c2 */ 9 [x264]$ ./configure --disable-interlaced --bit-depth=8 \ 10 --chroma-format=444 --disable-bashcompletion 11 [x264]$ time make ; ls -l x264 12 >> 0m19.658s 13 >> -rwxr-xr-x 1904936 x264

Figure 4 :

 4 Figure 4: The distance between different generated configurations, per batch, in five subject systems

Figure 6 :

 6 Figure 6: The number of configurations with a faster incremental build (IB) than clean build (CB) in each system

Figure 7 :

 7 Figure 7: The gained time, in seconds, by the incremental build of configurations instead of their clean build

Table 1 :

 1 Example of clean build (CB) and incremental build (IB) on four random configurations of xterm

	𝑐 1 (33 options)		𝑐 2 (29 options)	𝑐 3 (35 options)	𝑐 4 (27 options)
	-disable-active-icon	-disable-ansi-color	-disable-ansi-color	-disable-ansi-color
	-diabel-16-color		-disable-direct-color	-disable-16-color	-disable-direct-color
	-disable-256-color	-disable-88-color	-disable-direct-color	-disable-88-color
	-disable-88-color	-enable-broken-osc	-disable-88-color	-enable-broken-osc
	-disable-broken-st	-disable-bold-color	-disable-blink-cursor	-disable-c1-print
	# +28 other options	# +24 other options	# +30 other options	# +22 other options
	CB: 11.94 seconds	11.04 seconds	12.88 seconds	10.04 seconds
	IB:	-	10.36 seconds	10.91 seconds	8.21 seconds
	Diff:	n/a	6.16%	15.30%	18.23%
	Total	CB: 45.90 seconds	IB: 41.42 seconds	Diff: 9.80%

Table 2 :

 2 Subject systems with their respective analysed commit/tag ID, LoC (lines of code), considered compile-time options, range of options within configurations, and batches

	System Commit/Tag ID	#LoC #Opt. Range #Batches
	x264	ae03d92 115.243	16	3 -7	2 x 20
	sqlite	version-3.35.4 318.521	25	7 -18	2 x 20
	xz	e7da44d	39.714	87 14 -23	2 x 20
	curl	curl-7_78_0 248.713	109 39 -47	2 x 20
	xterm	xterm-368 130.850	63 26 -37	2 x 20

  𝑐 𝑏 system with 𝑐 𝑏 𝑐 3 . . . 𝑐 𝑛 𝑐 1 𝑐 3 . . . 𝑐 𝑛 𝑐 1 𝑐 2 . . . 𝑐 𝑛-1 𝑑𝑣 1 𝑑𝑣 2 𝑑𝑣 𝑛 𝑑𝑣 12 𝑑𝑣 13 𝑑𝑣 1𝑛 𝑑𝑣 21 𝑑𝑣 23 𝑑𝑣 2𝑛 𝑑𝑣 𝑛1 𝑑𝑣 𝑛2 𝑑𝑣 𝑛𝑛-1 Experimentation workflow. Where 𝑐 𝑏 is the system's baseline configuration, and 𝑐 1 -𝑐 𝑛 are its random generated configurations. The 𝑑𝑣 𝑛 and 𝑑𝑣 𝑛𝑚 are the measured dependent variables (build time, executable binary size, etc.)

	𝑐 2 Clean build	𝑐 1	𝑐 2	. . .	𝑐 𝑛
	Incremental build
	Figure 3:

Table 3 :

 3 The build time and binary size of subjects for two batches (𝐵 1 and 𝐵 2 ) with 20 configurations each. Legend of colors is in Table4. 𝐶𝐵 -clean build, 𝐼𝐵 -incremental build, 𝑚𝐼𝐵 -minimum IC, 𝑐𝐼𝐵 -currect IB, " -" -failed build, and "/" -no value

	System	𝑐 1	𝑐 2	𝑐 3	𝑐 4	𝑐 5	𝑐 6	𝑐 7	𝑐 8	𝑐 9	𝑐 10	𝑐 11	𝑐 12	𝑐 13	𝑐 14	𝑐 15	𝑐 16	𝑐 17	𝑐 18	𝑐 19	𝑐 20
	1 ) (𝐵 x264	CB (𝑡𝑛 ) IB (𝑐𝑚 ) IB (𝑡𝑛 ) BS [MB]	38.09 𝑐 3 37.42 1.83	38.60 𝑐 4 37.85 1.85	34.91 𝑐 11 33.93 2.17	70.58 𝑐 17 69.24 2.91	38.24 𝑐 4 37.41 2.33	66.00 𝑐 11 65.18 2.71	21.30 𝑐 4 20.96 1.53	20.79 𝑐 20 20.33 1.58	66.40 𝑐 3 65.35 2.70	32.27 𝑐 7 31.78 1.67	65.72 𝑐 3 64.58 2.71	38.13 𝑐 8 37.25 1.83	20.61 𝑐 5 20.25 1.50	17.90 𝑐 12 17.65 1.40	33.91 𝑐 11 33.38 2.12	18.57 𝑐 4 18.17 1.48	40.74 𝑐 8 39.99 1.95	19.14 𝑐 4 18.76 1.49	35.15 𝑐 6 34.46 2.18	37.87 𝑐 18 37.22 1.83
	2 ) (𝐵 x264	CB (𝑡𝑛 ) IB (𝑐𝑚 ) IB (𝑡𝑛 ) BS [MB]	38.09 𝑐 15 37.95 1.85	18.49 𝑐 8 18.54 1.42	18.31 𝑐 18 18.24 1.48	31.31 𝑐 3 31.32 1.64	69.86 𝑐 3 69.84 2.95	65.46 𝑐 14 65.52 2.75	17.73 𝑐 3 17.70 1.37	34.45 𝑐 16 34.53 1.78	40.12 𝑐 13 40.06 1.95	34.18 𝑐 1 34.04 2.17	34.56 𝑐 16 34.51 2.18	64.44 𝑐 3 64.56 2.69	36.40 𝑐 17 36.32 1.79	18.25 𝑐 1 18.23 1.48	33.62 𝑐 3 33.68 2.17	70.73 𝑐 3 70.77 2.96	34.03 𝑐 3 34.03 2.17	18.43 𝑐 15 18.38 1.47	38.18 𝑐 3 38.07 1.85	31.35 𝑐 17 31.34 1.64
	1 ) (𝐵 sqlite	CB (𝑡𝑛 ) IB (𝑐𝑚 ) cIB (𝑡𝑛 ) mIB (𝑡𝑛 ) BS[MB]	61.07 𝑐 7 / 0.01 9.20	65.67 𝑐 4 / 0.01 9.70	68.35 𝑐 15 / 0.01 9.25	68.64 𝑐 7 / 0.01 9.73	68.55 𝑐 7 / 0.01 9.68	72.64 𝑐 3 70.02 0.01 9.73	57.08 𝑐 4 / 0.01 8.07	59.41 𝑐 14 / 0.01 8.13	72.58 𝑐 3 / 0.01 9.72	71.36 𝑐 3 / 0.01 9.64	68.11 𝑐 15 / 0.01 9.74	68.57 𝑐 4 / 0.01 9.68	54.45 𝑐 4 / 0.01 8.17	70.82 𝑐 8 / 0.01 9.61	62.49 𝑐 8 / 0.01 8.55	65.98 𝑐 7 / 0.01 9.52	67.85 𝑐 5 / 0.01 9.65	58.87 𝑐 2 / 0.01 8.26	72.43 𝑐 8 / 0.01 9.73	70.91 𝑐 3 / 0.01 9.62
	2 ) (𝐵 sqlite	CB (𝑡𝑛 ) IB (𝑐𝑚 ) cIB (𝑡𝑛 ) mIB (𝑡𝑛 ) BS[MB]	103.25 𝑐 3 63.42 0.01 9.70	94.24 𝑐 16 / 0.01 9.51	101.89 𝑐 4 / 0.01 9.62	103.8 𝑐 1 / 0.01 9.73	83.63 𝑐 15 / 0.01 8.41	98.71 𝑐 20 94.30 0.01 9.75	90.24 𝑐 8 / 0.01 9.23	101.67 𝑐 3 / 0.01 9.60	82.28 𝑐 3 / 0.01 8.07	91.83 𝑐 9 / 0.01 8.64	82.95 𝑐 4 / 0.01 8.58	87.05 𝑐 3 / 0.01 8.39	89.91 𝑐 5 / 0.01 9.68	105.17 𝑐 4 / 0.01 9.73	87.05 𝑐 5 / 0.01 8.61	96.4 𝑐 2 / 0.01 9.68	84.8 𝑐 6 / 0.01 8.62	103.32 𝑐 12 / 0.01 9.70	103.58 𝑐 3 / 0.01 9.72	96.58 𝑐 16 56.32 0.01 9.70
	1 )	CB (𝑡𝑛 )	12.15	10.78	11.39	10.52	10.24	10.37	11.20	11.89	11.24	10.59	10.29	10.20	10.58	10.44	10.53	12.46	10.53	11.17	11.59	10.19
	xz (𝐵	IB (𝑐𝑚 ) cIB (𝑡𝑛 )	𝑐 18 11.43	𝑐 18 10.28	--	𝑐 18 10.72	𝑐 10 /	--	--	𝑐 9 11.28	𝑐 8 /	𝑐 5 /	--	𝑐 18 10.06	𝑐 17 /	--	𝑐 18 10.65	--	𝑐 13 /	𝑐 20 10.67	--	𝑐 18 10.30
		mIB (𝑡𝑛 )	11.43	10.28	-	10.72	0.40	-	-	1.35	0.42	0.87	-	10.06	0.61	-	10.65	-	0.96	10.67	-	10.30
		BS [MB]	1.16	1.02	1.15	1.02	1.02	1.06	1.09	1.13	1.10	0.96	1.00	0.99	1.02	1.09	1.04	1.23	0.96	1.03	1.16	1.01
	2 )	CB (𝑡𝑛 )	10.38	10.08	11.01	9.75	10.02	10.20	9.94	9.69	10.00	10.90	9.96	9.86	10.74	11.47	9.98	10.18	11.63	11.08	9.82	9.83
	xz (𝐵	IB (𝑐𝑚 ) cIB (𝑡𝑛 )	𝑐 13 /	𝑐 17 9.93	𝑐 2 10.91	𝑐 2 9.46	𝑐 7 10.08	--	𝑐 5 /	𝑐 9 9.74	𝑐 2 10.10	𝑐 6 /	--	𝑐 3 10.17	𝑐 1 10.42	𝑐 8 11.49	𝑐 17 /	𝑐 18 10.18	𝑐 15 11.51	𝑐 5 10.95	𝑐 17 /	𝑐 2 9.77
		mIB (𝑡𝑛 )	0.86	9.93	10.91	9.46	0.81	-	0.47	9.74	10.10	0.95	-	10.17	0.89	11.49	0.28	10.18	1.91	10.95	0.38	9.77
		BS [MB]	1.17	1.01	1.18	0.94	1.02	1.18	1.05	0.92	1.06	1.19	1.09	1.02	1.08	1.17	1.10	1.03	1.16	1.06	0.95	1.01
	1 ) (𝐵 curl	CB (𝑡𝑛 ) IB (𝑐𝑚 ) cIB (𝑡𝑛 ) mIB (𝑡𝑛 )	23.56 𝑐 5 / 0.05	42.42 𝑐 16 38.17 1.06	30.52 𝑐 1 25.99 0.11	44.02 𝑐 16 39.82 0.11	24.99 𝑐 9 / 0.06	23.61 𝑐 5 / 1.17	22.91 𝑐 6 18.66 0.12	34.05 𝑐 5 / 0.05	29.37 𝑐 3 / 0.06	24.05 𝑐 5 19.66 0.10	55.98 𝑐 16 51.47 0.11	26.14 𝑐 5 22.01 1.07	40.80 𝑐 16 36.34 0.12	70.95 𝑐 16 64.56 1.07	41.08 𝑐 16 37.70 0.36	44.38 𝑐 11 / 1.01	29.34 𝑐 1 24.71 0.12	23.26 𝑐 9 / 0.05	21.72 𝑐 18 17.33 1.05	56.86 𝑐 16 52.37 1.08
		BS [MB]	4.67	3.50	0.61	4.15	1.02	4.31	4.09	4.56	0.75	4.31	4.29	0.82	2.61	4.54	3.47	3.89	4.45	0.69	1.10	4.01
	2 ) (𝐵 curl	CB (𝑡𝑛 ) IB (𝑐𝑚 ) cIB (𝑡𝑛 ) mIB (𝑡𝑛 )	28.61 𝑐 13 24.69 1.06	71.51 𝑐 11 67.95 35.01	33.53 𝑐 11 29.63 0.11	39.86 𝑐 11 36.75 19.56	25.26 𝑐 11 21.32 0.12	67.21 𝑐 13 65.67 34.78	30.87 𝑐 11 26.98 1.06	28.31 𝑐 13 24.39 0.11	29.61 𝑐 13 25.80 0.12	50.13 𝑐 11 46.52 24.54	23.47 𝑐 13 / 1.01	41.16 𝑐 13 37.59 19.94	23.40 𝑐 11 / 0.05	23.58 𝑐 13 19.61 0.11	44.98 𝑐 11 41.64 22.08	23.35 𝑐 13 19.32 0.11	25.30 𝑐 13 21.18 0.11	22.97 𝑐 13 18.93 0.11	44.97 𝑐 13 41.48 21.82	29.27 𝑐 11 24.82 1.07
		BS [MB]	4.47	4.42	4.42	2.85	1.31	4.32	3.60	4.67	3.66	2.83	0.54	3.22	0.58	4.22	3.93	0.70	0.82	3.60	3.93	3.89
	1 ) (𝐵 xterm	CB (𝑡𝑛 ) IB (𝑐𝑚 ) IB (𝑡𝑛 ) BS [MB]	8.60 8.42 2.61	8.24 8.06 2.35	11.64 11.43 3.05	11.33 11.13 3.19	11.82 11.68 3.30	10.23 9.83 2.88	9.74 9.56 2.72	9.96 9.74 2.77	11.53 11.42 3.07	10.77 10.59 2.88	9.89 9.66 2.77	9.08 8.94 2.75	10.17 10.01 2.88	8.91 8.72 2.62	10.26 10.11 2.92	9.83 9.65 2.73	7.67 7.50 2.28	8.63 8.49 2.61	11.85 11.66 3.14	10.91 10.72 2.89
	2 ) (𝐵 xterm	CB (𝑡𝑛 ) IB (𝑐𝑚 ) IB (𝑡𝑛 ) BS [MB]	11.41 𝑐 3 11.18 3.11	11.32 𝑐 1 11.11 3.09	10.46 𝑐 2 10.24 2.88	8.88 𝑐 5 8.69 2.55	10.19 𝑐 3 10.05 2.81	10.20 𝑐 2 10.06 2.84	9.08 𝑐 10 8.93 2.52	8.33 𝑐 10 8.17 2.50	12.80 𝑐 2 12.57 3.38	10.76 𝑐 2 10.68 2.91	10.46 𝑐 9 10.31 2.80	10.81 𝑐 7 10.62 3.04	8.52 𝑐 6 8.38 2.44	11.74 𝑐 3 11.53 3.21	11.68 𝑐 5 11.1 3.13	9.88 𝑐 3 9.67 2.61	7.60 𝑐 5 7.4 2.30	11.76 𝑐 2 11.58 3.23	10.59 𝑐 2 10.41 2.75	8.45 𝑐 5 8.24 2.51

Table 4 :

 4 The percentage of correct systems after their incremental builds, based on their binary size (BS) and symbols

		Legend:	x264 (𝐵 1 )	x264 (𝐵 2 )	sqlite (𝐵 1 )	sqlite (𝐵 2 )	xz (𝐵 1 )	xz (𝐵 2 )	curl (𝐵 1 )	curl (𝐵 2 )	xterm (𝐵 1 )	xterm (𝐵 2 )
	Fast & Same BS	&	20	12	1	3	5	8	13	18	20	20
	¬Fast & Same BS	&	0	7	0	0	3	5	0	0	0	0
	Fast &¬Same BS	&	0	1	19	17	5	5	7	2	0	0
	¬Fast &¬ Same BS	&	0	0	0	0	7	2	0	0	0	0
	Overall same BS (%)		100	95	5	15	40	65	65	90	100	100
	Same Symbols (%)		100	95	2	2	2	2	32	46	100	100
	¬Same Symbols (%)		0	5	97	98	98	98	68	54	0	0

Table 5 :

 5 Results for the optimal ordering

	System	Total Clean Build	Total Optimal Ordering of Incremental Build	Gain	Reduced N°of Clean Builds
	x264 (𝐵 1 )	754.92 [sec]	666.12 [sec]	11.76%	20 → 2
	x264 (𝐵 2 )	747.99 [sec]	747.26 [sec]	0.10%	20 → 8
	sqlite (𝐵 1 )	1,325.83 [sec]	1323.21 [sec]	0.20%	20 → 19
	sqlite (𝐵 2 )	1,888.35 [sec]	1803.85 [sec]	4.47%	20 → 17
	xz (𝐵 1 )	218.35 [sec]	216.89 [sec]	0.67%	20 → 13
	xz (𝐵 2 )	206.52 [sec]	205.67 [sec]	0.41%	20 → 13
	curl (𝐵 1 )	710.01 [sec]	652.01 [sec]	8.17%	20 → 7
	curl (𝐵 2 )	707.35 [sec]	641.14 [sec]	9.36%	20 → 2
	xterm (𝐵 1 )	201.06 [sec]	197.33 [sec]	1.86%	20 → 1
	xterm (𝐵 2 )	204.92 [sec]	201.14 [sec]	1.84%	20 → 1
	report in

Table 3 ,

 3 that is, all measured times for the different combinations of incremental build. For this reason, we searched for an optimal ordering of configurations based on build time. To do that, we first start by building a directed graph 𝑔 = (𝑉 , 𝐸) where vertices

https://doi.org/10.5281/zenodo.5915116

ACKNOWLEDGMENTS

We thank anonymous reviewers for their valuable comments and suggestions. This research was funded by the ANR-17-CE25-0010-01 VaryVary project and the SLIMFAST project with DGA-Pôle Cyber (PEC) and Brittany region.