Tag Archives: languages

Cross-Language Compiler Benchmarking: Are We Fast Yet?

Research on programming languages is often more fun when we can use our own languages. However, for research on performance optimizations that can be a trap. In the end, we need to argue that what we did is comparable to state-of-the-art language implementations. Ideally, we are able to show that our own little language is not just a research toy, but that it is, at least performance-wise, competitive with for instance Java or JavaScript VMs.

Over the last couple of years, it was always a challenge for me to argue that SOM or SOMns are competitive. There were those 2-3 paragraphs in every paper that never felt quite as strong as they should be. And the main reason was that we don’t really have good benchmarks to compare across languages.

I hope we finally have reasonable benchmarks for exactly that purpose with our Are We Fast Yet? project. To track performance of benchmarks, we also set up a Codespeed site, which shows the various results. The preprint has already been online for a bit, but next week, we are finally going to present the work at the Dynamic Languages Symposium in Amsterdam.

Please find abstract and details below:

Abstract

Comparing the performance of programming languages is difficult because they differ in many aspects including preferred programming abstractions, available frameworks, and their runtime systems. Nonetheless, the question about relative performance comes up repeatedly in the research community, industry, and wider audience of enthusiasts.

This paper presents 14 benchmarks and a novel methodology to assess the compiler effectiveness across language implementations. Using a set of common language abstractions, the benchmarks are implemented in Java, JavaScript, Ruby, Crystal, Newspeak, and Smalltalk. We show that the benchmarks exhibit a wide range of characteristics using language-agnostic metrics. Using four different languages on top of the same compiler, we show that the benchmarks perform similarly and therefore allow for a comparison of compiler effectiveness across languages. Based on anecdotes, we argue that these benchmarks help language implementers to identify performance bugs and optimization potential by comparing to other language implementations.

  • Cross-Language Compiler Benchmarking: Are We Fast Yet? Stefan Marr, Benoit Daloze, Hanspeter Mössenböck; In Proceedings of the 12th Symposium on Dynamic Languages (DLS ’16), ACM, 2016.
  • Paper: HTML, PDF, DOI
  • BibTex: BibSonomy

Which Problems Does a Multi-Language Virtual Machine Need to Solve in the Multicore/Manycore Era?

As preparation for SPLASH’11, here my paper for the VMIL workshop. It is a position paper discussing in which direction virtual machines should evolve in the future with regard to the challenges manycore architectures and concurrent programming bring.

As I said, this is a position paper, which hopefully provokes discussion. Feedback of any kind is welcome, and I am happy to adapt my presentation accordingly.

Abstract

While parallel programming for very regular problems has been used in the scientific community by non-computer-scientists successfully for a few decades now, concurrent programming and solving irregular problems remains hard. Furthermore, we shift from few expert system programmers mastering concurrency for a constrained set of problems to mainstream application developers being required to master concurrency for a wide variety of problems.

Consequently, high-level language virtual machine (VM) research faces interesting questions. What are processor design changes that have an impact on the abstractions provided by VMs to provide platform independence? How can application programmers’ diverse needs be facilitated to solve concurrent programming problems?

We argue that VMs will need to be ready for a wide range of different concurrency models that allow solving concurrency problems with appropriate abstractions. Furthermore, they need to abstract from heterogeneous processor architectures, varying performance characteristics, need to account for memory access cost and inter-core communication mechanisms but should only expose the minimal useful set of notions like locality, explicit communication, and adaptable scheduling to maintain their abstracting nature.

Eventually, language designers need to be enabled to guarantee properties like encapsulation, scheduling guarantees, and immutability also when an interaction between different problem-specific concurrency abstractions is required.

  • Which Problems Does a Multi-Language Virtual Machine Need to Solve in the Multicore/Manycore Era?, Stefan Marr, Mattias De Wael, Michael Haupt, Theo D’Hondt, Proceedings of the 5th Workshop on Virtual Machines and Intermediate Languages, USA, ACM (2011), to appear.
  • Paper: PDF
    ©ACM, 2011. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. To appear.
  • BibTex: BibSonomy

Slides

Theory and Practice of Language Implementation, part 1

Thanks to the financial support of FWO and a grant by the summer school itself, I was able to go to Eugene, Oregon and learn about theory and practice of language implementation.

The first part of this summer school had three different topics. Ras Bodik presented highly interesting approaches for program synthesis. Oliver Danvy taught us how to use continuations and how to transform a program into continuation passing style. Matt Might tried to explain control-flow analysis(CFA) for high-order programs, starting with 0-CFA(zero-CFA) and k-CFA.

Algorithmic Program Synthesis

The program synthesis lectures were from my perspective the most comprehensible and interesting ones. Ras gave a high-level overview over different approaches to utilize expert knowledge i.e. domain insights to guide the synthesis of algorithms. He presented two different directions: derivative and selective synthesis. The derivative synthesis has its roots in the formal world. The idea is to define a problem with a formal language and to automatically derive a proof for it. As a by-product of this proof, an algorithm to solve the problem is synthesized. This approach is limited mainly by the formal skills of the programmers, and thus, was not successful in a larger scale.

Selective synthesis tries to circumvent these limitations by trying to preserve the usual tools for the programmers as the basic foundation. One example he explained in more detail was SKETCH. Here, the programmer has to describe a space of possible programs and the synthesizer can chose an exemplar of this space by testing/verifying whether it fulfills a specification, which also has to be given by the programmer. An example could be an optimized sort algorithm, which might be tailored to a specific memory model. The programmer implements the basic sketch and leaves some open holes, which needs to be synthesized. She also can give a simple bubble sort as specification, or as an alternative, a checking algorithm, whether the resulting data is sorted. He concluded his lectures with a demonstration of angelic programming, which uses the idea of sketching a solution and automatically deriving an implementation.

Continuations to Go

Oliver was the first lecturer asking us to do exercises. This was a good way to force us to really think about the content of his lectures. At first he taught us the three basic steps to transform a program to continuation-passing style (CPS): 1. name all immediate values, 2. sequentialize immediate evaluations, and 3. introduce the actual continuation. Then, he gave us some exercises, for instance to build the list of suffixes of a list and the list of prefixes. In a language supporting linked lists, the list of suffixes can be realized by sharing the data between all suffixes. The list of suffixes, thus is comprised of pointers pointing to the according element of the original list, where the suffix starts. For the list of prefixes, it is not possible to share the data, but, by implementing it in a continuation-passing style. You can share the computation of the prefixes similar to sharing the data in the case of the suffixes.

Another example, he ask to implement was a convolution of two lists. Thus, the result is a list of pairs of elements of each list, where the second list is reverse beforehand. The interesting thing here is, that it can be implemented in a recursive way with n steps of recursion for lists with n elements. The solution is simple, if you figure out that you can use the return time of a recursion to traverse the second lists, which is equal to a reverse. Later he pointed out, that an implementation of this, using CPS and defunctionalization will result in a plain usual zip/reverse like it would be done in Haskell.

Control-flow Analysis of Higher-Order Languages

Well, and then there was the control-flow analysis (CFA). At the moment, I have not figured out completely how to read the slides, since my Greek is rather limited. What I was able to take away from this course was, that there are several different techniques where 0-CFA is a robust and efficient one. In general, the k in k-CFAs denotes the amount of history, which is considered in the analysis. Usually, only 0-CFA and 1-CFA are applied in practice, i.e. in compilers, since the state space of the analysis explodes very fast. The concrete semantics of a program would be described by an infinite-CFA. He also talked about possible optimizations, like applying garbage collection, to eliminate unreachable states/possibilities during the CFA and thereby increasing the efficiency of the analysis significantly.