#  Supersonic: Learning to Generate
Source Code Optimizations in C/C++

Zimin Chen, Sen Fang, and Martin Monperrus Zimin Chen, Sen Fang and Martin
Monperrus are with KTH Royal Institute of Technology, Sweden.
E-mail: {zimin, senf<EMAIL_ADDRESS>
###### Abstract

Software optimization refines programs for resource efficiency while
preserving functionality. Traditionally, it is a process done by developers
and compilers. This paper introduces a third option, automated optimization at
the source code level. We present Supersonic, a neural approach targeting
minor source code modifications for optimization. Using a seq2seq model,
Supersonic is trained on C/C++ program pairs ($x_{t}$, $x_{t+1}$), where
$x_{t+1}$ is an optimized version of $x_{t}$, and outputs a diff. Supersonic’s
performance is benchmarked against OpenAI’s GPT-3.5-Turbo and GPT-4 on
competitive programming tasks. The experiments show that Supersonic not only
outperforms both models on the code optimization task but also minimizes the
extent of the change with a model more than 600x smaller than GPT-3.5-Turbo
and 3700x smaller than GPT-4.

###### Index Terms:

Code Optimization, Seq2Seq Learning, Large Language Model.

##  1 Introduction

Software optimization refers to the process of refining a program so that it
utilizes fewer resources, such as time, memory, CPU, and energy while
preserving its original functionality. Traditionally, this task has been
carried out by the developer and/or the compiler. The developer possesses deep
human expertise to enhance the program by using a more efficient data
structure or an algorithm with better complexity. On the other hand, the
compiler can apply a range of automated optimizations on the intermediate
representation that can significantly enhance the program’s performance. Human
developers optimize at the source code level, and compilers at the machine
code level. In this work, we explore a third way: automated optimization at
the source code level.

For developers, automatic source code optimization is invaluable. Firstly, it
encompasses optimizations that are beyond the scope of compiler optimizations,
high-level optimizations that a compiler cannot achieve with guarantees. For
instance, refactoring an inefficient algorithm or modifying data structures to
boost performance is beyond the compiler’s scope. Secondly, it facilitates the
optimization of legacy systems for which language and domain expertise have
been lost over time, such as Fortran libraries or Cobol systems. Process-wise,
automatic source code optimization can be used in modern code bases, with
automated pull requests [1].

In this paper, we introduce Supersonic, an innovative end-to-end system that
employs a supervised machine-learning approach to the problem of automatic
source code optimization. Supersonic, implemented as a seq2seq model, learns
the relationship between input programs and their optimized versions. Our
process involves collecting a dataset of past source code optimizations, where
each pair ($x_{t}$, $x_{t+1}$) consists of a base program $x_{t}$ and its
optimized counterpart $x_{t+1}$. Special attention has been given to creating
such a high-quality training dataset. With this dataset, we then tailor a
model and devise a data and training loop specifically for the optimization
task.

At inference time, Supersonic has three phases: canonicalization, diff-
synthesis, and post-processing. During the canonicalization phase, Supersonic
removes source code comments and ensures a canonical code format (w.r.t.
whitespaces, tabs, etc.) that has also been enforced at training time. The
diff-synthesis phase takes the input program and predicts a diff-based output
representation, which is similar to the typical Unix patch format. The post-
processing phase is responsible for validating the predicted diff-based output
representation and applying it to the original program. Supersonic is
implemented for C/C++ and trained on a large corpus of C/C++ program
optimizations.

For the training and evaluation of Supersonic, we use programs from three code
competition websites. This is a perfect evaluation benchmark since problems on
code competition websites are usually designed to have a large solution space
and they also have a strong emphasis on optimization, running time and memory
consumption. They are excellent for collecting training data as well as for
assessing optimized programs. For evaluation, we compare against a strong
baseline. Supersonic competes with OpenAI’s GPT-3.5-Turbo and GPT-4, two
industrial large language models that have proven to be state-of-the-art in
many software engineering tasks [2, 3, 4, 5]. Our evaluation of 559 programs
shows that Supersonic outperforms both GPT-3.5-Turbo and GPT-4. Not only is
the performance better on the task of optimizing C/C++ programs, but
Supersonic’s model is approximately 600x smaller111We assume it is the same
size as GPT3, which is a 175B parameter model. than GPT-3.5-Turbo and 3700x
smaller222There are no official numbers on the number of parameters of GPT-4,
we assume it is a trillion parameter model. than GPT-4, making it more cost
and energy-efficient.

Supersonic is unique compared to the most related work, such as PIE4Perf [6]
and DeepDev-PERF [7]. First, we take special care in removing essentially full
re-implementations, and not optimized solutions from the dataset. Second,
Supersonic uses a novel diff-based output representation as opposed to
generating the entire program, a feature that, as demonstrated in our
evaluation, significantly boosts its effectiveness. Last, the evaluation of
Supersonic is done on third-party competition websites, giving our results
strong external validity.

In summary, our contributions are:

  * •

Supersonic, a novel source code optimization technique based on state-of-the-
art sequence-to-sequence learning. Supersonic is able to generate source code
level optimizations while retaining significant similarity with the original
program.

  * •

We show that Supersonic outperforms GPT-3.5-Turbo and GPT-4 when submitting
tentative optimizations to the official Codeforces website. It improves
running time for 26.0% programs, compared to only 12.0% for GPT-3.5-Turbo and
4.0% for GPT-4.

  * •

We investigate the optimization performance of Supersonic, GPT-3.5-Turbo, and
GPT-4 at various string similarity thresholds between the optimized and
original program. We find that Supersonic is better than GPT-3.5-Turbo and
GPT-4 when the threshold is above 0.4. However, the threshold of 0.4 is close
to a complete rewrite.

  * •

We demonstrate that the diff-based output representation is better than
outputting the full program. Our ablation study shows that changing the full
program output representation to a diff-based output representation of
Supersonic boosts the optimization success rate by 2x at least.

  * •

For the sake of open science and future research on this topic, we share all
our code, data, and train models at https://github.com/ASSERT-KTH/Supersonic.

##  2 Background

###  2.1 Large language models

A Large Language Model (LLM) is a type of deep learning (DL) model commonly
used in the field of natural language processing (NLP). Unlike traditional DL
models designed for specific tasks, LLMs are initially trained on large
textual datasets to acquire a universal language representation. This learned
representation can be further refined and adapted for various downstream tasks
through supervised fine-tuning [8]. The majority of current LLMs are built
upon the core modules of the Transformer model [9], and they can be
categorized into three main types based on the chosen modules: encoder-only
[8], decoder-only [10], and encoder-decoder [11].

The design of an encoder-only LLM involves stacking multiple Transformer
encoder layers, with BERT [8] emerging as a renowned representative of this
LLM class. BERT specifically undergoes training with two training objectives -
masked language modeling and next sentence prediction. The former lets BERT
predict masked words according to their located context, and the latter lets
BERT measure whether two sentences are continuous, both of which allow it to
learn a universal contextual representation of words. In contrast, decoder-
only LLMs are structured around the Transformer decoder as their fundamental
building block. The GPT family [10, 12], as one of the most well-known
decoder-only LLMs, is pre-trained with an objective called next token
prediction. Here, the models are tasked to predict the present word based on
its preceding context. The encoder-decoder LLM, as the name suggests,
incorporates both Transformer encoder and decoder layers. T5 [13], a
prototypical example of this LLM category, is pre-trained with an objective
analogous to a fill-in-the-blank task, which compels the model to predict
missing words in relation to their specific context.

Due to the inherent differences in LLMs’ core architectures and training
objectives, encoder-only and decoder-only LLMs respectively excel in language
understanding and generation tasks. On the other hand, encoder-decoder LLMs,
while capable of delivering high performance across both types of tasks,
necessitate more parameters for their construction.

LLMs are increasingly utilized in the field of software engineering (SE) to
expedite automation processes. An example of this is CodeBERT [14], an LLM
designed specifically for programming language. This model was initially
trained on a broad, cross-programming language (PL) corpus. Subsequently,
supervised fine-tuning allows its application to various SE tasks, such as
code searching [15] and summarization [16]. To augment the efficacy of LLMs in
handling code, [*]wang2021codet5 introduced CodeT5 [17], which was pre-trained
using an innovative method known as identifier-aware denoising training.
Additional training objectives include identifier tagging, masked identifier
prediction, and bimodal dual generation. All of these objectives facilitated
the model’s ability to effectively comprehend both programming and natural
language. In recent developments, next-generation LLMs like LLaMa [18], BLOOM
[19], and PaLM [20] are gaining momentum. These models are typically trained
on both extensive PL and natural language corpora. As a result, they offer
robust support for tasks within both NLP and SE domains.

Figure 1: The pipeline of Supersonic for code optimization.

###  2.2 The State-of-the-art Models at OpenAI

Recently, OpenAI released GPT-3.5-Turbo [21] and GPT-4 [22], two
groundbreaking NLP systems specializing in generating text that closely
mirrors human language. These state-of-the-art systems owe their performance
to the Transformer decoder-based architecture, known as GPT [10].
GPT-3.5-Turbo’s training involves a two-stage process: unsupervised pre-
training and subsequent instruction fine-tuning. In the pre-training phase,
the model learns from an extensive corpus of Internet data dated until
September 2021. It is important to underscore that the system does not possess
specific knowledge about the documents that comprise its training data and
cannot directly access any database or document. The second stage, instruction
fine-tuning, involves training the model on a smaller dataset with human
feedback, utilizing a technology called reinforcement learning from human
feedback [23]. With suitable instructions, also called prompts, GPT-3.5-Turbo
can serve a wide array of applications, including but not limited to
generating code [3], debugging [24], acting as a tutoring assistant[2],
translating languages [25], and even simulating characters for video games
[26]. Following the success of GPT-3.5-Turbo, OpenAI introduced GPT-4, an even
more advanced model with an increased number of parameters and refined
training techniques. The GPT-4 is better than GPT-3.5-Turbo on understanding
and generating text, improving its predecessor in terms of context accuracy,
diversity of output, and adaptability across diverse applications [22]. In
this work, we explore the capability of GPT-3.5-Turbo and GPT-4 in code
optimization.

###  2.3 Sequence-to-Sequence learning

Sequence-to-Sequence (Seq2Seq) learning [27], a concept introduced by the NLP
community, is a machine learning paradigm that models conditional probability
distributions for sequence outputs based on sequence inputs. This is usually
implemented through an end-to-end neural network structure: an encoder and a
decoder. Specifically, the encoder maps the input sequence into a fixed-length
vector. To illustrate, taking code optimization as an example, the encoder
could process a section of code requiring optimization, such as a C++ program,
and convert it into a compact vector representation. Leveraging the powerful
learning capabilities of neural networks, this vector can effectively capture
the semantic information of the input sequence. Subsequently, the decoder
utilizes this vector to produce the output sequence. Continuing with our
example, the decoder could yield a C++ program optimized for some objectives,
e.g., execution speed or memory usage. Training Seq2Seq models are typically
conducted end-to-end, tuning the parameters to maximize the likelihood of the
correct output sequence given the input sequence. Thus, Seq2Seq learning is a
robust framework for tackling generation tasks involving intricate, variable-
length sequence transformations.

##  3 Technical Solution: Supersonic

###  3.1 Overview

Supersonic leverages seq2seq learning initialized with pre-trained models to
generate optimized C/C++ programs. Importantly, the optimized programs are
syntactically similar to the original program, meaning that the optimization
only changes a few lines of the program. It is done by training Supersonic on
program pairs, ($x_{t}$, $x_{t+1}$), where $x_{t}$ and $x_{t+1}$ are
functionally equivalent, with a small edit distance. Supersonic consists of
three phases:  1. Canonicalization,  2. Diff synthesis,  3. Post-processing.

Figure 1 shows the training and inference pipeline of Supersonic for code
optimization from canonicalization to post-processing. The canonicalization
phase canonicalizes the program coding style (whitespaces, tabs, and newlines)
and removes comments before it is used as the input to the diff synthesis
phase. The diff synthesis phase generates multiple optimization candidates in
a diff-based output representation. The post-processing phase checks for the
well-formedness of the diff-based output representation, and then applies the
output as a patch on the original program. For the training stage of
Supersonic, the file is first canonicalized, then it is used as input to the
seq2seq model. The seq2seq model generates a diff-based representation in the
diff synthesis phase, and it is compared with the ground truth to update the
parameter to the seq2seq model in an iterative loop. For the inference stage
of Supersonic, the input still goes through the canonicalization and diff
synthesis phase, but since there is no ground truth, the output is applied to
the original program in the post-processing phase.

In the following sections, we illustrate each phase of Supersonic in detail
and describe our training dataset.

###  3.2 Canonicalize training source code

The goal of the canonicalization phase is to canonicalize program pairs
($x_{t}$, $x_{t+1}$) before they are used as input to the machine learning
model. In this phase, we first remove source code comments and apply a unique,
consistent code style.

We remove source code comments because they are subjective in nature, varying
greatly in style, quality, and content. Meanwhile, although they do not affect
the logical flow of the code, including comments makes the input program
longer, which impacts negatively on the inference performance of the language
model [28].

Input programs also vary in coding styles, for example number of whitespace,
newlines, and how brackets are placed. These are all tokenized and used as
input to the machine-learning model. Therefore we use a single coding style to
let the machine learning model focus on the functionality of the program.

We use GCC (using the command ”gcc -fpreprocessed -dD -E -P”) to remove source
code comments and clang-format (using the command ”clang-format –style=llvm”)
to format all C/C++ programs according to LLVM coding style.

###  3.3 Output representation & Diff synthesis

⬇

#include <algorithm>

#include <iostream>

#include <map>

using namespace std;

using ll = long long;

int main() {

ll N, ans{};

cin >> N;

map<string, int> m;

string S;

while (cin >> S) {

sort(begin(S), end(S));

ans += m[S]++;

}

cout << ans << endl;

}

Listing 1: A user submission to the Green Bin problem at AtCoder

⬇

#include <algorithm>

#include <iostream>

using namespace std;

using ll = long long;

int main() {

ll N, ans{};

cin >> N;

string S;

while (cin >> S) {

sort(begin(S), end(S));

ans += m[S]++;

}

cout << ans << endl;

}

Listing 2: The improved solution by the same user. unordered_map that do not
sort the mapping is used instead. The changed lines are highlighted in red.

⬇

#include <iostream>

-#include <map>

+#include <unordered_map>

using namespace std;

cin >> N;

- map<string, int> m;

+ unordered_map<string, int> m;

string S;

Listing 3: The diff-based output representation by Supersonic, the ‘-’ and ‘+’
are part of the output of the network. Listing 4: The comparison between the
full program and the diff-based output representation generated by Supersonic.
When tokenized, the fully optimized program contains 124 tokens whereas the
diff-based output representation contains 71 tokens. The difference will be
even bigger if the original solution is longer. A longer output increases the
probability of generating an erroneous program because of accumulated
mistakes.

A key aspect of Supersonic is that it generates a diff-based output
representation instead of generating the whole optimized program. The diff-
based output representation is the Unix unified diff format between $x_{t}$
and $x_{t+1}$ with one line context, i.e. one line before and after the
change. Compared to the original diff format, the diff header that specifies
the filenames and changed line numbers is removed. Multiple change hunks are
concatenated with newlines to represent a change that modifies multiple
locations. In contrast, most related works [6, 7] employ a full program output
representation. We use the diff-based output representation because generating
a longer output sequence increases the probability of errors due to
accumulated mistakes. It is widely known that seq2seq models performance
decreases with the output length [29].

subsection 3.3 shows an example of the diff-based output representation
generated by Supersonic. This example is a user submission to AtCoder - Green
Bin problem 333https://atcoder.jp/contests/abc137/tasks/abc137_c. The task is
to find the number of anagrams from a list of strings. The original solution,
1, uses a sorted mapping map to store pairs of strings and integers. The
improved solution, 2, by the same user used unordered_map that does not sort
the mapping compared to map. This change improved the running time from 144 ms
to 97 ms, and memory consumption from 11136 B to 10660 B. Supersonic’s diff-
based output representation of 2 is shown in 3. The diff-based output
representation contains 71 tokens instead of 124 tokens when tokenizing the
full improved program. As we will see in the evaluation, the shorter token
length helps the model to capture knowledge with fewer tokens.

###  3.4 Post-processing synthesized code

During the inference stage of Supersonic, the diff-based output representation
from the diff synthesis phase needs to be patched on the original program to
get the full source code of the predicted optimized program. We greedily match
each predicted changed hunk to the original program using the one-line
context, and then apply the changed hunk. If we fail to match the context
lines in the original program, it means that the diff synthesis phase has
generated a malformed diff-based output representation and we simply discard
it.

###  3.5 Training loop

The core machine learning model of Supersonic that generates and predicts the
diff-based output representation is implemented as a transformer-style seq2seq
model. The encoder and decoder are initialized with CodeBERT which is pre-
trained on C++ code, CodeBERT-CPP [30]. CodeBERT is a pre-trained LLM on
source code and natural language [14]. The training objective of CodeBERT is
masked language modeling, where the model predicts the token masked by a
special mask token, and replaced token detection, where the model predicts if
a token is the original one or not. CodeBERT trained on these two objectives
achieves a robust understanding of code semantics and syntax. By initializing
our model with weights from CodeBERT, we leverage this rich foundation of code
semantics and structure, which accelerates convergence during training and can
lead to better overall performance [31].

Our seq2seq model is trained to generate $x_{t+1}$ by using $x_{t}$ as the
input of the program pair ($x_{t},x_{t+1}$) of the training set. We reuse the
tokenizer CodeBERT-CPP, which is based on the subword tokenization from
WordPiece with $50\,265$ as the vocabulary size [32]. The total amount of
parameters for the seq2seq model is 278M.

Split | Size |  $x_{t}$ LOC |  $x_{t+1}$ LOC |  Supersonic output lines | Codeforces solutions | AtCoder solutions | AIZU solutions
---|---|---|---|---|---|---|---
Train | 312876 | (35, 91) | (35, 90) | (5, 16) | 276714 | 28665 | 7497
Validation | 1000 | (36, 88) | (36, 88) | (5, 15) | 877 | 96 | 27
Test | 559 | (33, 86) | (33, 86) | (5, 17) | 300 | - | 259
Total | 314435 | (35, 91) | (35, 90) | (5, 16) | 277891 | 28761 | 7783
TABLE I: Our dataset statistics. The values in parentheses of the $x_{t}$ LOC, $x_{t+1}$ LOC and Supersonic output lines columns are the lower and upper quartile. Attribute |  Description
---|---
origin |  The origin of the submission: AIZU, AtCoder, or Codeforces
author |  The author of the submission
contest_id |  ID of the contest/problem
submission_id |  ID of the submission
creation_time |  When the submission is created
problem |  The problem name
programming_language |  The programming language: C or C++
cpu_time |  The execution time
memory |  The memory consumption
source_code |  The submission source code
TABLE II: Collected attributes for each submission to AIZU, AtCoder, and
Codeforces.

###  3.6 Training Dataset

Training Supersonic to optimize C/C++ programs requires a dataset of source
code optimization program pairs ($x_{t}$, $x_{t+1}$). In our work, we collect
source code optimization program pairs from code competition websites. Code
competition websites usually record the execution time and memory usage of all
submitted solutions to each problem. It makes them the ideal source to crawl
high-quality and accurate source code optimization program pairs.

In our work, we use data from Codeforces 444https://codeforces.com, as well as
AIZU 555https://judge.u-aizu.ac.jp and AtCoder 666https://atcoder.jp
originally from the CodeNet dataset [33] to build our goal dataset. For the
Codeforces dataset, we first use the Codeforces API to get all the past
contests and submissions to each contest. However, the Codeforces API does not
return the source code, therefore we use another source
777https://codeforces.com/blog/entry/94755 to find the source code for each
submission. For submissions to AIZU and AtCoder, the CodeNet dataset already
provides all the necessary information that we need to process the data. All
the submissions that we collect are accepted by each competition website,
therefore their correctness is guaranteed. The attributes that we collect from
each competition website are shown in Table II.

To ensure the relevance of our dataset, we specifically focused on program
pairs ($x_{t}$, $x_{t+1}$) from the same author, where $x_{t+1}$ strictly
improves either on the running time or memory usage over $x_{t}$. By requiring
the submissions to be in chronological order, we aimed to capture the author’s
progress and improvements over time. This approach allowed us to observe the
evolution of optimizations employed by an author and analyze the specific code
changes that led to enhanced performance. Collecting these pairs of programs
directly from the same author, in chronological order, minimizes confounding
factors such as coding style, enabling us to attribute improved performance to
code changes.

The primary objective of Supersonic is to generate optimized programs while
minimizing the extent of changes from the original code. Intuitively, we want
to train the system to generate optimizations that modify a few lines of code
only. To do this, we filter all pairs of submissions based on the following
criteria:

  1. 1.

At most 20 lines are changed between $x_{t}$ and $x_{t+1}$.

  2. 2.

At most 20% of lines are changed between $x_{t}$ and $x_{t+1}$.

  3. 3.

At least a string similarity score of 0.8 between $x_{t}$ and $x_{t+1}$.

The string similarity metric provides a value between 0.0 and 1.0, with 0.0
indicating two strings are entirely dissimilar and 1.0 indicating a perfect
match between the strings. The string similarity metric we use is the
SequenceMatcher from the Python difflib library. It uses a variant of the
Gestalt pattern matching string-matching algorithm [34].

In total, we collected 20M Codeforces submissions and 6M submissions from the
CodeNet dataset. Then, we extracted 746K and 138K submission pairs from
Codeforces and CodenNet which either improves on the running time or memory
consumption. After filtering the submission pairs, we split the remaining
submission pairs into train, validation, and test sets, consisting of
$312\,876$, $1000$, and $559$ samples, respectively. The pre-training dataset
used to pre-train CodeBERT is the C++ source code of the GitHub-Code-Clean
dataset under the CodeParrot project on Huggingface
888https://huggingface.co/datasets/codeparrot/github-code-clean. The full
dataset statistics are shown in Table I.

##  4 Experimental Setup

In this section, we describe our experimental setup to evaluate Supersonic
against the state-of-the-art related work.

###  4.1 Research Questions

  1. RQ1 - Effectiveness

How does Supersonic compare against GPT-3.5-Turbo and GPT-4 on the task of
code optimization while minimizing the extent of changes?

  2. RQ2 - Optimization Focus

How does Supersonic compare against GPT-3.5-Turbo and GPT-4 depending on the
extent of acceptable changes?

  3. RQ3 - Ablation Study

To what extent is the diff-based output representation better than the full
program output representation?

These research questions are framed to address different aspects of the
problem domain. RQ1 compares Supersonic against GPT-3.5-Turbo and GPT-4 on
running time and memory consumption optimizations, while minimizing the extent
of changes, by submitting predicted program to code competition websites. RQ2
in contrast to RQ1, relaxes the constraint of minimizing the extent of
changes. Lastly, RQ3 explores the impact of using our diff-based output
representation compared to using the full program, to validate our core
design.

###  4.2 Test dataset

Our test dataset, described in subsection 3.6, consists of user submissions of
code competition problems. The problems are of different difficulties and are
designed with possible optimization in mind. These problems are known to be
hard for language models. For example, GPT-4 is ranked at the bottom 5% when
trying to Codeforces problems[22]. The code competition website is also used
to compute and report the running time and memory usage.

Our full test dataset consists of 559 user submissions (see Table I), of which
300 are Codeforces user submissions, and 259 are AIZU user submissions. The
559 user submissions, along with their predictions, and the collected running
time and memory consumption are used to answer all research questions. Our
test set does not overlap with any examples in the pre-training or our own
training dataset. The check is done by checking all pairs of examples in the
test set and the pre-training dataset for exact matches.

###  4.3 Methodology for RQ1

Metrics | GPT-3.5-Turbo | GPT-4 | Supersonic
---|---|---|---
Running time | Memory | Running time | Memory | Running time | Memory
Codeforces | %OPT | 12.0% (36) | 3.7% (11) | 4.0% (12) | 1.3% (4) | 26.0% (78) | 8.0% (24)
| PI |  3.80$\times$ |  11.57$\times$ |  2.73$\times$ |  1.53$\times$ |  2.65$\times$ |  1.81$\times$
AIZU | %OPT | 4.6% (12) | 1.9% (5) | 1.5% (4) | 0.8% (2) | 3.5% (9) | 1.2% (3)
| PI |  6.87$\times$ |  3.69$\times$ |  4.88$\times$ |  2.45$\times$ |  2.82$\times$ |  1.23$\times$

TABLE III: The computed metrics for $300$ Codeforces user submissions and
$259$ AIZU user submissions for GPT-3.5-Turbo, GPT-4 and Supersonic. Within
the parentheses for %OPT is the absolute number of optimized program.

The goal of RQ1 is to study whether Supersonic, OpenAI’s GPT-3.5-Turbo and
GPT-4 can optimize programs. Recall that code optimization typically involves
making edits to only a portion of the original program, without completely
changing it: [35] found that the majority of changes are classified as small,
changing 6-46 lines [35]. With that respect, the experiment takes care of
discarding re-implementations of the original program. Smaller edits are also
less likely to contain bugs [36] and more likely to be accepted as a pull
request [37].

Concretely, Supersonic, GPT-3.5-Turbo and GPT-4 are asked to generate 10
optimization predictions per original program in our test set described in
subsection 3.6. Then, we filter those where the string similarity value
compared to the original program is lower than 0.8, the value we used in
subsection 3.6, in order to discard re-implementations. Next, the metrics that
we use to compare Supersonic and GPT-3.5-Turbo are running time and memory
usage (from [6]):

  * •

Percent optimized \- %OPT: The percentage of optimized programs in the test
set.

  * •

Performance improvement \- PI: The average improvement in running time or
memory usage of the best-optimized program among the predictions. If old and
new are running time or memory usage of the original and optimized program,
then $\textsc{PI}=\frac{\textit{old}}{\textit{new}}$. We report the average PI
over the test set.

We compute these metrics for strictly better memory improvements and for
strictly better running time improvements. We realize that code competition
measurements are not perfectly precise and tend to have some variation. To
account for this noise, we only consider a program to be truly more optimized
if the performance improvement is at least 20%, i.e. PI is at least $1.2$.

⬇

system prompt: I want you to act as an experienced C and C++ developer and
your task is to optimize my written C or C++ programs. I want you to optimize
my program for running time and memory usage. I will type my C or C++ program
and you will optimize the program and return the optimized program. I want you
to only reply with the fixed program inside one unique code block, and nothing
else. Do not write explanations.

user prompt: [CODE]

Listing 5: The prompt used for querying OpenAI models to generate more
optimized programs.

We utilize OpenAI’s official APIs to call GPT-3.5-Turbo and GPT-4 for
generating predictions. As per OpenAI’s official API
documentation999https://platform.openai.com/docs/models/gpt-3-5, the APIs are
updated to incorporate the latest model iteration approximately two weeks
subsequent to its
release101010https://help.openai.com/en/articles/6825453-chatgpt-release-
notes. To ensure clarity regarding the API version employed in our
experiments, our predictions spanned from April 17 to July 5 2023, whereas for
GPT-4, predictions were conducted between August 21 and August 25 2023. The
GPT-3.5-Turbo and GPT-4 prompt we use to generate the predictions is shown in
5. We use a carefully designed prompt per the best
practices111111https://github.com/f/awesome-chatgpt-prompts. The prompt
instructs the model to act as an experienced C/C++ developer and optimize the
given program with respect to running time and memory usage.

###  4.4 Methodology for RQ2

In RQ2, the goal is to study to what extent Supersonic, GPT-3.5-Turbo and
GPT-4 optimize by re-implementing. To do that, we compare Supersonic,
GPT-3.5-Turbo and GPT-4 at various string similarity thresholds using the same
protocol as RQ1. Also, we study the string similarity distribution for all
predictions to see how much the programs are changed for Supersonic and
GPT-3.5-Turbo. Then, we plot the %OPT value for different string similarity
thresholds between 0 and 1.

###  4.5 Methodology for RQ3

The goal of RQ3 is to evaluate if the diff-based output representation is a
better code representation than the full program representation. We use the
same model architecture and the same dataset split described in subsection 3.6
and used in RQ1 and RQ2. The only difference is that one model learns to
generate the full program, while the other learns to generate the diff-based
output representation described in subsection 3.3. Similar to RQ1 described in
subsection 4.3, 10 predictions are generated per sample in the test set and
predictions with a string similarity value below 0.8 are filtered. The rest
are submitted to the corresponding code competition website. We compute %OPT
and SP on running time and memory consumption.

##  5 Results

###  5.1 Answer to RQ1 (Effectiveness)

⬇

-28,12 +28,7 @@

sort(v.rbegin(), v.rend());

for (int i = 0; i < v.size(); i++) {

sm += v[i];

- if (i == 0)

- arr[0] = v[0];

- else {

- arr[i] = sm / (i + 1);

- }

- if (arr[i] >= m)

+ if (sm / (i + 1) >= m)

cnt++;

}

cout << cnt << E;

#include <algorithm>

#include <cmath>

Listing 6: Unified diff for one optimization by Supersonic. It simplifies if
statements, and removes the need of array arr. The string similarity between
the original and predicted program is 0.95. The original problem is the Middle
Class problem on
Codeforces131313https://codeforces.com/problemset/problem/1334/B.

⬇

-1,3 +1,6 @@

+#pragma GCC optimize(”Ofast”)

+#pragma GCC optimize(”unroll-loops”)

+#pragma GCC target(”avx,avx2,sse,sse2”)

#define _CRT_SECURE_NO_WARNINGS

#include <algorithm>

#include <cmath>

Listing 7: Unified diff for another optimization by Supersonic. It add several
GCC pragmas that instructs the GCC compiler on how to handle the code. These
optimize the code’s execution speed and enable specific compiler optimizations
and instruction sets. The string similarity between the original and predicted
program is 0.99. The original problem is the WW problem on
AIZU151515https://onlinejudge.u-aizu.ac.jp/problems/1537.

Table III shows the comparison between Supersonic, GPT-3.5-Turbo, and GPT-4 on
generating source code optimizations for Codeforces and AIZU submissions. For
the Codeforces submissions, Supersonic generates optimizations that improve
26.0% (78) and 8.0% (24) of the programs on running time and memory
consumption respectively. This shows the advantage and efficacy of Supersonic
over both GPT-3.5-Turbo and GPT-4, illustrating its capability for optimizing
a range of problems, even when compared against the most advanced generative
models currently available. This is despite the fact that Supersonic is 600x
and 3700x smaller than GPT-3.5-Turbo and GPT-4. For AIZU submissions, both
Supersonic and GPT-3.5-Turbo perform at a similar level for running time and
memory optimization, while GPT-4 is still performing worse. The reason why
Supersonic has a lower performance for AIZU submissions than Codeforces
submissions might be because our training data contains more than 80% program
pairs from Codeforces, hence have better learned on that type of problem. The
problem set on Codeforces and AIZU is indeed different, Codeforces being
competitive in nature with regular contests dividing participants with
ratings, AIZU being primarily an educational platform.

6 and 7 are two examples of optimization by Supersonic, as a diff between the
original and generated program. The first example simplifies the if statements
to a single if statement and removes the need for the array arr that keeps the
intermediate values. The generated example reduces the memory consumption from
2.64MB to 1.56MB, saving 41% of memory usage. The second example adds three
GCC pragma directives that are instructions to the GCC compiler on how to
compile the code. optimize(”Ofast”) enables all -O3 optimizations along with
those applicable to all programs compliant with the standard.
optimize(”unroll-loops”) unroll loops, a technique that attempts to optimize
the running time by sacrificing the binary size. target(”avx,avx2,sse,sse2”)
enables the use of specific instruction set extensions for vector operations.
The generated program reduces the running time to 7ms from the original 17ms,
which is a significant 60% decrease. This also demonstrates that Supersonic is
able to instruct the compiler on how to better compile the program, in
addition to changing the data structures, compilers, or algorithms.

We give a breakdown of all 5590 predicted programs (10x559 predictions, for
every program in the test set), for Supersonic. The post-processing phase of
Supersonic removed 2045 programs because of malformed diff-based output
representation that can not be applied to the original program. For the
remaining 3545 programs that we submitted for evaluation, 1686 programs are
accepted as valid solutions, they compile and pass the functional tests,
showing the capabilities of Supersonic to output proper syntax and to maintain
semantics. Among the 1686 accepted programs, 356 programs either improved the
running time or memory consumption.

RQ1: Supersonic, a model 600x and 3700x smaller than GPT-3.5-Turbo and GPT-4
is able to generate significantly more optimized programs than OpenAI models.
It is capable of producing, short, target optimizations, including appropriate
compiler directive addition.

###  5.2 Answer to RQ2 (Optimization Focus)

Figure 2: The string similarity distribution for the similarity between the
predicted submission and the original solution. Best viewed in color. Figure
3: %OPT for running time optimization of Supersonic, GPT-3.5-Turbo and GPT-4
if we limit the string similarity at various thresholds between the predicted
submission and the original solution.

⬇

-1,18 +1,24 @@

-#include <bits/stdc++.h>

+#include <iostream>

+#include <cstring>

using namespace std;

+

int main() {

- string s;

- cin >> s;

- short i, t = 0;

- for (i = 0; i < s.size(); i++) {

- if (s[i] > 96)

- t++;

- }

- i = s.size() - t;

- if (t < i)

- transform(s.begin(), s.end(), s.begin(), ::toupper);

- else

- transform(s.begin(), s.end(), s.begin(), ::tolower);

- cout << s;

- return 0;

-}

+ char s[1000001];

+ cin >> s;

+ int upper = 0, lower = 0;

+ for (int i = 0; i < strlen(s); i++) {

+ if (s[i] >= ’a’ && s[i] <= ’z’) lower++;

+ else upper++;

+ }

+ if (upper > lower) {

+ for (int i = 0; i < strlen(s); i++) {

+ s[i] = toupper(s[i]);

+ }

+ } else {

+ for (int i = 0; i < strlen(s); i++) {

+ s[i] = tolower(s[i]);

+ }

+ }

+ cout << s;

+ return 0;

+}

