mendation Using Code Embeddings

Abstract

We present a lightweight compiler autotuning approach that combines concepts from configuration space learning with recommender techniques. Our approach uses code embeddings generated by diferent large language models for data representation and calculation of similarity scores. The best-performing code embedding approach shows, on average, 4.11% faster binaries than the best-performing code metric-based alternative. Compilers are powerful and highly configurable tools. The C compiler GCC 1 has about 200 optimization options that can be activated or deactivated independently. Each option may positively or negatively impact diferent properties, such as the generated binary's runtime, size, or energy consumption. If these options are correctly utilized, the generated program binaries can be faster, smaller, or more energy-eficient without further investing resources into code refinement. However, choosing the correct options requires expertise in compiler optimization and the program to be optimized. Compiler autotuning addresses this issue by recommending optimization options for a program without any expert involvement. Most approaches for compiler autotuning are computationally expensive and take days to continuously refine the recommended options [ 1, 2, 3, 4, 5, 6]. Alternative lightweight approaches for compiler autotuning proposed by Burgstaller et al. [7] and Garber et al. [8], can reduce the time needed for recommendation to milliseconds allowing an interactive user experience. This lightweight approach is called Optimisation Space Learning (OSL) [7] and relies on training data collected in advance that is then used for recommendation utilizing nearest-neighbor-based collaborative filtering [ 9] based on extracted code metrics. The major contributions of this paper are as follows: (1) We extend OSL by incorporating and comparing diferent code embeddings. (2) We show that the new embeddings significantly outperform the standard compiler optimization options in terms of the runtime performance of the generated program.

1. Introduction

2. Related

Work

Compiler autotuning is the automated selection of advantageous compiler optimization options for a program. It can be divided into the phase selection problem and the phase ordering problem [ 10 ]. Phase ordering tries to find an optimal sequence to apply the options, while phase selection, the focus of this

ISSN1613-0073 work, tries to identify which optimizations should be applied. The optimality of options can be defined with diferent properties, the most common of which is runtime. However, space, energy, or similar measurable properties could also be employed.

The state-of-the-art in compiler autotuning is primarily dominated by iterative approaches [ 1, 2, 3, 4, 5, 6 ]. Bodin et al. [ 11 ] propose one of the first compiler autotuning approaches. They generate an initial set of optimization options to be activated, compile the program using these options, measure its performance, and refine the configuration in a loop until achieving satisfactory results. Most newer approaches build on this concept, like COBAYN [ 12 ], which uses Bayesian Networks to narrow the search space. The current state-of-the-art method, BOCA [ 13 ], employs Bayesian Optimization to identify key optimizations and streamline the search process. CompTuner [ 14 ] builds a prediction model for the runtime of diferent optimization options and uses a particle swarm optimization algorithm [ 15 ] to improve the search performance. Cole [ 4 ] can perform multi-target optimization by iteratively creating a Pareto front.

Performance is a key challenge for the computationally intensive, iterative, state-of-the-art approaches, as they require numerous compilations. As project sizes grow, this becomes a significant issue. For instance, Cole must construct a Pareto front, which takes 50 days on a single machine [ 4 ]. To address these limitations, newer lightweight approaches like Optimization Space Learning (OSL) [ 7 ] adopt alternative strategies to provide faster optimization recommendations, trading of a small degree of recommendation quality for improved responsiveness.

OSL achieves this by combining configuration space learning [ 16, 17 ] techniques like the t-wise feature coverage heuristic [ 16, 17, 18 ] with collaborative filtering [ 9 ]. In this context, collaborative ifltering relies on code metrics (e.g., McCabe, Halstead, or counts of keywords) extracted from the optimized programs. This paper presents an alternative collaborative filtering approach based on code embeddings [19].

3. Recommendation Approach

