HINNPerf: Hierarchical Interaction Neural Network for Performance Prediction of Configurable Systems

Modern software systems are usually highly configurable, providing users with customized functionality through various configuration options. Understanding how system performance varies with different option combinations is important to determine optimal configurations that meet specific requirements. Due to the complex interactions among multiple options and the high cost of performance measurement under a huge configuration space, it is challenging to study how different configurations influence the system performance. To address these challenges, we propose HINNPerf, a novel hierarchical interaction neural network for performance prediction of configurable systems. HINNPerf employs the embedding method and hierarchic network blocks to model the complicated interplay between configuration options, which improves the prediction accuracy of the method. Besides, we devise a hierarchical regularization strategy to enhance the model robustness. Empirical results on 10 real-world configurable systems show that our method statistically significantly outperforms state-of-the-art approaches by achieving average 22.67% improvement in prediction accuracy. In addition, combined with the Integrated Gradients method, the designed hierarchical architecture provides some insights about the interaction complexity and the significance of configuration options, which might help users and developers better understand how the configurable system works and efficiently identify significant options affecting the performance.


INTRODUCTION
Modern configurable software systems offer customized services to users through a set of configuration options. By specifying a combination of these options (i.e., a configuration), one can tailor the system's behavior to meet specific functional requirements. Meanwhile, the non-functional properties of the system may be significantly influenced by different configuration selections.
Performance (such as response time and throughput) is one of the most important non-functional properties as it directly affects user experience and cost [12,13]. It is necessary for both users and developers to efficiently identify the performance-optimal configurations when deploying and testing the software system. However, it is infeasible to exhaustively measure the system performance under all possible configurations, since the combinatorial explosion of configuration options results in an exponential number of configurations [12,13,42].
Recently, researchers have devised various machine learning methods to predict system performance under any certain configuration [11-14, 42-44, 52]. In this way, a performance model is constructed to ease understanding, debugging, and optimization of highly configurable software systems. For example, the performance model can help a user find the best performing configuration under specific functional constraints. And a developer may compare the performance model with his own mental model to check whether the software behaves as expected, and improve the software based on the comparison [42]. Compared to the huge time cost of measuring the system performance by executing a complex benchmark, a performance model can predict the performance under a certain configuration within a few seconds, which significanlty reduces software testing cost.
To build a performance model, the scalar performance values of a set of configurations are required to be first measured. The configurations and their corresponding performance measurements compose a sample for training a model which later can be used for predicting the performance values of new configurations. Most importantly, prediction accuracy determines whether a performance model can really help users and developers improve software quality, rather than causing unnecessary misleading. This is why most of prior work have focused on improving the accuracy of performance models [11-14, 42-44, 52]. Nevertheless, learning a performance model with high accuracy is very challenging because of the following aspects: (1) Complex interactions among features: Configurable systems typically have multiple binary and/or numeric configuration options (also called features). The interactions among different features can be non-linear, multi-way and hierarchical [43,45]. Failing to learn the interactions that contribute substantially to software performance causes significant drop on prediction accuracy. (2) Small sample: Typically, measuring the performance of a configuration requires executing a realistic workload on the whole system, which is costly and time-consuming [33]. Hence, only a limited set of configurations can be measured as a training sample in practice [12]. A small sample could cause the performance model to easily overfit (i.e., the model performs well on the training data but badly during testing).
Existing methods tackle the above challenges in varied ways. For interaction modeling, SPLConqueror [42][43][44] learns the influences of individual configuration options (features) and their interplay on performance by multiple linear regression. However, the method only models the interactions with linear combinations of low-order functions (e.g., linear, quadratic and logarithmic), limiting its flexibility in recognizing complex non-linear interactions. Further, CART/DECART [11,12] employs classification and regression trees to build a more flexible non-linear performance model. Fourier learning algorithms [14,52] transform the regression problem into its Fourier form and predict the performance by estimating the Fourier coefficients. The main disadvantage of CART/DECART and Fourier methods is that they can only learn the interactions among binary configuration options. DeepPerf [13] introduces a deep feedforward neural network (FNN) to overcome the shortcomings of previous methods. Nonetheless, a deep FNN can only model the feature interactions implicitly through multiple hidden layers, which probably limits its flexibility and accuracy. For example, some hierarchical configuration interactions prone to affecting the system performance are hard to be engaged to DeepPerf, since the interactions between different layers of FNN is opaque [3]. On the other hand, to mitigate the limitation of the small sample, both SPLConqueror [42] and DECART [12] incorporate several sampling heuristics to select a set of representative configurations for training. However, it takes extra time and effort to determine the appropriate sampling strategy for each system since there is no universal optimal sampling heuristics [10]. Instead, PerLasso [14] and DeepPerf [13] focus on restricting the performance model to be sparse with 1 regularization. This strategy takes the risk of making the model highly sensitive to the regularization hyperparameter, that is, small changes in hyperparameter may cause large fluctuations in model accuracy. In this case, the regularization hyperparameter must be carefully tuned in a large search space, which increases model training cost.
To better address the aforementioned challenges, we propose a novel Hierarchical Interaction Neural Network for Performance Prediction and name it HINNPerf. Similar to DeepPerf [13], our method can model all types of complex interactions (i.e., binary, numeric, and binary-numeric interactions) in various configurable systems. Differently, inspired by previous work [42,43,45] revealing that interactions among configuration options are hierarchical, we decompose the deep neural network architecture into multiple blocks connected hierarchically, where lower (higher) blocks learn the influences of lower-order (higher-order) interactions on system performance. Within each block, similarly to embedding methods [4,19,51] widely used in deep learning world, we employ an FNN to embed the feature interactions into a vector. All the blocks link to each other by the vector concatenation. Also, each block predicts a partial performance value and the final prediction is the sum of all partial predictions. In this way, it is much easier for HINNPerf to learn the influences of individual features and their interactions on performance via a deeper and more expressive architecture 1 . In addition, based on the sparsity prior of the software performance functions [13,42,43], we engage the 1 regularization [48] for the first FNN layer of each block to address the challenge of small sample. We empirically find that such hierarchical regularization architecture is more robust to the regularization hyperparameter and reduces hyperparameter tuning cost. As for practicality, on the one hand, the hierarchical structure of HINNPerf enables it to provide some insights on configuration coupling of the system, which can help users and developers understand which kind of interactions (lower-or higher-order) has the major influence on the system performance. On the other hand, combined with the Integrated Gradients [47] method, HINNPerf recognizes the significant configuration options in different interaction orders and reveals some potential interaction patterns for the system, presenting more actionable information for users and developers. Finally, it can be demonstrated that the DeepPerf [13] model is simply a special case of our HINNPerf architecture. From this perspective, our method provides a general deep learning framework for performance prediction of configurable systems.
We evaluate our method on 10 real-world configurable software systems including compilers, web servers, video encoders, etc. The experimental results show that HINNPerf outperforms the stateof-the-art methods on most systems. Remarkably, when compared to the advanced deep learning method DeepPerf [13], HINNPerf achieves statistically significant improvements on binary-numeric systems (i.e., the systems with both binary and numeric configuration options), demonstrating its strength in capturing complex feature interactions.
In summary, our contributions are of four-folds: • We introduce the embedding method and propose a novel deep neural network architecture to model the hierarchical interactions among configuration options and predict the performance of configurable software systems. To our knowledge, although the embedding method has achieved great success in various deep learning tasks [4,19,51,56], few literatures have employed it to model the feature interactions of configurable systems. And we aim to bridge the gap in this work. • We devise a hierarchical regularization strategy to help the 1 regularization address the small sample challenge more efficiently, with the advantages of improving model robustness to the regularization hyperparameter and reducing hyperparameter tuning cost. • We conduct extensive experiments on 10 real-world configurable software systems with various sample sizes and show the advantages of our method against most state-of-the-art baseline approaches, demonstrating new benchmark on the public datasets. Our experimental data and source code are publicly available at the Google Drive 2 . • In addition to accuracy improvement, our method provides some insights on the complexity of configuration coupling and identifies the significant configuration options in different interaction orders by automatic learning, which could help users and developers better understand how the configurable system works. Table 1 illustrates a performance example of a configurable software system. The system has 14 configuration options with 11 binary options and 3 numeric options. Each row of the table represents one configuration and its performance measurement that can be response time, throughput, workload and so on. Evidently, different configurations usually lead to different performance values. Our main task is to predict the performance value of a new configuration that is not measured (e.g., the value ? in the last row of Table 1), based on the observations of previously measured configurations. Formally, we aim to learn a function that maps a configuration with options o = [ 1 , 2 , ..., ] ⊤ to its performance value:

Problem Formulation
where : X → R is the performance function and X is the Cartesian product of the domains of all the configuration options. Naively, we can derive a precise performance function by exhaustively measuring the performance of every valid configuration of the software system, which is infeasible in practice because of the exponentially growing configuration space [12,13,42,49]. Therefore, the objective is to design a performance model for precisely approximating the performance function using only a small sample.

Hierarchical Interactions
A large number of configuration options with different types (binary and numeric) can generate complex interactions that affect configurable system performance in different ways. In theory, any combination of the configuration options may cause a distinct interaction pattern [43]. Fortunately, researchers have found that relevant interactions form a hierarchical relationship [42,43,45]. That is, higher-order interactions usually build on lower-order interactions. As is pointed out by [42], three-way interactions (i.e., interactions among three options) build on corresponding two-way interactions among the same set of options. To improve the accuracy of performance prediction, it is necessary to model the influence of diverse interaction patterns on performance through a hierarchical and expressive method.

Deep Feedforward Neural Network
Deep neural networks are one of the most expressive models owing to their excellent strength in capturing non-linear data relationships [9]. A feedforward neural network (FNN) is a network which connects the input and the output through multiple stacked layers (hidden layers) of computational units (neurons) [9,13]. According to the universal approximation theorem [18,26,29], an FNN with at least one hidden layer can approximate any continuous function from one finite dimensional space to the other at any level of accuracy, as long as enough neurons and a suitable activation function (e.g., sigmoid, ReLU) are provided [13]. Hence, it is feasible to approximate the performance prediction function of a configurable system with an FNN. However, the number of neurons needed to approximate a real-world function might be infinitely large and it is impossible to train such an FNN in finite time. Instead, researchers have tuned to train deep FNNs under an upper bound of the approximation error [38,50]. Theoretically, a deeper FNN can better enrich the "levels" of data features and is more expressive to approximate functions with higher level of accuracy [6,15,27]. Nevertheless, we propose that a deep FNN is probably not a sufficiently good architecture for the performance prediction problem, mainly due to following reasons: • The interaction modeling process of a deep FNN is opaque. Under a general FNN architecture, features of lower hidden layers serve as inputs to higher hidden layers and the final output is the non-linear combinations of the features in the last hidden layer. In this way, it is easy for a deep FNN to learn a performance function of high-level data features but ignore the hierarchical interactions between lower-and higher-order features. Such a limitation might not be well suited for the hierarchical interaction nature of configurable software systems and reduce the prediction accuracy. • The FNN architecture is a complete black box model such that it can only predict the scalar performance value without providing insights about how feature interactions of different orders influence the system performance.
To overcome above limitations of FNN, deep learning researchers have extended general FNNs into hierarchical network architectures, achieving significant improvements in image processing [15,28], natural language processing [4,24], time series prediction [36], etc. Similarly in this paper, we devise a novel network architecture consisting of multiple blocks connected hierarchically, where different network blocks learn the influence of different interactions on system performance. Our method well fits the hierarchical interaction nature of configurable systems and thus achieves higher accuracy than the DeepPerf [13] method. Besides, by measuring the contributions of different blocks to the system performance and computing the significance score of each configuration option in different interaction orders, our approach provides some additional insights into the coupling complexity and interaction patterns of the system, as we will discuss in later sections.

Interaction Embedding
The main task of the embedding method is to translate an object from a high-dimensional abstract space (e.g., a word, an image, a video, etc) into a vector representation of a low-dimensional space, while maintaining some basic properties such as semantics and temporal relationships. Various embedding methods have been proposed to improve a variety of deep learning tasks such as natural language processing [4,31,32], recommendation systems [2,51], and video encoding [19].
As we described in Section 1, the interaction space of configurable systems could be extremely high-dimensional due to the exponential configuration space and complex interaction patterns. Hence, it is reasonable to embed the interactions into low-dimensional vectors and model their influence on the performance. However, there is little work about introducing embedding methods into performance prediction of configurable systems and we hope to make a step forward. Following the popular neural network language embedding method [4], we employ multiple FNNs to perform interaction embedding of different orders and empirically find it beneficial for prediction accuracy improvement.

Sparsity Regularization
In general, training a deep neural network with high prediction accuracy requires large-scale datasets, which is not applicable for the performance prediction task domain. A good way to mitigate the limited dataset issue is to incorporate prior knowledge into the neural network to guide its learning process [13]. One important prior knowledge is that only a small number of configuration options and their interactions have a significant impact on system performance [13,42,43], implying sparsity on the parameters of the performance model (i.e., making parameters of many insignificant options and interactions equal to zero). The 1 regularization [48] is one of the most widely-used techniques for sparsity enforcement. By adding a penalty term constructed from the sum of the absolute values of model parameters to the loss function, 1 regularization encourages the magnitude of parameters to be small and even zero [35]. However, the model accuracy might be highly sensitive to the regularization hyperparameter and it usually takes a lot of effort and time to search for optimal value on a large hyperparameter space [13,14]. To reduce training cost, it is necessary to design an effective mechanism to improve model robustness and reduce the hyperparameter space.

APPROACH
We propose HINNPerf, a hierarchical interaction neural network to predict performance values of configurable systems. Based on the discussion in Section 2, our network architecture design relies on three key principles. First, for better interaction modeling, the architecture should incorporate the embedding method and the hierarchical interaction nature of configurable systems. Second, considering the small sample challenge, the architecture should be sparse but efficient for hyperparameter tuning. Third, the architecture should provide some insights for users and developers on how feature interactions of different orders affect the system performance. We now describe in detail how these principles converge to our method.