Listing 8: Unified diff for one example prediction from GPT-3.5-Turbo. Almost
all source code lines are changed and the string similarity between the
prediction and original program is 0.36. This cannot be considered as a
targeted optimization. The original problem is the Word problem on
Codeforces171717https://codeforces.com/problemset/problem/59/A.

The string similarity distribution for all generated programs is shown in
Figure 2. GPT-3.5-Turbo and GPT-4 generate prediction at all string similarity
levels, which means they sometimes generate target optimizations and sometimes
rewrite the whole program. On the contrary, most of Supersonic’s predictions
have a high string similarity (red distribution shifted to the right), which
shows Supersonic generates much more precise edits to the programs under
optimization. In addition, we see that most generated programs have a
similarity higher than 0.8, which is very consistent with the training data
curation, as described in subsection 3.2, showing the soundness of the end-to-
end training and inference loop.

Figure 3 shows how the %OPT metric changes with different string similarity
thresholds for generated programs that optimize the running time. The y-axis
is the %OPT value. The x-axis is the string similarity threshold, meaning that
we filter all generated programs with a lower string similarity score than the
corresponding x value. For $x=0$, it means that we include all generated
programs, and for $x=1$, all generated programs are filtered out. Reading the
graph from right to left, we can see that Supersonic is the best (red curve at
the top) until the string similarity threshold is close to 0.4. This means the
string similarity threshold of 0.8 in RQ1 was not a magic, unstable one.
Rather, it can be changed to a large degree and Supersonic would still be the
best performing tool. From the same graph, we can also see that GPT-4 performs
better than GPT-3.5-Turbo when the threshold is 0, but the relationship
reverses when the threshold is higher. Overall, it is clear that GPT-4 is
generating more full rewrites than GPT-3.5-Turbo.

