# TEP-GNN: Accurate Execution Time Prediction of Functional Tests using Graph
Neural Networks

Hazem Peter Samoaa  Chalmers University of TechnologyGothenburgSweden
<EMAIL_ADDRESS>,  Antonio Longa  Fondazione Bruno Kessler and University
of TrentoTrentoItaly<EMAIL_ADDRESS>,  Mazen Mohamad  University of
GothenburgGothenburgSweden<EMAIL_ADDRESS>,  Morteza Haghir Chehreghani
Chalmers University of TechnologyGothenburgSweden
<EMAIL_ADDRESS>and  Philipp Leitner  Chalmers $|$ University
of GothenburgGothenburgSweden<EMAIL_ADDRESS>
###### Abstract.

Predicting the performance of production code prior to actually executing or
benchmarking it is known to be highly challenging. In this paper, we propose a
predictive model, dubbed TEP-GNN, which demonstrates that high-accuracy
performance prediction is possible for the special case of predicting unit
test execution times. TEP-GNN uses FA-ASTs, or flow-augmented ASTs, as a
graph-based code representation approach, and predicts test execution times
using a powerful graph neural network (GNN) deep learning model. We evaluate
TEP-GNN using four real-life Java open source programs, based on 922 test
files mined from the projects’ public repositories. We find that our approach
achieves a high Pearson correlation of 0.789, considerable outperforming a
baseline deep learning model. However, we also find that more work is needed
for trained models to generalize to unseen projects. Our work demonstrates
that FA-ASTs and GNNs are a feasible approach for predicting absolute
performance values, and serves as an important intermediary step towards being
able to predict the performance of arbitrary code prior to execution.

##  1\. Introduction

Performance is a critical quality property of many real-live software systems.
Hence, performance modeling and analysis have gradually become an increasingly
important part of the software development life-cycle. Unfortunately,
predicting the performance of real-life production code is well-known to be a
difficult problem – predicting the absolute execution time of applications
based on code structure is challenging as it is a function of many factors,
including the underlying architecture, the input parameters, and the
application’s interactions with the operating system (Ramadan2021, ).
Consequently, works that attempted to predict absolute performance counters
(e.g., execution time) for arbitrary applications from source code generally
report poor accuracy (Meng2017, ; Narayanan2010, ).

However, recent research has shown that predicting performance characteristics
is indeed possible in more specialized contexts, via the application of modern
machine learning architectures. For example, Guo et al. successfully predict
the execution time of a specific untested configuration of a configurable
system (guo:13, ; guo:18, ), Samoaa and Leitner have shown that the execution
time of a benchmark with specific workload configuration can be predicted
(samoaa:21, ), and Laaber et al. have shown that a categorical classification
of benchmarks into high- or low-variability is feasible (laaber:21, ).

In this work, we demonstrate that another context where performance prediction
is possible is the prediction of execution times of functional tests. Test
execution times are crucial in agile software development and continuous
integration. While individual test cases might have short execution times,
software products often have thousands of test cases, which makes the total
execution time in the build process high. Researchers have been working on
solutions to speed up the testing process by optimizing the code or
prioritizing test cases (codeOptimization1, ; testPrio1, ; testPrio2, ;
testPrio3, ). The goal of this study is to provide the developers with
predictions of the execution times of their test cases, and consequently
giving them an early indication of the time required to run the cases in the
build process. We believe that this would support decisions regarding code
optimization and test case selection in early stages of the software life-
cycle.

In this paper, we propose an approach dubbed TEP-GNN (Test Execution Time
Prediction using Graph Neural Networks) that makes use of structural features
of test cases (the abstract syntax tree, AST). In TEP-GNN we enrich the AST
with various types of edges representing data and control flow. Following Wang
and Jin, we refer to this resulting graph as flow-augmented abstract syntax
trees (FA-AST) (Wang20, ). We apply a graph neural network (GNN) deep learning
model, more specifically GraphConv (morris2019weisfeiler, ), on the resulting
FA-ASTs to predict execution times. We train and test our model on a dataset
collected from four well-known open source projects hosted on GitHub: H2
database111https://github.com/h2database/h2database, a relational database,
RDF4J222https://github.com/eclipse/rdf4j, a project for handling RDF data,
systemDS333https://github.com/apache/systemds, an Apache project to manage the
data science life cycle, and finally the Apache remote procedure call library
Dubbo444https://github.com/apache/dubbo. As labelled ground truth data, we
collect 922 real test execution traces from these projects’ publicly available
build systems.

Figure 1. Schematic overview of the main phases of TEP-GNN. Java unit tests
are parsed into ASTs, which get augmented with control and data flow edges.
The resulting graph is then used as input for a GNN.

We conduct experiments with our TEP-GNN model to answer the following research
questions:

  * •

RQ1: How accurately can the absolute execution time of a test file consisting
of one or multiple test cases be predicted using FA-ASTs and GNNs?

  * •

RQ2: Does our usage of GraphConv improve execution time prediction compared to
a baseline using Gated Graph Neural Networks (GGNN), as frequently used in
previous software engineering research (Fernandes2018, ; Allamanis2017, )?

  * •

RQ3: How well are models trained on a subset of projects transferable to
unseen other projects? Can a TEP-GNN model trained on a subset of projects
predict the execution time of tests in a project that was not used during
training?