Theoretical Model
We construct the theoretical model by decomposing the performance function of Equation (1) into the sum of subfunctions: where o ∈ X ⊂ R is the configuration with options and ⊕ denotes the vector concatenation operation. The model defined by Equation (2) contains two function families: That is, each embeds the interaction information into a vector of R space. With this condition, we can infer that x ∈ R from the definition of Equation (2). Note that the embedding dimension could be designed flexibly according to the demands of the real-world environmental settings.
• { : R → R} 1≤ ≤ , the performance subfunctions. Each maps the input features x ∈ R to a partial performance value, which is summed with other partial values into the actual performance value (o).
The design rationale of our theoretical model is exactly the hierarchical interaction rule described in Section 2.2 and the interaction embedding described in Section 2.4. In this case, the higher-order interaction x is built by the concatenation of lower-order interactions x −1 and −1 (x −1 ), which facilitates the performance representation of different interaction orders. For example, subfunction 1 might only represent the partial performance value under the influences of original configurable options and the two-way interactions among them. And the embedding function 1 might embed these two-way interactions into the vector 1 (o). By concatenating the original configuration o with its interaction embedding vector 1 (o) as the input for 2 , it is easier for 2 to represent the partial performance value under the influences of three-way interactions. Similarly, higher-order subfunctions ( ≥ 3) correspond to performance influences of higher-order interactions. Note that the interaction patterns of real-world configurable software may be much more complex than the simple example above, but our theoretical model is flexible to handle different situations.

Network Architecture
According to our theoretical model, we design a hierarchical interaction network architecture to approximate all the performance subfunctions and interaction embedding functions in Equation (2). Figure 1 (right) presents an overview of the proposed HINNPerf architecture. Similar in spirit to the N-BEATS model [36] and other hierarchical network architectures [24,28], our model consists of multiple hierarchically connected building blocks. Figure 1 (left) shows the -th block of the HINNPerf architecture. The -th block accepts its input x and employs a multi-layer feedforward neural network (FNN) to approximate subfunction and embedding function . The input and the hidden layers of FNN are shared by the two approximation functionsˆandˆwhile different output layers are utilized to produce partial performance predictionˆ(x ) and interaction embedding vectorˆ(x ), respectively.
x 1 x 2 x jn Suppose the FNN of the -th block has hidden layers with each layer containing neurons, the computation of the -th block is described by the following equations: where: • W , , b , (1 ≤ ≤ ) are weights and biases of the -th hidden layer.
• ReLU is the activation function for non-linear learning in deep FNN [8,34].
• h , ∈ R (1 ≤ ≤ ) is the output vector of the -th hidden layer.
• W , ∈ R , , ∈ R are weights and bias used for predicting the partial performance valueˆ(x ), respectively. Note thatˆ(x ) is the linear output of h , since the performance prediction is a regression problem [13]. • W , ∈ R × , b , ∈ R are weights and biases that project the output vector of the last hidden layer to the interaction embedding space, respectively.

Hierarchical Regularization
As discussed in Section 1 and Section 2.5, training a deep neural network on the small sample of a configurable system is difficult because of the high risk of overfitting. One way to solve the problem is to introduce additional restriction to the network parameters by employing a suitable regularization technique. Instructively, researchers have found that for configurable software systems, although there are exponential number of interactions among configuration options, a very large portion of potential interactions has no influence on system performance [13,42,43].
This observation inspires us that parameters corresponding to unimportant interactions should be eliminated in the performance model, that is, parameters of the performance model could be quite sparse. Under the sparsity condition, we decide to apply the 1 regularization technique to our method because of its strength on sparsity enforcement. Denote as the parameters of a performance model, X as the input data, Y as the output data and ( , X, Y) as the loss function of the model. Generally, The 1 regularization changes the loss function from ( , X, Y) to: where || · || 1 denotes the 1 norm and is the regularization hyperparameter. For a deep FNN, includes weights and biases of all the hidden layers in the network. However, as discussed in [13], it is infeasible to apply regularization to all the hidden layers in deep FNN due to the diversity and high sensitivity of the regularization hyperparameters in different hidden layers. Hence, [13] only applies 1 regularization to the first hidden layer of their DeepPerf model, which achieves a great improvement on performance prediction. The disadvantage of such strategy is that the sparsity of the whole network is controlled only by the regularization of the first hidden layer. In this case, the behavior of the model heavily depends on the regularization hyperparameter of the first hidden layer and even small changes of may cause large fluctuations in prediction accuracy. Therefore, one should carefully search for the optimal hyperparameter value on a large numerical space in order to achieve desired results, which increases the cost of hyperparameter tuning. Taking the advantage of the hierarchical network architecture of our HINNPerf model, we suggest to apply 1 regularization to the first layer of the FNN in each block with one global regularization hyperparameter, as shown in Figure 1 (left). The loss function of our method is changed to: Such hierarchical regularization technique allows us to shrink the parameters of unnecessary interactions in different orders and thus is more flexible and effective. In our experiments, we show that our method is more robust to the regularization hyperparameter and our hyperparameter search space is reduced by 6 times compared to the DeepPerf model [13].