To give an idea of how dissimilar two programs are when the similarity score
is low, 8 shows a GPT-3.5-Turbo generated program with similarity 0.36. It is
clear that most lines are changed, including variable names. Other significant
rewrites by GPT-3.5-Turbo in that example include std::transform substituted
with for-loops and char type used instead of integer for comparison.

RQ2: Supersonic is the best performing model compared to GPT-3.5-Turbo and
GPT-4 even when we lower the similarity threshold. GPT-3.5-Turbo and GPT-4
tend to optimize by fully rewriting the program which is argued to be a
different task than optimization, closer to re-implementation. To the best of
our knowledge, Supersonic is the best model for generating precise, targeted,
and effective source code optimizations.

###  5.3 Answer to RQ3 (Ablation Study)

1717footnotetext: https://codeforces.com/problemset/problem/59/A

Metrics |  Supersonic Full |  Supersonic Diff
---|---|---
Running time | Memory | Running time | Memory
Codeforces | %OPT | 11.0% (33) | 2.7% (8) | 26.0% (78) | 8.0% (24)
| PI |  3.28$\times$ |  1.57$\times$ |  2.65$\times$ |  1.81$\times$
AIZU | %OPT | 1.5% (4) | 0.0% (0) | 3.5% (9) | 1.2% (3)
| PI |  3.24$\times$ |  0.00$\times$ |  2.82$\times$ |  1.23$\times$