Our results show that using TEP-GNN, test execution time can be predicted with
a very high prediction accuracy (Pearson correlation of 0.789). Further, we
show that our usage of GraphConv indeed improves the model significantly over
GGNN. Finally, we show that trained models are _not_ easily transferable. We
conclude that test execution times can indeed be predicted using GNN models
with high accuracy, even based on performance counters that have been
collected "in the wild" by real projects (as opposed to performance
measurements collected on a dedicated performance testing machine). Even
though test cases are shorter and structurally simpler than arbitrary
programs, we see our results as an important stepping stone towards the
prediction of the performance of arbitrary software systems prior to
execution. However, more work is needed to train general models that can be
applied to arbitrary, unseen projects.

##  2\. The TEP-GNN Approach

In this section, we introduce TEP-GNN. We first provide a general overview of
the model and discuss the problem addressed in this paper, followed by a
detailed discussion of the main components of TEP-GNN (FA-ASTs and the machine
learning pipeline based on the GraphConv (morris2019weisfeiler, ) higher order
GNN).

###  2.1. Approach Overview

Our goal in this paper is to predict the execution time of test cases based on
static code information alone, i.e., without access to prior benchmarking of
the test case or dynamic analysis data. The general procedure of our TEP-GNN
approach is sketched in Figure 1. To process a test file, we first parse it
into its AST. Next, we build a graph representation (FA-AST) by adding edges
representing control and data flow to the AST. We then initialize the
embeddings of FA-AST nodes and edges before jointly feeding a vectorized FA-
AST into a GNN. We use a 3-layer higher order graph convolution neural network
to predict the execution time. Each layer is followed by a ReLU activation
function. Since GNN learns node embedding, we use global max pooling to
compute a graph embedding. Finally, the graph embedding goes into two Linear
layers with a ReLU and a sigmoid activation function to perform the prediction
of the test execution time. To train our model we use the mean square error
loss.

###  2.2. Problem Definition

Given a test file (source code containing one or multiple test cases) $C_{i}$
and the corresponding run-time value $X_{i}$ (execution time of all test cases
in the file), for a set of test files with known execution times we can build
a training set $D={(Ci,Xi)}$. We aim to train a deep learning model for
learning a function $\phi$ that maps a test file $C_{i}$ to a feature vector
$v$ mapped to the corresponding value $X_{i}$.

###  2.3. Building Flow-Augmented Abstract Syntax Trees

Recent studies (samoaa2022, ) emphasize the importance of the code
representation when using deep learning in software engineering. Hence, and
given the complexity of predicting performance, prediction based on the
syntactical information extracted from ASTs alone is not sufficient to achieve
high-quality predictions. In TEP-GNN, the basic structural information
provided by the AST is enriched with semantic information representing data
and control flow. Consequently, the tree structure of the AST is generalized
to a (substantially richer) graph, encoding more information than code
structure alone. This idea is based on the earlier work by Wang and Jin
(Wang20, ), who have also introduced the term FA-AST for this kind of source
code representation.

####  2.3.1. AST Parsing

⬇

1package org.myorg.weather.tests;

2

3import static

4 org.junit.jupiter.api.Assertions.assertEquals;

5import org.myorg.weather.WeatherAPI;

6import org.myorg.weather.Flags;

7

8public class WeatherAPITest {

9

10 WeatherAPI api = new WeatherAPI();

11

12 @Test

13 public void testTemperatureOutput() {

14 double currentTemp = api.currentTemp();

15 Flags f = api.getFreezeFlag();

16 if(currentTemp <= 3.0d)

17 assertEquals(Flags.FREEZE, f);

18 else

19 assertEquals(Flags.THAW, f);

20 }

21}

Listing 1: A Simple JUnit 5 Test Case

We demonstrate our approach for constructing FA-ASTs for test files using the
example of a Java JUnit 5 test case (see Listing 1). In this example, a single
test case testTemperatureOutput() is presented that tests a feature of an
(imaginary) API. As common for test cases, the example is short and
structurally relatively simple. Much of the body of the test case consists of
invocations to the system-under-test and calls of JUnit standard methods, such
as assertEquals. We speculate that these properties make predicting test
execution time a more tractable problem than predicting performance of
general-purpose programs, which previous authors have argued to be extremely
challenging (Meng2017, ; Narayanan2010, ).

Figure 2. Simplified abstract syntax tree (AST) representing the illustrative
example presented in Listing 1. Package declarations, import statements, as
well as the declaration in Line 15 are skipped for brevity.

A (slightly simplified) AST for this illustrative example is depicted in
Figure 2. The produced AST does not contain purely syntactical elements, such
as comments, brackets, or code location information. We make use of the pure
Python Java parser javalang555https://pypi.org/project/javalang/ to parse each
test file, and use the node types, values, and production rules in javalang to
describe our ASTs.

####  2.3.2. Capturing Ordering and Data Flow

In the next step, we augment this AST with different types of additional edges
representing data flow and node order in the AST. Specifically, we use the
following additional flow augmentation edges, in addition to the AST child and
AST parent edges that are produced readily by AST parsing:

FA Next Token (b):
This type of edge connects a terminal node (leaf) in the AST to the next
terminal node. Terminal nodes are nodes without children. In Figure 2, an FA
Next Token edge would be added, for example, between WeatherAPI and api.

FA Next Sibling (c):
This connects each node (both terminal and non-terminal) to its next sibling.
This allows us to model the order of instructions in an otherwise unordered
graph structure. In Figure 2, such an edge would be added, for example,
connecting the first usage of api and with the CONSTR node (representing a
Java constructor call).

