Plb2 Save

TL;DR: see the figure below. Note that nqueen and matmul are implemented in all languages but sudoku and bedcov are only implemented in some.

Table of Content

• Introduction
• Results
  • Overall impression
  • Caveats
    • Startup time
    • Elapsed time vs CPU time
  • Subtle optimizations
    • Optimizing inner loops
    • Controlling memory layout
• Discussions
• Appendix: Timing on Apple M1 Macbook Pro

Introduction

Programming Language Benchmark v2 (plb2) evaluates the performance of 25 programming languages on four CPU-intensive tasks. It is a follow-up to plb conducted in 2011. In plb2, all implementations use the same algorithm for each task and their performance bottlenecks do not fall in library functions. We do not intend to compare different algorithms or the quality of the standard libraries in these languages. Plb2 aims to evaluate the performance of a language when you have to implement a new algorithm in the language - this may happen if you can't find the algorithm in existing libraries.

The four tasks in plb2 all take a few seconds for a fast implementation to complete. The tasks are:

• nqueen: solving a 15-queens problem. The algorithm was inspired by the second C implementation from Rosetta Code. It involves nested loops and integer bit operations.

• matmul: multiplying two square matrices of 1500x1500 in size.

• sudoku: solving 4000 hard Sudokus (20 puzzles repeated for 200 times) using the kudoku algorithm. This algorithm heavily uses small fixed-sized arrays with a bit complex logic.

• bedcov: finding the overlaps between two arrays of 1,000,000 intervals with implicit interval trees. The algorithm involves frequent array access in a pattern similar to binary searches.

Every language has nqueen and matmul implementations. Some languages do not have sudoku or bedcov implementations. Most programs were initially implemented by me and a few were contributed by others. As I am mostly a C programmer, implementations in other languages may be suboptimal. Pull requests are welcomed!

Results

The figure at the top of the page summarizes the elapsed time of each implementation measured on an Apple M1 MacBook Pro. Hyperfine was used for timing except for a few slow implementations which were timed with the "time" bash command without repetition. A plus sign "+" indicates ahead-of-time compilation (AOT). Exact timing can be found in the table below. The figure was programmatically generated from the table.

Overall impression

Programming language implementations in plb2 can be classified into three groups depending on how and when compilation is done:

1. Purely interpreted (QuickJS, Perl and CPython, the official Python implementation). Not surprisingly, these are among the slowest language implementations in this benchmark.

2. JIT compiled (Dart, Bun/Node, Java, Julia, LuaJIT, PHP, PyPy and Ruby3 with YJIT). They are generally faster than pure interpretation. Nonetheless, there is a large variance in this group. While PHP and Ruby3 are faster than Perl and CPython, they are still an order of magnitude slower than PyPy. The two JavaScript engines (Bun and Node) and Julia perform well. They are about twice as fast as PyPy.

3. AOT compiled (the rest). Optimizing binaries for specific hardware, these compilers tend to generate the fastest executables.

Caveats

Startup time

Some JIT-based language runtimes take up to ~0.3 second to compile and warm-up. We are not separating out this startup time. Nonetheless, because most benchmarks run for several seconds, including the startup time does not greatly affect the results.

Elapsed time vs CPU time

Although no implementations use multithreading, language runtimes may be doing extra work, such as garbage collection, in a separate thread. In this case, the CPU time (user plus system) may be longer than elapsed wall-clock time. Julia, in particular, takes noticeably more CPU time than wall-clock time even for the simplest nqueen benchmark. In plb2, we are measuring the elapsed wall-clock time because that is the number users often see. The ranking of CPU time may be slightly different.

Subtle optimizations

Controlling memory layout

When implementing bedcov in Julia, C and many compiled languages, it is preferred to have an array of objects in a contiguous memory block such that adjacent objects are close in memory. This helps cache efficiency. In most scripting languages, unfortunately, we have to put references to objects in an array at the cost of cache locality. The issue can be alleviated by cloning objects to a new array. This doubles the speed of PyPy and Bun.

Optimizing inner loops

The bottleneck of matrix multiplication falls in the following nested loop:

for (int i = 0; i < n; ++i)
    for (int k = 0; k < n; ++k)
        for (int j = 0; j < n; ++j)
            c[i][j] += a[i][k] * b[k][j];

It is obvious that c[i], b[k] and a[i][k] can be moved out of the inner loop to reduce the frequency of matrix access. The Clang compiler can apply this optimization. Manual optimization may actually hurt performance.

However, many other languages cannot optimize this nested loop. If we manually move a[i][k] to the loop above it, we can often improve their performance. Some C/C++ programmers say compilers often optimize better than human, but this might not be the case in other languages.

Discussions

The most well-known and the longest running language benchmark is the Computer Language Benchmark Games. Plb2 differs in that it includes different languages (e.g. Nim and Crystal), different language runtimes (e.g. PyPy and LuaJIT) and new tasks, and it comes with more uniform implementations and focuses more on the performance of the language itself without library functions. Plb2 complements the Computer Language Benchmark Games.

One important area that plb2 does not evaluate is the performance of memory allocation and/or garbage collection. This may contribute more to practical performance than generating machine code. Nonetheless, it is challenging to design a realistic micro-benchmark to evaluate memory allocation. If the built-in allocator in a language implementation does not work well, we can implement customized memory allocator just for the specific task but this, in my view, would not represent typical use cases.

When plb was conducted in 2011, half of the languages in the figure above were not mature or even did not exist. It is exciting to see many of them have reached the 1.0 milestone and are gaining popularity among modern programmers. On the other hand, Python remains one of the two most used scripting languages despite its poor performance. In my view, this is because PyPy would not be officially endorsed while other JIT-based languages are not general or good enough. Will there be a language to displace Python in the next decade? I am not optimistic.

Appendix: Timing on Apple M1 Macbook Pro

In the following table, star "*" indicates AOT compilation and plus "+" indicates JIT compilation.