Why is this C++ code faster than my hand-written assembly (2016)

I live my life by that adage

One thing to keep in mind is that the CPU is no longer the CPU you think it is. While the x86 instruction set used to directly control the processor, today it's just a compatibility shim. Under the covers, the CPU is converting your assembly into its own microcode and it's that microcode which is doing the real work. For example, look at some of the block diagrams in section 2 of this Intel manual:

https://software.intel.com/sites/default/files/managed/a4/60...

Combine that with all kinds of other voodoo they've added--fancy caches, branch prediction, and so forth--and the "don't even try" maxim starts to make sense. I'd amend that to say "don't even try unless you're just curious."

Personally, I think assembly is a great learning tool, e.g. for understanding how pointers work, how the stack works vs. the heap, how function calls work, and so-forth. I was exposed to Motorola 68K assembly in college and it completely changed my world--lots of C++ things I considered voodoo suddenly made total sense. But I've never used assembly in production code and probably never will.

I find this "Why would you even do that?" attitude in StackOverflow to be very irritating. And it's not just in low-level optimization questions. StackOverflow should be a place for questions and answers, not a collection of lessons on corporate best practices where curiosity and experimentation is discouraged.

Surprising that people writing a book 25 years ago would not have been aware of this work.

https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

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

While speed wasn't a huge issue, consistency was. Simply using sin/cos to draw the circle works, but it can lead to jagged and inconsistently placed pixels if your degree step isn't perfect. Even with my middle school level math, I realized I could just iterate over the bounding box for the circle and just use r^2 as a threshold on x^2+y^2 to determine whether a pixel should be on or off - no square root required, since it's totally redundant.

It has the bonuses of using only integer math (consistency!) and only requires slight changes to yield filled or unfilled circles. It's also almost as fast as drawing a simple filled rectangle!

The idea that the author could miss such a simple algorithm baffles me.

Yeap. But once you do, it's almost always easy to get some efficiency gains, because you understand what the code intends, and the compiler does not.

Surprisingly it doesn't take much experience to do this: just a profiler, and a willingness to try different things until you find something that works.

On the topic of hand-optimizing or not: There always seem to be two camps. The first say: "Never bother with assembly. Let the compiler do optimizing. If anything, try to write code that the compiler can optimize.".

The second camp always states something like "It is not that hard to outperform the compiler.".

I guess the complicated pipeline models are mostly the reason for the complexity. I'm not sure how much compilers do to avoid pipeline stalls though. For example, how detailed the execution model that they use is. It shouldn't be too complicated, since most compilers (as far as I know) don't differentiate between different processors, while different processors have a different execution model.

Essentially you must have a piece of code where that constant is just a parameter to the algorithm that suddenly when set to a value of 2 makes it that much more efficient.

Now here's the bummer: if you had already planned for it, then writing custom assembly for it is not going to make the algorithm that much faster. But when you didn't - you're rewriting the whole of the algorithm anyway.

It was an amazing crash-course on just how good compilers have become at optimizing. Not a single student could hand craft assembly that was faster than the compiler output. The teacher of the course was able to generate assembly that was slightly faster, and he stated that in order to do so, he had to greatly exploit his in-depth knowledge of the processor's pipeline system. That was roughly year 2000, and I'm sure compilers have only become better at their job since then.

All in all, excellent learning experience. I've since encountered several instances where developers assert superior assembly skills, and by default I'm silently skeptical of their claims.

I measured, but it did not run any faster. Damnit, this is assembly, I said, it has to be faster. So I looked at the assembly code generated by the compiler: Turned out it was pretty much identical to the code I had written. At that point, I felt brief surge of pride (because I was as clever as the compiler) and then disappointment (because I was not more clever than the compiler), and I figured trying to be smarter than the compiler was a waste of my time.

Also back in 2016, I participated in a pseudo-challenge on the fasm board [1] and it is trivial to optimise both the C/C++ as well as hand-written assembly. IMO comparing how good a compiler is at optimising is akin to how good it is at figuring out your intentions (and they all suck at that).

1: https://board.flatassembler.net/topic.php?t=19103

The OP clearly does understand assembly enough to start doing project Euler type problems, which is a good way to learn basic programming in any language. They get a solution in assembler which is more than many people here would be able to do I suspect.

And they're looking to expand their knowledge by asking on stack-overflow about something they don't understand.

So why do you think they should they be met with rudeness and hostility?

What C and C++ give you (and Assembly gives you even more of) is control. If you can, and know how to, capitalise on that control, you _will_ get more performance. But those requirements are non-trivial.

I personally find it a shame that there are so many juicy instructions that compilers have no hope of ever using effectively. How often is a compiler smart enough to solve a problem with PDEP/PEXT, for example? Those functions are versatile as heck, but you need to plan for them if you want them to show up.

Start with compiler output, add intrinsics where you can see help is needed, benchmark, repeat.