TABLE IV: Supersonic with diff-based output representation (Supersonic Diff)
and full program (Supersonic Full) as output. Within the parentheses for %OPT
is the absolute number of optimized programs

For this research question, we focus on investigating the efficacy of two
distinct code output representations when training our Supersonic model. One
version of Supersonic is trained to generate an entire program as output,
exemplified in 2. The second version is trained to produce a diff-based output
representation, which can be seen in 3. Table IV shows the comparison between
the two versions on the predicted submission to the Codeforces and AIZU code
competition website.

Supersonic with a diff-based output representation is clearly better than
Supersonic with a full program output. The diff-based output representation
optimizes more programs on both Codeforces (26.0% versus 11.0% for running
time, 8.0% versus 2.7% for memory consumption) and AIZU (3.5% versus 1.5% for
running time, 1.2% versus 0.0% for memory consumption). Considering the
presented data, it is evident that the diff-based output representation of
Supersonic consistently outperforms its full program counterpart in terms of
generating a higher percentage of optimized programs.

This fully validates our initial hypothesis that longer output sequences are
harder to learn and lower the overall performance of the model. However, the
diff-based representation comes at a cost of stricter well-formedness rules
for applying the diff-based output. During the breakdown of all generated
programs of Supersonic in RQ1, we indeed showed that a portion of diff-based
output representations are malformed (2045 out of 5590). While being
potentially valid optimizations, this results in fewer programs being
submitted for evaluation. Overall, the advantages of the sort diff
representation win over the cons, and Supersonic with diff-based output
representation clearly outperforms the full program output representation.