Complexity Analysis
We now analyze the complexity of our HINNPerf model through the scale of network parameters. For model construction, we set the number of hidden layers and the number of hidden neurons to be the same in all blocks, that is, we set 1 = 2 = · · · = = and 1 = 2 = · · · = = . According to Equation (3), the -th block of HINNPerf has ( + 1) + ( − 1) ( + 1) + ( + 1) ( + 1) parameters, where: • the first term ( + 1) comes from the weights W ,1 ∈ R × and biases b ,1 ∈ R of the first hidden layer; • the second term ( − 1) ( + 1) corresponds to the weights W , ∈ R × and biases b , ∈ R (2 ≤ ≤ ) of the last − 1 hidden layers; • the third term ( +1) ( +1) is produced by the weights and biases of the interaction embedding (W , ∈ R × , b , ∈ R ) and the partial performance output (W , ∈ R , , ∈ R).
Hence, the scale of network parameters in the -th block is O ( + 2 ), implying total O ( 2 + 2 ) complexity of the HINNPerf model. On the other hand, suppose that the DeepPerf [13] model has ′ hidden layers and the same neurons in each hidden layer as HINNPerf, the total complexity of DeepPerf is O ( + ′ 2 ). Note that < ′ since the number of hidden layers in each block of HINNPerf is typically smaller than the total number of hidden layers in DeepPerf, and we roughly have ≈ ′ . Accordingly, HINNPerf mainly increases O ( 2 ) complexity compared to DeepPerf. However, based on the previous works [42,43,45] revealing that there are at most five-way interactions in configurable systems, we restrict ≤ 5 in our model. Therefore, the increase in model complexity caused by the parameter could be regarded as constant (i.e., . Another question is that how many configuration options can be handled by our model? Is there an upperbound of the option number for HINNPerf ? We state that according to the the universal approximation theorem [18,26,29] of deep neural networks, there is no theoretical upperbound of under our HINNPerf architecture. Theoretically, HINNPerf can predict the performance of complex systems with arbitrary number of configuration options. The complete theoretical proof is beyond the scope of this paper, and here we intuitively justify the statement using the main theorem from [29]: Theorem 1 (main theorem). Under certain assumptions, it holds that for any function : R → R with given approximation error , there exists a positive integer , and a fully connected and feedforward deep neural network of = ⌈log 2 ⌉ hidden layers, with inputs and a single output and with ReLU activation such that: where the constant depends on certain assumptions, but not on .
All the assumptions and the complete proof of the above theorem can be found in [29]. Note that as → ∞ or → 0, we have < ∞ and thus < ∞, implying that for any value of , there always exists a deep FNN that can approximate the function with proper error . When it comes to our HINNPerf architecture, the -th block employs a deep FNN with hidden layers to approximate the performance subfunction : R → R under an error bound ≤ √︃ 2 . Therefore, we conclude that in theory HINNPerf can approximate the performance function of configurable systems having arbitrary configuration options without upperbound. And we show that the approximation error of HINNPerf is smaller than other baselines in the experiment part of this paper.

Model Advantages
3.5.1 Beyond the Accuracy. Although the goal of our method is to improve the prediction accuracy of the performance model, the proposed hierarchical architecture allows us to extract some valuable information about the configurable system. First of all, by measuring the contributions of different partial performance functions (x ) to the whole performance function (o) in Equation (2), we can obtain some insights about the influences of different interactions on the system performance. If the partial function of lower-order interactions (e.g., 1 (o)) has the major contribution, it implies that the interactions among different configuration options are relatively simple and each option tends to affect the system performance independently (i.e., the configuration options are designed to be relatively disentangled). On the contrary, if the partial function of higher-order interactions (e.g., (x )) has the major contribution, the feature interactions of the software system might be very complex and more careful configuration decisions should be considered when deploying the configurable system. Second, by computing the significance score of each configuration option in different blocks, we can identify which options have the greatest impact on different partial performance functions (x ). Recognizing significant options in different interaction orders (i.e., different blocks) could help users and developers efficiently pinpoint the key performance factors and reveal some potential interaction patterns of the system. The above two advantages make our model more helpful to users and developers than other deep learning methods such as DeepPerf [13].
We will show these insights of different real-world subject systems in the experimental part of this paper.

Generality.
If we only use one block and empty interaction embedding function (i.e., = 1 and 1 (·) = ∅), our HINNPerf architecture reduces to the DeepPerf model [13]. Therefore, DeepPerf can be viewed as a special case of our method. From this point of view, HINNPerf shows a general deep learning framework for performance prediction of configurable systems. And we believe that more advanced deep learning performance models can be derived from this framework.

Training Details
To train our proposed model, we utilize the following technical practice of machine learning: • Dataset separation: As in most machine learning scenarios, we split the performance dataset into training, validation, and testing sets. We use the training set to optimize the model parameters, the validation set to search for the hyperparameters and the testing set to evaluate the model accuracy. • Data normalization: To speed up network training process and facilitate hyperparameter tuning, we normalize the input and the output of the training data. There are two kinds of normalization techniques: maximization and Gaussian normalization. The former normalizes the data in [0, 1] and the latter normalizes the data to a Gaussian distribution. We use the validation dataset to choose the better normalization technique. During testing, we normalize the testing dataset by exactly the same parameters of normalization during training, and then denormalize the model predicted output for accuracy evaluation. • Loss function: The loss function of our approach is the mean square error between the real performance values and the predicted output, which is the common regression loss function in machine learning. • Optimization: We utilize the Adam [23] algorithm to train our neural network. During the training process, the batch size is equal to the whole sample size of the training dataset since the size of the training data is small for performance prediction problem. • Hyperparameter setting: We conduct a grid search over all hyperparameters of our method.
We fix the initial learning rate to be 0.001 and employ a learning rate schedule that drops the rate by a factor of 10 −3 after every training epoch. We vary the number of blocks in {2, 3, 4, 5} (i.e., the hyperparameter in Equation (2)) since the interactions among different options are at most five-way [42,43,45]. Also, we choose the number of hidden layers in each block from {2, 3, 4} and fix the number of neurons in each hidden layer to be 128. The 1 regularization hyperparameter is chosen from {0.001, 0.01, 0.1, 1, 10}. The optimal hyperparameter setting is the setting that achieves the smallest validation error.
Finally, we implement our proposed method HINNPerf using Python 3.6 and Tensorflow 1.13.0 [1] under a machine with one NVIDIA GeForce GTX 1080 GPU and one Intel(R) Core(TM) i7-6800K CPU 3.40GHz.

EVALUATION
The core of this section is to evaluate whether our method can better model the complex interactions in real-world configurable systems and accurately predict the performance with a small training sample (i.e., the two challenges mentioned in Section 1). Specifically, we aim at answering the following research questions (RQ): • RQ1: How accurate is our approach in predicting performance of configurable software systems?
• RQ2: Are the proposed hierarchical interaction embedding architecture and the hierarchical 1 regularization strategy necessary for improving prediction accuracy? • RQ3: How do the 1 regularization hyperparameter and the interaction order affect the efficacy of HINNPerf ? • RQ4: In addition to predicting performance values, can HINNPerf provide some insights on configuration coupling and help users and developers find out significant configuration options in the performance model? • RQ5: What is the time cost of training and testing the HINNPerf model for performance prediction?
We next conduct different experiments to answer the RQs above, comprehensively demonstrating the effectiveness, robustness and practicality of our approach.

Evaluation Metric
As described in Section 3.6, we use the training and validation datasets to generate a performance model for each system, and then use this model to predict the performance values of configurations on the testing dataset. Similar to [12][13][14]42], we utilize the mean relative error (MRE) to evaluate the model's prediction accuracy: where T denotes the testing dataset, (o) is the actual performance value of configuration o, and (o) is the predicted performance value of configuration o. In our experiments, we consider 10 real-world configurable software systems from different domains, including video encoders, database systems, multi-grid solvers, image processing frameworks, compilers, etc. Five of these systems only have binary configuration options and the other five systems have both binary and numeric configuration options. Different systems have different sizes (from 45 thousands to more than 300 thousands lines of code) and are written in different programming languages (Java, C, and C++). Table 2 provides an overview of the subject systems.

Subject Systems
According to previous work [13,22,42,43], the performance datasets of the ten subject systems are collected in the following way: • x264 is a video encoder for the H.264 compression format. Relevant configuration options included the number of reference frames, enabling or disabling the default entropy encoder, and the number of frames for ratecontrol and lookahead. We have measured the time to encode the Sintel trailer (734 MB) on an Intel Core Q6600 with 4 GB RAM (Ubuntu 14.04). • BDB-J is the Java version of the Berkeley Database. we use Oracle's standard benchmark to measure the performance of BDB-J. The workload produced by the benchmarks is a typical sequence of database operations. • LRZIP is a file compression tool. We consider configuration options that define, for instance, the compression level and the use of encryption. We used the uiq28 generator to generate a file (632 MB), and we measured the time for compressing this file with version 0.600 on a machine with AMD Athlon64 Dual Core, 2 GB RAM (Debian GNU/Linux 6). • HIPA is an image processing acceleration framework, which generates efficient low-level code from a high-level specification. Binary options are, among others, the kind of memory to be used (e.g., texture vs. local). The number of pixels calculated per thread is an example of a numeric option. We measured the time needed for solving a test set of partial differential equations on an nVidia Tesla K20 card with 5GB RAM and 2496 cores (Ubuntu 14.04). • HSMGP is a highly scalable multi-grid solver for large-scale data sets. Binary options include in-place conjugate gradient and in-place algebraic multi-grid solvers. Numeric options include the number of smoothing steps and the number of nodes used for computing the solution. As a benchmark, we performed a multi-grid iteration of solving Poisson's equation. We executed the benchmark runs on JuQueen, a Blue Gene/Q system, located at the Julich Supercomputing Center, Germany. • JavaGC is the Java garbage collector (version 7) with several options for adaptive garbagecollection boundary and size policies. For measurement, we executed the DaCapo benchmark suite on a computing cluster consisting of 16 nodes each equipped with an Intel Xeon E5-2690 Ivy Bridge having 10 cores and 64 GB RAM (Ubuntu 14.04). • SaC is a variant of C for high-performance computing based on stateless arrays. The SaC compiler implements a large number of high-level and low-level optimizations to tune high-level programs for efficient parallel executions. The compiler is highly configurable, allowing users to select various optimizations and to customize the optimization effort (e.g., optimization cycles and loop-unrolling threshold). As benchmark, we compile and execute an n-body simulation shipped with the compiler, measuring the execution time of the simulation at different optimization levels. We executed all benchmarks on an 8 core Intel i7-2720QM machine with 8 GB RAM (Ubuntu 12.04).