FA Next Use (d):
This type of edge connects a node representing a variable to the place where
this variable is next used. For example, the variable api is declared in Line
10 in Listing 1, and then used next in Line 14.

Figure 3. Flow-Augmented AST (FA-AST) for the example presented in Listing 1.
Solid lines represent AST parent and child edges, and dashed lines different
types of flow augmentations.

Figure 3 shows an example augmenting the AST in Figure 2 (and, consequently,
the example test case in Listing 1). Solid black lines indicate the AST parent
and child relationships (for simplicity indicated through a single arrow, read
from top to bottom). Red dashed arrows refer to the new edges added to
represent the data and control flow in the FA-AST, with letter codes
indicating the edge type. Terminal nodes are connected with FA Next Token
edges (b), modelling the order of terminals in the test case. Similarly, the
ordering of siblings is modelled using FA Next Sibling edges (c). Finally,
data flow is modelled by connecting each variable to their next usage via FA
Next Use edges (d). Edge types (e), (f), and (i) represent a control flow
statement, which will be discussed in the following. Multiple edges of
different types are possible between the same nodes. For example, the terminal
nodes Flags.FREEZE and f are connected via both, an FA Next Token (b) and an
FA Next Sibling (c) edge.

####  2.3.3. Capturing Control Flow

In a second augmentation step, we now add further edges representing the
control flow in the test cases. We currently support _if_ statements, _while_
and _for_ loops, as well as _sequential execution_. We currently do not
support _switch_ statements or _do-while_ loops, as these are less common in
test cases. Test files containing these elements will still be parsed
successfully, but these control flow constructs will not be captured by the
FA-AST. Specifically, the following further edges are added:

FA If Flow (e):
This type of edge connects the predicate (condition) of the if-statement with
the code block that is executed if the condition evaluates to true. Every if
statement contains exactly one such edge by construction.

Figure 4. Capturing the control flow of if statements.

FA Else Flow (f):
Conversely, this edge type connects the predicate to the (optional) else code
block. Figure 4 depicts how if-statements are modelled.

FA While Flow (g):
A while loop essentially entails two elements - a condition and a code block
that is executed as long as the condition remains true. We capture this
through a FA While Flow (g) edge connecting the condition to the code block,
and an FA Next Use (d) edge in the reverse direction. The latter is used to
model the next usage of a loop counter. Figure 5 shows this.

Figure 5. Capturing the control flow of while loops.

FA For Flow (h):
For loops are conceptually similar to while loops. We use FA For Flow (h)
edges to connect the condition to the code block, and an FA Next Use (d) edge
in the reverse direction. Similar to the modelling of while-loops, FA Next Use
(d) relates to the usage (typically incrementing) of a loop counter. This is
again illustrated in Figure 6.

Figure 6. Capturing the control flow of for loops.

FA Next Statement Flow (i):
In addition to the control flow constructs discussed so far, Java of course
also supports the simple sequential execution of multiple statements in a
sequence within a code block. FA Next Statement Flow edges (i) are used to
represent this case. Different from the constructs discussed so far, a code
block can contain an arbitrary number of children, and the FA Next Statement
Flow edge is always used to connect each statement to the one directly
following it. An illustration is shown in Figure 7.

Referring back to Figure 3, two types of control flow annotations are visible
- the modelling of the if-statement in lines 16 to 19 of the test case on the
right-hand side, and various sequential executions (FA Next Statement flow (i)
) edges. Further note how flow annotation adds a large number of edges to even
a very small AST, transforming the syntax tree into a densely connected graph.
This rich additional information can be used in the next step by our GNN model
to predict highly accurate test execution times.

Figure 7. Capturing the control flow of sequential execution. Figure 8.
Architecture of the GNN Model used in TEP-GNN.

###  2.4. GNN Model for Test Execution Time Prediction

Once the FA-AST graph has been built for a test file using the three steps
discussed above, we use a higher order GNN model to predict the execution time
of the Java code.

Graphs are complex structures, verifying if two graphs are identical (also
known as isomorphism test) is an important and difficult task. It is unknown
if the problem can be solved in polynomial time or it is computationally
intractable for large graphs. A fast heuristic to verify if two graph are the
same is the $k$-Weisfeiler-Leman test (weisfeiler1968reduction, ). The
algorithm produces for each graph a canonical form. Then, if the canonical
forms of two graphs are not equivalent, the graphs are not considered
isomorphic. However, there is the possibility that two non-isomorphic graphs
share a canonical form. Thereby, this test might not provide a conclusive
evidence that two graphs are isomorphic. Morris et al. (morris2019weisfeiler,
) prove that a GNN network can be as powerful as the $k$-Weisfeiler-Leman test
with $k$ equal to 1, in which the canonical form propagates the information by
nodes. With $k$ greater than 1, the information is propagated among
substructures of order $k$. Morris et al. (morris2019weisfeiler, ) also
propose a higher order graph convolution layer ($k$-GNN), wherein messages are
exchanged among nodes, edges and substructure with tree nodes (triads). Once
messages are exchanged among substructures, each node has a latent
representation. In order to predict property of the graphs (i.e., the
execution time of a graph representing Java code), node embeddings are
globally aggregated (pooling step) with an ordering invariant function (i.e.
sum, max, mean). In particular, $k$-GNN is defined as: given is an integer $k$
the $k$-element subset $[V(G)]^{k}$ over $V(G)$. Let
$s=\\{s_{1},s_{2},\dots\\}$ be $k$-set in $[V(G)]^{k}$, then the neighborhood
of $s$ is defined as:

(1) $N(s)=\\{t\in[V(G)]^{k}||s\cup t|=k-1\\}$

In Equation 1, the neighbour of a $k$-set is defined as the set of $k$-set
such that the intersection of their cardinality is equal to $k-1$. The local
neighborhood is defined as:

(2) $N_{L}(s)=\\{t\in N(s)|(u,w)\in E(G)\text{ with }u\in s/t\text{ and }w\in
t/s\\}$

The local neighborhood defined in Equation 2 is a subset of the neighbour (eq.
1). Finally, the $k$-GNN is defined as:

(3) $f_{k,L}^{(l)}(s)=\sigma(f_{k,L}^{(l-1)}(s)\cdot W_{1}^{(t)}+\sum_{u\in
N_{L}(s)}f_{k,L}^{(t-1)}(u)\cdot W_{2}^{(t)})$

The $l$-th layer of the $k$-GNN computes an embedding of $s$, using the non
linear activation function $\sigma$ of the summation over the substructure
itself in the previous layer (i.e., layer $l-1$) and the summation over the
previous layer embedding of each local neighbor of the substructure $s$. A
scheme of the deep learning architecture we use in TEP-GNN is shown in Figure
8. Due to the proven superiority of higher order GNN with respect to classic
GNN (morris2019weisfeiler, ), we adopt GraphConv, a PyTorch-geometric
implementation of the higher order Graph Neural Network layer. The GNN is
composed of three convolutional layers, each layer has a GraphConv layer with
an ReLU activation function and a batch normalization. Then node embeddings
are converted into a graph embedding using a global max pooling layer.
Finally, the predicted execution time is predicted using two multi-layers
perceptrons with ReLU and sigmoid activation functions. We use the Mean Square
Error as the loss function. In order to make the learning easier for the
neural network, and to reduce the optimization problems, real execution times
have been normalized between 0 and 1.

##  3\. Evaluation

Table 1. Overview of study subjects. Project |  Description |  Test files |  Test runs |  Number of nodes |  Vocabulary size
---|---|---|---|---|---
systemDS |  Apache Machine Learning system for data science lifecycle |  127 |  1321 |  110651 |  3161
H2 |  Java SQL database |  194 |  1391 |  405706 |  17972
Dubbo |  Apache Remote Procedure Call framework |  123 |  524 |  75787 |  4499
RDF4J |  Scalable RDF processing for Java |  478 |  1055 |  214436 |  10755
Total |  |  922 |  4291 |  806580 |  36387

We now present the results of an experimental evaluation of TEP-GNN based on
open source Java projects. As training and test data we make use of existing
test suite execution traces from the study subjects’ build systems. A
replication package containing the scripts used to implement the TEP-GNN
approach, all data used in the evaluation, as well as all analysis scripts,
are available (hazem_peter_2022_7003881, ).

###  3.1. Dataset

Related studies in performance engineering frequently collect their own
performance data, for example by repeated execution of the projects on a
researcher’s laptop (alcocer:16, ), in cloud virtual machines (laaber:19, ),
or on controlled hardware (schulz:21, ). To increase the realism of the study
we have chosen a different approach – we harvest existing execution traces
from an open source build system (GitHub), and extract test execution times
from this public data. This data represents actual, real-life test execution
times. However, we do not have the option to collect more data on-demand, and
we do not know what precise hardware has been used to collect the data.

To collect the data, we searched for projects to serve as study subjects. We
applied the following selection criteria: _(i)_ projects written in Java;
_(ii)_ available on GitHub; _(iii)_ include test results published on GitHub;
and _(iv)_ use GitHub shared runners as build system.

Based on these criteria, we selected four projects of diverse application
domains, i.e., databases, web servers, and data science life-cycle (systemDS,
H2, Dubbo, and RDF4J). These are depicted in Table 1. The first column shows
the project’s name, the second provides a brief description of the project.
The third column shows the number of distinct test files extracted from the
project. As for the fourth column, it shows the total number of runs performed
in the testing job. The last two columns show the total number of tokens in
the entire project test files and the vocabulary size (the number of distinct
nodes in the graphs). We observe that RDF4J, a triplestore database used in
semantic web contexts (samoaa-pipeline:2021, ), contains more test files than
the other projects. For the H2 relational database and systemDS we were able
to collect the most test runs. Finally, it should be noted that H2 has the
highest code density as measured by the number of nodes and the resulting
vocabulary size by a wide margin. This indicates that H2 tests are generally
larger and more complex than the test cases in the other study subjects.

All data was extracted from GitHub-hosted runners, which are virtual machines
hosted by GitHub with the GitHub Actions runner application installed. All
shared runners can be assumed to use the same hardware resources, which is
available at GitHub’s website666https://docs.github.com/en/actions/using-
github-hosted-runners/about-github-hosted-runners#supported-runners-and-
hardware-resources and each job runs in a fresh instance of the virtual
machine. Additionally, all jobs from which the data is extracted uses the same
operating system, specifically Ubuntu 18.04. This allows us to minimize bias
introduced by variations in execution environment or hardware.

