Langage de programmation de bas niveau

vignette|Language de programmation Un langage de programmation de bas niveau ne fournit que peu d'abstraction par rapport au jeu d'instructions du processeur de la machine. Les langages de bas niveau sont à opposer aux langages de haut niveau, qui permettent de créer un programme sans tenir compte des caractéristiques particulières (registres, etc) de l'ordinateur censé exécuter le programme. Le langage machine et le langage d'assemblage sont les archétypes de langages de bas niveau, puisqu'ils permettent de manipuler explicitement des registres, des adresses mémoires, des instructions machines. Hors ces cas extrêmes, la distinction entre bas niveau et haut niveau n'est pas binaire. Les discussions pour savoir si des langages comme C et C++, qui ont à la fois des aspects de bas niveau (possibilités d'accès à la mémoire en utilisant des adresses explicites, "bitfields" dans les structures) et de haut niveau, méritent ou pas le nom de langage de haut ou bas niveau ont toujours c

Building Efficient Query Engines using High-Level Languages

Ioannis Klonatos

We are currently witnessing a shift towards the use of high-level programming languages for systems development. These approaches collide with the traditional wisdom which calls for using low-level languages for building efficient software systems. This shift is necessary as billions of dollars are spent annually on the maintenance and debugging of performance-critical software. High-level languages promise faster development of higher-quality software; by offering advanced software features, they help to reduce the number of software errors of the systems and facilitate their verification. Despite these benefits, database systems development seems to be lagging behind as DBMSes are still written in low-level languages. The reason is that the increased productivity offered by high-level languages comes at the cost of a pronounced negative performance impact. In this thesis, we argue that it is now time for a radical rethinking of how database systems are designed. We show that, by using high-level languages, it is indeed possible to build databases that allow for both productivity and high performance. More concretely, in this thesis we follow this abstraction without regret vision and use high-level languages to address the following two problems of database development. First, the introduction of a new storage or memory technology typically requires the development of new versions of most out-of-core algorithms employed by the database system. Given the increasing popularity of hardware specialization, this leads to an arms race for the developers. To make things even worse, there exists no clear methodology for creating such algorithms and we must rely on significant creative effort to serve our need for out-of-core algorithms. To address this issue, we present the OCAS framework for the automatic synthesis of efficient out-of-core algorithms. The developer provides two independent inputs: 1) a memory-hierarchy-oblivious algorithm, expressed using a high-level specification language; and 2) a description of the target memory hierarchy. Using these specifications, our system is then able to automatically synthesize memory-hierarchy and storage-device-aware algorithms for tasks such as joins and sorting. The framework is extensible and quickly synthesizes custom out-of-core algorithms as new storage technologies become available. Second, from a software engineering point of view, years of performance-driven DBMS development have led to complicated, monolithic, low-level code bases, which are hard to maintain and extend. In particular, the introduction of new innovative approaches can be a very time-consuming task. To overcome such limitations, we present LegoBase, a query engine written in the high-level language, Scala. LegoBase realizes the abstraction without regret vision in the domain of analytical query processing. We show how by offering sufficiently powerful abstractions our system allows to easily implement a broad spectrum of optimizations which are difficult to achieve with existing approaches. Then, the key technique to regain efficiency is to apply generative programming and source-to-source compile the entire high-level Scala code to specialized, low-level C code. Our architecture significantly outperforms a commercial in-memory database system and an existing query compiler. LegoBase is the first step towards providing a full DBMS written in a high-level language.

EPFL2017

Jet: An Embedded DSL for High Performance Big Data Processing

Stefan Ackermann, Vojin Jovanovic, Martin Odersky, Tiark Rompf

Cluster computing systems today impose a trade-off between generality, performance and productivity. Hadoop and Dryad force programmers to write low level programs that are tedious to compose but easy to optimize. Systems like Dryad/LINQ and Spark allow concise modeling of user programs but do not apply relational optimizations. Pig and Hive restrict the language to achieve relational optimizations, making complex programs hard to express without user extensions. However, these extensions are cumbersome to write and disallow program optimizations. We present a distributed batch data processing framework called Jet. Jet uses deep language embedding in Scala, multi-stage programming and explicit side effect tracking to analyze the structure of user programs. The analysis is used to apply projection insertion, which eliminates unused data, as well as code motion and operation fusion to highly optimize the performance critical path of the program. The language embedding and a high-level interface allow Jet programs to be both expressive, resembling regular Scala code, and optimized. Its modular design allows users to extend Jet with modules that produce good performing code. Through a modular code generation scheme, Jet can generate programs for both Spark and Hadoop. Compared with naïve implementations we achieve 143% speedups on Spark and 126% on Hadoop.

2012

Abstractions for Type-Level Programming

Olivier Eric Paul Blanvillain

Over the past decade, the Scala community has shown great interest in using type-level programming to obtain additional type safety.Unfortunately, the lack of support from the Scala compiler has been a barrier to the adoption of that technique, notably due to its negative impact on compilation times.In this thesis, we present three techniques for type-level programming in Scala.First, we explain the status quo, implicits, and show how we can divert them from their intended use to write ad hoc type-level programs.Second, we propose a generalization of Scala's singleton types, which adds the ability to manipulate term-level programs at the type level.Third, we introduce match types, a type-level equivalent of pattern matching, which we implemented in the Scala~3 compiler.Throughout this dissertation, we demonstrate the practicality of our newly introduced techniques, by the means of case studies and examples.Our performance evaluation shows that our new techniques outperform the status quo in terms of binary sizes and compilation times.

EPFL2022

Building Efficient Query Engines using High-Level Languages

Ioannis Klonatos

EPFL2017