Microbenchmarks are experiments
Wake up babe, new microbenchmark just dropped!
More languages, more insights!
A few interesting takeaways:
* Java and Kotlin are quick! Possible explanation: Google is heavily invested in performance here.
* Js is really fast as far as interpreted / jit languages go.
* Python is quite slow without things like PyPy. pic.twitter.com/GIshus2UXO— Ben Dicken (@BenjDicken) November 25, 2024
This one has cool animations of balls bouncing around. It claims more
insights compared to the other microbenchmark that was all the rage last
week! Yay!
Sigh. 2025 is almost around the corner and people still seem to think that the
goal of a benchmark is to produce a number which by itself reveals some hidden
truth about the world. You write a loop in Dart, you write a loop in C. You
run it three times (statistics!). You compare the running time and,
lo and behold, these two numbers reveal you all you need to know about
Dart and C performance. The rest of the day can be spent browsing numerological
magazines for the meaning of your date of birth…
Benchmarks are not numerology. Their results are not a divine revelation.
Benchmarks are experiments. Their results are meaningless without
interpretation and validation. Our understanding of performance is
driven by the same cyclic process that drives science in general:
you formulate a hypothesis, you devise the experiment, you analyze the results,
you adjust the hypothesis and repeat.“Zen and The Art of Motorcycle Maintenance” has a pretty good description of scientific method, which I think every programmer should read and will likely benefit from.
I hope next time you see a cool benchmark animation on your favorite social
network your first question will rather be “Why have the author spent time
making the animation, instead of making an analysis of results benchmarks?”.
The answer is that animations are simpler.
Anyway, the benchmark in question.
I know, I know. I claimed with rightful indignation that I would not be bothered
by meaningless benchmarks. Still I could not resist trying to understand what
hides behind the number, because that is much more important then the number
itself. The benchmark itself fits on a napkin:
import 'dart:math';
void main(List<String> args) {
final u = int.parse(args[0]); // Get an input number from the command line
final r = Random().nextInt(10000); // Get a random integer 0 <= r < 10k
final List<int> a = List.filled(10000, 0, growable: false);
for (int i = 0; i < 10000; i++) {
// 10k outer loop iterations
for (int j = 0; j < 100000; j++) {
// 100k inner loop iterations, per outer loop iteration
a[i] = a[i] + j % u; // Simple sum
}
a[i] += r; // Add a random value to each element in array
}
print(a[r]); // Print out a single element from the array
}
JavaScript version is:
The code is slightly modified compared to the original to make it directly runnable in JavaScriptCore shell: console.log became print and process.argv[2] became arguments[0]
var u = Number(arguments[0]); // Get an input number from the command line
var r = Math.floor(Math.random() * 10000); // Get a random number 0 <= r < 10k
var a = new Int32Array(10000); // Array of 10k elements initialized to 0
for (let i = 0; i < 10000; i++) { // 10k outer loop iterations
for (let j = 0; j < 100000; j++) { // 100k inner loop iterations, per outer loop iteration
a[i] = a[i] + j%u; // Simple sum
}
a[i] += r; // Add a random value to each element in array
}
print(a[r]); // Print out a single element from the array
Running this on nightly versions of Dart and JavaScriptCore yields the
following:You might be surprised that a former V8 engineer
like me is using JSC for benchmarking here, but that’s simply because JSC was
fastest of two runtimes. Thus it makes sense to look at what it does.
$ dart compile exe -o dart/code.exe dart/code.dart
Generated: /Users/vegorov/src/temp/languages/loops/dart/code.exe
$ hyperfine '~/.jsvu/bin/javascriptcore js/code.js -- 40' 'dart/code.exe 40'
Benchmark 1: ~/.jsvu/bin/javascriptcore js/code.js -- 40
Time (mean ± σ): 2.079 s ± 0.026 s [User: 2.052 s, System: 0.013 s]
Range (min … max): 2.057 s … 2.145 s 10 runs
Benchmark 2: dart/code.exe 40
Time (mean ± σ): 2.809 s ± 0.023 s [User: 2.773 s, System: 0.011 s]
Range (min … max): 2.790 s … 2.860 s 10 runs
Summary
~/.jsvu/bin/javascriptcore js/code.js -- 40 ran
1.35 ± 0.02 times faster than dart/code.exe 40
Okay, that’s interesting. Maybe even disconcerting to some. JavaScript is faster
than Dart?! How is this possible? Well, the truth is JavaScript is a pretty
fast language if all you need to is loop over Int32Array using constant
iteration bounds and add few integers together.
Leaving snark aside, the first thing to notice is that Dart and JavaScript
programs are not exactly equivalent: JavaScript is written using Int32Array
while Dart is using List which is closer to JS Array. Lets fix that:
// ...
final a = Int64List(10000);
// ...
$ dart compile exe -o dart/code.exe dart/code.dart
Generated: /Users/vegorov/src/temp/languages/loops/dart/code.exe
$ hyperfine '~/.jsvu/bin/javascriptcore js/code.js -- 40' 'dart/code.exe 40'
Benchmark 1: ~/.jsvu/bin/javascriptcore js/code.js -- 40
Time (mean ± σ): 2.081 s ± 0.033 s [User: 2.051 s, System: 0.014 s]
Range (min … max): 2.060 s … 2.171 s 10 runs
Benchmark 2: dart/code.exe 40
Time (mean ± σ): 2.212 s ± 0.015 s [User: 2.175 s, System: 0.011 s]
Range (min … max): 2.192 s … 2.241 s 10 runs
Summary
~/.jsvu/bin/javascriptcore js/code.js -- 40 ran
1.06 ± 0.02 times faster than dart/code.exe 40
Well, that’s better. Still some difference though, so it makes sense to look
at the generated code.
$ dart compile exe -o dart/code.exe \
-v \
--extra-gen-snapshot-options=--print-flow-graph-optimized \
--extra-gen-snapshot-options=--print-flow-graph-filter=dart_::_main \
--extra-gen-snapshot-options=--disassemble-optimized \
--extra-gen-snapshot-options=--code-comments \
dart/code.dart > /tmp/dart-code.asm 2>&1
$ ~/.jsvu/bin/javascriptcore --dumpDFGDisassembly=true js/code.js -- 40
Here is what Dart’s AOT compiler produces for the innermost loop:
;; B7
;; CheckStackOverflow:58(stack=0, loop=2)
loop:
ldr tmp, [thr, #56]
cmp sp, tmp
bls ->interrupt
;; Branch if RelationalOp(<, v15, v66) goto (5, 6)
movz tmp2, #0x86a0
movk tmp2, #0x1 lsl 16
cmp r4, tmp2
bge ->loop_exit
;; B5
;; v67 <- LoadIndexed:44([_Int64List] v46, v10)
add tmp, r2, r1 lsl #3
ldr r5, [tmp, #23]
;; v23 <- BinaryInt64Op(%, v15, v5)
cbz r0, 0x1036b2400
sdiv r7, r4, r0
msub r6, r7, r0, r4
cmp r6, zr
blt ->mod_slow_path
;; v24 <- BinaryInt64Op(+, v67, v23)
add r7, r5, r6
;; StoreIndexed:50([_Int64List] v46, v10, v24)
add r5, r2, r1 lsl #3
str r7, [r5, #23]
;; v25 <- BinaryInt64Op(+, v15, v68 T{_Smi})
add r5, r4, #0x1
;; ParallelMove r4 <- r5 goto:56 B7
mov r4, r5
b ->loop
JavaScriptCore does this for comparison:I have stripped information about DFG/B3/Air IL levels because it makes output too verbose for an unprepared eye. Full output for both Dart and JSC is available here
loop:
ldr w7, [x2, w9, uxtw#2]
sxtw x6, w8
mul x6, x6, x0
lsr x6, x6, #32
asr w6, w6, #4
add w6, w6, w6, lsr #31
msub w6, w6, w4, w8
tst w8, w8
b.mi ->mod_slow_path
adds w6, w6, w7
b.vs ->overflow
str w6, [x2, w9, uxtw#2]
add w8, w8, #1
cmp w8, w3
b.lt ->loop
Comparing Dart and JSC output reveals the following differences:
The last item is the most interesting to me. I have always known that the cost
of interrupt checks inserted into all loops tends to add up if these loops are
very tight. I periodically come back to this and discuss with my colleagues
various possible optimizations we could apply here, but so far we have not
come up with something that would be fairly simple to implement and would
significantly improve the performance. Instead, I have added an escape hatch:
@pragma('vm:unsafe:no-interrupts') can tell the compiler that it should
omit interrupt checks on the loops inside the function.
JSC uses a combination of signals and code patching to
interrupt JIT compiled code: a signal is sent to interrupt the thread, if thread
is executing JIT compiled code that code will be patched to go into runtime
system when signal handler completes. See VMTraps.cpp and JumpReplacement::installVMTrapBreakpoint.
For environments where code patching is not an option JSC also supports a
polling based
interruption mechanism which works by inserting explicit checks into the JIT
compiled code.
It might be tempting to just plaster this pragma on the main, but that’s
exactly what one should not do. At least not when using this pragma in the
real world (though you probably should not actually use it in the real world).
// no. NO. NO! Not a good idea.
// @pragma('vm:unsafe:no-interrupts')
void main(List<String> args) {
// ...
}
Other Dart VM specific pragmas are documented here. Those with unsafe in their names are intended to be used with
caution – only if you fully understand the implications associated with them.
Your reasoning should go like this: main has two nested loops, and executes
for ~2seconds. Making it uninterruptible for the whole two seconds is not a
good idea. What if VM needs to trigger a GC in some other isolate in the same
isolate group? That GC would have to wait whole 2 seconds, blocking the
whole isolate group. Not a good idea. Instead, you could do the following:
void main(List<String> args) {
// ...
@pragma('vm:unsafe:no-interrupts')
void innerLoop(int i) {
for (int j = 0; j < 100000; j++) {
// 100k inner loop iterations, per outer loop iteration
a[i] = a[i] + j % u; // Simple sum
}
}
for (int i = 0; i < 10000; i++) {
// 10k outer loop iterations
innerLoop(i);
a[i] += r; // Add a random value to each element in array
}
// ...
}
This way main will still be interruptible in the outer loop, but there will
be no interrupt checks in the inner loop reducing uninterruptible periods to
0.2ms, which is probably just fine for most of the situations.Note that inliner fully inlines and eliminates overhead of the innerLoop. It does not always happen – so when writing performance sensitive code and factoring it into various helpers you should always check the code which gets generated.
This version of Dart code yields the following result:
$ hyperfine '~/.jsvu/bin/javascriptcore js/code.js -- 40' 'dart/code.exe 40'
Benchmark 1: ~/.jsvu/bin/javascriptcore js/code.js -- 40
Time (mean ± σ): 2.100 s ± 0.059 s [User: 2.056 s, System: 0.016 s]
Range (min … max): 2.059 s … 2.236 s 10 runs
Benchmark 2: dart/code.exe 40
Time (mean ± σ): 2.091 s ± 0.022 s [User: 2.056 s, System: 0.010 s]
Range (min … max): 2.069 s … 2.131 s 10 runs
Summary
dart/code.exe 40 ran
1.00 ± 0.03 times faster than ~/.jsvu/bin/javascriptcore js/code.js -- 40
Which is fine by me. By the way, as described in a sidenote above JSC does also
support polling based interruption, so we could do this comparison the other
way around: keep Dart VM’s interruption checks in the code and ask JSC to add
them as well by passing --usePollingTraps=true:
$ hyperfine '~/.jsvu/bin/javascriptcore --usePollingTraps=true js/code.js -- 40' 'dart/code.exe 40'
Benchmark 1: ~/.jsvu/bin/javascriptcore --usePollingTraps=true js/code.js -- 40
Time (mean ± σ): 2.204 s ± 0.032 s [User: 2.161 s, System: 0.015 s]
Range (min … max): 2.174 s … 2.261 s 10 runs
Benchmark 2: dart/code.exe 40
Time (mean ± σ): 2.197 s ± 0.013 s [User: 2.167 s, System: 0.008 s]
Range (min … max): 2.187 s … 2.220 s 10 runs
Summary
dart/code.exe 40 ran
1.00 ± 0.02 times faster than ~/.jsvu/bin/javascriptcore --usePollingTraps=true js/code.js -- 40
Now you ask a question: why are we comparing against JavaScript and
not against a more serious competitor like C?
#include "stdio.h"
#include "stdlib.h"
#include "stdint.h"
int main (int argc, char** argv) {
int u = atoi(argv[1]); // Get an input number from the command line
int r = rand() % 10000; // Get a random integer 0 <= r < 10k
int32_t a[10000] = {0}; // Array of 10k elements initialized to 0
for (int i = 0; i < 10000; i++) { // 10k outer loop iterations
for (int j = 0; j < 100000; j++) { // 100k inner loop iterations, per outer loop iteration
a[i] = a[i] + j%u; // Simple sum
}
a[i] += r; // Add a random value to each element in array
}
printf("%d\n", a[r]); // Print out a single element from the array
}
$ clang -O3 -o c/code.exe c/code.c
$ hyperfine 'c/code.exe 40' 'dart/code.exe 40'
Benchmark 1: c/code.exe 40
Time (mean ± σ): 644.0 ms ± 11.9 ms [User: 630.9 ms, System: 3.3 ms]
Range (min … max): 635.1 ms … 671.6 ms 10 runs
Benchmark 2: dart/code.exe 40
Time (mean ± σ): 2.234 s ± 0.024 s [User: 2.186 s, System: 0.014 s]
Range (min … max): 2.189 s … 2.267 s 10 runs
Summary
c/code.exe 40 ran
3.47 ± 0.07 times faster than dart/code.exe 40
Well, that’s some serious competion!
What if I told you that you can make original Dart version (one with
List.filled and interrupt checks) to run just 10% slower than C version with
a one line change? And on that line there would be only 4 non-whitespace
characters and a semicolon?
$ hyperfine --warmup 1 'c/code.exe 40' 'dart/code.exe 40'
Benchmark 1: c/code.exe 40
Time (mean ± σ): 638.6 ms ± 7.0 ms [User: 629.2 ms, System: 2.1 ms]
Range (min … max): 631.6 ms … 655.6 ms 10 runs
Benchmark 2: dart/code.exe 40
Time (mean ± σ): 692.4 ms ± 5.0 ms [User: 667.6 ms, System: 6.0 ms]
Range (min … max): 686.1 ms … 701.3 ms 10 runs
Summary
c/code.exe 40 ran
1.08 ± 0.01 times faster than dart/code.exe 40
Are you ready?
import 'dart:math';
void main(List<String> args) {
final u = int.parse(args[0]); // Get an input number from the command line
final r = Random().nextInt(10000); // Get a random integer 0 <= r < 10k
final a = List.filled(10000, 0, growable: false);
for (int i = 0; i < 10000; i++) {
// 10k outer loop iterations
a[i]; /* <- THIS LINE WAS ADDED */
for (int j = 0; j < 100000; j++) {
// 100k inner loop iterations, per outer loop iteration
a[i] = a[i] + j % u; // Simple sum
}
a[i] += r; // Add a random value to each element in array
}
print(a[r]); // Print out a single element from the array
}
I added a[i]; right before the inner loop and that somehow made things
massively faster. How did that happen?
What LLVM notices and what Dart does not is that a loop:
As far as I could see by inspecting output of
-mllvm --print-before-all this happens in the LLVM’s LICM pass, probably in promoteLoopAccessesToScalars.
for (int j = 0; j < 100000; j++) {
a[i] = a[i] + j % u; // Simple sum
}
is the same as
var v = a[i];
for (int j = 0; j < 100000; j++) {
v = v + j % u; // Simple sum
}
a[i] = v;
This means inner loop no longer touches any memory which makes it much faster.
Dart compiler is relatively good at forwarding loads, but it does not perform
any load hoisting. Once we manually added a[i] before the loop
made a[i] inside the loop redundant. Compiler noticed that it has a[i]
value flowing on all edges and eliminated a[i] load inside the loop:You might be tempted to try combining Int64List change with a[i]; hint but that would not work. It turns out that Dart’s load forwarding pass is very shy around forwarding stores into typed lists. It is a bug I intend to fix.
var v = a[i];
for (int j = 0; j < 100000; j++) {
v = v + j % u;
a[i] = v; // (1)
}
a[i] = v + r; // (2)
After that it noticed that a[i] = ... at (1) is dead because it will
be overwritten by store at (2) and we end up with code similar to the one
LLVM was able to produce.
var v = a[i];
for (int j = 0; j < 100000; j++) {
v = v + j % u;
}
a[i] = v + r;
In reality compiler should really try to perform this optimization itself:
I have occasionally encountered hot loops (e.g. lexer keeping a
character position in a field) where it would be really beneficial. I am
planning to take a look at this some time in the future.
I wish to conclude this post in a circular fashion, like a novel where
weary hero returns home and discovers that everything, including him, have
changed. Hopefully you, reader, too have changed and no longer believe that
measuring a time it takes to perform 1000000000 of modulo operations and
looking at that number alone somehow enlightens you about performance of
some programming language.
My blog no longer has
comments section. If you want to discuss
contents of this post you can send me an email at [email protected]
or find me on Mastodon or
X.