Optimization Space Learning (OSL) is a compiler autotuning approach introduced initially by Burgstaller et al. [ 7 ]. The approach combines concepts from configuration space learning [ 16, 17 ] for data generation and collaborative filtering [ 9 ] for configuration recommendation. The key contribution of OSL is its recommendation speed, which is achieved after a one-time collection of training data within tens of milliseconds. Meanwhile, the iterative state-of-the-art compiler autotuning approaches [ 1, 2, 3, 4, 5, 6 ], report computation times of several days. These diferences are due to the iterative approaches requiring a continuous refinement process of recommendation result testing, adaptation, and restarting.

3.1. Data Collection

OSL needs to collect initial training data to provide recommendations for a new hardware environment. Two decisions have to be made to generate the training data. The first is which programs to use for training. The second is the heuristic used for generating the sample configurations.

The training approach is based on configuration space learning [ 16, 20, 17 ], motivated by the infeasibility of exhaustively exploring configuration spaces due to their exponential size [ 21]. For example, GCC includes around 200 options, yielding a configuration space of roughly 2200 configurations. Even assuming 1 per compilation and measurement, full exploration would take 5 ∗ 1049 years. Therefore, following Pereira et al. [ 16 ], collecting a small, representative configuration subset is necessary.

In order to collect such a small representative set of configurations, we use sampling approaches discussed by Pereira et al. [ 16 ] and Garber et al. [17]. Burgstaller et al. [ 7 ] considered initially two sampling approaches: Uniform Random Sampling (URS) and t-wise Feature Coverage Heuristics (FCH). URS is well-established [ 16, 17, 22, 23, 24 ], but has drawbacks with scalability. The main drawback of FCH, on the other hand, is its expensive computation, which is mitigated by the unconstrained nature of the problem (options are independent of each other) and the fact that this needs to be performed only once. Therefore, OSL ultimately relies on the t-wise FCH [ 16, 17 ] to generate the samples for the programs’ runtime [s] when compiled with the referenced compiler configuration .

Programs al. [ 7 ] report FCH with = 3 to perform best for this task, which is confirmed by Garber et al. [ 8 ] and our work presented in this paper. Next, we need a set of programs to synthesize the needed data. We use the same benchmark used in the original work by Burgstaller et al. [ 7 ] and in the improved OSL by Garber et al. [ 8 ]. The PolyBench benchmarks [25] provide 30 programs written in C and are widely used in related literature [ 7, 13, 14, 8 ].

We construct the training data by compiling an executable for each configuration provided by the sampling approach and each program in the benchmark. The performance properties of these executables are then measured using perf-stat.2

OSL extracts at this point a vector of 111 source code metrics, such as McCabe’s Cyclomatic Complexity [26], Halstead Complexity [27], or simple counts like the number of times a particular keyword occurs, using the CQMetrics tool by [28]. OSL uses the first 66 of those source code metrics to calculate program similarities during the recommendation process since the latter metrics primarily are related to coding style, i.e., indentation space counts. A complete list of the metrics extracted is provided in the CQMetrics documentation.3 We compare the performance of this code metric-based similarity with our approach of using code embeddings-based similarity. A description of the code embeddings used is provided in Section 4.

3.2. Recommendation

Essentially, we apply nearest neighbor-based collaborative filtering [ 9 ] on synthesized data [29, 22], which has been obtained using heuristics known from configuration space learning [ 16, 17 ].

Our variant of user-based collaborative filtering difers slightly from the standard setting (see Table 1).

Here, programs act as users, configurations as items, and runtime serves as the rating (a lower runtime is analogous to a higher rating). Unlike typical scenarios, we have complete performance data for all program-configuration pairs generated by the data collection process, except for the target program. Thus, we require an external metric to estimate program similarity. The version of OSL used by Burgstaller et al. [ 7 ] and Garber et al. [ 8 ] computes similarity using source code metrics and the Euclidean distance [ 30, 7 ] (see Formula 1 and Formula 2). In this context, and are -dimensional vectors with components 1 to and 1 to , representing programs and . In OSL, these vectors consist of = 66 code metrics, while in our approach, they are the extracted fixed-size (n) embedding vectors.