RQ3: Supersonic with the original diff-based output representation doubles the
performance, compared to traditional full program output representation. While
the majority of works in the field of code generation with deep learning use
full program or full function output, our results clearly call for more
exploration of shorter, contextual output representations such as
Supersonic’s.

##  6 Discussion

###  6.1 Threats to Validity

####  6.1.1 Internal Threats

##### Data leakage.

The evaluation of GPT-3.5-Turbo and GPT-4 poses an internal threat in the form
of potential data leakage that is beyond our control. The data used to train
GPT-3.5-Turbo and GPT-4 is not publicly accessible, which means we lack
visibility into the specific information it was exposed to during its training
process. Consequently, there exists a potential risk of data leakage that
GPT-3.5-Turbo and GPT-4 has already seen examples in the test set during its
training process.

##### Functionally incorrect programs.

We have noticed that some original programs are functionally correct according
to the original metadata, but they failed when we submitted them ourselves.
For Codeforces, the main reason was that they were either because of
time/memory limit, or compilation error. For AIZU, it is a mix of compile
error, time/memory limit, and wrong answer. We hypothesize that it is because
of the compiler version being updated throughout the year. For these programs,
we still count them as failures when calculating the %OPT value to ensure a
fair comparison.

##### Measurement uncertainty.

We also found that if we submit the same program twice to the Codeforces
platform, we may get different execution times, e.g. 0ms and 15ms. This is
because the Codeforces platform splits the execution time as different blocks,
which means 0ms and 15ms are equal. Therefore when comparing execution time
for programs on Codeforces, we divided all time into blocks of 16, i.e. 0 and
15 would be block 1, 16 and 31 would be block 2. Then we use the block number
to calculate the speed up. Additionally, to account for noise, we also define
a program to be more optimized if the time or memory improvement is at least
1.2, as mentioned in subsection 4.3.

