Hacker News Reader

GCC with -O3 might try to unroll this loop into a single constant. O(0) is pretty fast.

That's very likely. Clang 8.0 collapses the loop with any optimizer setting other than -O0.

But if you had to do it manually, loop unrolling and SIMD instructions (although not part of standard C) would be good bets and can probably get you an order of magnitude.

Clang 8.0?

Apple Clang version number is approximately the same as the Xcode version number, and not identical to the Clang release it's based on.

So what version of upstream Clang is Xcode 8.0 based on?

GCC as expected, O>2

        sub     rsp, 8
        mov     rdi, QWORD PTR [rsi+8]
        mov     edx, 10
        xor     esi, esi
        call    strtol              <-- atoi
        xor     eax, eax            <-- zero return value
        add     rsp, 8
        ret                         <-- return from main

Interestingly enough it does not elide the entire function body.

How do you get objdump -S to print out non AT&T syntax? My output looked like this:

    000000000400400 <main>:
      400400:	48 83 ec 08          	sub    $0x8,%rsp
      400404:	48 8b 7e 08          	mov    0x8(%rsi),%rdi
      400408:	ba 0a 00 00 00       	mov    $0xa,%edx
      40040d:	31 f6                	xor    %esi,%esi
      40040f:	e8 dc ff ff ff       	callq  4003f0 <strtol@plt>
      400414:	31 c0                	xor    %eax,%eax
      400416:	48 83 c4 08          	add    $0x8,%rsp
      40041a:	c3                   	retq   
      40041b:	0f 1f 44 00 00       	nopl   0x0(%rax,%rax,1)

Which I'm not a fan of. I've always wanted "add (store), (get)" but could never get that.

Not on a development machine right now, so I just went to godbolt ;)

https://godbolt.org/

Use the '-M intel' option.

-M intel

ITYM "O(1)".

"O(0)" is pretty much meaningless.

I mean O(0) because no operation occured. The only operation that will occur is parsing the data which is not the problem specified. When looking at the loop, and just the loop, O(0) is the correct answer for this.

Well the obvious answer would be, eliminate the loop, which is what any compiler optimizer will do ;)

But let's assume that the operation is not quite so trivial like here, then this structure would be a prime example where each loop operation is independent from each other, so you can sum a vector in parallel (=SIMD) and then sum the vector once in the end.

Also, since we're obviously not using any compiler optimizations, you can unroll the loop, which reduces per-iteration loop overhead (the conditional jump) and in such a simple case as here is bound to give a nice boost.

When you say "eliminate the loop", do you mean loop unrolling? They are compiling with -O2, I'm not sure if that does loop unrolling. If it does, how much unrolling does it do, exactly? I can't imagine it would construct a block of code with a billion add instructions.

s += NUMBER

or

s = NUMBER

Eliminating the loop means the compiler looks at the code and says "the value computed in this loop is never actually used, so might as well just get rid of that code altogether".

First, it's unused, so it'll just kill it. If it wasn't, most compilers can compute sum reductions, etc, pretty well.

Anything that is easily expressed as a set of simple recurrences that can be solved, it'll solve.

You can't really do loop unrolling and constant folding as some suggest because the number of iterations is determined at run time.

But assuming his CPU takes one cycle for an addition and one cycle for a conditional jump, his CPU only needs to run at 1GHz to achieve his result.

Given that branch prediction should be nearly perfect for such a simple and short loop, modern x86 CPUs doing at least 4 integer additions per cycle, and typical CPU speeds in the range of 2-4 GHz, a properly optimized version should be nearly an order of magnitude faster.

So either more aggressive compiler flags and maybe SIMD intrinsics, or hand written assembly (easy here, not so easy in the real world)

> You can't really do loop unrolling and constant folding as some suggest because the number of iterations is determined at run time.

Huh?

That question is a bit unspecific :D

>NUMBER = atoi(argv[1]);

argv is populated at runtime based on what the OS passed you.

But you are right if you meant that my statement is too strong: you can't do arbitrary loop unrolling. You can jump to a loop that's unrolled once if the number is even, etc.

There are certainly also optimizers that will just output the input without any loop, but that's beyond anything I would expect of a current production compiler.

If you are going from 0 -> NUMBER and adding one to a variable every iteration, what will the variable's final result be? NUMBER. The compiler can see this and will just do the following:

    s = i = atoi(argv[1]);

Now the loop is gone.

Edit: This will still happen even if you're doing other stuff in there. GCC will attempt to inline and optimize like this. If it is impossible then you will see a loop with most of the stuff factored out of it.

Well, you could do arbitrary loop unrolling - with Duff's Device:

https://en.wikipedia.org/wiki/Duffs_device

for a data parallel problem like that you could vectorize it using the SIMD unit. It never ceases to amaze me at any point how much of silicon real estate just sits idle because no one really bothered to look behind the curtain and tailor the code for a specific architecture. for reference, a recent Intel chip will have 256b wide vector unit (512 for server class chips) that can be treated as a vector of 8/16/32/64b units to do parallel math. at a typical 16b ops you get 16x speedup for practically nothing. plus its considerably more if you have predictable but non standard data access patterns.

now <rant> IMO what the parent commenter was trying to say is often this punchline about premature optimizations used as catch-all justification for all the convenience/expediency related decisions taken. & also it just works well to create future work. unfortunately that never gets scheduled as I have seen management time frame shrink too. almost everyone is in quick & dirty 'working' version to book a success and move on. with this culture if you try to push resolving these 'technical debt' type issues you are just perceived as a downer. </rant>

I've heard that modern processors are designed with the expectation (or even a requirement) that no more than 10% of the chip will be active at once. In addition, there are power density constraints (even those 10% of the chip that can be active at once must not be concentrated in the same spot).

Nope, but processors, especially larger ones, have pretty advanced power and clock management which allows them to deal with power envelope and thermal envelope constraints. E.g. the two clocking and core voltage ladders in Xeon E5/E7 for AVX vs. non-AVX code. (Though this particular example is a bit of a sledge-hammer approach).