For collecting test execution traces we looked at the latest successful action
workflow run for each project. We then extracted the run times from the test
report in the workflow, and mined the corresponding source code files from the
respective project repositories in order to feed them to the parser. For H2,
some test cases are run several times during the same build job. In these
cases, we recorded the average of the run times. As the execution times of
tests can vary dramatically between and within projects, to increase the
efficiency of the model training, we normalize each execution time to interval
$[0;1]$. Hence, our final dataset includes distinct test files, each
associated with one runtime value between 0 and 1. Then after model training,
we denormalize the runtime value and present the results based on the original
values.

Table 2 indicates how prevalent different control flow nodes were in the test
cases of our study subjects. For all projects, block statements are the most
frequent control flow construct, since sequential executions widely exist in
nearly all programs. For loops are substantially more common than while loops,
and if statements are also frequent. Do-while loops and switch statements,
which are currently unsupported by TEP-GNN, are both quite rare in the tests
of our subjects (not shown in the table).

Table 2. Occurrences of Control Flow Nodes in Each Project  Control Flow Statement |  systemDS |  H2 |  Dubbo |  RDF4J
---|---|---|---|---
If Statement |  166 |  1322 |  53 |  161
While Loop |  2 |  222 |  3 |  22
ForStatement |  196 |  1114 |  42 |  158
Block Statement |  293 |  2900 |  116 |  395
Total |  707 |  5612 |  214 |  736

###  3.2. Results

In this section, we investigate the results of applying TEP-GNN to our
dataset, answering RQ1 – RQ3 introduced in Section 1.

####  3.2.1. RQ1: Quality of Predictions

In order to answer the first research question, we combine the collected data
for all projects into one dataset entailing 922 code fragments and associated
normalized execution times. After that, we apply TEP-GNN as discussed in
Section 2. For model training, we split the dataset into train and test sets
using $80\%$ and $20\%$, respectively. Each network is trained for 100 epochs.
As optimizer we use Adam (Adam, ) with a learning rate $=0.001$. To evaluate
the results of our model, we use a Pearson correlation metric, a measure of
linear correlation between two sets of data. In addition, as a loss function,
we use mean squared error, which is the average squared difference between the
estimated and actual values. All experiments have been executed in a machine
equipped with a GeForce 940MX graphics card and 16GB of RAM.

Table 3. Results of the TEP-GNN on the entire dataset  Pearson correlation |  Mean squared error
---|---
0.789 |  0.017

Results are shown in Table 3. Our model trained on FA-AST is able to predict
test execution times with a very high accuracy, as can be seen in the Pearson
correlation (between predicted and actual execution times in the test data
set) of 0.789, and a mean squared error of 0.017. These results substantially
outperform the accuracy values reported in previous studies that attempted to
predict absolute software performance counters (Meng2017, ; Narayanan2010, ).
We argue that the key innovation that enables this high accuracy is the
combination of FA-AST as a powerful code representation model and GraphConv as
a modern GNN.

####  3.2.2. RQ2: Comparison of TEP-GNN Against a Baseline GNN

To validate the suitability of our approach and the selected GNN model, we
compare it to a commonly used GNN baseline, called Gated Graph Neural Networks
(GGNN)(Li2015, ). GGNNs are widely used in studies that attempt to learn code
semantics (Fernandes2018, ; Allamanis2017, ). We compare the methods at two
levels – for the entire dataset (similar to the analysis presented for RQ1)
and at the level of individual projects.

##### Comparison for the entire dataset

We first apply both TEP-GNN and the baseline method to the dataset consisting
of all projects. Figure 9 depicts the respective results. Our model
outperforms the baseline, with a Pearson correlation that is higher almost up
to 0.1 (i.e., 0.789 versus 0.697). Hence, we conclude that our model and GNN
architecture is indeed more appropriate to predict the execution time of test
cases than a more standard GGNN approach.

Figure 9. Comparison of TEP-GNN and a baseline (applying GGNN to the same FA-
AST graphs). Dot points show real (y axes) and predicted (x axes) execution
times produced by our model. The dash line refers to the perfect prediction.

Analyzing the results, we observe that TEP-GNN is able to achieve highly
accurate predictions in most cases. However, there are rare outliers where our
prediction model misses by approximately 20%. The baseline GGNN method, on the
other hand, has a tendency to predict fairly uniform execution times between
$10^{2}$ and $10^{3}$, almost independent of what the actually observed test
execution time is. Hence, it suffers from lower accuracy scores.

##### Comparison for individual projects

In the next step, we conduct a similar analysis, but focused on individual
projects. This study answers the question of how well TEP-GNN works if trained
on and used by a single project. Thus, we train and test TEP-GNN and the
baseline on each of the four projects individually. The results for each
project are depicted in Figure 10.

Figure 10. Overview of TEP-GNN and the GGNN baseline trained for each
individual project.

We observe that in general the prediction quality is substantially lower if
the model is trained on individual projects, both for TEP-GNN and the
baseline. TEP-GNN still outperforms the baseline for each project, but only
with negligible prediction performance differences in the case of H2 and
Dubbo. For RDF4J, which contains the largest number of test cases (and,
consequently, the largest number of graphs to learn from), the difference
between our approach and the baseline remains larger.

From these results we conclude that (a) TEP-GNN indeed outperforms the
baseline in all the settings we tested, but (b) our approach works best if
sufficient training graphs are available in comparison to the size of the
graphs and vocabulary (if graphs are complex and/or training data is sparse
the difference between our approach and the baseline is insignificant); (c)
finally, we conclude that both approaches appear to learn some transferable
knowledge even when training on graphs that originate from a different
project.

####  3.2.3. RQ3: Evaluation of Models Trained on Different Projects