####  6.1.2 External Threats

A significant external threat is that CodeNet and Codeforces datasets are both
from code competition websites. They do not fully represent the diversity of
real-world optimization problems. The problems on competition websites are
designed with code optimizations in mind, and they facilitate the comparison
between submissions by having functional correctness, running time, and memory
consumption as part of their result. However, real-world optimizations are
likely more varied. Future work may address this threat by creating new
benchmarks for code optimization.

###  6.2 Code Optimization Versus Code Synthesis

Our extensive experience looking at predicted optimization has convinced us
that the boundary between code optimization and code synthesis is hard to
define. Consider a hypothetical example: an original program implements a
naive algorithm to sort a list, such as bubble sort. In some cases, the
distinction between optimization and synthesis is obvious, for example if the
model proposes to replace the original program with a quicksort or mergesort
implementation. In other cases, if the model made many changes while retaining
the core concept of bubble sort, the distinction is less clear.

The distinction between code optimization and full re-implementation has
received limited attention in related research. We believe that clarifying
this distinction is crucial in understanding the true capabilities of neural
models. In this paper, we contribute to this clarification in a fully
operational way. We draw the line between optimization and re-implementation
by looking at the string similarity between the original and the predicted
optimized program. This is a well-formed definition: a string similarity value
of 0 is pure code synthesis, and a value close to 1 is a small change to the
program. Nonetheless, this purely syntactic solution could be improved with
semantic and runtime analysis, we leave this as a topic for future
exploration.

###  6.3 Importance of Input/Output Code Representation

Designing the input and output representations of code for machine learning
models is a critical aspect that demands careful consideration. The
effectiveness of these representations can significantly impact the
performance and efficiency of the resulting models.

Creating an appropriate input representation for code is akin to providing the
model with the right set of tools for understanding and processing the task at
hand. When designing input representations, it is essential to strike a
balance between comprehensiveness and conciseness. The representation must
capture the relevant information that enables the model to perform the desired
task effectively. For the code optimization task, it is uncommon that we know
in advance the source code location where we can optimize the program. In
comparison with other code-related tasks such as the program repair task, we
often have fault localization techniques that guide us toward the buggy
locations. Therefore for Supersonic, we decided to use the full program as
input.

Crafting a concise and precise output representation for code is akin to
presenting the model’s insights and solutions in a simple manner, ensuring
that the generated code conveys the intended functionality without unnecessary
redundancy. Redundancy in the output is repeating information that was present
in the input and increases the probability of unnecessary mistakes. Such
mistakes are more unforgiving than mistakes in natural languages, as programs
are interpreted by compilers with strict parser rules. In Supersonic, we use
the diff-based output representation to minimize the redundancy and risk of
mistakes and only keep two context lines to localize the change. RQ3 proves
that this design choice alone improves the performance of the model by 2
times. It shows the importance of designing a proper input and output
representation for machine learning for code models that are rarely discussed.

###  6.4 Large versus Small Models

It is widely accepted that larger models perform better, they are more sample
efficient [12], are few-shot learners [38], and the performance increases with
model size [20]. Furthermore, the accuracy and the robustness of a model also
increase with dataset size [39]. One model that we compared against,
GPT-3.5-Turbo, has at least 175B parameters and is trained on 500 billion
tokens [12]. It demonstrated capabilities for many software engineering-
related tasks, such as code generation [3], program repair [4], and code
summarization [2]. In RQ2 of our study, we have also shown the good
performance of GPT-3.5-Turbo on the code optimization task. However in RQ1,
Supersonic was able to outperform GPT-3.5-Turbo on the task of generating
similar but optimized programs, despite being approximately 600x smaller (175B
versus 278M) and trained with much less data. It shows the relevance of
training a smaller model focusing on a single task with well-curated input and
output representation.

##  7 Related Work

###  7.1 ML for Source Code Optimization

PIE4Perf is the most related work [6]. In this work, [6] investigates the
ability of large language models to suggest performance-improving code edits.
First, they extract samples of performance-improving code edits from the
Codenet dataset. Then, they fine-tune the CodeGen model and they prompt Codex
using few-shot prompting. They find that the system can generate performance-
improving edits with speedups of more than 2.5x for over 25% of the programs,
with a model 10x smaller than Codex to match its performance. The main
differences between Supersonic and PIE4Perf are: 1) we study both the running
time and memory optimization while PIE4Perf only looks at running time
optimization. 2) Supersonic is based on an original diff-based output
representation, while PIE4Perf outputs simple vanilla programs. 3) we take
care of removing re-implementations in the evaluation procedure, yielding more
meaningful measurements. 4) we report competitive results w.r.t. GPT-3.5-Turbo
and GPT-4 with a model that is 600x and 3700x smaller.

DeepDev-PERF is a deep learning-based approach to improve software performance
for C# applications [7]. The model is pre-trained on both English and source
code corpora and fine-tuned on the task of performance improvement for C#
applications. The evaluation shows that the model can generate the same
performance improvement suggestions as the developer patches in 53% of the
cases. The authors also submitted 19 pull requests with performance
optimizations, of which 11 of these are accepted. Supersonic is different from
DeepDev-PERF by looking at C/C++ optimizations. The evaluation is also done by
submitting to code competition websites that report the running time and
memory consumption, instead of using the benchmark.

[40] propose a discrete variational auto-encoder to extract discrete latent
variables, each representing a code-edit that increases program performance
[40]. The learned discrete latent variables can be used to guide programmers
toward writing more efficient source code. They show that the discrete
variational auto-encoder extracts better code efficiency edits than the
Transformer baseline. Supersonic on the other hand does not extract code
efficiency edits but directly predicts the more optimized program in an end-
to-end way.

RAPGen is an approach based on the OpenAI Codex model to do zero-shot code
inefficiency fixing in C# methods [41]. This is done by first collecting a
dataset of performance bug fixes by keyword matching on the commit message.
The dataset is used to extract identifiers that are changed in the commits to
form a knowledge base. The knowledge base is used to form an instruction to
describe which identifiers were added/removed/edited when giving the input
method. To predict the code inefficiency fix, they build a prompt by using the
buggy method as a comment, followed by the instruction of which variables to
change, and ending with the buggy method’s signature. The prompt is used as
input to the Codex model, and it generates the fixed method. They found that
it performs better than DeepDev-PERF on exact match and CodeBLEU score,
without any training.

Artemis++ is a tool for syntax-based optimization of C++ using a genetic
algorithm [42]. The tool automatically chooses implementations of common data
structures to provide performance improvements. It uses a genetic algorithm
that automatically performs source code transformations and produces an
optimized version of the program. The tool is evaluated on three C++
libraries, observing improvements by up to 16.09%, 27.90%, and 2.74% for CPU
usage, runtime, and memory, respectively. Supersonic is different in that it
is trained to do more than data structure optimization, and relies on language
model and seq2seq learning instead of a genetic algorithm.

LoopLearner is a tool that predicts the speedup of loop transformations [43].
They encode the source code as a vector and concatenate a compact encoding of
transformations to the vector. The concatenated vector is then fed into CNN or
RNN to predict the speedup of transformations. They found that by applying the
top transformation, the program yields an average speedup of 1.29x. While
LoopLearner only focuses on loops, Supersonic’s input the whole program and
can target different source code locations.

###  7.2 ML for Compiler Optimization

[*]ashouri2018survey have a survey about compiler autotuning [44]. They
summarize papers on two problems in the machine learning for compiler
optimization field, 1) selecting the best optimization and 2) the phase-
ordering of optimizations. [*]wang2018machine focus more on the different
machine-learning techniques used in the compiler optimization field.

[*]cummins2020programl propose ProGraML, a graph-based program representation,
that can be used as input to machine learning models [46]. The representation
is a union of a control flow graph, data flow graph, and call flow graph. They
show that on the task of choosing a CPU or GPU to run an OpenCL kernel, it
surpassed prior approaches on all metrics.

