Benchmarking 20 programming languages on N-queens and matrix multiplication
github.com
github.com
First, the graph is misleading, stacking times with languages that have half the implementation, they appear faster, until you dig in. I'd suggest producing an alternate graph that shows only the implemented puzzles in every language, or make a unique graph for every language:puzzle.
Second, the examples are taken from rosetta code and are not necessarily what would be the best implementation, or even close to the best implementation, for benchmarking purposes.
Finally, those examples should be reproduced across various hardware platforms, I'm on arm64 Darwin myself, but you might find different results on Intel platforms due to the various compiler optimizations available based on the hardware.
More benchmarks would be interesting to see, such as actual real world operations, e.g. opening a file, reading it, parsing json, opening a socket server, etc.
This is only true when three matrices are independent of each other, and also why C has a `restrict` qualifier that enables this assumption. The benchmark itself has no such assumption because all three variables are defined as `double **`, and it can be verified by assembly outputs. Clang's excellent performance in matmul is probably much more due to autovectorization.
If you have enough idle execution units, you might not see a difference in wall clock time. But with many algorithms you can put those units to good use.
The Julia matmul implementation has its rows and columns flipped though - unlike C, Julia uses row-major matrices. This has large implications for speed.
Also, the code may be much faster if you enable SIMD in the function, which is disabled in the code because a) the code unnecessarily checks bounds at every index instead of at the top of the function, and b) float SIMD is opt-in since SIMD changes the rounding
It doesn't make sense to allow "warmup" time for them unless your expected application is a server which for most of the time will be running "warm" (and even then with scalable containers that assumption may not even be true in some cases). For servers, however, what matters is mostly how fast its HTTP library is and how good the async IO is... check Techempower benchmarks for that: https://www.techempower.com/benchmarks/#hw=ph&test=fortune&s...
With command line tools, the dominant design philosophy is that a program completes one task and exits. The tasks may be large or small, and the same tools are often expected to handle both.
https://www.oracle.com/java/technologies/security-in-java.ht...
Why should that run time startup cost be ignored?
Maybe that was PyPy with program times >5 seconds.
The difference is mostly in matmul.
I see how C, for an n x n matrix, does 2 allocations, while rust does n+1. C's matrix rows are right next to each other, rusts are probably all over the place. Didn't look at nim or zig.
Maybe a slice of slice of double would perform better than a vec of vec of double? Then again, an argument can be made that rust pushes you to vec, so this impl is more honest for how a beginner would do it. Otoh, C has the optimization so why doesn't rust?
i sent a pr to fix it
Edit: I have tried making an iterator-based version to elide bound checks, but had to resort to unsafe, and it's barely 50% faster than the original rust version (not as fast as C): https://gist.github.com/anisse/6b580628206293ef242faa7db6219...
Edit 2: updated, and my rust iterator version now ~equivalent to C with no unsafe.
Edit 3: too late, the repo has been updated with an other iterator-based version that is just as fast.
also, `const N` is used in rust's nqueen test, so figured it would be fine.
someone posted an `.iter().zip()` solution which benchmarks only a little slower (+10ms) than static allocation:
https://github.com/attractivechaos/plb2/pull/4#issuecomment-...
I saw the update to the PR, but I still prefer my collect()-based version :-)
It would be nice to see those other languages in a chart that doesn't include the slower four. Alternatively, you could also show those slower four with "broken" columns like this https://peltiertech.com/broken-y-axis-in-excel-chart/
The choice of stacked bar charts is also strange because the languages are not all comparable
> Every language has nqueen and matmul implementations. Some languages do not have sudoku or bedcov implementations. In addition, I implemented most algorithms in plb2 and adapted a few contributed matmul and sudoku implementations in plb. As I am mostly a C programmer, implementations in other languages may be suboptimal and there are no implementations in functional languages. Pull requests are welcomed!
So the point still stands that many charts doing one thing each would be better than fewer charts doing many things each
Would not be a summary.
Given that its become increasingly more common for CPUs to have both Performance & Efficency cores … how do benchmarks ensure they are only being run on the P-cores?
I believe Game Mode will push the processes to e cores to keep a consistent game play without thermal throttling.
Why would you think that?
Maybe the "naive" implementation just shows how fast the easily removed hotspot in your code is going to run.
"Swap the order of two statements and see the Java code slow down … Swap globals for local variables in a function and see the Python code speed up. Swap language implementations and see the C code speed up."
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
Recently there have been some decent improvements to CPython's speed, but there are real upper limits to how fast you can make an interpreter. CPython will need JIT compilation if it is ever to break out of its current speed bracket.
JavaScript has had a feature complete JIT reference implementation since 2008 which is a major part of the reason JS applications exploded so much in the 2010s.
check out how a modern language deals with this stuff https://bun.sh/docs/api/ffi#usage
PHP added JIT in 8.0, and these math-heavy tasks can take advantage of it. It's not trivial to fine tine JIT configuration though.
In PHP 8.4 (scheduled Nov 2024), there is a major upgrade to JIT as well.
[0] - https://docs.aws.amazon.com/lambda/latest/dg/dotnet-native-a...
There are only 20 thousand array allocations in total, not a lot. Javascript also has these many arrays allocated/deallocated but it is 4 times as fast.
However, translating Sudoku and N-Queens into a similar problem that you can feed into a solver can get you a long way. Even better, you can move that solver into whatever language gives you the best optimizations that you can work. Even better, there are almost certainly optimizations in common solvers that you don't want to deal with implementing on your on.
Here are naive line-by-line transliterations from an original C program:
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
Here exhaustively-optimised + multicore + vector-instruction programs are included:
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
Maybe I made an accidental optimization in my language translation, or maybe there are some operations that are much slower in JS and these benchmarks didn't hit any of them.
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
"How source code size is measured"
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
Including time to JIT compile is questionable, why not also include time to compile the compiled languages?
As-in "Wtf kind of benchmark counts the jvm startup time?"
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
You'll never have a perfect metric here, but human readable size of code base is well justified. Do you write minified javascript?
For emitting programs, if we assume the program is already fully formed in my brain and I'm just transcribing it, then we would like an accurate physical model of my hands moving over a QWERTY keyboard that can tell us how many joules and milliseconds I will use for each keystroke to type the given sequence of symbols. Ideally we would have a complete model or simulation of my brain so we can measure how many neurons need to fire for each keystroke as well. We don't have that, so we could measure my average milliseconds per character and multiply it by the total count of characters, but a language that is just made up of one symbol function names is probably harder to type than one made out of English words and there's also all the typing mistakes I will make. This is what the simple compression algorithm (gzip) is an attempt to normalize for, that a more verbose but more predictable language is as fast to write and read than an overly terse one. gziping is an imitation of a complex model.
Yes [1] [2] [3]?
[1] https://js1024.fun/demos/2020/46/readme
[2] https://js1024.fun/demos/2022/18/readme
[3] https://github.com/lifthrasiir/roadroller/blob/442caa4/index...
Jokes aside, human doesn't read each (uncompressed) byte anyway. The number of tokens would have been much better than the number of bytes, but even this is unclear because a single token can have multiple perceived words (e.g. someLongEnoughIdentifier) and multiple tokens can even be perceived as a single word for some cases (e.g. C/C++ `#define` is technically two tokens long, but no human would perceive it as such). I would welcome a more realistic estimate than the gzipped size, but I'm confident that it won't be the number of uncompressed bytes.
nqueen vs. sudoku: 0.531
matmul vs. sudoku: 0.362
matmul vs. nqueen: 0.127
1. https://www.cs.utexas.edu/users/flame/pubs/blis1_toms_rev3.p...
Would .NET with F# make big difference here?
I'm little surprised Java beat .NET. Is that typical these days?
Not at all, this is just a bad benchmark, it measure from the CLI run, with no specific flags which is just terrible for cold starts.
OP - are you interested in pull requests adding support for other languages?
C# also has arrays-of-arrays, and could (should) be written in the same manner.
There appears to be roughly the same code structure, ported to every language, while for some languages, arbitrary optimizations are introduced (such as using `array` instead of `list` in Python).
But nobody working in Python uses matrix multiplication code written in Python. They use NumPy, which is a de facto standard library for people working in the relevant fields. It's as much part of "Python" as list comprehensions.
Without taking such real-world conventions into account, such comparisons say essentially nothing about the languages involved (and their all-important ecosystems).
So this shouldn't be taken as "how fast does a real-world Python program do at matrix multiplication", since of course no one writes real-world programs doing matrix multiplication in pure Python. But it can show the relative speed of pure Python at purely computational tasks.
But that's irrelevant if nobody uses "pure Python" for computational tasks.
It's like asking "how well do these languages run on a Lisp machine from 1979?". It simply has no relevance to real-world considerations today.
[1]: https://www.exxactcorp.com/blog/Deep-Learning/how-to-speed-u...
If this were the only concern, it should be valid to create a blob of binary and call that function for the optimal performance. (Python's ctypes makes this very easy, for example.) So you want an idiomatic solution instead, and Numpy for matrix computation is considered idiomatic in Python, even more than the pure Python code.
And even if using a C library is idiomatic Python, it still has no place in a language benchmark. It's a C library, not a Python implementation.
Once again, "realistic" is subjective and I would say no "realistic" user will try to multiply arbitrarily-sized matrices in pure Python. (I can see small enough matrices, like 3x3 or 4x4, might be different.) And...
> So, it's not fair game in any honest benchmark. And even if using a C library is idiomatic Python, it still has no place in a language benchmark. It's a C library, not a Python implementation.
...you have correctly figured out that it's unfair for anyone using your (vague) definition of "realistic". It's also true that your proposal is also unfair for anyone using my definition of "idiomatic" however. I can try to defend my definition with quantative arguments, but I don't feel like doing so. In fact I tend to ignore most "language benchmarks" because it is virtually impossible to make them reasonably fair. This one is no exception.
Best "language benchmarks" tend to be more like language showcases with useful commentaries, there will be no single winner but you will get a good sense of pros and cons of each language-implementation-strategy combination. They are generally not advertised as "benchmarks", of course.
pidigits gcc #1
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
pidigits Python3 #3
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
It also means that adding performance to an existing Python program requires dropping into a different language, which is not only complicated, but also requires engineers capable in both Python and C (or similar).
People use matrix multiplication libraries (often written in Assembly) from every language if they really care about performance. That's because such libraries incorporate 100 PhD theses' worth of tricks that no individual can hope to reinvent in the course of solving another problem. There is absolutely nothing special about Python in this context.
> It also means that adding performance to an existing Python program requires dropping into a different language
As stated above, this applies to all languages. BLAS routines used for serious numerical work are hand-vectorized Assembly fine-tuned for each processor architecture, written by a few hyper-experts who do nothing else.
Nobody who needs performant matrix multiplication from C thinks "hey, let me just write two nested loops".
If you have a specific problem with constraints you can exploit (e.g. known fixed dimensions, sparsity patterns, data layouts, type conversions, etc.), it's not hard at all to beat MKL, etc... if you are using a language like C++. If you are using python, you have no chance.
It isn't even necessarily that different from a few nested loops. Clang is pretty damn good at autovectorizing, you just have to be a little careful about how you write the code.
Of course you do. Every special-case multiplication algorithm you might need already has an optimized implementation that you can just `pip install`, and move on with what you're actually working on.
The whole scientific computing world runs on Python. Straightforward numerics code using NumPy tends to murder C/C++ code in regard to performance, unless that code is written by people who make a living hand-optimizing computational routines.
If you ignore the majority of scientific code running on supercomputers doing most of science in C++ and Fortran.
Even in areas where python is used, the majority of the compute runs on C/C++/Fortran, with a little python as glue.
If you think numpy (written in c/c++) murders c/c++ code, you should learn about HPC, where really high performance happens. They don't use numpy.
I'll file this under "talk is cheap". :) I tried it last year and got within 50% of BLAS. Getting above that is tons of work. Which you have to repeat for every processor model, NUMA, and every combination of matrix type (long thin, short wide, etc).
The less involved versions still get ~70%.
But this is also quite general. I’m claiming you can beat BLAS if you have some unique knowledge of the problem that you can exploit. For example, some kinds of sparsity can be implemented within the above example code yet still far outperform the more general sparsity supported by MKL and similar.
As for the inner loop not being well optimized... the disassembly looks like the same basic thing as OpenBLAS. There's disassembly in the comments of that file to show what code it generates, I'd love to know what you think is lacking! The only difference between the one I linked and this is prefetching and outer loop ordering: https://github.com/dsharlet/array/blob/master/examples/linea...
On my machine single-threaded OpenBLAS (called via NumPy) multiplies two single precision 4096x4096 matrices in 0.95 seconds. Your code takes over 30 seconds when compiled with clang++. And yes I used -O3, -march=native, and all that jazz. Btw, your code crashes g++ which doesn't necessarily mean that it is incorret, but it indicates that the code may be difficult for the compiler to optimize. For comparison, my own matrix multiplication code (https://github.com/bjourne/c-examples/blob/master/libraries/...) run in single-threaded mode takes 0.89 seconds. Which actually beats OpenBLAS, but OpenBLAS retakes the lead for larger arrays when multi-threading is added. You can look at my code for how to write a decent inner kernel. Writing it in pure C without intrinsics and hoping that the compiler will optimize it definitely will not work.
It also is not true that "Parallelism would be easy to add". Unless your algorithm is designed from the start to exploit multi-threading, attempting to bolt it on later will not yield good performance.
Here's what I see:
$ clang++ --version
clang version 18.0.0
$ time make bin/matrix
mkdir -p bin
clang++ -I../../include -I../ -o bin/matrix matrix.cpp -O2 -march=native -ffast-math -fstrict-aliasing -fno-exceptions -DNDEBUG -DBLAS -std=c++14 -Wall -lstdc++ -lm -lblas
1.25user 0.29system 0:02.74elapsed 56%CPU (0avgtext+0avgdata 126996maxresident)k
159608inputs+120outputs (961major+25661minor)pagefaults 0swaps
$ bin/matrix
...
reduce_tiles_z_order time: 3.86099 ms, 117.323 GFLOP/s
blas time: 0.533486 ms, 849.103 GFLOP/s
$ OMP_NUM_THREADS=1 bin/matrix
...
reduce_tiles_z_order time: 3.89488 ms, 116.303 GFLOP/s
blas time: 3.49714 ms, 129.53 GFLOP/s
Despite being on a current-ish version of clang, I've been getting similar results from clang for years now.
Anyways, I'm not going to debate any further. It works for me :) If you want to keep writing code the way you have, go for it.
You're probably now comparing parallel code to single threaded code.
You're changing it to a very different case, presumably one that you cared about, although 4096x4096 is oddly square and a very clean power of 2... I said right at the beginning of this long digression that what is hard about reproducing BLAS is its generality.
You don't have to use Assembly.
Case in point, this is as fast as OpenBLAS: https://github.com/mratsim/weave/tree/master/benchmarks/matm...
I have benches on i5-5257U (dual core from old MBP15), i9-9980XE (Skylake-X 18 cores), Dual Xeon Gold 6132, AMD 7840U.
See: https://github.com/mratsim/laser/blob/master/benchmarks%2Fge...
And using my own threadpool instead of OpenMP - https://github.com/mratsim/weave/issues/68#issuecomment-5692... - https://github.com/mratsim/weave/pull/94
Reproduction:
- Assuming x86 and preferably Linux.
- Install Nim
- Install a C compiler with OpenMP support (not the default MacOS Clang)
- Install git
The repo submodules MKLDNN (now Intel oneDNN) to bench vs Intel JIT Compiler
```
git clone https://github.com/mratsim/laser
cd laser
git submodule update --init --recursive
nim cpp -r --outdir:build -d:danger -d:openmp benchmarks/gemm/gemm_bench_float32.nim
```
This should output something like this
```
Laser production implementation
Collected 10 samples in 0.230 seconds
Average time: 22.684 ms
Stddev time: 0.596 ms
Min time: 21.769 ms
Max time: 23.603 ms
Perf: 624.037 GFLOP/s
OpenBLAS benchmark
Collected 10 samples in 0.216 seconds
Average time: 21.340 ms
Stddev time: 3.334 ms
Min time: 19.346 ms
Max time: 27.502 ms
Perf: 663.359 GFLOP/s
MKL-DNN JIT AVX512 benchmark
Collected 10 samples in 0.201 seconds
Average time: 19.775 ms
Stddev time: 8.262 ms
Min time: 15.625 ms
Max time: 43.237 ms
Perf: 715.855 GFLOP/s ```
Note: the Theoretical peak limit is hardcoded and used my previous machine i9-9980XE.
It maybe that your BLAS library is not named libopenblas.so, you can change that here: https://github.com/mratsim/laser/blob/master/benchmarks/thir...
Implementation is in this folder: https://github.com/mratsim/laser/tree/master/laser/primitive...
in particular, tiling, cache and register optimization: https://github.com/mratsim/laser/blob/master/laser/primitive...
AVX512 code generator: https://github.com/mratsim/laser/blob/master/laser/primitive...
And generic Scalar/SSE/AVX/AVX2/AVX512 microkernel generator (this is Nim macros to generate code at compile-time): https://github.com/mratsim/laser/blob/master/laser/primitive...
I'll come back later with details on how to use my custom HPC threadpool Weave instead of OpenMP (https://github.com/mratsim/weave/tree/master/benchmarks/matm...). As a side bonus it also has parallel nqueens implemented.
/home/bjourne/p/laser/benchmarks/gemm/gemm_bench_float32.nim(77, 8) Warning: use `std/os` instead; ospaths is deprecated [Deprecated] /home/bjourne/p/laser/benchmarks/gemm/gemm_bench_float32.nim(101, 8) template/generic instantiation of `bench` from here /home/bjourne/p/laser/benchmarks/gemm/gemm_bench_float32.nim(106, 21) template/generic instantiation of `gemm_nn_fallback` from here /home/bjourne/p/laser/benchmarks/gemm/arraymancer/blas_l3_gemm.nim(85, 34) template/generic instantiation of `newBlasBuffer` from here /home/bjourne/p/laser/benchmarks/gemm/arraymancer/blas_l3_gemm_data_structure.nim(30, 6) Error: signature for '=destroy' must be proc[T: object](x: var T) or proc[T: object](x: T)
Anyway the reason for your competitive performance is likely that you are benchmarking with very small matrices. OpenBLAS spends some time preprocessing the tiles which doesn't really pay off until they become really huge.
It was from an older implementation that wasn't compatible with Nim v2. I've commented it out.
If you pull again it should work.
> Anyway the reason for your competitive performance is likely that you are benchmarking with very small matrices. OpenBLAS spends some time preprocessing the tiles which doesn't really pay off until they become really huge.
I don't get why you think it's impossible to reach BLAS speed. The matrix sizes are configured here: https://github.com/mratsim/laser/blob/master/benchmarks/gemm...
It defaults to 1920x1920 * 1920x1920. Note, if you activate the benchmarks versus PyTorch Glow, in the past it didn't support non-multiple of 16 or something, not sure today.
Packing is done here: https://github.com/mratsim/laser/blob/master/laser/primitive...
And it also support pre-packing which is useful to reimplement batch_matmul like what CuBLAS provides and is quite useful for convolution via matmul.
Assume the author knows about BLAS, and that the point is to benchmark the language not the FFI. Most people don't actually spend their time bashing vectors together.
In other words, Python IS slow, but it can call fast code written in other languages.
> adding performance to an existing Python program requires dropping into a different language
...is demonstrably false for a significant class of programs that can be rewritten into the array paradigm. The benchmark should have picked other numerical problem to avoid this issue. The Computer Language Benchmarks Game, for example, uses the `n-body` problem for this purpose.
It's actually not that bad. I think it's part of the reason Python became so popular, it's fairly easy to write C code and expose it via python.
You need libraries to do _anything_ in Python. It's interpreted, so literally any call you make in Python will eventually make it back to something written in a compiled language (like a call to NumPy commands).
It is supposed to show 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. If you don't like matmul, ignore it and focus on nqueen, sudoku and bedcov.