Notice that clang's is much longer. Also notice all of the "# imm = 0xFFFFFFFFFFFFFC00" lines in clang. Those immediate values correspond to inlining the norm() functions: it's how clang is computing x%1024.
How do you compute x%1024? It sure would be nice to strength-reduce it to x&1023, but that's always going to produce a non-negative number, which is not what you want if x is negative. That is, -1025 % 1024 ought to be -1, and not 1023. So that strength reduction (x%1024 -> x&1023) is only valid if you can prove that x is non-negative.
And that's the first big difference. gcc-4.8 convinces itself that all of the ints involved are non-negative, and so it computes x%1024 as x&1023. clang fails to notice that all ints are non-negative, and so emits the slow path for the mod.
Let's replace int with unsigned int, and see what happens:
This allows the x&1023 strength reduction, but now we hit the second big difference: clang is futzing with xmm registers, perhaps packing a single 'vec' into a register. The codegen just looks silly to me - all those pshufd and punpckldq. Let's disable that noise with -mno-sse:
Now clang is totally kicking ass, with fewer instructions than gcc, and about 17% faster. (Of course gcc may in turn be massaged to be even faster yet.)
Timings on my i3 NUC with -O3, input 4. Lower is better:
gcc w/ signed: 4.78 sec
clang w/ signed: 7.11 sec
gcc w/ unsigned: 3.83 sec
clang w/ unsigned: 7.11 sec
clang w/ unsigned no-sse: 3.14 sec
In summary, clang is missing a big optimization, and then emitting some dubious SSE code. Fixing those more than doubles its speed. This illustrates the importance of monitoring your codegen for tight loops, and the hazards of micro benchmarks!
Wow, you're right! That improves the time from 7.11 to 3.94 seconds. I was skeptical because 'add' is inlined, which I expected would eliminate pointless copies, but I guess not!
Not only does JITting normally only occur once (something that microbenchmarks take into consideration by "warming up" the method), but if it does occur an Nth time it's because the runtime has acquired profiling information to do a more intelligent optimization pass on the method: far exceeding the quality of assumptions/heuristics made during the first JIT pass. As far as I know Hotspot implements PGO JITting.
Static compilers can do profile guided optimization, but this only takes into account the static scenario that you profiled - not the real world scenario that the program is encountering. Your PGO is only as good as your profile.
In theory, not only is your statement untrue - but reality can turn out to be the exact opposite.
There's also a significant overhead for not being able to target exactly the CPU model and parameters for the call at compile time. Unless of course doing profile guided optimization just for that CPU model and use case.
I've been playing around with an idea for a long time to write a JIT for native code. I think it's possible to speed up most native code by JITting it. Sadly it would take much more time I can afford to spend. The principle is sound, though.
It'd be possible to eliminate a lot of computation at runtime. Remove a lot of branches, use CPU model specific instructions when a suitable pattern is detected, etc. Functions could be simplified to constraints, function calls could be dynamically inlined. Spilled stack variables could be allocated in registers. Calling conventions optimized into passing more parameters in the registers. On register starved 32-bit x86, registers for parameters with effectively constant values could be converted into instructions with immediate values, saving registers for actually changing data.
There's also no reason why you can't cache previously JITted code into a file.
> All fast RegExp matchers do JIT compilation. Like PCRE. Native code just can't compete.
I thought that most "native" regex engines basically amounted to small interpreters written in a compiled language. I'd be surprised if the languages that actually compile their regexes to native code are not competitive.
Yes! But it's important to keep in mind the sort of optimizations that JIT enables: monomorphic dispatch, type specialization, etc. And also what it's bad at: computationally expensive or memory-intensive operations, like graph-coloring register allocation.
So generally speaking, we'd expect JIT to shine with certain branchy or unpredictable code, but static compilers to shine for basic blocks. Since the hot spot of the code in question is one big basic block (no if statements, etc.), where even the loop trip count is known statically, it would be surprising in this case if a JIT outperforms a static compiler.
Yeah, it might be worse at allocating registers, but on the other hand it can often free registers as well.
Static compilers just don't have the runtime information to take advantage of. Some maybe, by using profile guided optimization. JIT can always have profile guided, and adapt just for that particular case.
Right, but JITs only have the runtime information after a slower warmup period, and even then recording and exploiting this information has a cost too. The real divide here is between client/server: fancy JIT techniques can benefit long-running apps on beefy servers, but won't help a Java app launch faster on a smartphone.
There's absolutely no reason why there needs to be a warm-up period. You can cache the JITted binary code to disk. CPUs really don't care how the code was produced.
A sampling profiler can be pretty cheap. Just record stack state every n milliseconds, no need to instrument everything.
Actual JITting can be done on those other cores that would otherwise be idle anyways.
Maybe - it sounds tricky though, since optimizations can be rendered invalid across runs (e.g. a plugin may be loaded that invalidates a monomorphic dispatch optimization). So you must track and re-validate the assumptions underlying the optimized code before it can be used. Also startup code is often executed once, and so is a poor candidate for expensive JIT optimizations. That said, in principle it seems like one could do as you say - it's just hard.
Empirically, the industry seems to be moving from JIT to AOT, at least for clients. .NET -> Ngen, Dalvik -> ART, JavaScript -> asm.js, etc.
(Oh, and it's a suspect assumption that there exists other cores that "would be idle anyways!")
AOT doesn't exclude JIT! Doing both is the winning combination. AOT will ensure fast start-up time and JIT will ensure optimization to runtime conditions.
1) This program has no negative numbers yet the c++ source uses signed ints while having a lot of modulo calls which are slower than if unsigned int was used
2) This program was benchmarked with clang++
In the following numbers "new program" is replacing signed int with unsigned int and all times are measured with perf stat -r5 <binary> and run on an old intel wolfdale cpu.
Original program compiled with clang++ -O3: 1.441151117s
Original program compiled with g++ -O3: 0.826723649s
New program compiled with clang++ -O3: 1.181305003s
New program compiled with g++ -O3: 0.721448016s
Edit: Newer program with proper pass by reference vec::add
Newer program compiled with clang++ -O3: 0.770128848s
Yeah, same silly things programmers do in real world statically compiled code. Bad choices for something like data type and bad compiler options. A JIT can figure out negative numbers can't happen and optimize accordingly. It might know about the CPU model that didn't even exist when the static code was compiled.
It can do simple control flow analysis and data flow analysis and generate the constraints out of that. It doesn't even need to be right, if there's a proper guard condition in the generated code.
Interestingly, you brought up two things that are typically categorized as static analysis. Keep in mind GCC does figure out the values will never be negative and its run-times destroy all the JIT competitors listed on that page. Also, static compilers can and do generate code with guard conditions.
Yes. They're all compilers. Static compilers just limit themselves to generating and caching code just once, one size fits all. Dynamic JITs can do all that and adapt at runtime.
You could even statically compile a binary and JIT on top of that based on runtime profiles. That would probably be the winning combination performance wise.
How does this follow from you implying a JIT advantage for this use case and me asking exactly what the JIT advantage is? I think you are just arguing to win at this point.
The JIT advantage is the runtime information. Only benchmarks will always run the code in same way. Any useful piece of software runs under different conditions in different invocations and situations.
JIT can remove code from inner loops that is unnecessary for the current invocation. It can also use any instructions available on the CPU it's running on. It can use more registers if the CPU has them.
JIT advantage is higher performance, which is mostly untapped today.
I don't care about winning any points. I just want people to understand it's not black and white. JIT as an acronym causes them to jump to conclusions without even thinking about it.
Statically compiled code is suboptimal for all but the idealized case the code was compiled for. It has to take general case into account. Wasting cycles checking the condition that's always false anyways for current problem. Setting up the inner loop that's executed just once or twice every time.
A JIT can spend a few microseconds optimizing for that and running the code for 10 milliseconds. Instead of running the generic statically compiled case for 20 milliseconds. JIT can produce code more native than the "native" statically compiled presentation.
1. That is on 32-bit, for fairness it's worth mentioning that Safari is slow there because its FTL JIT is 64-bit only.
2. Firefox would also be faster on 64-bit as well (less significantly). However, TurboFan results aren't showing up on the 64-bit bot - not sure if that's an issue with the bot, or if TurboFan doesn't build on 64-bit yet.
30 comments
[ 3.0 ms ] story [ 68.4 ms ] threadAnd it's not just a little slower either, it's 36% slower than the fastest Javascript implementation.
https://github.com/h4writer/arewefastyet/blob/master/benchma...
On my Linux box, clang 3.4 is 50% slower than gcc 4.9 on -O3 on that code, for all inputs.
The key difference is, unsurprisingly, in the inner block: for (int j = 0; j < 50000; j++)...
clang's inner block asm: https://gist.github.com/ridiculousfish/24b16ba5b4e8abbe051b
gcc's inner block asm: https://gist.github.com/ridiculousfish/bee5217d6ae1f4f34a5d
Notice that clang's is much longer. Also notice all of the "# imm = 0xFFFFFFFFFFFFFC00" lines in clang. Those immediate values correspond to inlining the norm() functions: it's how clang is computing x%1024.
How do you compute x%1024? It sure would be nice to strength-reduce it to x&1023, but that's always going to produce a non-negative number, which is not what you want if x is negative. That is, -1025 % 1024 ought to be -1, and not 1023. So that strength reduction (x%1024 -> x&1023) is only valid if you can prove that x is non-negative.
And that's the first big difference. gcc-4.8 convinces itself that all of the ints involved are non-negative, and so it computes x%1024 as x&1023. clang fails to notice that all ints are non-negative, and so emits the slow path for the mod.
Let's replace int with unsigned int, and see what happens:
clang's uint asm: https://gist.github.com/ridiculousfish/c35ffcff5963160c9622
This allows the x&1023 strength reduction, but now we hit the second big difference: clang is futzing with xmm registers, perhaps packing a single 'vec' into a register. The codegen just looks silly to me - all those pshufd and punpckldq. Let's disable that noise with -mno-sse:
clang's uint asm (no SSE): https://gist.github.com/ridiculousfish/0afc79d458ae30dc6327
Now clang is totally kicking ass, with fewer instructions than gcc, and about 17% faster. (Of course gcc may in turn be massaged to be even faster yet.)
Timings on my i3 NUC with -O3, input 4. Lower is better:
gcc w/ signed: 4.78 sec
clang w/ signed: 7.11 sec
gcc w/ unsigned: 3.83 sec
clang w/ unsigned: 7.11 sec
clang w/ unsigned no-sse: 3.14 sec
In summary, clang is missing a big optimization, and then emitting some dubious SSE code. Fixing those more than doubles its speed. This illustrates the importance of monitoring your codegen for tight loops, and the hazards of micro benchmarks!
Static compilers can do profile guided optimization, but this only takes into account the static scenario that you profiled - not the real world scenario that the program is encountering. Your PGO is only as good as your profile.
In theory, not only is your statement untrue - but reality can turn out to be the exact opposite.
I've been playing around with an idea for a long time to write a JIT for native code. I think it's possible to speed up most native code by JITting it. Sadly it would take much more time I can afford to spend. The principle is sound, though.
It'd be possible to eliminate a lot of computation at runtime. Remove a lot of branches, use CPU model specific instructions when a suitable pattern is detected, etc. Functions could be simplified to constraints, function calls could be dynamically inlined. Spilled stack variables could be allocated in registers. Calling conventions optimized into passing more parameters in the registers. On register starved 32-bit x86, registers for parameters with effectively constant values could be converted into instructions with immediate values, saving registers for actually changing data.
There's also no reason why you can't cache previously JITted code into a file.
Do you have any benchmarks to back that up?
My sense is that JITet platforms lose most of the time still, but that the JITted platforms are getting closer, and occasionally win.
Static code carries a lot of overhead in some cases.
SwiftShader is a specialized JIT. It generates the code at runtime. It beats any C-code by about an order of magnitude.
https://www.transgaming.com/swiftshader/faq
All fast RegExp matchers do JIT compilation. Like PCRE. Native code just can't compete. IIRC, about an order of magnitude advantage.
Firewall rules can benefit from JIT by an order of magnitude. For example: https://wiki.freebsd.org/SummerOfCode2014/ConvertingIPFWRule...
I thought that most "native" regex engines basically amounted to small interpreters written in a compiled language. I'd be surprised if the languages that actually compile their regexes to native code are not competitive.
So generally speaking, we'd expect JIT to shine with certain branchy or unpredictable code, but static compilers to shine for basic blocks. Since the hot spot of the code in question is one big basic block (no if statements, etc.), where even the loop trip count is known statically, it would be surprising in this case if a JIT outperforms a static compiler.
Static compilers just don't have the runtime information to take advantage of. Some maybe, by using profile guided optimization. JIT can always have profile guided, and adapt just for that particular case.
A sampling profiler can be pretty cheap. Just record stack state every n milliseconds, no need to instrument everything.
Actual JITting can be done on those other cores that would otherwise be idle anyways.
Empirically, the industry seems to be moving from JIT to AOT, at least for clients. .NET -> Ngen, Dalvik -> ART, JavaScript -> asm.js, etc.
(Oh, and it's a suspect assumption that there exists other cores that "would be idle anyways!")
It's tricky I'm sure, but it'll happen.
1) This program has no negative numbers yet the c++ source uses signed ints while having a lot of modulo calls which are slower than if unsigned int was used
2) This program was benchmarked with clang++
In the following numbers "new program" is replacing signed int with unsigned int and all times are measured with perf stat -r5 <binary> and run on an old intel wolfdale cpu.
Original program compiled with clang++ -O3: 1.441151117s
Original program compiled with g++ -O3: 0.826723649s
New program compiled with clang++ -O3: 1.181305003s
New program compiled with g++ -O3: 0.721448016s
Edit: Newer program with proper pass by reference vec::add
Newer program compiled with clang++ -O3: 0.770128848s
You could even statically compile a binary and JIT on top of that based on runtime profiles. That would probably be the winning combination performance wise.
JIT can remove code from inner loops that is unnecessary for the current invocation. It can also use any instructions available on the CPU it's running on. It can use more registers if the CPU has them.
JIT advantage is higher performance, which is mostly untapped today.
I don't care about winning any points. I just want people to understand it's not black and white. JIT as an acronym causes them to jump to conclusions without even thinking about it.
Statically compiled code is suboptimal for all but the idealized case the code was compiled for. It has to take general case into account. Wasting cycles checking the condition that's always false anyways for current problem. Setting up the inner loop that's executed just once or twice every time.
A JIT can spend a few microseconds optimizing for that and running the code for 10 milliseconds. Instead of running the generic statically compiled case for 20 milliseconds. JIT can produce code more native than the "native" statically compiled presentation.
2. Firefox would also be faster on 64-bit as well (less significantly). However, TurboFan results aren't showing up on the 64-bit bot - not sure if that's an issue with the bot, or if TurboFan doesn't build on 64-bit yet.
3. Those are microbenchmarks, for more realistic workloads click on "apps", which leads to http://arewefastyet.com/#machine=28&view=breakdown&suite=asm...
which.. actually reflects reality.