5 ms·

This is how a human would code the same (a human would know, for instance, that (s)he wants to multiply 50 times, passing that in %rax (that would be your "n" i

This is how a human would code the same (a human would know, for instance, that (s)he wants to multiply 50 times, passing that in %rax (that would be your "n" in C), something a compiler can never know, which is one of many reasons (and there are many!) why a compiler can never, ever beat a human at coding in assembler: DotProduct: subss %xmm0, %xmm0 .Loop: movss (%rdi, %rax, 4), %xmm1 mulss (%rdi, %rax, 4), %xmm1 addss %xmm1, %xmm0 subq $1, %rax cmpq $0, %rax jnz .Loop ret ...potentially, depending on how 80x86 processors work, the Z flag might be set when subq $1, %rax reaches 0 and the cmpl $0, %rax could be optimized away, making the code even shorter (and faster). But I'll leave it in there because this handily beats the compiler in both size and speed, even with the compiler often trying to cheat with nopw instructions to warm up the data cache. Now compare that with the garbage GCC generated. At -O3 no less! What a bunch of garbage! On a personal note, you forced me to write code for a processor architecture I do not even know (80x86 family of processors in 64-bit mode), at all, so you just assumed my primary system is powered by that intel / AMD garbage of processors, and I don't appreciate that one bit. And you doubted me, which I appreciate even less.

tom_mellior 7y ago
> a human would know, for instance, that (s)he wants to multiply 50 times A human would turn the for loop that counts up into a do-while loop that counts down? That's doable on the C level, and in that case GCC also generates less ceremony: dot_product_2: .LFB1: .cfi_startproc pxor %xmm0, %xmm0 movslq %edx, %rdx .p2align 4,,10 .p2align 3 .L8: movss (%rdi,%rdx,4), %xmm1 mulss (%rsi,%rdx,4), %xmm1 subq $1, %rdx leal 1(%rdx), %eax testl %eax, %eax addss %xmm1, %xmm0 jg .L8 rep ret But of course if you do this you have changed the implied original spec, and you have reassociated a floating-point computation, computing different results. At that point you might as well pass -ffast-math to GCC, and it will beat your code by 8x due to vectorization. > But I'll leave it in there because this handily beats the compiler in both size and speed Not on my machine. On arrays of 1048576 (2 ^ 20) elements I didn't measure any difference between my first variant, the do-while variant and yours. On arrays of 1024 elements I still didn't measure a difference between the two compiled versions, but yours is about 1-2% slower. On 128 elements do-while looks a bit slower than for, and your variant is more than 20% slower. Here are some numbers for n = 128, calling each function 10000000 times. dot_product is the original, dot_product_2 uses do-while, dot_product_3 is your code (with an extra move of edx to rax at the start of the function, of course). dot_product: 1.036514 sec dot_product_2: 1.097186 sec dot_product_3: 1.290411 sec (Edit: This seems to be due to your use of subss instead of pxor to zero xmm0 at the beginning. Removing that gets your code back up to only 1-2% slower than the for loop version.) > even with the compiler often trying to cheat with nopw instructions to warm up the data cache What? > Now compare that with the garbage GCC generated. At -O3 no less! What a bunch of garbage! You still haven't pointed out what exactly you think is garbage. Which line? Which instruction? Or don't you like that it generates some metadata? > you forced me to write code for a processor architecture I do not even know I didn't force you to do anything, I specifically asked you to provide an example of your choice. You could have chosen a piece of code where you knew in advance GCC would do badly. You could have chosen an architecture that you know well and/or one where you know that GCC's backend hasn't had as much work as x86-64. You chose not to do this. I didn't force you to do anything. > And you doubted me Based on the data it looks like I was right to doubt you.
- Annatar 7y ago
  "A human would turn the for loop that counts up into a do-while loop that counts down?" Of course an experienced coder would do that; that's the entire point of why a compiler will never be able to generate as short and as fast of code as a human would. An experienced coder can see opportunities that a program with a hard-coded logic such as a compiler is incapable of seeing; if it were, we would have true artificial intelligence, with the neural network of a human brain or denser. "That's doable on the C level," For some bizarre reason unbeknown to me, you just cannot seem to get your head around writing a program in assembler from start to finish. An experienced assembler coder looking for performance would not use a high level language like C because it would be a waste of her or his time, since they already know from experience that they can easily beat hard-coded program logic of a compiler (and if they did, they would chose Fortran over C). Programming in a high-level language only makes sense when the trade-off of losing performance is acceptable in the name of portability. Even then, there are situations where a portable program in a high level language has hand-written, per-processor assembler code (OpenSSL comes to mind). Why do you think that is? "What?" Some versions of GCC for intel 80x86 family of processors will generate one or more nopw instructions, the idea being to give the processor time to prime the data cache. It's a cheap gimmick of desperate compiler constructors, more of a gamble really, because cache games heavily depend on a very particular processor model in a processor family. "At that point you might as well pass -ffast-math to GCC, and it will beat your code by 8x due to vectorization." I could have vectorized this myself (that was actually the first thought I had) but chose not to because I didn't want to spend the time researching how to do that on the intel 80x86 family of processors; I could have also unrolled the loop about four to eight times for even more of a performance gain, but chose not to do so because I believe I made my point. Now you are just being purposely obtuse, because it seems that you just don't want to accept that high level compilers still aren't as fast as a human coder is: you chose a dot product because you likely knew that the compiler would generate pretty fast code, but that one isolated example doesn't really prove anything. If you do more comparisons over decades like I have, you will see how silly it was trying to argue that compilers generate faster code than coders. Also, -ffast-math can generate code which will run the fastest only on that particular processor (and might generate instructions which will not run on other processors of the same family), but the far worse danger is that -ffast-math won't generate IEEE-754 compliant results. When one needs very high precision floating point arithmetic, -ffast-math cannot guarantee correct results. For these two reasons, -ffast-math is useless in real life applications. And indeed, wouldn't you know it: -ffast-math Sets the options -fno-math-errno, -funsafe-math-optimizations, -ffinite-math-only, -fno-rounding-math, -fno-signaling-nans and -fcx-limited-range. This option causes the preprocessor macro "__FAST_MATH__" to be defined. This option is not turned on by any -O option besides -Ofast since it can result in incorrect output for pro- grams that depend on an exact implementation of IEEE or ISO rules/specifications for math functions. It may, however, yield faster code for programs that do not require the guarantees of these specifications. "(Edit: This seems to be due to your use of subss instead of pxor to zero xmm0 at the beginning. Removing that gets your code back up to only 1-2% slower than the for loop version.)" There are two ways to do it fast: eor (or what the idiotic intel architecture calls "xor"), or the sub instruction. On the Motorola MC680x0 family, both run at the same speed. Up until that time, I have never in my entire life written a single line of assembler code for the intel 80x86 family of processors. What you saw is the first assembler code I ever wrote for that platform; I even had to look up which registers to use for floating point and how to do floating point arithmetic on that family of processors, and my hard target was less than 15 minutes of total time wasted on a someone is wrong on the InterNet (https://www.xkcd.com/386/ https://www.xkcd.com/386/) discussion. If I could do that in under 15 minutes for a processor family I literally know nothing about, imagine what a real coder experienced in writing 64-bit assembler code for the intel 80x86 family of processors can do. "You still haven't pointed out what exactly you think is garbage. Which line? Which instruction? Or don't you like that it generates some metadata?" I haven't because I was on a mobile telephone and it was just too much of a bother to quote and reply what I wanted to address. I had to log into a workstation to reply to this and I resent that too. I don't like all of the above, the code and the metadata the compiler generated, because it's machine generated nonsense which jumps back and forth and it is hard to read and comprehend. Assembler code written by a human isn't. Now, since I already resent what I'm doing, I might as well go all the way. Let's pick apart the compiler generated examples in reverse order. movslq %edx, %rdx movslq isn't even necessary, but the compiler, having hard-coded logic and being just a program generated it anyway. Waste of CPU cycles. .p2align 4,,10 .p2align 3 more assembler directives because a compiler cannot figure out whether such packing is necessary or not. My code didn't need them because I know that I don't. leal 1(%rdx), %eax testl %eax, %eax again, nonsense: two instructions wasted with what could amount to a single subq. This isn't more efficient. rep ret Why, when a ret will do? Obviously in my code it worked, but the compiler felt that it had to generate this nonsense, which on top of being nonsense is harder to read and understand, and isn't any faster. Next example: testl %edx, %edx jle .L4 leal -1(%rdx), %eax testl is a total waste of processor cycles here. Which purpose does it serve? Then more cycles are wasted on jumping to an instruction to clear %xmm0, presumably to be able to utilize the instruction pipeline, but all the jump does is waste cycles. xorl %eax, %eax why xorl %eax in a loop when it could be done once? More waste of processor cycles. That code is extremely inefficient, and hopes to trade off readability for banking on a specific feature of intel 80x86, hoping that the instruction cache and pipelining will offset the losses. Idiotic in the extreme considering a human could get the same performance with far less and simpler code! "Based on the data it looks like I was right to doubt you." It might look that way to you now, but if you choose to acquire more experience in coding in assembler, you will eventually realize that I'm correct. You just need more experience, and from that will come insight. Run more tests on more algorithms; study the intel / AMD architecture manuals. Try to construct your own compiler, which I think will really make you realize why a program cannot beat a human. Shame only that you have to deal with such a shitty family of processors, but even that insight will be extremely valuable.

tom_mellior 7y ago

> a human would know, for instance, that (s)he wants to multiply 50 times A human would turn the for loop that counts up into a do-while loop that counts down? That's doable on the C level, and in that case GCC also generates less ceremony: dot_product_2: .LFB1: .cfi_startproc pxor %xmm0, %xmm0 movslq %edx, %rdx .p2align 4,,10 .p2align 3 .L8: movss (%rdi,%rdx,4), %xmm1 mulss (%rsi,%rdx,4), %xmm1 subq $1, %rdx leal 1(%rdx), %eax testl %eax, %eax addss %xmm1, %xmm0 jg .L8 rep ret But of course if you do this you have changed the implied original spec, and you have reassociated a floating-point computation, computing different results. At that point you might as well pass -ffast-math to GCC, and it will beat your code by 8x due to vectorization. > But I'll leave it in there because this handily beats the compiler in both size and speed Not on my machine. On arrays of 1048576 (2 ^ 20) elements I didn't measure any difference between my first variant, the do-while variant and yours. On arrays of 1024 elements I still didn't measure a difference between the two compiled versions, but yours is about 1-2% slower. On 128 elements do-while looks a bit slower than for, and your variant is more than 20% slower. Here are some numbers for n = 128, calling each function 10000000 times. dot_product is the original, dot_product_2 uses do-while, dot_product_3 is your code (with an extra move of edx to rax at the start of the function, of course). dot_product: 1.036514 sec dot_product_2: 1.097186 sec dot_product_3: 1.290411 sec (Edit: This seems to be due to your use of subss instead of pxor to zero xmm0 at the beginning. Removing that gets your code back up to only 1-2% slower than the for loop version.) > even with the compiler often trying to cheat with nopw instructions to warm up the data cache What? > Now compare that with the garbage GCC generated. At -O3 no less! What a bunch of garbage! You still haven't pointed out what exactly you think is garbage. Which line? Which instruction? Or don't you like that it generates some metadata? > you forced me to write code for a processor architecture I do not even know I didn't force you to do anything, I specifically asked you to provide an example of your choice. You could have chosen a piece of code where you knew in advance GCC would do badly. You could have chosen an architecture that you know well and/or one where you know that GCC's backend hasn't had as much work as x86-64. You chose not to do this. I didn't force you to do anything. > And you doubted me Based on the data it looks like I was right to doubt you.

Annatar 7y ago
"A human would turn the for loop that counts up into a do-while loop that counts down?" Of course an experienced coder would do that; that's the entire point of why a compiler will never be able to generate as short and as fast of code as a human would. An experienced coder can see opportunities that a program with a hard-coded logic such as a compiler is incapable of seeing; if it were, we would have true artificial intelligence, with the neural network of a human brain or denser. "That's doable on the C level," For some bizarre reason unbeknown to me, you just cannot seem to get your head around writing a program in assembler from start to finish. An experienced assembler coder looking for performance would not use a high level language like C because it would be a waste of her or his time, since they already know from experience that they can easily beat hard-coded program logic of a compiler (and if they did, they would chose Fortran over C). Programming in a high-level language only makes sense when the trade-off of losing performance is acceptable in the name of portability. Even then, there are situations where a portable program in a high level language has hand-written, per-processor assembler code (OpenSSL comes to mind). Why do you think that is? "What?" Some versions of GCC for intel 80x86 family of processors will generate one or more nopw instructions, the idea being to give the processor time to prime the data cache. It's a cheap gimmick of desperate compiler constructors, more of a gamble really, because cache games heavily depend on a very particular processor model in a processor family. "At that point you might as well pass -ffast-math to GCC, and it will beat your code by 8x due to vectorization." I could have vectorized this myself (that was actually the first thought I had) but chose not to because I didn't want to spend the time researching how to do that on the intel 80x86 family of processors; I could have also unrolled the loop about four to eight times for even more of a performance gain, but chose not to do so because I believe I made my point. Now you are just being purposely obtuse, because it seems that you just don't want to accept that high level compilers still aren't as fast as a human coder is: you chose a dot product because you likely knew that the compiler would generate pretty fast code, but that one isolated example doesn't really prove anything. If you do more comparisons over decades like I have, you will see how silly it was trying to argue that compilers generate faster code than coders. Also, -ffast-math can generate code which will run the fastest only on that particular processor (and might generate instructions which will not run on other processors of the same family), but the far worse danger is that -ffast-math won't generate IEEE-754 compliant results. When one needs very high precision floating point arithmetic, -ffast-math cannot guarantee correct results. For these two reasons, -ffast-math is useless in real life applications. And indeed, wouldn't you know it: -ffast-math Sets the options -fno-math-errno, -funsafe-math-optimizations, -ffinite-math-only, -fno-rounding-math, -fno-signaling-nans and -fcx-limited-range. This option causes the preprocessor macro "__FAST_MATH__" to be defined. This option is not turned on by any -O option besides -Ofast since it can result in incorrect output for pro- grams that depend on an exact implementation of IEEE or ISO rules/specifications for math functions. It may, however, yield faster code for programs that do not require the guarantees of these specifications. "(Edit: This seems to be due to your use of subss instead of pxor to zero xmm0 at the beginning. Removing that gets your code back up to only 1-2% slower than the for loop version.)" There are two ways to do it fast: eor (or what the idiotic intel architecture calls "xor"), or the sub instruction. On the Motorola MC680x0 family, both run at the same speed. Up until that time, I have never in my entire life written a single line of assembler code for the intel 80x86 family of processors. What you saw is the first assembler code I ever wrote for that platform; I even had to look up which registers to use for floating point and how to do floating point arithmetic on that family of processors, and my hard target was less than 15 minutes of total time wasted on a someone is wrong on the InterNet (https://www.xkcd.com/386/ https://www.xkcd.com/386/) discussion. If I could do that in under 15 minutes for a processor family I literally know nothing about, imagine what a real coder experienced in writing 64-bit assembler code for the intel 80x86 family of processors can do. "You still haven't pointed out what exactly you think is garbage. Which line? Which instruction? Or don't you like that it generates some metadata?" I haven't because I was on a mobile telephone and it was just too much of a bother to quote and reply what I wanted to address. I had to log into a workstation to reply to this and I resent that too. I don't like all of the above, the code and the metadata the compiler generated, because it's machine generated nonsense which jumps back and forth and it is hard to read and comprehend. Assembler code written by a human isn't. Now, since I already resent what I'm doing, I might as well go all the way. Let's pick apart the compiler generated examples in reverse order. movslq %edx, %rdx movslq isn't even necessary, but the compiler, having hard-coded logic and being just a program generated it anyway. Waste of CPU cycles. .p2align 4,,10 .p2align 3 more assembler directives because a compiler cannot figure out whether such packing is necessary or not. My code didn't need them because I know that I don't. leal 1(%rdx), %eax testl %eax, %eax again, nonsense: two instructions wasted with what could amount to a single subq. This isn't more efficient. rep ret Why, when a ret will do? Obviously in my code it worked, but the compiler felt that it had to generate this nonsense, which on top of being nonsense is harder to read and understand, and isn't any faster. Next example: testl %edx, %edx jle .L4 leal -1(%rdx), %eax testl is a total waste of processor cycles here. Which purpose does it serve? Then more cycles are wasted on jumping to an instruction to clear %xmm0, presumably to be able to utilize the instruction pipeline, but all the jump does is waste cycles. xorl %eax, %eax why xorl %eax in a loop when it could be done once? More waste of processor cycles. That code is extremely inefficient, and hopes to trade off readability for banking on a specific feature of intel 80x86, hoping that the instruction cache and pipelining will offset the losses. Idiotic in the extreme considering a human could get the same performance with far less and simpler code! "Based on the data it looks like I was right to doubt you." It might look that way to you now, but if you choose to acquire more experience in coding in assembler, you will eventually realize that I'm correct. You just need more experience, and from that will come insight. Run more tests on more algorithms; study the intel / AMD architecture manuals. Try to construct your own compiler, which I think will really make you realize why a program cannot beat a human. Shame only that you have to deal with such a shitty family of processors, but even that insight will be extremely valuable.