DeepTune is a tool that predicts optimization heuristics on OpenCL kernel
[47]. It directly uses the source code, instead of the binary code, as the
input to an LSTM model to predict heterogeneous mapping (CPU or GPU) and
OpenCL thread coarsening factor. The results show that by learning directly on
source code, instead of manual features extracted from the binary code,
DeepTune could match or surpass 89% of the predictions.

[*]narayanamurthy2016finding use genetic algorithms to find the best set of
compiler optimizations that optimized the performance while providing better
error resilience [48]. The fitness function used in the genetic algorithm
measures the error resilience of a candidate optimization. The resulting
program is able to achieve similar performance as -O1, -O2, and -O3 while
having better error resilience.

[*]schulte2014post use a genetic algorithm to reduce the non-functional
properties of executables such as power efficiency [49]. The fitness function
used in the genetic algorithm is hardware performance counters combined into a
single scalar value. They find that they can reduce on average 20% energy
usage on AMD and Intel systems.

[*]wang2013using use machine learning to partition stream processing programs
[50]. The partition refers to dividing the program graph into clusters that
are allocated to threads. They define different program features and used PCA
to reduce the dimensionality to 10. Then, they use a k-means clustering
algorithm to find the previous similar good partitions. They find that it
achieves a 1.90x speedup over the already-tuned partition by the compiler.

[*]churchill2017sound propose an approach to optimize loops in the Google
native Client [51]. The approach has a bounded verifier that verifies the
correctness of a loop transformation up to bound k. If it fails, it can create
a counter-example that guides the search away from this transformation. Then
they apply a sound verifier that uses strong loop invariants. In the
evaluation, they achieve an average 25% speedup compared to libraries shipped
by Google, and the optimized program can be formally verified.

Stoke is a tool that formulates the binary superoptimization problem as a
stochastic search problem [52]. The search is guided by a cost function with a
correctness term and a performance term. They use Markov chain Monte Carlo to
sample the binary modification. By starting with a binary that is compiled
with -O0, Stoke was able to either match or outperform code produced by -O3.

[*]bunel2016learning improve upon Stoke by replacing the searched distribution
[53]. Stoke uses a uniform distribution to sample modifications of the
program, and [*]bunel2016learning instead used reinforcement learning to learn
the distribution from past behaviors and program semantics. By doing so, they
can increase the probability of reaching the best-optimized programs and
generate better programs in fewer iterations.

[*]rotem2021profile tackle the problem of improving the LLVM’s
BranchProbabilityInfo (BPI) heuristics [54]. They first use the profile-guided
optimization (PGO) workflow to compile many different programs and record
their branch probabilities. These data are used to train a model of gradient-
boosted trees. Once the model is trained, it can be used to predict branch
probabilities on programs without PGO workflow. They find that the geometric
mean speedup of the new BPI heuristic across 10 workloads is 1.016.

[*]baghdadi2021deep develop a deep learning-based cost model for predicting
speedups of code transformations in the Tiramisu compiler [55]. The training
data is created by generating random programs, applying a series of code
transformations, and recording the actual speedups. The deep learning model is
a combination of recurrent and recursive neural networks. They find that the
proposed model has only 16% of mean absolute percentage error in predicting
speedups on full programs and that it is able to find transformations that
match or are better than SOTA compilers.

[*]agakov2006using use machine learning to speed up the process of iterative
optimization on loops [56], i.e., iterative try different compilation
optimization to determine the best set of compilation optimization. They
extract different features from the loop and use PCA to represent the loop
with a 5-dimension vector. This vector is used to determine the nearest
neighbor in the training data and extract the best compilation optimization.
They found that the average speedup is 1.22x on the T1 C6713 and 1.27x on the
AMD Au1500.

###  7.3 Other Work on Optimization

[*]petke2017genetic have a comprehensive survey about papers using genetic
algorithms to improve programs [57]. They find that genetic algorithm has been
able to improve the performance of a program for a diverse set of properties,
such as execution time, energy, and memory consumption.

[*]marco2017improving propose an approach to estimate the memory behavior of
Spark applications to allow higher server utilization and system throughput
[58]. They extract 22 raw features from the application and use PCA to reduce
it to 5 principal components. To predict the function that best describes the
memory usage, they use K nearest neighbor to find the most similar cluster.
The evaluation shows that they achieve a 1.28x improvement on system
throughput and 1.68x on turnaround time.

[*]chen2018learning introduce a framework AutoTVM to optimize tensor operators
that are used in deep learning models [59]. They use simulated annealing with
a statistical cost function trained from past historical data to find more
optimized low-level code. Experiments on existing frameworks show that it
yields 1.2x to 3.8x performance improvement.

[*]ahn2020chameleon propose Chameleon that improves upon AutoTVM by using
reinforcement learning to optimize tensor operators [60]. Instead of using
simulated annealing that relies on random walks, they use adaptive exploration
by leveraging reinforcement learning. The result is that they achieve a 4.45x
speed up in optimization time over AutoTVM.

##  8 Conclusion

In this paper, we have proposed Supersonic, a tool that can generate source
code optimizations for C/C++ programs with targeted changes. Supersonic
features an original diff-based output representation that is similar to a
software patch. Our experiments clearly show that Supersonic outperforms
GPT-3.5-Turbo and GPT-4 on the task of source code optimization. We believe
that there is a large research avenue in the area of using small but specific
models targeting a given software engineering task instead of using larger
general models.