(, ) = (, ) = ∑ | − |2 =1

1 1 + (, ) for these values. In the example, the highest similarity is 16.7 % between 1 and 3. Thus, 3 is the most similar program to 1. We propose the use of code embeddings extracted from the programs instead. To this end, we test the performance of two embeddings, shown in Table 4. After testing several common ways of calculating the similarities of two embedding vectors, such as the cosine similarity, we use the same Euclidian distance-based approach described earlier.

The remaining process is identical to the typical user-based collaborative filtering procedure. The best-rated (fastest runtime) configuration of the most similar program recommends a configuration for 4.

The final recommendation step aggregates the results. Since the FCH-collected configurations cover only a small subset of all compiler settings, we generate multiple recommendations from the nearest neighbors and combine them via majority vote (Table 5). Following Burgstaller et al. [ 7 ], we set the number of top configurations and nearest neighbors to 5, a choice we confirmed and applied to all experiments. Thus, the final recommendation aggregates the 5 best configurations from the 5 nearest neighbors.

4. Evaluation

In this section, we evaluate the use of code embeddings to recommend compiler optimization options and whether they outperform code metric-based approaches like OSL [ 7 ] or its enhanced version of OSL Normalized and Equalized (OSL N&E) [ 8 ]. Code embeddings represent code as fixed-sized numerical vectors containing semantic and structural information [19]. They are usually employed by machine learning or large language models when working with code. We test two embeddings BGE 4, a general 4https://huggingface.co/BAAI/bge-base-en-v1.5 text embedding, and RoBERTa 5, a specialized code embedding (described in Table 4).

4.1. Experimental Setup

Our evaluation uses GCC version 14.2.1 on a Lenovo ThinkPad P53s machine with an Intel i7-8665U processor and 32GB memory running Linux 6.1.119-1-MANJARO. We use the PolyBench/C Benchmark [25] for training and testing, which contains 30 programs written in C and is commonly used in compiler autotuning evaluation settings [ 7, 13, 14, 8 ]. Due to the relatively small sample size, we apply leave-one-out cross-validation [31]. Thus, each benchmark program in PolyBench was tested using a model trained with the remaining 29. In order to visualize the performance more eficiently, we define a speedup factor compared to GCC’s set of default optimizations O3 in Equation 3. = 3 (3) 3 and

4.2. Results

represent the program’s runtime compiled using O3 and the recommended parameter settings respectively. A speedup of 1.1 indicates a 1.1 times faster runtime. code embeddings outperformed the baseline OSL method, which achieved an average speedup of 1.126. BGE reached 1.141, slightly below the enhanced OSL N&E at 1.144. RoBERTa achieved the highest average speedup of 1.191. Regarding frequency as a top performer, RoBERTa leads (Top 1 in 10/30 cases, Top 2 in 19/30), followed by BGE narrowly outperforming OSL, while OSL N&E comes last. These results indicate that embeddings are efective for recommending compiler optimizations, especially when using models like RoBERTa, which are specifically trained on code.

5. Future Work

6. Conclusion

The first results of using code embeddings in the context of lightweight compiler autotuning show promise. However, in future work, we would like to expand the number of evaluated code embeddings, especially further towards models specialized in coding or code manipulations, such as CodeBERT or GraphCodeBERT, potentially improving our results further.

In summary, we evaluated using code embeddings to recommend compiler optimizations. Our results show that embeddings perform comparably to code metric-based approaches and surpass them in the case of embeddings from models trained on code. The best-performing method leverages embeddings from a RoBERTa model trained for code search, achieving an average runtime speedup factor of 1.191, 4.11% faster than the enhanced code metrics baseline. Major tasks of future work include the extension of the dataset as well as the testing of additional embeddings.

Acknowledgments

This study was funded by GENRE, Austrian Research Promotion Agency (Grant No. 915086). 5https://huggingface.co/flax-sentence-embeddings/st-codesearch-distilroberta-base