RQ1: Performance Prediction Comparison
4.3.1 Baselines. As introduced in Section 1, many learning methods have been proposed to predict performance values of configurable systems with binary and/or numeric options, including SPLConqueror [42,43], Fourier methods [14,52], DECART [12], and DeepPerf [13]. Besides, traditional machine learning methods such as Random Forests [17] (RF) can also be used for the performance prediction task. For configurable systems with only binary options, DECART and DeepPerf are recent advanced methods and can achieve higher prediction accuracy than others [12,13]. Therefore, to save experiment time, we only compare the proposed method with three baselines DECART, DeepPerf and RF on binary systems. For configurable systems with both binary and numeric options, we compare the effectiveness of our HINNPerf model with that of SPLConqueror, DeepPerf and RF, since the DECART model cannot deal with numeric options.

Setup.
Following the experiment setup in [13], we randomly select a certain number of configurations and their corresponding performance values to construct the training and validation datasets (sample 3 ), and use the remaining configuration measurements as the testing dataset. For each subject system, we test the model accuracy under different sample sizes. The sample sizes of each binary system are , 2 , 4 , 6 , where is the number of binary options of each system (shown in the column |B| of Table 2); for each binary-numeric system, we choose the same sample sizes that SPLConqueror suggested [42]. Same as in [13], for DECART, DeepPerf, RF and our HINNPerf methods, we repeat the random sampling, training and testing process 30 times, and then report the mean and the 95% confidence interval of each method's MRE obtained after 30 experiments. For SPLConqueror, however, we cannot choose a random sample since it combines different sampling heuristics for binary options (e.g., option-wise (OW), pair-wise (PW), etc), and several experimental design methodologies (e.g., Plackett-Burman (PBD), Random Design (RD), etc) for numeric options to predict system performance. Each combination of sampling heuristics and non-random experimental designs yields a unique sample, implying that repeating 30 experiments for SPLConqueror produces exactly the same results and thus the variance of the 30 experimental results is zero. Hence, we only report the MRE of SPLConqueror on the testing dataset since the 95% confidence interval is also zero when the variance is zero [13]. Moreover, we check whether there is a statistically significant difference between the results of the best and the second best methods by using the Wilcoxon rank sum test [7], a non-parametric test that compares different distributions. When the -value is smaller than 0.05, we consider that there is a significant difference and report the significantly better method.
To replicate the results of SPLConqueror, DECART and DeepPerf, we utilize the code published on their supplement websites and run their models with the best hyperparameter settings [12,13,42]. For the RF method, we use the function RandomForestRegressor in scikit-learn package [37] to perform model training and prediction. To select the best hyperparameters for RF, we construct the grid search by varying four hyperparameters in RandomForestRegressor: 10 values of n_estimators ranging from 10 to 1000, 10 values of min_samples_leaf ranging from 0.05 to 0.5, 10 values of max_leaf_nodes ranging from 2 to 100 and the max_features are auto, sqrt or log2. With this setting, the hyperparameter space contains 3000 different combinations of hyperparameter values. Hence, we believe it is sufficient enough to find the optimal setting for RF.  Table 3 summarizes the performance prediction results of each approach on the 10 subject systems with small and large sample sizes, from which we obtain the following observations:

Results.
• Our method clearly outperforms other approaches on most of the subject systems, showing the superiority of hierarchical interaction network design for performance prediction. Specifically, HINNPerf achieves best prediction accuracy on 7 out of 10 systems, reducing the MRE by an average of 22.67% compared to the second best results of other baselines. Remarkably, HINNPerf achieves the best 54.35% improvement on the x264 system with 6 sample size. Among the 7 winning systems, the Wilcoxon test shows that HINNPerf significantly outperforms the second best method on 5 of them. For the other 3 systems LRZIP, POLLY, and HSMGP, HINNPerf and other methods perform quite similarly without significant difference between them. On the other hand, we observe that the sample size of in systems with only binary options seems too small to train each performance model for achieving good accuracy. As we can see from Table 3, the prediction MREs of all models under sample size are more than twice higher than the MREs under sample size 2 on the x264, BDB-J, LRZIP, and POLLY systems, respectively. What's worse, the MREs of all models under the sample size of the LRZIP system are more than 100%, implying that all performance models cannot work when trained in this case. Therefore, the prediction results under sample size may not really reveal the efficacy of each performance model. • We conduct the Wilcoxon test on the prediction results of our method and the most related deep learning method DeepPerf [13]. It shows that HINNPerf significantly outperforms DeepPerf over all of the 5 systems with both binary and numeric configuration options (i.e., Dune MGS, HIPA , HSMGP, JavaGC, and SaC). Since binary-numeric interactions are usually more complicated than binary-binary interactions [13,42], the result of the Wilcoxon test demonstrates that our method can better model the influences of complex interactions on system performance. • Since the major contribution of the performance model is to accurately predict the performance when only a small subset of data samples is avaliable for training, it is important to evaluate the accuracy of each performance model under a small sample size. From Table 3, except for the BDB-J system, the smallest sample size used for training is less than 5% of the total number of data samples measured for each system. Using these small data subsets, our HINNPerf model achieves a prediction accuracy of more than 83% (i.e., MRE less than 17%) on 9 out of 10 systems, with accuracy of 5 systems (i.e., x264, BDB-J, VP9, HIPA , and HSMGP) more than 90%. Besides, our method outperforms other baselines on 7 out of 10 systems under the smallest sample size. Therefore, we conclude that our proposed HINNPerf model can still attain a good accuracy when trained with only a small subset of data samples. Furthermore, to obtain the same level of accuracy, HINNPerf needs fewer data than other methods. For example, with the system JavaGC, HINNPerf only needs 2571 sample to achieve a prediction MRE of 10.02% (i.e., accuracy of 89.98%) whilst DeepPerf needs 5312 (more than 2 times) sample to obtain the similar prediction accuracy. These observations demonstrate the effectiveness of our approach in small sample predictions. • We observe that there are some differences in the prediction MREs of different systems.
For example, the prediction MRE of all performance models on the LRZIP system is much higher than other subject systems, probably due to the large scales and variance of the performance value of the LRZIP system (see Table 2). It seems that the scales and variance of the performance metrics may be an issue affecting the prediction accuracy of the performance model, and the data with larger variance is more difficult to predict. This observation inspires us that, in practice, it is better to properly control the data variance when measuring the performance of a configurable system to train the performance model. Since the goal of this paper is to design a novel performance model that outperforms other state-of-the-art models, we demonstrate the effectiveness of our model only using the public benchmark datasets [13,22,42,43] without changing the scales and variance of the datasets. Instead, we show that our HINNPerf model achieves better accuracy on most systems with performance metrics having different scales and variance.
In summary, compared to existing methods, our proposed architecture HINNPerf provides a more effective and accurate deep learning performance model to address the interaction modeling and the small sample challenges mentioned in Section 1.