Based on the third conclusion above, we now raise the question if it is
possible to build a generic model trained on a subset of projects and apply it
to a new (unseen) project. Hence, we now train new TEP-GNN models using three
of the projects in our dataset, and test on the fourth one. The results for
all four combinations are shown in Figure 11.

We observe that the quality of predictions in this setting is in general
rather disappointing, ranging from a Pearson correlation of 0.381 when testing
on the H2 database to -0.02 when testing on systemDS. Interestingly, H2, which
has the structurally most complex test cases in our study subjects, seems to
perform better with a transferred model than the other projects, where test
cases tend to be simpler. This is likely due to the test cases in projects
such as systemDS mainly consisting of calls to the specific system-under-test,
about which a transferred model clearly cannot learn any execution time
properties.

Despite these results, we conclude that the models that achieve the highest
prediction performance are trained with data across multiple projects,
including ones with both complex and simpler test cases. A more general model,
i.e., a model that has been trained using data of multiple projects (including
the one that it is being applied to) is able to outperform a "pure" model that
is trained and tested on a single, individual project.

Figure 11. Testing trained models on unseen projects.

##  4\. Discussion

Our study results show that the accurate prediction of execution times of test
suites is possible. This gives developers an early indication of the time
required to run the cases in the build process, deciding in the process if
techniques such as test case selection are required.

###  4.1. Lessons Learned

FA-ASTs are a promising approach to represent source code for performance
prediction. Unlike previous work (Narayanan2010, ; Meng2017, ; Zhou2019, ),
our goal in this study was to treat performance prediction as a regression
rather than a classification (slow or fast) problem. Our results in Section
3.2 indicate that using flow augmentation we are able to achieve good
prediction quality. Furthermore, more information could be added to the FA-
AST, such as program dependency graphs. We speculate that this approach is
also promising to predict the performance of more complex, arbitrary code;
however, more specific experiments in this direction need to be carried out as
future research.

GraphConv substantially outperforms the more common GGNN models in performance
prediction as long as sufficient data is available. As discussed in Section
3.2, our GraphConv based GNN model substantially outperforms GGNN, which is a
currently commonly used graph neural network model in software engineering
research (Fernandes2018, ; Allamanis2017, ). However, this is only true if
sufficient data is available – when training models for individual projects,
we observed that, due to the limited amount of training data available in
these cases, the performance difference between our GraphConv based model and
the GGNN baseline was minimal. We conclude that, as long as sufficient data is
available, GraphConv should also be investigated in other software engineering
contexts that make use of GNNs.

TEP-GNN in its current form is not able to generalize to unseen projects.
While TEP-GNN can effectively predict the execution time of unseen test files,
it can only do so if _other test cases from the same project_ have been used
to build the model. This implies that much of what the model learns about test
case performance during training is project-specific and does not generalize
to other projects. This is not surprising, given that the core of test cases
consist of invocations to the system-under-test, which will be different from
project to project. However, our results also demonstrate that training a
model on test cases originating from a range of different projects leads to
better predictions than training on a single project. This indicates that some
cross-project learning indeed happens. Evidently, for practitioners a general
model that can be applied to any project, without the need to train first
based on historical executions from the same project, would be much more
directly useful. Hence, future research should investigate whether approaches
such as meta-learning (Joaquin2018, ) could be used to build more transferable
models. At the very least, we hypothesize that general prediction models for
project families, such as Apache or Eclipse projects, could be built.

###  4.2. Threats to Validity

Similar to other experimental studies in software engineering, our work is
subject to certain limitations and threats to validity, which we elaborate in
the following.

Internal Validity Threats. A key design choice in our study was the usage of
existing, real-world data from GitHub’s build system, rather than collecting
performance data ourselves (e.g., on a dedicated experiment machine). This has
obvious advantages with regards to the realism of our approach, but raises the
threat that our training and test data may be subject to confounding factors
outside of our knowledge. In particular, prior research has shown that even
identically configured cloud virtual machines can vary significantly in
performance (leitner:16, ). However, the high accuracy achieved by our
prediction models indicates that this is not a major concern with the data we
used. That said, we expect that TEP-GNN would perform even better on the
performance data that has been measured more rigorously.

Another design choice was that we predict execution times for entire test
classes (files). More fine-grained predictions (e.g., for individual test
cases in a class) would of course be doable, for instance by constructing the
FA-AST with test methods as entry points rather than for an entire class as
compilation unit. However, individual test cases often have very short
execution times in relation to the precision with which build systems
typically measure execution times (milliseconds), and the resulting graphs
would be very small. We argue that our choice of test class granularity
constitutes a good trade-off that is still useful for developers.

External Validity Threats. An obvious question raised by our work is how well
the results reported in Section 3.2 would generalize to other projects. To
mitigate this threat, we have chosen four relatively different Java projects
as study subjects following a diversity sampling strategy (baltes:22, ).
However, our study does not allow us to conclude whether the TEP-GNN approach
would generalize to other programming languages or closed-source software.

##  5\. Related Work

Predicting software performance. Predicting the absolute value of a
performance counter, such as execution time, based on the source code alone is
challenging, as application performance is a function of several unknowns
stemming from the application run-time and interactions between the OS and
underlying hardware. This makes the problem notoriously challenging for any
machine learning model, including deep learning techniques. Hence, existing
studies often struggle with poor prediction accuracy (Meng2017, ;
Narayanan2010, ). One way to simplify the problem (and hence make it more
tractable) is to convert it into a classification problem. Examples of this
approach include Zhou et al. (zhou:19, ), who predict if a program from a
programming competition website exceeds the time limit, Ramadan et al.
(Ramadan2021, ), who predict whether a performance change is introduced by a
code structure change, or Laaber et al. (laaber:21, ), who have shown that a
categorical classification of benchmarks into high- or low-variability is
feasible.

