Why compilers aren't magic
-
Magic doesn't exist by definition, but there are also real reasons why compilers do not rise to meet the naive expectations that are nevertheless often repeated as a kind of software engineering meme. Some people think memes are true and maybe some wishful thinking plays a roll (I get it, it would be great if the compiler was magic), and will just think I'm talking shit when I give the short version, so here's a longer one. There is way too much to cover, so for now I'll just concentrate on one thing, why are compilers not godly at code generation. They are pretty good nowadays, but their mythical status is undeserved. A fairly fundamental problem (for both compilers and novice programmers, but programmers can learn) is that the cost model is wrong, so when it's tiling its internal representation with pieces of machine code, it's not modeling reality accurately enough. As far as I know, every reasonable code generation technique, even [advanced ones](http://llvm.org/pubs/2008-CGO-DagISel.pdf) want the cost to be a scalar. But it isn't a scalar, not in an accurate model of reality anyway, not since the end of what I'll call "simple architectures" (circularly defined as those architectures where the cost of an instruction is the number of cycles it takes and no other considerations exist). What does reality look like? Let's look at the code below. It doesn't really matter what it actually does, I'm just going analyze the cost (for Haswell) to show a bit of what's involved.
.L3:
mov rcx, rdi ; free 0
imul rcx, rax ; p1 3
imul rdx, rsi ; p1 3
add rcx, rdx ; p0156 1
mul rsi ; p1 p6 3/4 (4 for the upper half)
add rdx, rcx ; p0156 1
shrd rax, rdx, 2; p1 3
sar rdx, 2 ; p06 1
add rsi, 1 ; p0156 1
mov rcx, rsi ; free 0
adc rdi, 0 ; 2p0156 2
xor rcx, 10000000; p01256 1
or rcx, rdi ; \ fused,
jnz .L3 ; / p6 1This is a fairly interesting loop because it has a non-trivial loop carried dependency, which I have drawn [here](http://i.imgur.com/SyC6V1b.png) (two iterations shown, arrows are in the direction of the dependency, data flow is from bottom to top "against" the arrows). Just adding the latencies on the critical path (imul3, add3, add4, shrd2) or (mul2, add4, shrd2), either way gives 8, but it actually costs 9 cycles per iteration: imul3 and mul2 cannot be executed in the same cycle (both need p1), one of them has to wait a cycle and either way that
-
Magic doesn't exist by definition, but there are also real reasons why compilers do not rise to meet the naive expectations that are nevertheless often repeated as a kind of software engineering meme. Some people think memes are true and maybe some wishful thinking plays a roll (I get it, it would be great if the compiler was magic), and will just think I'm talking shit when I give the short version, so here's a longer one. There is way too much to cover, so for now I'll just concentrate on one thing, why are compilers not godly at code generation. They are pretty good nowadays, but their mythical status is undeserved. A fairly fundamental problem (for both compilers and novice programmers, but programmers can learn) is that the cost model is wrong, so when it's tiling its internal representation with pieces of machine code, it's not modeling reality accurately enough. As far as I know, every reasonable code generation technique, even [advanced ones](http://llvm.org/pubs/2008-CGO-DagISel.pdf) want the cost to be a scalar. But it isn't a scalar, not in an accurate model of reality anyway, not since the end of what I'll call "simple architectures" (circularly defined as those architectures where the cost of an instruction is the number of cycles it takes and no other considerations exist). What does reality look like? Let's look at the code below. It doesn't really matter what it actually does, I'm just going analyze the cost (for Haswell) to show a bit of what's involved.
.L3:
mov rcx, rdi ; free 0
imul rcx, rax ; p1 3
imul rdx, rsi ; p1 3
add rcx, rdx ; p0156 1
mul rsi ; p1 p6 3/4 (4 for the upper half)
add rdx, rcx ; p0156 1
shrd rax, rdx, 2; p1 3
sar rdx, 2 ; p06 1
add rsi, 1 ; p0156 1
mov rcx, rsi ; free 0
adc rdi, 0 ; 2p0156 2
xor rcx, 10000000; p01256 1
or rcx, rdi ; \ fused,
jnz .L3 ; / p6 1This is a fairly interesting loop because it has a non-trivial loop carried dependency, which I have drawn [here](http://i.imgur.com/SyC6V1b.png) (two iterations shown, arrows are in the direction of the dependency, data flow is from bottom to top "against" the arrows). Just adding the latencies on the critical path (imul3, add3, add4, shrd2) or (mul2, add4, shrd2), either way gives 8, but it actually costs 9 cycles per iteration: imul3 and mul2 cannot be executed in the same cycle (both need p1), one of them has to wait a cycle and either way that
I'd agree - compilers are pretty good, but they still don't come close to an experienced human who knows what he is doing with a specific machine code / assembler. Part of that is that the language being compiled enforces specific structure on the program being written, which may not be an ideal match for the task being coded: an example I had was where I needed to output 128 bit data serially with a clock bit - The compiler generated code was slow as heck because it just didn't know what exactly I was trying to do, and there was no way to tell it. In assembler, it was two machine instructions per bit and an order of magnitude faster (and the clock was symmetric as well, unlike the compiler version).
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
-
Magic doesn't exist by definition, but there are also real reasons why compilers do not rise to meet the naive expectations that are nevertheless often repeated as a kind of software engineering meme. Some people think memes are true and maybe some wishful thinking plays a roll (I get it, it would be great if the compiler was magic), and will just think I'm talking shit when I give the short version, so here's a longer one. There is way too much to cover, so for now I'll just concentrate on one thing, why are compilers not godly at code generation. They are pretty good nowadays, but their mythical status is undeserved. A fairly fundamental problem (for both compilers and novice programmers, but programmers can learn) is that the cost model is wrong, so when it's tiling its internal representation with pieces of machine code, it's not modeling reality accurately enough. As far as I know, every reasonable code generation technique, even [advanced ones](http://llvm.org/pubs/2008-CGO-DagISel.pdf) want the cost to be a scalar. But it isn't a scalar, not in an accurate model of reality anyway, not since the end of what I'll call "simple architectures" (circularly defined as those architectures where the cost of an instruction is the number of cycles it takes and no other considerations exist). What does reality look like? Let's look at the code below. It doesn't really matter what it actually does, I'm just going analyze the cost (for Haswell) to show a bit of what's involved.
.L3:
mov rcx, rdi ; free 0
imul rcx, rax ; p1 3
imul rdx, rsi ; p1 3
add rcx, rdx ; p0156 1
mul rsi ; p1 p6 3/4 (4 for the upper half)
add rdx, rcx ; p0156 1
shrd rax, rdx, 2; p1 3
sar rdx, 2 ; p06 1
add rsi, 1 ; p0156 1
mov rcx, rsi ; free 0
adc rdi, 0 ; 2p0156 2
xor rcx, 10000000; p01256 1
or rcx, rdi ; \ fused,
jnz .L3 ; / p6 1This is a fairly interesting loop because it has a non-trivial loop carried dependency, which I have drawn [here](http://i.imgur.com/SyC6V1b.png) (two iterations shown, arrows are in the direction of the dependency, data flow is from bottom to top "against" the arrows). Just adding the latencies on the critical path (imul3, add3, add4, shrd2) or (mul2, add4, shrd2), either way gives 8, but it actually costs 9 cycles per iteration: imul3 and mul2 cannot be executed in the same cycle (both need p1), one of them has to wait a cycle and either way that
In the beginning there were only ones and zeroes, then came Assembly language. Unfortunately, people did not understand what they saw. An angry mob came forth carrying pitchforks and shouted: "Aye, dark wizards! Keep yer magic tomes of olde to yerself! We dun want yer magic here, lest ye curse us all to heck! Now let us call upon the Witchfinder General, that she may release us from evil!" And thus came forward Grace Hopper, who wrote the first compiler, hiding the runes of the computer which people did not understand. And people could use higher level languages and they did not look back. Yet, compilers have since been known to contain dark magic, but a necessary evil and those who dare open up these Pandora boxes are known as dark wizards.
Best, Sander arrgh.js - Bringing LINQ to JavaScript SQL Server for C# Developers Succinctly Object-Oriented Programming in C# Succinctly
-
In the beginning there were only ones and zeroes, then came Assembly language. Unfortunately, people did not understand what they saw. An angry mob came forth carrying pitchforks and shouted: "Aye, dark wizards! Keep yer magic tomes of olde to yerself! We dun want yer magic here, lest ye curse us all to heck! Now let us call upon the Witchfinder General, that she may release us from evil!" And thus came forward Grace Hopper, who wrote the first compiler, hiding the runes of the computer which people did not understand. And people could use higher level languages and they did not look back. Yet, compilers have since been known to contain dark magic, but a necessary evil and those who dare open up these Pandora boxes are known as dark wizards.
Best, Sander arrgh.js - Bringing LINQ to JavaScript SQL Server for C# Developers Succinctly Object-Oriented Programming in C# Succinctly
And how do unspeakable interpreters from Mordor fit into that picture? Know what? Today I went out on the field again and only saw one black/yellow warning sign license plate. The invasion seems to be over. :-)
The language is JavaScript. that of Mordor, which I will not utter here
This is Javascript. If you put big wheels and a racing stripe on a golf cart, it's still a fucking golf cart.
"I don't know, extraterrestrial?" "You mean like from space?" "No, from Canada." If software development were a circus, we would all be the clowns. -
And how do unspeakable interpreters from Mordor fit into that picture? Know what? Today I went out on the field again and only saw one black/yellow warning sign license plate. The invasion seems to be over. :-)
The language is JavaScript. that of Mordor, which I will not utter here
This is Javascript. If you put big wheels and a racing stripe on a golf cart, it's still a fucking golf cart.
"I don't know, extraterrestrial?" "You mean like from space?" "No, from Canada." If software development were a circus, we would all be the clowns.CDP1802 wrote:
And how do unspeakable interpreters from Mordor fit into that picture?
They don't fit... they just force place for them fighting around
M.D.V. ;) If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about? Help me to understand what I'm saying, and I'll explain it better to you Rating helpful answers is nice, but saying thanks can be even nicer.
-
Magic doesn't exist by definition, but there are also real reasons why compilers do not rise to meet the naive expectations that are nevertheless often repeated as a kind of software engineering meme. Some people think memes are true and maybe some wishful thinking plays a roll (I get it, it would be great if the compiler was magic), and will just think I'm talking shit when I give the short version, so here's a longer one. There is way too much to cover, so for now I'll just concentrate on one thing, why are compilers not godly at code generation. They are pretty good nowadays, but their mythical status is undeserved. A fairly fundamental problem (for both compilers and novice programmers, but programmers can learn) is that the cost model is wrong, so when it's tiling its internal representation with pieces of machine code, it's not modeling reality accurately enough. As far as I know, every reasonable code generation technique, even [advanced ones](http://llvm.org/pubs/2008-CGO-DagISel.pdf) want the cost to be a scalar. But it isn't a scalar, not in an accurate model of reality anyway, not since the end of what I'll call "simple architectures" (circularly defined as those architectures where the cost of an instruction is the number of cycles it takes and no other considerations exist). What does reality look like? Let's look at the code below. It doesn't really matter what it actually does, I'm just going analyze the cost (for Haswell) to show a bit of what's involved.
.L3:
mov rcx, rdi ; free 0
imul rcx, rax ; p1 3
imul rdx, rsi ; p1 3
add rcx, rdx ; p0156 1
mul rsi ; p1 p6 3/4 (4 for the upper half)
add rdx, rcx ; p0156 1
shrd rax, rdx, 2; p1 3
sar rdx, 2 ; p06 1
add rsi, 1 ; p0156 1
mov rcx, rsi ; free 0
adc rdi, 0 ; 2p0156 2
xor rcx, 10000000; p01256 1
or rcx, rdi ; \ fused,
jnz .L3 ; / p6 1This is a fairly interesting loop because it has a non-trivial loop carried dependency, which I have drawn [here](http://i.imgur.com/SyC6V1b.png) (two iterations shown, arrows are in the direction of the dependency, data flow is from bottom to top "against" the arrows). Just adding the latencies on the critical path (imul3, add3, add4, shrd2) or (mul2, add4, shrd2), either way gives 8, but it actually costs 9 cycles per iteration: imul3 and mul2 cannot be executed in the same cycle (both need p1), one of them has to wait a cycle and either way that
Hi Harold, this (for me "dense") post seems like the start of a long, and very interesting article, for CP. I think for those (like me) who once programmed in assembler back-when bytes were scarce, but, are now devotees (addicts?) of way-beyond-registers-and-op-codes high-level sauces, like C#, there is a void/vacuum of sorts ... how the hell do you figure out where in your modern C# code you might benefit from going "unsafe" ? Oh yeah, some scenarios are obviously ripe for lower-level manipulations, like modifying every byte in some image, but, those seem not so frequent (to me). cheers, Bill
«When I consider my brief span of life, swallowed up in an eternity before and after, the little space I fill, and even can see, engulfed in the infinite immensity of spaces of which I am ignorant, and which know me not, I am frightened, and am astonished at being here rather than there; for there is no reason why here rather than there, now rather than then.» Blaise Pascal
-
Magic doesn't exist by definition, but there are also real reasons why compilers do not rise to meet the naive expectations that are nevertheless often repeated as a kind of software engineering meme. Some people think memes are true and maybe some wishful thinking plays a roll (I get it, it would be great if the compiler was magic), and will just think I'm talking shit when I give the short version, so here's a longer one. There is way too much to cover, so for now I'll just concentrate on one thing, why are compilers not godly at code generation. They are pretty good nowadays, but their mythical status is undeserved. A fairly fundamental problem (for both compilers and novice programmers, but programmers can learn) is that the cost model is wrong, so when it's tiling its internal representation with pieces of machine code, it's not modeling reality accurately enough. As far as I know, every reasonable code generation technique, even [advanced ones](http://llvm.org/pubs/2008-CGO-DagISel.pdf) want the cost to be a scalar. But it isn't a scalar, not in an accurate model of reality anyway, not since the end of what I'll call "simple architectures" (circularly defined as those architectures where the cost of an instruction is the number of cycles it takes and no other considerations exist). What does reality look like? Let's look at the code below. It doesn't really matter what it actually does, I'm just going analyze the cost (for Haswell) to show a bit of what's involved.
.L3:
mov rcx, rdi ; free 0
imul rcx, rax ; p1 3
imul rdx, rsi ; p1 3
add rcx, rdx ; p0156 1
mul rsi ; p1 p6 3/4 (4 for the upper half)
add rdx, rcx ; p0156 1
shrd rax, rdx, 2; p1 3
sar rdx, 2 ; p06 1
add rsi, 1 ; p0156 1
mov rcx, rsi ; free 0
adc rdi, 0 ; 2p0156 2
xor rcx, 10000000; p01256 1
or rcx, rdi ; \ fused,
jnz .L3 ; / p6 1This is a fairly interesting loop because it has a non-trivial loop carried dependency, which I have drawn [here](http://i.imgur.com/SyC6V1b.png) (two iterations shown, arrows are in the direction of the dependency, data flow is from bottom to top "against" the arrows). Just adding the latencies on the critical path (imul3, add3, add4, shrd2) or (mul2, add4, shrd2), either way gives 8, but it actually costs 9 cycles per iteration: imul3 and mul2 cannot be executed in the same cycle (both need p1), one of them has to wait a cycle and either way that
This would make a great article for CP, I would agree. I would think that "hinting" the compiler at some level would be helpful, I have used that, and EMIT statements in the past to fix some localized code (force 32 bit instructions to be used inside of a 16 bit program). But keep in mind, if you think finding programmers is hard now. Imagine if we ONLY had assembly to work with? 99.99% of what we do does not require this level of attention or speed, or efficiency. Sure, if it was free it would be nice... And that is the other thing. The Compiler has 3 goals: Compilation Speed, Execution Speed, working on ANY Compatible Computer. (Meaning a multi-threaded faster solution on my machine is the worse choice, because my clients are running much smaller machines). I think this is what makes it hard. I would prefer to see FASTER compiles while working, and DEEPER/OPTIMIZING compiles when pushing a candidate forward for testing/release. But don't double or triple my compile speeds just to make my System Idle Process get more CPU .
-
Magic doesn't exist by definition, but there are also real reasons why compilers do not rise to meet the naive expectations that are nevertheless often repeated as a kind of software engineering meme. Some people think memes are true and maybe some wishful thinking plays a roll (I get it, it would be great if the compiler was magic), and will just think I'm talking shit when I give the short version, so here's a longer one. There is way too much to cover, so for now I'll just concentrate on one thing, why are compilers not godly at code generation. They are pretty good nowadays, but their mythical status is undeserved. A fairly fundamental problem (for both compilers and novice programmers, but programmers can learn) is that the cost model is wrong, so when it's tiling its internal representation with pieces of machine code, it's not modeling reality accurately enough. As far as I know, every reasonable code generation technique, even [advanced ones](http://llvm.org/pubs/2008-CGO-DagISel.pdf) want the cost to be a scalar. But it isn't a scalar, not in an accurate model of reality anyway, not since the end of what I'll call "simple architectures" (circularly defined as those architectures where the cost of an instruction is the number of cycles it takes and no other considerations exist). What does reality look like? Let's look at the code below. It doesn't really matter what it actually does, I'm just going analyze the cost (for Haswell) to show a bit of what's involved.
.L3:
mov rcx, rdi ; free 0
imul rcx, rax ; p1 3
imul rdx, rsi ; p1 3
add rcx, rdx ; p0156 1
mul rsi ; p1 p6 3/4 (4 for the upper half)
add rdx, rcx ; p0156 1
shrd rax, rdx, 2; p1 3
sar rdx, 2 ; p06 1
add rsi, 1 ; p0156 1
mov rcx, rsi ; free 0
adc rdi, 0 ; 2p0156 2
xor rcx, 10000000; p01256 1
or rcx, rdi ; \ fused,
jnz .L3 ; / p6 1This is a fairly interesting loop because it has a non-trivial loop carried dependency, which I have drawn [here](http://i.imgur.com/SyC6V1b.png) (two iterations shown, arrows are in the direction of the dependency, data flow is from bottom to top "against" the arrows). Just adding the latencies on the critical path (imul3, add3, add4, shrd2) or (mul2, add4, shrd2), either way gives 8, but it actually costs 9 cycles per iteration: imul3 and mul2 cannot be executed in the same cycle (both need p1), one of them has to wait a cycle and either way that
Nope nope, nope. I had a manager I lovingly refer to as my Former Bitch Supervisor From Helltm who thought program bugs were like roaches. If there was 1, there were 10, and no program was bug free. However, when we encountered a compiler bug, she refused to believe it. We tried to remind her how she claimed all programs had bugs. Didn't apply, this was a compiler (as in, it wasn't a program). So compilers ARE magic, according to her. Sorry to be the bearer of bad news.
Psychosis at 10 Film at 11 Those who do not remember the past, are doomed to repeat it. Those who do not remember the past, cannot build upon it.
-
In the beginning there were only ones and zeroes, then came Assembly language. Unfortunately, people did not understand what they saw. An angry mob came forth carrying pitchforks and shouted: "Aye, dark wizards! Keep yer magic tomes of olde to yerself! We dun want yer magic here, lest ye curse us all to heck! Now let us call upon the Witchfinder General, that she may release us from evil!" And thus came forward Grace Hopper, who wrote the first compiler, hiding the runes of the computer which people did not understand. And people could use higher level languages and they did not look back. Yet, compilers have since been known to contain dark magic, but a necessary evil and those who dare open up these Pandora boxes are known as dark wizards.
Best, Sander arrgh.js - Bringing LINQ to JavaScript SQL Server for C# Developers Succinctly Object-Oriented Programming in C# Succinctly
LOL :laugh: Joking aside, it is reported that Dr. John von Neumann actually frowned upon at the idea of an assembler!
Quote:
John von Neumann, when he first heard about FORTRAN in 1954, was unimpressed and asked "why would you want more than machine language?" One of von Neumann's students at Princeton recalled that graduate students were being used to hand assemble programs into binary for their early machine. This student took time out to build an assembler, but when von Neumann found out about it he was very angry, saying that it was a waste of a valuable scientific computing instrument to use it to do clerical work.
Source: Computing at Columbia Timeline[^] Gerardo
-
LOL :laugh: Joking aside, it is reported that Dr. John von Neumann actually frowned upon at the idea of an assembler!
Quote:
John von Neumann, when he first heard about FORTRAN in 1954, was unimpressed and asked "why would you want more than machine language?" One of von Neumann's students at Princeton recalled that graduate students were being used to hand assemble programs into binary for their early machine. This student took time out to build an assembler, but when von Neumann found out about it he was very angry, saying that it was a waste of a valuable scientific computing instrument to use it to do clerical work.
Source: Computing at Columbia Timeline[^] Gerardo
Von Neumann sounds like an idiot :) I know he wasn't, but I guess it proves everyone makes mistakes. Maybe he was just jealous that he didn't come up with the idea ;p
Best, Sander arrgh.js - Bringing LINQ to JavaScript SQL Server for C# Developers Succinctly Object-Oriented Programming in C# Succinctly