## References

  * [1] Caitlin Sadowski et al. “Tricorder: Building a program analysis ecosystem” In _2015 IEEE/ACM 37th IEEE International Conference on Software Engineering_ 1, 2015, pp. 598–608 IEEE
  * [2] Haoye Tian et al. “Is ChatGPT the Ultimate Programming Assistant–How far is it?” In _arXiv preprint arXiv:2304.11938_ , 2023
  * [3] Chao Liu et al. “Improving ChatGPT Prompt for Code Generation” In _arXiv preprint arXiv:2305.08360_ , 2023
  * [4] Dominik Sobania, Martin Briesch, Carol Hanna and Justyna Petke “An analysis of the automatic bug fixing performance of chatgpt” In _arXiv preprint arXiv:2301.08653_ , 2023
  * [5] Russell A Poldrack, Thomas Lu and Gašper Beguš “AI-assisted coding: Experiments with GPT-4” In _arXiv preprint arXiv:2304.13187_ , 2023
  * [6] Aman Madaan et al. “Learning performance-improving code edits” In _arXiv preprint arXiv:2302.07867_ , 2023
  * [7] Spandan Garg et al. “DeepDev-PERF: a deep learning-based approach for improving software performance” In _Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2022, pp. 948–958
  * [8] Jacob Devlin, Ming-Wei Chang, Kenton Lee and Kristina Toutanova “Bert: Pre-training of deep bidirectional transformers for language understanding” In _arXiv preprint arXiv:1810.04805_ , 2018
  * [9] Ashish Vaswani et al. “Attention is all you need” In _Advances in neural information processing systems_ 30, 2017
  * [10] Alec Radford, Karthik Narasimhan, Tim Salimans and Ilya Sutskever “Improving language understanding by generative pre-training” OpenAI, 2018
  * [11] Mike Lewis et al. “Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension” In _arXiv preprint arXiv:1910.13461_ , 2019
  * [12] Tom Brown et al. “Language models are few-shot learners” In _Advances in neural information processing systems_ 33, 2020, pp. 1877–1901
  * [13] Colin Raffel et al. “Exploring the limits of transfer learning with a unified text-to-text transformer” In _The Journal of Machine Learning Research_ 21.1 JMLRORG, 2020, pp. 5485–5551
  * [14] Zhangyin Feng et al. “Codebert: A pre-trained model for programming and natural languages” In _arXiv preprint arXiv:2002.08155_ , 2020
  * [15] Xiaodong Gu, Hongyu Zhang and Sunghun Kim “Deep code search” In _Proceedings of the 40th International Conference on Software Engineering_ , 2018, pp. 933–944
  * [16] Xing Hu et al. “Deep code comment generation” In _Proceedings of the 26th conference on program comprehension_ , 2018, pp. 200–210
  * [17] Yue Wang, Weishi Wang, Shafiq Joty and Steven CH Hoi “Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation” In _arXiv preprint arXiv:2109.00859_ , 2021
  * [18] Hugo Touvron et al. “Llama: Open and efficient foundation language models” In _arXiv preprint arXiv:2302.13971_ , 2023
  * [19] Teven Le Scao et al. “Bloom: A 176b-parameter open-access multilingual language model” In _arXiv preprint arXiv:2211.05100_ , 2022
  * [20] Aakanksha Chowdhery et al. “Palm: Scaling language modeling with pathways” In _arXiv preprint arXiv:2204.02311_ , 2022
  * [21] OpenAI “Introducing ChatGPT”, 2022 URL: https://openai.com/blog/chatgpt
  * [22] OpenAI “GPT-4 Technical Report” In _arXiv preprint arXiv:2303.08774_ , 2023
  * [23] Long Ouyang et al. “Training language models to follow instructions with human feedback” In _Advances in Neural Information Processing Systems_ 35, 2022, pp. 27730–27744
  * [24] Nigar M Shafiq Surameery and Mohammed Y Shakor “Use chat gpt to solve programming bugs” In _International Journal of Information Technology & Computer Engineering (IJITC) ISSN: 2455-5290_ 3.01, 2023, pp. 17–22
  * [25] Wenxiang Jiao et al. “Is ChatGPT a good translator? A preliminary study” In _arXiv preprint arXiv:2301.08745_ , 2023
  * [26] Joon Sung Park et al. “Generative agents: Interactive simulacra of human behavior” In _arXiv preprint arXiv:2304.03442_ , 2023
  * [27] Ilya Sutskever, Oriol Vinyals and Quoc V Le “Sequence to sequence learning with neural networks” In _Advances in neural information processing systems_ 27, 2014
  * [28] Cem Anil et al. “Exploring length generalization in large language models” In _Advances in Neural Information Processing Systems_ 35, 2022, pp. 38546–38556
  * [29] Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau and Yoshua Bengio “On the properties of neural machine translation: Encoder-decoder approaches” In _arXiv preprint arXiv:1409.1259_ , 2014
  * [30] Shuyan Zhou, Uri Alon, Sumit Agarwal and Graham Neubig “CodeBERTScore: Evaluating Code Generation with Pretrained Models of Code” arXiv, 2023 URL: https://arxiv.org/abs/2302.05527
  * [31] Alaa Sagheer and Mostafa Kotb “Unsupervised pre-training of a deep LSTM-based stacked autoencoder for multivariate time series forecasting problems” In _Scientific reports_ 9.1 Nature Publishing Group UK London, 2019, pp. 19038
  * [32] Yonghui Wu et al. “Google’s neural machine translation system: Bridging the gap between human and machine translation” In _arXiv preprint arXiv:1609.08144_ , 2016
  * [33] Ruchir Puri et al. “Codenet: A large-scale ai for code dataset for learning a diversity of coding tasks” In _arXiv preprint arXiv:2105.12655_ , 2021
  * [34] John W Ratcliff and David Metzener “Pattern matching: The gestalt approach” In _Dr. Dobb’s Journal_ 13.7, 1988, pp. 46
  * [35] Abdulkareem Alali, Huzefa Kagdi and Jonathan I Maletic “What’s a typical commit? a characterization of open source software repositories” In _2008 16th IEEE international conference on program comprehension_ , 2008, pp. 182–191 IEEE
  * [36] Ranjith Purushothaman and Dewayne E Perry “Toward understanding the rhetoric of small source code changes” In _IEEE Transactions on Software Engineering_ 31.6 IEEE, 2005, pp. 511–526
  * [37] Peter Weißgerber, Daniel Neu and Stephan Diehl “Small patches get in!” In _Proceedings of the 2008 international working conference on Mining software repositories_ , 2008, pp. 67–76
  * [38] Jared Kaplan et al. “Scaling laws for neural language models” In _arXiv preprint arXiv:2001.08361_ , 2020
  * [39] Suhua Lei, Huan Zhang, Ke Wang and Zhendong Su “How training data affect the accuracy and robustness of neural networks for image classification”, 2018
  * [40] Binghong Chen et al. “Learning to Improve Code Efficiency” In _arXiv preprint arXiv:2208.05297_ , 2022
  * [41] Spandan Garg, Roshanak Zilouchian Moghaddam and Neel Sundaresan “Rapgen: An approach for fixing code inefficiencies in zero-shot” In _arXiv preprint arXiv:2306.17077_ , 2023
  * [42] Rafail Giavrimis et al. “Genetic optimisation of C++ applications” In _2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ , 2021, pp. 1180–1182 IEEE
  * [43] Rahim Mammadli, Marija Selakovic, Felix Wolf and Michael Pradel “Learning to make compiler optimizations more effective” In _arXiv preprint arXiv:2102.13514_ , 2021
  * [44] Amir H Ashouri et al. “A survey on compiler autotuning using machine learning” In _ACM Computing Surveys (CSUR)_ 51.5 ACM New York, NY, USA, 2018, pp. 1–42
  * [45] Zheng Wang and Michael O’Boyle “Machine learning in compiler optimization” In _Proceedings of the IEEE_ 106.11 IEEE, 2018, pp. 1879–1901
  * [46] Chris Cummins et al. “Programl: Graph-based deep learning for program optimization and analysis” In _arXiv preprint arXiv:2003.10536_ , 2020
  * [47] Chris Cummins, Pavlos Petoumenos, Zheng Wang and Hugh Leather “End-to-end deep learning of optimization heuristics” In _2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT)_ , 2017, pp. 219–232 IEEE
  * [48] Nithya Narayanamurthy, Karthik Pattabiraman and Matei Ripeanu “Finding resilience-friendly compiler optimizations using meta-heuristic search techniques” In _2016 12th European Dependable Computing Conference (EDCC)_ , 2016, pp. 1–12 IEEE
  * [49] Eric Schulte et al. “Post-compiler software optimization for reducing energy” In _ACM SIGARCH Computer Architecture News_ 42.1 ACM New York, NY, USA, 2014, pp. 639–652
  * [50] Zheng Wang and Michael FP O’boyle “Using machine learning to partition streaming programs” In _ACM Transactions on Architecture and Code Optimization (TACO)_ 10.3 ACM New York, NY, USA, 2013, pp. 1–25
  * [51] Berkeley Churchill, Rahul Sharma, JF Bastien and Alex Aiken “Sound loop superoptimization for google native client” In _ACM SIGPLAN Notices_ 52.4 ACM New York, NY, USA, 2017, pp. 313–326
  * [52] Eric Schkufza, Rahul Sharma and Alex Aiken “Stochastic superoptimization” In _ACM SIGARCH Computer Architecture News_ 41.1 ACM New York, NY, USA, 2013, pp. 305–316
  * [53] Rudy Bunel et al. “Learning to superoptimize programs” In _arXiv preprint arXiv:1611.01787_ , 2016
  * [54] Nadav Rotem and Chris Cummins “Profile Guided Optimization without Profiles: A Machine Learning Approach” In _arXiv preprint arXiv:2112.14679_ , 2021
  * [55] Riyadh Baghdadi et al. “A Deep Learning Based Cost Model for Automatic Code Optimization” In _Proceedings of Machine Learning and Systems_ 3, 2021
  * [56] Felix Agakov et al. “Using machine learning to focus iterative optimization” In _International Symposium on Code Generation and Optimization (CGO’06)_ , 2006, pp. 11–pp IEEE
  * [57] Justyna Petke et al. “Genetic improvement of software: a comprehensive survey” In _IEEE Transactions on Evolutionary Computation_ 22.3 IEEE, 2017, pp. 415–432
  * [58] Vicent Sanz Marco, Ben Taylor, Barry Porter and Zheng Wang “Improving spark application throughput via memory aware task co-location: A mixture of experts approach” In _Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference_ , 2017, pp. 95–108
  * [59] Tianqi Chen et al. “Learning to optimize tensor programs” In _arXiv preprint arXiv:1805.08166_ , 2018
  * [60] Byung Hoon Ahn, Prannoy Pilligundla, Amir Yazdanbakhsh and Hadi Esmaeilzadeh “Chameleon: Adaptive code optimization for expedited deep neural network compilation” In _arXiv preprint arXiv:2001.08743_ , 2020