Declaration on Generative AI

While preparing this work, the author(s) used ChatGPT-4 (GPT-4-turbo) and Grammarly to check grammar and spelling and improve formulations. After using these tool(s)/service(s), the author(s) reviewed and edited the content as needed and take(s) full responsibility for the publication’s content. software configuration spaces: A systematic literature review, Journal of Systems and Software 182 (2021) 111044. [17] D. Garber, T. Burgstaller, A. Felfernig, V.-M. Le, S. Lubos, T. Tran, S. Polat-Erdeniz, Collaborative recommendation of search heuristics for constraint solvers, in: ConfWS’23: 25th International Workshop on Configuration, Sep 6–7, 2023, Málaga, Spain, 2023. [18] J. Oh, P. Gazzillo, D. Batory, T-wise coverage by uniform sampling, in: Proceedings of the 23rd International Systems and Software Product Line Conference - Volume A, SPLC ’19, Association for Computing Machinery, New York, NY, USA, 2019, p. 84–87. URL: https://doi.org/10.1145/3336294. 3342359. doi:10.1145/3336294.3342359. [19] Z. Chen, M. Monperrus, A literature study of embeddings on source code, arXiv preprint arXiv:1904.03061 (2019). [20] D. Benavides, P. Trinidad, A. Ruiz-Cortés, Automated reasoning on feature models, in: International

Conference on Advanced Information Systems Engineering, Springer, 2005, pp. 491–503. [21] M. Acher, H. Martin, J. A. Pereira, A. Blouin, J.-M. Jézéquel, D. E. Khelladi, L. Lesoil, O. Barais, Learning very large configuration spaces: What matters for Linux kernel sizes, Ph.D. thesis, Inria Rennes-Bretagne Atlantique, 2019. [22] K. S. Meel, Counting, sampling, and synthesis: The quest for scalability., in: IJCAI, 2022, pp.

5816–5820. [23] J. Oh, D. Batory, R. Heradio, Finding near-optimal configurations in colossal spaces with statistical guarantees, ACM Transactions on Software Engineering and Methodology 33 (2023) 1–36. [24] Q. Plazar, M. Acher, G. Perrouin, X. Devroey, M. Cordy, Uniform sampling of sat solutions for configurable systems: Are we there yet?, in: 2019 12th IEEE Conference on Software Testing, Validation and Verification (ICST), IEEE, 2019, pp. 240–251. [25] L.-N. Pouchet, Polybench: The polyhedral benchmark suite, http://www.cs.ucla.edu/~pouchet/ software/polybench/, 2012. Accessed: 2024. [26] T. J. McCabe, A complexity measure, IEEE Transactions on software Engineering (1976) 308–320. [27] M. H. Halstead, Elements of Software Science (Operating and programming systems series), Elsevier

Science Inc., 1977. [28] D. Spinellis, P. Louridas, M. Kechagia, The evolution of c programming practices: a study of the unix operating system 1973–2015, in: Proceedings of the 38th International Conference on Software Engineering, ICSE ’16, Association for Computing Machinery, New York, NY, USA, 2016, p. 748–759. URL: https://doi.org/10.1145/2884781.2884799. doi:10.1145/2884781.2884799. [29] J. Alves Pereira, M. Acher, H. Martin, J.-M. Jézéquel, Sampling efect on performance prediction of configurable systems: A case study, in: Proceedings of the ACM/SPEC International Conference on Performance Engineering, 2020, pp. 277–288. [30] G. Jain, T. Mahara, K. N. Tripathi, A survey of similarity measures for collaborative filtering-based recommender system, in: Soft Computing: Theories and Applications: Proceedings of SoCTA 2018, Springer, 2020, pp. 343–352. [31] T.-T. Wong, Performance evaluation of classification algorithms by k-fold and leave-one-out cross validation, Pattern recognition 48 (2015) 2839–2846.