However, recent research has shown that predicting absolute performance values
can be feasible in more specialized contexts. For example, Guo et al.
successfully predict the execution time of a specific untested configuration
of a configurable system (guo:13, ; guo:18, ), and Samoaa and Leitner have
shown that the execution time of a benchmark with a specific workload
configuration can be predicted (samoaa:21, ). In this work, our core
contribution is we demonstrate that predicting absolute performance values is
possible in another context, namely for the execution time of test files.

Graph neural networks for software engineering. Graph Neural Networks (GNNs)
constitute an up-and-coming machine learning model in the context of software
engineering research (samoaa2022, ). Graphs are mathematical structures used
to model pairwise relations between objects. A graph can be used to model a
wide number of different domains, ranging from biology (huber2007graphs, ),
face-to-face human interactions (longa2022efficient, ; longa2022neighbourhood,
), or digital contact tracing (cencetti2021digital, ). Li et al (Li2015, ) use
a GRU cell in gated graph neural networks (GGNNs) for updating the nodes’
states. To evaluate their model they run the model on a basic program and try
to detect null pointers. Instead of having the whole program as an input Li et
al. (Li2015, ) use the memory heap states of the program to the model. Since
the original work by Li et al. (Li2015, ), GGNNs have become a commonly used
tool for applying GNNs in software engineering. One challenge that needs to be
solved before any GNN approach can be applied for code-based software
engineering research is how to represent a program as graph.

Phan et al. (Phan2017, ) use graph convolutional networks (GCNs) based on
compiled assembly code to detect defects on control flow graphs in C. Another
application of control flow graphs is using graph matching networks (GMN)
between two graphs of binary functions proposed by Li et al. (li19d, ). Other
researchers propose the creation of program graphs based on the AST. Allamanis
et al. (Allamanis2017, ) and Brockschmidt et al. (Brockschmidt2018, ) use GGNN
in C# for naming variables and generating program expressions for code
completion respectively.

##  6\. Conclusion and Future Work

Inn this work we presented TEP-GNN, an effective method for predicting the
execution time of Java test files. Our approach leverages explicitly capturing
control and data flow information as augmentations to the program AST.
Further, our approach applies high order convolution graph neural networks
over this flow-augmented AST (FA-AST). By building FA-AST using original ASTs
and flow edges, our approach can directly capture the syntax and semantic
structure of test classes. Experimental results on four diverse test subjects
demonstrate that by combining graph neural networks and control/data flow
information, we can predict absolute test execution times with high accuracy.

As the future work, we plan to further extent the FA-AST model currently used
by TEP-GNN, as well as explore other ways of program representation to capture
more syntactic and semantic code features. Additionally, we plan to apply our
approach to the execution time of general-purpose programs rather than test
cases. Finally, we would like to extend our current labeled data set by
applying active learning to increase the amount of training data in a
systematic way.

## Acknowledgements

This work received financial support from the Swedish Research Council VR
under grant number 2018-04127 (Developer-Targeted Performance Engineering for
Immersed Release and Software Engineering).