RQ2: Effectiveness of Architecture Design
Our method consists of two key components, the hierarchical interaction embedding (Equation (2)) and the hierarchical 1 regularization, as shown in Figure 1. In this experiment, we aim to evaluate whether these two components are necessary to improve performance prediction accuracy, or they can be substituted by other techniques. To show the effectiveness of each component, we compare HINNPerf with following design alternatives: • MB-FNN : We remove the hierarchical interaction embedding from the HINNPerf architecture. In this way, the neural network reduces to a multi-block FNN with 1 regularization on the first layer of each block. • L2-HINN : We replace the 1 regularization of HINNPerf with 2 regularization.
• Plain-HINN : This architecture is simply the HINNPerf model without regularization.
We evaluate each architecture on the 10 subject systems and compare the prediction results with the HINNPerf model.

Setup.
For all the alternative models, we also use the same grid search strategy to tune the hyperparameters. All the hyperparameter settings are the same as those for HINNPerf. Except that, for Dropout-HINN, the search range for the dropout rate is {0.1, 0.25, 0.5, 0.75, 0.9} since the dropout rate needs to be ≤ 1. Table 4 shows the prediction MREs of HINNPerf and 4 alternative methods. Overall, HINNPerf achieves the best accuracy on most subject systems. Comparing the results of HINNPerf and MB-FNN, we find that removing the interaction embedding from the architecture causes a large accuracy drop overall (e.g., on average, 58% accuracy drop on VP9 and 68% accuracy drop on POLLY), which demonstrates that the hierarchical interaction embedding plays an important role in improving the prediction accuracy of our performance model. Hence, we believe that it is worth introducing the embedding method to further improve deep learning performance models, confirming our discussion in Section 2.4.

Results.
On the other hand, removing the regularization technique from HINNPerf (i.e., the Plain-HINN model) causes the most significant accuracy drops, since a deep neural network is prone to overfit on training data. The L2-HINN and Dropout-HINN methods perform much better than Plain-HINN but are still less effective than HINNPerf. These observations show that the hierarchical 1 regularization architecture may be the most important component for our approach.
In conclusion, both the hierarchical interaction embedding and the hierarchical 1 regularization techniques are necessary for prediction accuracy improvement. The full HINNPerf architecture is the most accurate and effective peformance model for configurable systems when compared to other alternatives.

Robustness of Regularization.
In the context of performance prediction with small sample, the 1 regularization hyperparameter of Equation (5) is crucial for the model accuracy. Usually, it takes effort and time to search for the optimal hyperparameter value. DeepPerf conducts grid search with 30 points logarithmically spaced in the range [0.01, 1000] to find the best value for the 1 regularization hyperparameter [13]. However, for the regularization hyperparameter of our proposed approach, we only use grid search with 5 points in {0.001, 0.01, 0.1, 1, 10} to obtain better accuracy than DeepPerf, reducing the search space by 6 times. We believe that the reduction of hyperparameter space benefits from the improvement of the model robustness. In this experiment, we demonstrate our hypothesis by testing the sensitivity of our model to the regularization hyperparameter and compare the results with DeepPerf. Figure 2 shows the prediction MREs of the two methods under different hyperparameter values logarithmically spaced in the range [0.001, 100]. We present the results on 9 subject systems except the HSMGP system, since our method seems to make insignificant improvement on the HSMGP system from Table 3. We can observe that HINNPerf is much less sensitive to the changes of regularization hyperparameter than DeepPerf on most systems, demonstrating better robustness of our model. Hence, we conclude that the hierarchical 1 regularization strategy makes HINNPerf more robust to the regularization hyperparameter and thus we can search for the optimal hyperparameter value on a much smaller space.

Impact of Interaction
Order. In our experiment, HINNPerf chooses the interaction order (i.e., the number of blocks) from {2, 3, 4, 5} and learns the best order value for each system from the data. We set the upper limit of to 5 degrees rigorously based on the findings of previous work [42,43,45] that the interaction order of configurable systems is at most five. Moreover, it is necessary to investigate how different values of affect the efficacy of HINNPerf on each system. Hence, we fix the hyperparameter to a default value of 1, 2, 3, 4, 5, 6 respectively and train the HINNPerf to predict the performance of the ten subject systems. Here we additionally evaluate = 6 to see how the HINNPerf behaves when > 5. Figure 3 presents the prediction errors of HINNPerf under different interaction orders. It can be observed that each system has its own best interaction order and increasing or decreasing the optimal value of will reduce the performance prediction accuracy. We thus conclude that learning the interaction order from the data of each  system is better than setting a default value manually. Besides, we find that setting = 6 does not cause significant differences 4 with ≤ 5, showing that it is possible for the HINNPerf to learn the information of interaction order higher than 5. However, to keep the consistency with previous work [42,43,45], we only consider ≤ 5 in this paper and leave the exploration with > 5 to future work. 4.6 RQ4: Model Practicality 4.6.1 Coupling Complexity. We leverage the hierarchical architecture of HINNPerf to investigate whether the performance of the configurable systems is mainly affected by lower-or higher-order interactions, so as to provide additional insights into the complexity of coupling among configuration options. As discussed in Section 3.5.1, we first train the HINNPerf model with the training dataset of a configurable system, and then predict the values of each partial performance function (·) and the final output (·) of Equation (2) on the testing dataset. We measure the contribution of each partial function (·) to the whole performance function (·) through computing the average percentage: where T denotes the testing dataset, (o) is the performance value of configuration o, (x ) is the -th partial performance value of configuration o, is the number of subfunctions/blocks learned by HINNPerf. As we describe in Section 3.1, different subfunctions (·) learn the influences of different interaction orders. Therefore, the average percentage allows us to measure how much of the -th order interaction affects the system performance. Figure 4 shows the contributions of different partial functions on the 10 subject systems, from which we obtain the following important observations: • Most configurable software systems have up to 3 partial performance functions with the second and the third subfunctions 2 (·), 3 (·) having the most significant influence on the system performance. Since subfunctions 2 (·) and 3 (·) of our method aims to learn partial performance values of higher-order interactions, this observation implies that multi-way hierarchical interactions are common in configurable software systems and the most common interaction patterns might be two-way and three-way. These findings are consistent with previous work [42] and demonstrate the feasibility of employing a hierarchical interaction architecture such as HINNPerf to model the interactions among configuration options. • For the system VP9 where the lower-order subfunction 1 (·) has the major influence on the system performance, HINNPerf tells us that the configuration options of this system are relatively decoupled and have simple interactions. Accordingly, when using systems such as VP9, users can make moderately casual decisions on configuration selections without paying much attention to feature interactions. And developers can optimize each configuration option relatively separately to improve software performance. • For the LRZIP system, however, the lower-order subfunction 1 (·) has a significant positive influence on the system performance while higher-order subfunctions 2 (·) and 3 (·) have negative influences, implying more complex relationships among configuration options. This may warn developers and users to carefully consider the feature interactions when deploying and using the system. Also, the JavaGC system should have similar concerns. The observations above demonstrate that our HINNPerf model provides some insights about which kind of interactions have the most siginificant influence on the system performance. And  we believe that these insights can help users and developers better understand the complexity of system coupling and make more rational decisions when deploying and using configurable systems. Note that HINNPerf automatically learns these insights from data without any manual intervention, which ensures the objectivity and the efficiency of our model. While employing the HINNPerf to automatically select the best value of for each system seems promising, we also interested in how HINNPerf reveals the coupling complexity when a default value of is used. Besides, for the HSMGP system in Figure 4, it could be worth testing for the six levels of interactions (i.e., = 6). Hence, we fix the hyperparameter to a default value of 3, 4, 5, 6 respectively and train the HINNPerf to learn the contribution of each partial function. Figure 5 shows the results under different values of , most of which are consistent with Figure 4. For example, Figure 4 shows that for the x264, POLLY, Dune MGS, HIPA , JavaGC and SaC systems, the third-order interaction (i.e., 3 ) has the most significant influence on the system performance. This is also true in Figure 5, no matter = 3, 4, 5 or 6. And Figure 5d shows that the contribution of the 6-th interaction order has insignificant contribution to the performance of all systems, including the HSMGP. Therefore, we believe that HINNPerf can still capture the importance of each interaction order when a (proper) default value of is used.