References

[1] Y. Chen , S. Fang , Y. Huang , L. Eeckhout , G. Fursin , O. Temam , C. Wu , Deconstructing iterative optimization , ACM Transactions on Architecture and Code Optimization (TACO) 9 ( 2012 ) 1 - 30 .

[2] U. Garciarena , R. Santana , Evolutionary optimization of compiler flag selection by learning and exploiting flags interactions , in: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion , 2016 , pp. 1159 - 1166 .

[3] S. V. Gheorghita , H. Corporaal , T. Basten, Iterative compilation for energy reduction , Journal of Embedded Computing 1 ( 2005 ) 509 - 520 .

[4] K. Hoste , L. Eeckhout, Cole: compiler optimization level exploration , in: Proceedings of the 6th annual IEEE/ACM international symposium on Code generation and optimization , 2008 , pp. 165 - 174 .

[5] L. Pérez Cáceres , F. Pagnozzi , A. Franzin , T. Stützle , Automatic configuration of gcc using irace , in: Artificial Evolution: 13th International Conference , Évolution Artificielle, EA 2017 , Paris, France, October 25-27 , 2017 , Revised Selected Papers 13 , Springer, 2018 , pp. 202 - 216 .

[6] S. Triantafyllis , M. Vachharajani , N. Vachharajani , D. I. August , Compiler optimization-space exploration , in: International Symposium on Code Generation and Optimization , 2003 . CGO 2003 ., IEEE, 2003 , pp. 204 - 215 .

[7] T. Burgstaller , D. Garber , V. -M. Le , A. Felfernig , Optimization space learning: A lightweight, noniterative technique for compiler autotuning , in: Proceedings of the 28th ACM International Systems and Software Product Line Conference , SPLC '24, Association for Computing Machinery, New York, NY, USA, 2024 , p. 36 - 46 . URL: https://doi.org/10.1145/3646548.3672588. doi: 10 .1145/ 3646548.3672588.

[8] D. Garber , S. Lubos , V. -M. Le , A. Felfernig , Enhanced optimization space learning: Towards real-time compiler optimization , in: 38th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems , 2025 . Accepted.

[9] M. D. Ekstrand , J. T. Riedl , J. A. Konstan , et al., Collaborative filtering recommender systems, Foundations and Trends® in Human-Computer Interaction 4 ( 2011 ) 81 - 173 .

[10] A. H. Ashouri , W. Killian , J. Cavazos , G. Palermo, C. Silvano , A survey on compiler autotuning using machine learning , ACM Computing Surveys (CSUR) 51 ( 2018 ) 1 - 42 .

[11] F. Bodin , T. Kisuki , P. Knijnenburg , M. O'Boyle , E. Rohou , Iterative compilation in a non-linear optimisation space , in: Workshop on profile and feedback-directed compilation , 1998 .

[12] A. H. Ashouri , G. Mariani, G. Palermo , E. Park, J. Cavazos , C. Silvano , Cobayn: Compiler autotuning framework using bayesian networks , ACM Transactions on Architecture and Code Optimization (TACO) 13 ( 2016 ) 1 - 25 .

[13] J. Chen , N. Xu , P. Chen , H. Zhang, Eficient compiler autotuning via bayesian optimization , in: 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE) , IEEE, 2021 , pp. 1198 - 1209 .

[14] M. Zhu , D. Hao , J. Chen , Compiler autotuning through multiple phase learning , ACM Trans. Softw. Eng. Methodol . ( 2024 ). URL: https://doi.org/10.1145/3640330. doi: 10 .1145/3640330, just Accepted.

[15] J. Kennedy , R. Eberhart , Particle swarm optimization , in: Proceedings of ICNN'95-international conference on neural networks , volume 4 , IEEE, 1995 , pp. 1942 - 1948 .

[16] J. Alves Pereira , M. Acher , H. Martin , J.-M. Jézéquel , G. Botterweck , A. Ventresque , Learning