Pathologically-slow ASM is pretty rare from modern compilers in my experience.

  #define FIZZ 1
  #define BUZZ 2
  static const uint8_t divs[] = 
 {FIZZ+BUZZ,0,0,FIZZ,0,BUZZ,FIZZ,0,0,FIZZ,BUZZ,0,FIZZ,0,0};
  static const char* strs[] = {
    [0] = "%u\n",
    [FIZZ] = "fizz\n",
    [BUZZ] = "buzz\n",
    [FIZZ+BUZZ] = "fizzbuzz\n"
  };

  void fizzbuzz(uint32_t upTo)
  {
    uint32_t i, state;

    for(i = state = 0; i < upTo; i++) {
      printf(strs[divs[state]], i);
      if(++state == sizeof(divs) / sizeof(*divs))
          state = 0;
  }

One level of arrays may be skipped at cost of extra .rodata size (store string pointers directly in divs). But in a modern cpu cost of the extra load is small

(Also, no, `%5` isn't "horrifically" slow when it's a compile-time-constant modulus: you or the compiler can do it with a multiply and shift for the integer division, and then x%5 = x - (x/5 * 5). https://godbolt.org/g/3HwBrF. It still sucks though.)

I wrote an x86 assembly FizzBuzz for fun a while ago, intended to be an example of how to optimize (https://stackoverflow.com/a/37494090/224132). Some parts of it kind of suck, though. I made some parts efficient (like appending "buzz\n" to a buffer with a mov [rdx], r13 / add rdx, 5), but left in too many conditional branches and a function call instead of inlining everything when unrolling.

I'm glad so many people like my post that the OP linked. It was fun to write. :)

I decided to reject your conditions and replace them with my own, for no apparent reason. Mine has some of the redundancy you wish to eliminate, but the loop body is completely branchless, aside from the call to printf, of course, which we're apparently ignoring.

    #include <stdio.h>
    
    #define NUM "\x06" "%zu\n\0"
    #define FIZZ "\x07" "Fizz\n\0"
    #define BUZZ "\x07" "Buzz\n\0"
    
    const char *x =
        NUM
        NUM
        FIZZ
        NUM
        BUZZ
        FIZZ
        NUM
        NUM
        FIZZ
        BUZZ
        NUM
        FIZZ
        NUM
        NUM
        "\xa6" "FizzBuzz\n";
    
    void fizzbuzz(size_t upTo) {
        for(size_t i = 1; i <= upTo; i++) {
            printf(x + 1, i);
            x += *x;
        }
    }
    
    int main(int argc, char **argv) {
        fizzbuzz(100);
    }

    #include <stdio.h>
    #include <stdint.h>
    
    #define FIZZ(x)         (x & 0x0924)
    #define BUZZ(x)         (x & 0x0210)
    #define FIZZBUZZ(x)     (x & 0x4000)
    #define NONE(x)         (x & 0x34cb)
    
    void fizzbuzz(size_t n_max)
    {
        uint32_t x = 1;
        for (size_t i = 1; i <= n_max; i++)
        {
            if (FIZZ(x))
              printf("fizz\n");
            if (BUZZ(x))
              printf("buzz\n");
            if (FIZZBUZZ(x))
              printf("fizzbuzz\n");
            if (NONE(x))
              printf("%d\n", i);
            x <<= 1;
            x |= (x >> 15);
        }
    }
    
    int main(int argc, char **argv)
    {
        fizzbuzz(100);
    }

  #include <stdio.h>
  #include <stdint.h>
  
  #define F(n) (1 << (2*(n)-2))
  #define B(n) (1 << (2*(n)-1))
  
  int main() {
    uint32_t m = F(3) | F(6) | F(9) | F(12) | F(15) | B(5) | B(10) | B(15);
    int i;
    static char t[4][16]= { "%d\n", "Fizz\n", "Buzz\n", "FizzBuzz\n" };
    for (i = 1; i <= 100; i++) {
      printf(t[m&3], i);
      m = (m >> 2) | (m << 28);
    }
    return 0;
  }

That said, I do think it's neat that the fastest brute-force variant is a rough factor-2 from your naïve memoized version. It might even win if it was fighting a hyperthread for cache space! Just shows how much throughput modern CPUs have... if only they were used this well all the time ;).

I'm not sure that's true. There are hundreds of compilers in the world, being maintained by thousands of developers. Then there are all the JITs. And the people who make the standard library implementations. And performance critical stuff in game engines, OS kernels, hardware drivers, high-frequency trading. Then there's the embedded space. And then there's Fabrice Bellard.

My previous employer, Cambridge Silicon Radio (one of hundreds of similar companies nobody's heard of) had dozens of people on the staff that worked on this kind of thing. I have friends at ARM, Broadcom, Samsung and Raspberry Pi that mess around with processor designs for a living. This is just my little experience of the industry. There are armies of these people.