Option Significance.
Based on previous insights about the percentage importance of different interaction orders, we further explore the significance of every configuration option in each interaction level. Recognizing the option significance in different interaction orders could help us pinpoint the options that have great impact on the performance and also provide some insights about the interaction patterns. Here we employ the Integrated Gradients [47] method to assign a significance score to each configuration option: where is the -th option of the configuration o, o ′ ∈ R is the baseline zero vector and (·) denotes the performance function. We compute the significance score of each option in different blocks of HINNPerf and report the option significance of three subject systems x264, SaC and HIPA in Figure 6 for examples. Comparing the option significance in different configurable systems, we can further extract some valuable information for both users and developers: • For most configurable software systems, only a small number of configurations and their interactions have significant impact on the performance. Figure 6 shows that there are only 3/16, 4/60 and 4/33 significant configuration options in the x264, SaC and HIPA systems, respectively. This finding is also consistent with all the previous work [13,42,43]. The main contribution of our work here is that we recognize the specific significant options through automatic learning without any manual efforts. For example, we can identify that the performance of the x264 system is mainly affected by three significant options no-mixed-refs, ref-1, and ref-9 from Figure 6a. • Combining with insights about coupling complexity in the previous section, we can quickly pinpoint configuration options that might have the greatest impact on the system performance.
For instance, Figure 4 shows that the third-order interactions ( 3 ) contribute the most to the SaC system performance, which corresponds to Block 3 in Figure 6b. Accordingly, we could roughly infer that the most significant options dcr and maxwlur in Block 3 has the greatest influence on the performance of SaC, so as to remind users and developers to pay special attention to these two options when using the system. • The option significance in different interaction orders also reveals some potential interaction patterns of the configurable system. For the HIPA system in Figure 6c, the LocalMemory and the pixelPerThread options have the greatest importance in the first-order interaction (Block 1). After entering into the second-order interaction (Block 2), the contribution of the CUDA option increases. Finally in the third-order interaction (Block 3), the CUDA, Ldg, and LocalMemory options maintain positive significance while the pixelPerThread option changes into negative significance. This observation inspires us that the HIPA system might have interaction patterns in the following form: (LocalMemory, pixelPerThread) + (CUDA, LocalMemory, pixelPerThread) where , , could be arbitrary interaction functions. Such an interaction form is intuitive since the usage and communication of the local memory between CPU and GPU (CUDA) can significantly affect the system performance, while the number of pixels calculated per thread is also highly related to the local memory capacity and the GPU computing power.
In summary, by inspecting the option significance in different interaction orders learned by HINNPerf, one can efficiently locate the small subset of configuration options and their interactions that have the greatest impact on system performance, instead of wasting a huge amount of time searching hard through a large number of configurations. Besides, HINNPerf can provide some insights on potential interaction patterns of the system through the hierarchical interaction architecture. We believe these advantages are more actionable for users and developers to deploy and test the configurable software systems. Although our method attains higher prediction accuracy and is more robust to the regularization hyperparameter than other approaches, it is also a more complex architecture with quantities of trainable parameters. Therefore, to evaluate the practicality and feasibility of our approach, it is necessary to measure the time consumed by the training and the testing process of HINNPerf. Since we implement the two deep learning methods DeepPerf and HINNPerf under CPU and GPU environment while the other methods SPLConqueror, DECART and RF under the environment without GPU, we only report the time cost of DeepPerf and HINNPerf on 10 subject systems with maximum sample size. As shown in Figure 7 (left), for all the systems with various configurable options, it takes HINNPerf 14 -16 minutes to do model training and hyperparameter searching, while DeepPerf spends 5 -13 minutes. Even though HINNPerf takes longer time to train the performance model than DeepPerf, the time cost of HINNPerf is still acceptable. As for testing process, Figure 7 (right) shows that both methods perform similarly with time cost less than 0.2 seconds, which is consistent with our analysis in Section 3.4 that HINNPerf only increases constant complexity than DeepPerf.
In addition to model complexity, the main reason why the training of our method is more timeconsuming than DeepPerf is that DeepPerf employs a more efficient hyperparameter search strategy. It first searches the optimal number of hidden layers for a non-regularized FNN. After applying the same number of hidden layers as the non-regularized FNN on the DeepPerf architecture, it then searches for the best regularization hyperparameter value. Such a separation hyperparameter search strategy can significantly reduce the hyperparameter space, but it is not suitable for all deep neural network architectures (i.e., not universally applicable). What's worse, this strategy risks hurting model accuracy because the optimal hyperparameters of the non-regularized FNN may not be optimal for DeepPerf. Instead, we directly search all optimal hyperparameters for the HINNPerf architecture, slightly increasing the training time but guaranteeing high prediction accuracy. Besides, compared to the search strategy with accuracy drawdown risk, it is more reasonable to develop a robust network structure to reduce the hyperparameter space.

Strengths and Limitations.
The main strength of our HINNPerf method is that it can model complicated interactions among the configuration options and attain higher prediction accuracy on various configurable systems than other state-of-the-art approaches. As shown in our experiments, for most of the software systems with binary and numeric options, compared to other baselines, HINNPerf achieves higher prediction accuracy with less sample. For software systems with binary options, HINNPerf can achieve better or comparable results compared to other methods.
HINNPerf 's second strength is that it provides additional insights about the contributions of different interactions to the system performance and significant configuration options in different interation orders, which could reveal some potential interaction patterns of the configurable system and help users and developers efficiently make rational decisions on configurations. We emphasize that unlike the SPLConqueror method [42], HINNPerf learns these insights from data automatically without any human efforts to design the interaction patterns. Another automated approach DeepPerf [13] does not show any additional insights in addition to performance prediction. Hence, compared to other performance models, our method is more efficient and helpful for users and developers.
Finally, the third strength of HINNPerf is that it is less sensitive to the regularization hyperparameter and more robust than another deep learning method DeepPerf [13]. Therefore, our method effectively reduces the hyperparameter tuning cost and improves the training efficiency.
The major limitation of HINNPerf is that it takes longer time to train than other baseline methods. However, considering the benefits of accuracy improvement and interaction insights brought by HINNPerf, it is worth taking slightly more time to train a more useful performance model. Also, we will optimize the network structure and explore more efficient deep learning methods in the future work.