## References

  * [1] M. Allamanis, M. Brockschmidt, and M. Khademi.  Learning to represent programs with graphs, 2017.
  * [2] S. Baltes and P. Ralph.  Sampling in software engineering research: a critical review and guidelines.  Empirical Software Engineering, 94(27).
  * [3] M. Brockschmidt, M. Allamanis, A. L. Gaunt, and O. Polozov.  Generative code modeling with graphs, 2018.
  * [4] G. Cencetti, G. Santin, A. Longa, E. Pigani, A. Barrat, C. Cattuto, S. Lehmann, M. Salathe, and B. Lepri.  Digital proximity tracing on empirical contact networks for pandemic control.  Nature communications, 12(1):1–12, 2021.
  * [5] F. G. de Oliveira Neto, A. Ahmad, O. Leifler, K. Sandahl, and E. Enoiu.  Improving continuous integration with similarity-based test case selection.  In Proceedings of the 13th International Workshop on Automation of Software Test, pages 39–45, 2018.
  * [6] P. Fernandes, M. Allamanis, and M. Brockschmidt.  Structured neural summarization, 2018.
  * [7] J. Guo, K. Czarnecki, S. Apel, N. Siegmund, and A. Wąsowski.  Variability-aware performance prediction: A statistical learning approach.  In 2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 301–311, 2013.
  * [8] J. Guo, D. Yang, N. Siegmund, S. Apel, A. Sarkar, P. Valov, K. Czarnecki, A. Wasowski, and H. Yu.  Data-efficient performance learning for configurable systems.  Empirical Software Engineering, 23(3):1826–1867, jun 2018.
  * [9] HP.Samoaa, A.Longa, M.Mohamed, MH.Chehreghani, and P.Leitner.  TEP-GNN: Accurate Execution Time Prediction of Functional Tests using Graph Neural Networks. Zenodo, Aug. 2022.  https://doi.org/10.5281/zenodo.7003881.
  * [10] W. Huber, V. J. Carey, L. Long, S. Falcon, and R. Gentleman.  Graphs in molecular biology.  BMC bioinformatics, 8(6):1–14, 2007.
  * [11] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization, 2014.
  * [12] E. Knauss, M. Staron, W. Meding, O. Söder, A. Nilsson, and M. Castell.  Supporting continuous integration by code-churn based test selection.  In 2015 IEEE/ACM 2nd International Workshop on Rapid Continuous Software Engineering, pages 19–25. IEEE, 2015.
  * [13] C. Laaber, M. Basmaci, and P. Salza.  Predicting unstable software benchmarks using static source code features.  Empirical Software Engineering, 26(6), nov 2021.
  * [14] C. Laaber, J. Scheuner, and P. Leitner.  Software Microbenchmarking in the Cloud. How Bad is it Really?  Empirical Software Engineering, 24(4):2469–2508, 2019.
  * [15] P. Leitner and J. Cito.  Patterns in the chaos - a study of performance variation and predictability in public iaas clouds.  ACM Transactions on Internet Technology, 16(3):15:1–15:23, apr 2016\.
  * [16] Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli.  Graph matching networks for learning the similarity of graph structured objects.  In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3835–3845. PMLR, 09–15 Jun 2019\.
  * [17] Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel.  Gated graph sequence neural networks, 2015.
  * [18] A. Longa, G. Cencetti, S. Lehmann, A. Passerini, and B. Lepri.  Neighbourhood matching creates realistic surrogate temporal networks.  arXiv preprint arXiv:2205.08820, 2022.
  * [19] A. Longa, G. Cencetti, B. Lepri, and A. Passerini.  An efficient procedure for mining egocentric temporal motifs.  Data Mining and Knowledge Discovery, 36(1):355–378, 2022.
  * [20] D. Marijan, A. Gotlieb, and M. Liaaen.  A learning algorithm for optimizing continuous integration development and testing practice.  Software: Practice and Experience, 49(2):192–213, 2019.
  * [21] K. Meng and B. Norris.  Mira: A framework for static performance analysis.  In 2017 IEEE International Conference on Cluster Computing (CLUSTER), pages 103–113, 2017.
  * [22] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4609, 2019.
  * [23] S. H. K. Narayanan, B. Norris, and P. D. Hovland.  Generating performance bounds from source code.  In 2010 39th International Conference on Parallel Processing Workshops, pages 197–206, 2010.
  * [24] T. Ramadan, T. Z. Islam, C. Phelps, N. Pinnow, and J. J. Thiagarajan.  Comparative code structure analysis using deep learning for performance prediction.  In 2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 151–161, Los Alamitos, CA, USA, mar 2021\. IEEE Computer Society.
  * [25] H. Samoaa and B. Catania.  A pipeline for measuring brand loyalty through social media mining.  In SOFSEM 2021: Theory and Practice of Computer Science, pages 489–504, Cham, 2021. Springer International Publishing.
  * [26] H. Samoaa and P. Leitner.  An exploratory study of the impact of parameterization on jmh measurement results in open-source projects.  In Proceedings of the ACM/SPEC International Conference on Performance Engineering, ICPE ’21, page 213–224, New York, NY, USA, 2021. Association for Computing Machinery.
  * [27] H. P. Samoaa, F. Bayram, P. Salza, and P. Leitner.  A systematic mapping study of source code representation for deep learning in software engineering.  IET Software.
  * [28] J. P. Sandoval Alcocer, A. Bergel, and M. T. Valente.  Learning from source code history to identify performance failures.  In Proceedings of the 7th ACM/SPEC on International Conference on Performance Engineering, ICPE ’16, page 37–48, New York, NY, USA, 2016. Association for Computing Machinery.
  * [29] H. Schulz, D. Okanović, A. van Hoorn, and P. Tůma.  Context-tailored workload model generation for continuous representative load testing.  In Proceedings of the ACM/SPEC International Conference on Performance Engineering, ICPE ’21, page 21–32, New York, NY, USA, 2021. Association for Computing Machinery.
  * [30] H. Spieker, A. Gotlieb, D. Marijan, and M. Mossige.  Reinforcement learning for automatic test case prioritization and selection in continuous integration.  In ISSTA, pages 12–22, 2017.
  * [31] J. Vanschoren.  Meta-learning: A survey.
  * [32] A. Viet Phan, M. Le Nguyen, and L. Thu Bui.  Convolutional neural networks over control flow graphs for software defect prediction.  In 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), pages 45–52, 2017.
  * [33] W. Wang, G. Li, B. Ma, X. Xia, and Z. Jin.  Detecting code clones with graph neural network and flow-augmented abstract syntax tree.  In 2020 IEEE 27th International Conference on Software Analysis, Evolution and Reengineering (SANER), pages 261–271, 2020.
  * [34] B. Weisfeiler and A. Leman.  The reduction of a graph to canonical form and the algebra which appears therein.  NTI, Series, 2(9):12–16, 1968.
  * [35] M. Zhou, J. Chen, H. Hu, J. Yu, Z. Li, and H. Hu.  Deeptle: Learning code-level features to predict code performance before it runs.  In 2019 26th Asia-Pacific Software Engineering Conference (APSEC), pages 252–259, 2019.
  * [36] M. Zhou, J. Chen, H. Hu, J. Yu, Z. Li, and H. Hu.  Deeptle: Learning code-level features to predict code performance before it runs.  In 2019 26th Asia-Pacific Software Engineering Conference (APSEC), pages 252–259, 2019.