Daniel Wunsch wrote:
On Tuesday 10 May 2005 21:18, Tim Starling wrote:
int main() {for (unsigned i=0; i<(unsigned)1e9; i++);} executes in 1.58 seconds on my desktop computer.
hm.. we all know how badly microbenchmarks can go wrong. in this case i'd have expected the loop to be optimized away, since it does not affect the state of the rest of the program in any way..
If I was using such a compiler, I would have just disabled that optimisation. For all compilers/interpreters, I tried with a few different loop sizes to make sure it was actually taking O(N) time. As it happens, for g++ -O3 I did dump the assembly code:
xor eax, eax .p2align 4,,15 L6: inc eax cmp eax, 999999999 jbe L6
I thought I'd be clever and make a tighter loop by hand:
mov ecx, 1000000000 .p2align 4,,15 L6: loop L6
But to my disappointment it was slower than the machine generated version. That's pipelining for you, I guess. I could have unrolled the loop, but, well, that's getting a bit silly.
The question I was trying to answer was: what is the fastest possible loop in a given language? I think it was a reasonable question to ask. For the interpreters, it was mainly a test of variable access speed. I did try Java, but I didn't include it because it was clear that it was using a JIT compiler to produce native code similar to the C++ version. My purpose was to make fun of the interpreters, the compiled language was just included as reference for what a fast language is.
Don't worry, I do have ways to make fun of Java, that just isn't one of them :)
Another point I would make is that fundamentally, it is weak typing that makes Perl and PHP slow. To optimise Perl or PHP properly, you'd have to not only convert it to a low level language, you'd have to inline the simpler variable access functions and then use an optimiser capable of identifying the types as loop invariants, thus removing some of the conditional branches from the loop. Object-oriented C++ has the same problem.
-- Tim Starling