Hacker News Reader

Comment by pklausler | Hacker News Reader

> But look again: C is taking 87 nanoseconds, while Rust and Haskell both take about 175 microseconds. It turns out that GCC it able to optimize this into a downward-counting loop, which drastically improves the performance. We can do similar things in Rust and Haskell to get down to nanosecond-level performance, but that's not our goal today. I do have to say: well done GCC.

Downward-counting or not, it is simply impossible for GCC to generate code that executes all 1,000,000 iterations of the loop in 87ns. That would be 87 femtoseconds per iteration, on average.

More likely, GCC figured out how to collapse the entire loop into a closed-form expression that is a function of the loop length.

View on HN

I just tested this on my machine (gcc 5.4.0). At -O2, gcc produced normal looking assembly code. At -O3, gcc produced a monstrosity [0] that I don't feel like fully deciphering.

However, from a brief glance, it does not appear to have created a closed form solution. Instead, it contains a single loop:

    .L4:
        addl    $1, %edx
        paddd   %xmm1, %xmm0
        paddd   %xmm2, %xmm1
        cmpl    %edx, %eax
        ja  .L4

which seems to be using a SIMD instruction (paddd[1]) that adds does 4 32-bit integer additions in parallel.

After this loop, it does some "housekeeping" (read, something I don't understand) before proceeding to an unwound version of the last iterations of the loop:

    leal    4(%rdx), %ecx
    addl    %edx, %eax
    cmpl    %ecx, %edi
    jl  .L2 
    addl    %ecx, %eax
    leal    8(%rdx), %ecx
    cmpl    %ecx, %edi
    ...
    jl  .L2 
    addl    %ecx, %eax
    leal    28(%rdx), %ecx
    cmpl    %ecx, %edi
    jl  .L2
    addl    %ecx, %eax
    addl    $32, %edx
    leal    (%rax,%rdx), %ecx
    cmpl    %edx, %edi
    cmovge  %ecx, %eax
    ret

Where .L2 is just:

    .L2:
        rep ret

I assume that this is just some form of return, but the documentation I could find [2] seems to suggest that rep is a prefix for string operations, which doesn't make sense.

[0]https://pastebin.com/raw/Y55gQG7p

[1] http://x86.renejeschke.de/html/file_module_x86_id_226.html

[2] https://c9x.me/x86/html/file_module_x86_id_279.html

the rep in rep ret is ignored, is just used for alignment; the 'housekeeping' code is to handle non-multiple of 8 loop counts.

Still, unless I'm missing something, the code should be executing 8 adds per clock[2]; at 4ghz, that still above 1us for 500k adds.

GCC doesn't seem to be able to fold the loop given a constant expression, unless the function is explicitly declared constexpr; in which case it will complain about the accumulator overflowing, but gcc doesn't seem to be taking advantage of it.

Clang does not vectorize the loop but will replace it with a constant given a constant parameter.

Bottom line, I'm not sure what's going on with the article's measurements.

[2] potentially 12 for skylake or even 24 with avx.

If you pass -march=skylake it will get even more monstrous, with AVX: https://godbolt.org/g/v7iKF3

I don't think so. https://godbolt.org/g/GBZgER

Perhaps the entire call of the function was replaced by a constant, then.

Yep: https://godbolt.org/g/LCUah9

    calls_cheating():
        movl    $60, %eax
        ret

No. The "constant" is only provided at runtime from Haskell through its FFI. GCC has no opportunity to optimize that.

Another possibility is that GCC discovered that the loop had no side effects in the benchmark harness and eliminated it. This is a very common thing that happens in microbenchmarks.

The c code defines a function that returns the sum computed in the loop. This function is than run using Haskell's FFI. GCC has no way of knowing there is no side effects, because other code might link to it and use the result of the function.

GHC, in concept, does know that there are no side effects, but that would apply to all of the functions being tested. Further, since it is using a benchmarking library, I assume the authors of said library were aware of the issue, and wrote it in such a way as to force evalutation of the function.

https://gist.github.com/snoyberg/9b1c77b595c4adf90880213fc49...

I.e. benchmarking is hard.

Being able to tell that a loop is gone shouldn't be too hard with a diff of the assembler output with optimizations on and off - at least for fairly trivial code.

I assume the 87 nanoseconds means the average per loop iteration, not all 1,000,000 iterations.

It's unlikely. The entire loop should have taken 0.87 seconds then. That's a bit too much for several million operations, which don't seem to require memory access.

0.087, but that still seems high.

Reply on news.ycombinator.com