Re:Decreasing the Number of Memory Accesses 1/2
by jerf on Friday March 31, 2023 @11:16AM
(#35388364)
Our intuition says that our code is full of opportunities like this and a "sufficiently smart compiler" ought to be able to work wonders with our code.
Our intuitions are wrong. In reality it takes a shockingly small problem to break these optimizations and make them do something in violation of the semantics of the language, and as a result, the compiler can't perform the optimization even if it is smart enough to try. Many, many, many compilers have tried. It is not a new idea, it is one that has been tried and failed over and over again.
This is one of the reasons why the functional programming crew advocate so hard for simpler semantics like pervasively immutable variables. The idea is that if the program's semantics promise less, the optimizations ought to be a lot easier. And at least at the surface level this is arguably true; Haskell does quite significant map (rather than "loop") fusion successfully. However, to date, the "sufficiently smart compiler" has not manifested to the extent that we'd like, the one that turns functional code into 2x - 3x faster code than imperative code. Generally the real-world smart compilers are straining just to keep up with C, as long as you write in a particular subset of the language.
I have quoted the term "sufficiently smart compiler" because if you want to dig further in, it is a good search term.
Many of our intuitions about our code are similarly broken. There was a lot of hope for exploiting "implicit paralellization" in our codebases; surely, our brains thought, there's just a ton of things in every code base that can be automatically turned into parallel code. That turned out to be false. There was a paper that took some representative code bases and extracted out the theoretical maximum parallelization that could even be done by any conceivable compiler optimization by analyzing the data dependencies themselves and it turned out to be shockingly small, thus effectively killing the idea. This story has been repeated a lot; another search term you can play with is "supercompiler", which amounts to "compilers are pretty good at optimizations in the small, surely our code bases are rife with opportunities to optimize at much higher levels across packages or the entire code base?" to which the answer to date has amounted to "No, not really."
In my opinion, the only hope for any of these ideas is someone sitting down and designing a language from the very get-go intended to work with these ideas. However, given the amount of experience necessary to do that and the subtlety of the task, I'm not sure that I'm not specifying a super-human degree of work by saying that.
Our intuitions are wrong. In reality it takes a shockingly small problem to break these optimizations and make them do something in violation of the semantics of the language, and as a result, the compiler can't perform the optimization even if it is smart enough to try. Many, many, many compilers have tried. It is not a new idea, it is one that has been tried and failed over and over again.
This is one of the reasons why the functional programming crew advocate so hard for simpler semantics like pervasively immutable variables. The idea is that if the program's semantics promise less, the optimizations ought to be a lot easier. And at least at the surface level this is arguably true; Haskell does quite significant map (rather than "loop") fusion successfully. However, to date, the "sufficiently smart compiler" has not manifested to the extent that we'd like, the one that turns functional code into 2x - 3x faster code than imperative code. Generally the real-world smart compilers are straining just to keep up with C, as long as you write in a particular subset of the language.
I have quoted the term "sufficiently smart compiler" because if you want to dig further in, it is a good search term.
Many of our intuitions about our code are similarly broken. There was a lot of hope for exploiting "implicit paralellization" in our codebases; surely, our brains thought, there's just a ton of things in every code base that can be automatically turned into parallel code. That turned out to be false. There was a paper that took some representative code bases and extracted out the theoretical maximum parallelization that could even be done by any conceivable compiler optimization by analyzing the data dependencies themselves and it turned out to be shockingly small, thus effectively killing the idea. This story has been repeated a lot; another search term you can play with is "supercompiler", which amounts to "compilers are pretty good at optimizations in the small, surely our code bases are rife with opportunities to optimize at much higher levels across packages or the entire code base?" to which the answer to date has amounted to "No, not really."
In my opinion, the only hope for any of these ideas is someone sitting down and designing a language from the very get-go intended to work with these ideas. However, given the amount of experience necessary to do that and the subtlety of the task, I'm not sure that I'm not specifying a super-human degree of work by saying that.