Difference with DeepPerf.
Although our method is designed based on the feedforward neural network (FNN) as DeepPerf, HINNPerf is significantly different from DeepPerf in the following aspects. First, HINNPerf is a deep neural network model specially designed for performance prediction of configurable systems, which considers the unique characteristics of hierarchical interaction patterns in configurable systems. However, DeepPerf is a general FNN model that has been widely used in deep learning field without specific design for the configurable systems. From this point of view, HINNPerf makes an essential contribution to the field of deep learningbased performance prediction than DeepPerf. Second, the hierarchical network architecture design allows HINNPerf to recognize important options in different interaction orders and reveal some potential interaction patterns of configurable systems, which could help users and developers better understand how configurable systems work and efficiently identify significant options affecting the performance. This makes HINNPerf more interpretable and practical than DeepPerf which cannot provide any information about the internal interaction structure in configurable systems. We believe that the advantages guarantee the novelty and contribution of our method.

Effectiveness of Neural Networks.
Although deep neural networks generally requires large data for training, the superiority of DeepPerf and HINNPerf over traditional machine learning (ML) methods such as SPLConqueror, DECART and RF shows that deep neural networks are also effective in the performance prediction domain with small data. The main reason is probably that the excellent non-linear learning ability enables neural networks to better capture the complex interactions between different configuration options. Although traditional ML methods are more intuitive to process small data, the poor learning ability prevents them from learning the complicated interactions and achieving higher accuracy in the performance prediction task domain. Instead, as demonstrated in Section 4.6 (RQ4), the non-linear activation mechanism in the neural network allows it to extract richer information from the data to compensate for the shortcomings of the small sample. Therefore, it is necessary to employ deep neural networks to better learn the complex hierarchical interaction patterns in configurable systems and attain higher accuracy for performance prediction, which has been demonstrated by the experiment results in Section 4.3 (RQ1).

Threats to Validity.
For internal validity, to minimize the measurement bias of random sampling, we select samples of different sizes from each subject system to train all the methods, and then evaluate the prediction accuracy of each method on a test dataset. The test dataset excludes all the configurations of the training and validation datasets so as to evaluate the real predictive ability of each model. Besides, we repeat the random sampling, training and testing process 30 times and report the averages and the 95% confidence intervals of the mean relative error for analysis. In this way, we believe that we control the measurement bias sufficiently and the experimental results reported in this paper are solid.
To increase external validity, we evaluate all the approaches on public datasets of 10 configurable systems. These systems are from different domains, with varying number of configuration options and different implementation languages. Although there is no guarantee that our method works for all other configurable systems, we are confident that the extensive experiments in this paper control this threat sufficiently.
The workload used to measure the configurable systems is also an important factor which can influence system performance but ignored by our work. The related studies [11-14, 22, 42, 43, 52] have not considered the workload factor either, which may be attributed to the great difficulty in quantifying the factor. According to previous work [22,42,43], all the datasets of the ten subject systems used in our experiments are collected under different workload settings, probably leading to mix workload in the data. However, in this work, we focus on designing a novel model for more accurate performance prediction. Thus, for fair comparison with the previous work, we directly adopt the widely-used public datasets released by [22,42,43]. With same datasets for comparison, the mix workload would not be an issue in our study, and the influence of workload on the performance prediction task is avoided. The experiment results in Table 3 demonstrates that our method can achieve the state-of-the-art accuracy in different workload settings. In future work, we will explore the influence of the workload on performance modeling.

RELATED WORK
Modern software systems are becoming increasingly complex and large-scale. Since poor performance can often be the cause of software project failure, how to manage system performance concerns along the software lifecycle has attracted great attention in the research and software industry communities [20,[53][54][55]. For large-scale configurable systems, understanding the influences of the configuration options and their interactions on system performance plays an important role in software testing and maintenance phases [14].
Recently, software researchers have conducted a large amount of work on performance prediction of highly configurable systems. In Section 1, we have discussed pros and cons of most state-of-theart approaches, including SPLConqueror [42][43][44], CART/DECART [11,12], Fourier methods [14,52], and DeepPerf [13]. Throughout the history of performance models, the evolution of prediction methods tends to sacrifice the interpretability of the model to improve the prediction accuracy. SPLConqueror [42][43][44] is an early linear regression model that achieves low accuracy but can explicitly show the influences of configuration options and their interactions through regression coefficients. Later, CART/DECART [11,12] employs decision trees to improve the prediction accuracy for binary configurable systems, but can only qualitatively measures the feature importance through the tree structure. Recently, DeepPerf [13] utilizes deep feedforward neural networks to greatly improve the performance prediction accuracy, but with the model interpretability completely lost. On the other hand, the major contribution of Fourier learning [52] is to derive a sample size that guarantees a theoretical boundary of the prediction accuracy. However, it attains no significant improvement in model interpretability and accuracy compared to SPLConqueror and CART/DECART, which is why we do not compare our model with Fourier methods in this paper.
Although our proposed HINNPerf approach mainly focuses on achieving higher accuracy with less sample for performance prediction of configurable systems, we also make some progress in model interpretability by introducing the hierarchical interaction network architecture. In this way, users and developers can better understand how different interactions influence the system performance and make rational configuration decisions to maximize software efficacy. Besides, there is also some work on increasing explainability of the performance model by measuring the uncertainty in performance estimations with Bayesian method [5]. We will also consider the uncertainty measurement of our method in the future work.
Another related research topic is to select an optimal sample of configurations. Sayyad et al. [40,41] propose evolutionary methods to select optimal features under multiple objectives. Later, Christopher et al. [16] extend the multi-objective search-based optimization with constraint solver and improve Software Product Line (SPL) feature selection. Other researchers focus on selecting proper configuration option under certain coverage criterion [21,25,30]. Recently, Christian et al. [22] propose a distance-based sampling strategy to better cover different kinds of interactions among configuration options in the sample set. Since we aim to propose a novel learning method for performance prediction in this paper, our method only employs random sampling strategy to build a performance model. In fact, we can combine our approach with different sampling work to further improve the model accuracy.

CONCLUSION
In this paper, we propose HINNPerf, a novel hierarchical interaction neural network architecture for performance prediction of highly configurable systems. Our method decomposes the whole deep neural network into multiple hierarchical blocks and employs the embedding method to model the complex interactions among configuration options. Besides, we devise a hierarchical regularization strategy to ensure the model accuracy when trained on a small sample. The experimental results on public datasets show that HINNPerf can better learn the complicated interactions in configurable systems and achieve better performance prediction accuracy with less data, when compared to other state-of-the-art methods. Furthermore, our approach provides additional insights for users and developers and is more robust than the advanced deep learning method DeepPerf [13].
For future research, the proposed model can be further improved by incorporating effective sampling heuristics [22,42]. We will also explore the uncertainty measurement methods [5] to increase the interpretability of our approach.