This presents a problem for telephone pollsters who are prohibited by the FCC from calling cell phones with automated equipment, and from calling people for whom receiving the call costs money.
I'd like to sign up immediately for a land phone plan whereby I pay 1 cent per call I receive.
Avoiding the combinatorial explosion is just an implementation issue, which I don't see as important.
I'm not sure you're getting my meaning. When you're dealing with an optimizing compiler, you can drown in "implementation issues". Optimizing compilers are already some of the most complex programs in existence.
Let me illustrate. Suppose a language has all the conditional constructs I mentioned: if-then, if-then-else, do-unless, try-catch. Further, suppose it has a few loop constructs: while-do, do-while, for-do.
Now you study your program and find this loop is hot:
if(limit < array.size) then { for(a=0; a < limit; a++) do { array[a] = 0; } }
(Sorry about the indentation.)
You discover that the loop is wasting time testing a against the array bounds, when you can tell by inspection that this is not necessary. So you construct an optimization that looks for array accesses by induction variables inside for-loops, then check if the loop is contained in an if-then statement which puts a limit on that induction variable, and finally make sure the limit itself is within the array bounds. You spend three days coding and testing this optimization to make sure you haven't forgotten any corner cases. During your testing, you discover that you forgot to make sure the vatiable array doesn't change between the if-then test and the inner loop.
Now, it occurs to you that you could generalize this so it works for any loop inside any conditional. That means 12 different combinations. You can check the loop and the conditional separately, so that's really just 3+4=7 tests you need. Still, that's 5 more tests than you needed before you generalized it.
Then you realize you could catch another case if you tweak your optimization more:
while(limit < array.size) do { for(a=0; a < limit; a++) do { array[a] = 0; } }
This is not a loop inside a conditional, but a loop inside another loop. Ok, so you add this to your tests, bringing the total number of tests to around 10. Oops, you just realized that this doesn't work if the outer loop is a do-while loop. Make that 9 tests.
Now you have done all this thinking and all this work. I have two questions for you:
Is this optimization as good as it could be? Could further tweaking improve it substantially?
Is the optimization correct?
You should find these two questions hard to answer, and that should be very worrisome. This kind of "implementation detail" is enough in practice to turn a poorly-designed optimization engine into a useless pile of crap.
Now consider an alternate solution: model the program at a lower level, as a control-flow graph containing quadruples, and annotated with use-def and def-use chains (which can be derived from the CFG and quads, so that's not really cheating). No space to describe these further here; see Google or a text on optimizing compilers.
The optimization becomes a matter of (1) running a dataflow pass that finds all conditional nodes in the CFG and propagates constraints to the blocks inside the graph, and (2) checking the constraints at each array access to see whether the bounds check is necessary.
This has become a fairly routine dataflow analysis. It can find all the unnecessary bounds checks of the first approach, and many more (eg. those that are not within loops), yet it is much simpler to write, to test, and to reason about.
Again, I'm not an optimizer expert (I work on a compiler back-end), but I hope this gives you a feel for why higher-level is not necessarily better when it comes to intermediate languages. It's important not only to have all the necessary high-level information, but also to abstract away irrelevant differences so that the compiler can easily find opportunities for optimization.
And also consider that a lot of very smart people have spent a lot of time on the optimization problem. If you think you can do better, you should make sure you understand the current state of the art first.
Otherwise, it needs to deal with an explosion of different language feature combinations to do a good job.
...I don't think it was false at all, you answer how it would work in your 'Otherwise,' clause.
Writing code to deal directly with a combinatorial explosion of possible situations is never a practical approach.
JIT certainly has a lot to still to offer, but there are still many applications that could benefit greatly from improved static optimistaion, in my opinion.
I only included the info about dynamic compilation for your interest's sake. Sorry to go off on a tangent like that. My real point was that low-level languages are suitable (and in some ways more suitable) for optimization than high-level languages.
Anyway, I am also open to revolution as opposed to evolution, but I don't know what the revolution is that you have in mind. If you can give me an example of some program for which your revolutionary language + optimizer would do a better job than current state-of-the-art static compilation techniques, I would find that most interesting.
Beware, though, that there is a fine line between adding expressiveness to a language versus placing the burden of optimization on the programmer. An example of the former is strong typing, which goes a long way to helping the compiler with alias analysis. An example of the latter is #pragmas that tell the compiler how to do its job.
If you are interested, there is a language called ZPL that tries to help the programmer and optimizer work together more effectively. I think this is quite a good example of a language that does not simply put optimization burden on the programmer, but instead simultaneously eases the job of both programmer and optimizer.
I think we both agree that compilers should, at least in theory, be better at optimising code given more hints, and this is something a good high level language should be implicitly supplying as a part of the constructs and features of language...
Ok, I'll agree with that.
...(some C compilers currently use #pragmas for compiler hints such as avg loop counts and branch probablilities).
That solution is, I think, less than ideal. Most times, programmers don't know these things, and even if they do, they are liable to become inaccurate as a program changes or as it is used in new circumstances.
When I said the high-level language would supply branch frequency information, I was talking about things like Java's exceptions. Java compilers tend to assume that exceptions are rare, and so the optimize for the non-exception case. For instance, they assume null pointer exceptions are rare, so they remove most null pointer checks and replace them with a SIGSEGV handler. This makes the non-exceptional path much faster, but the exceptional path becomes substantially slower. In most programs, this is a big win.
One could also imagine a language that provides different conditional statements indicating different branch probabilities. For instance, "if x then y" could indicate that the probability of x is roughly 1/2, while "do y unless x" could indicate that x is more likely to be false than true.
Dynamic compilers (like JIT compilers) can do even better. Even ignoring that they may have branch frequency profiling machanisms, they can use other heuristics that help substantially. For instance, imagine a Java method has been interpreted some number of times (say 1000), and then it is passed to the JIT for compilation. If the compiler finds a reference to an unresolved class, then it can conclude that the code containing that reference never got executed by the interpreter, so it is very likely to be a cold path. It can assume that the other logic in the method is more important, and can focus its optimization efforts there.
Having the programmer annotate programs with branch frequency info seems to me like a desperate last resort.
Anyway, the point is your original statement regarding the optimizer's ability to deal with low-level languages was simply false. High-level languages have the disadvantage that the optimizer must be familiar with each construct of the language and deal with it differently. If the high-level language gets "lowered" a into uniform constructs (eg. if-then, do-unless, exception throws, and loops all become control-flow graphs with branch frequency annotations) then the optimizer can deal with them all uniformly. Otherwise, it needs to deal with an explosion of different language feature combinations to do a good job.
Thankyou. I've looked at it a bit, and as far as I can tell it is hardware/software assist for converting code between instruction formats.
Woah. You need to read past the abstract. Dynamo is quite a remarkable system that interprets already-optimized binaries on the same system for which they were compiled. It recompiles the "hot" parts (again for the same platform), and paradoxically achieves a substantial speedup in spite of the overhead of interpretation and compilation. It's a very significant piece of evidence that perhaps one day dynamic compilers will beat static ones.
The reason it's relevant is that the input language that Dynamo works on is machine code. It doesn't get much lower-level than that, and yet Dynamo's optimizer is able to do substantial optimizations even at that level. Your assertion that higher-level languages are better for optimizers is dubious, and Dynamo is one piece of evidence to the contrary.
Lower level languages suffer from the problem that the programmer is explictly describing how to do something, and not what it is trying to do; thus the compiler can just unroll loops and perform peephole optimisations.
That's not true. You make it sound like the standard dataflow optimizations don't exist. Optimizers "reverse-engineer" code to figure out what it does, then transform it into better code that does the same thing. Higher-level languages sometimes help (perhaps they provide better branch probabilities, aliasing info, escape info, etc.), but even with low-level code like quadruples, optimizers can still do a hell of a lot more than loop unrolling and peepholing.
I don't understand your question, but if you're asking why we need intermediate languages, then I can answer that.
Imagine N high-level languages and M target platforms. A naive approach would wind up creating NxM separate compilers.
Intermediate languages (ILs) allow you to write N "front-ends" that compile the N high-level languages to the IL, and M "back-ends" that compile from the IL to the M target platforms. So rather than needing NxM compilers, you only need N+M.
Even more significant is the optimizer. Front-ends and back-ends are relatively straightforward, but optimizers are very hard to write well. In the naive approach, you need NxM optimizers. With an IL, you only need one. The front-end translates to IL; the optimizer transforms IL to better IL, and the back-end translates to native code.
In summary, to answer one of your questions:
What's wrong with making a good compiler that writes directly to machine code?
Every optimizing compiler uses an IL anyway. These companies, I presume, are simply agreeing to use the same IL across their products (though I'm only guessing because the article is slashdotted).
While Ars definately isn't targeted at the same audience as, say, KernelTrap, its nice to see there are a few technology websites/publications that aren't dumbed down.
How about hash table insertion? The time it takes to do an insertion depends on whether there is a collision, but it is still bound by a constant that does not depend on the size of the input.
Actually, Mars is a LOT bigger than the moon. It's roughly midway between the moon and Earth. Mars is 9 times the mass of the moon, and Earth is 9 times the mass of Mars. Mars is twice the diameter of the moon, and Earth is twice the diameter of Mars.
So if Mars is only slightly larger than the moon, then I suppose I'm only slightly larger than a 20-pound, 3-foot toddler.
Oh good God almighty. If you can make something as simple as a date so complex and broken (floating point???), then please never write any software that I'm going to try to use.
To clarify: leap seconds are a problem in the future, not the past. For the past ones, you need a database of when they occurred, which is a hassle, but it's possible. For future ones, you're hosed, because nobody can predict when they will be needed. (They depend on tiny perturbations of the earth's rotation.)
Be smart, and play it safe. Use a 5, or better yet, 10 digit year. What's a few bytes?
I know you're joking, but the way to play it smart is not to push the fall-down-dead date further into the future. The way to play it smart is with a proper Date abstraction. Then, 8000 years from now, all someone needs to do is recompile your code with a larger Date type and it will keep on running.
The central problem of Y2K is that a year is not a 2-digit number, nor a 4-digit number, nor any other number. It is a year. If you happen to store it as a 4-digit number, that's fine, but don't spread that assumption all over your code.
My dear sir, I'm afraid your post makes no sense at all. To wit:
However, if your source-drain gates are not sufficiently increased, the remaining charge carriers remain back and over a period of time this in itself builds up a capacitance.
I have a degree in electrical engineering and I have never heard of a "source-drain gate" nor how it might be "sufficiently increased".
There is no way someone could claim a x86 CPU to be as optimized as a current PPC one.
I do. SPECcpu2000 results: Pentium = 1620, Opteron = 1477, POWER4+ = 1113. Granted, the POWER4+ result was from May, but even at that time, PPC trailed Pentium and Opteron.
But seriously, I'd rather believe you're an over-exuberant Mac fanboy than a troll, so let me explain to you that nothing is cut-an-dried when it comes to statements like which processor is "more optimized".
What I love about Apple (in this case it's IBM but they're doing it for Apple) is they how look for alternative ways to improve performance appart from the obvious CPU clock speed increase.
You're making a mountain out of a mole hill. This is a little like congratulating Ford for working on their fuel injection and valve timings instead of the "obvious" horsepower increase. Well, how do you think they get the horsepower increase?
The two things you quote are very mundane and ordinary ways to get more performance from a CPU. Barring redesign, miniaturization and voltage drops are the ways to make hardware faster, and compiler optimizations are the way to make software faster. These are the bread and butter of performance improvement, and you give Apple/IBM entirely too much credit for doing these things. (And this is coming from someone who works on an IBM compiler.)
Having said that, the PPC compiler team's work has been amazing, and congratulations are due for the sheer magnitude of the performance boost. In a field where a 2% improvement is an achievement, 50% is incredible.
Fewer bugs per line of code means either fewer bugs or more lines of code. So if you blather on using long-winded, repetitive, cut-and-pasted code, you'll score highly on this scale.
Slashdot Mirror
I don't understand what that has to do pollsters.
Let me illustrate. Suppose a language has all the conditional constructs I mentioned: if-then, if-then-else, do-unless, try-catch. Further, suppose it has a few loop constructs: while-do, do-while, for-do.
Now you study your program and find this loop is hot:
(Sorry about the indentation.)
You discover that the loop is wasting time testing a against the array bounds, when you can tell by inspection that this is not necessary. So you construct an optimization that looks for array accesses by induction variables inside for-loops, then check if the loop is contained in an if-then statement which puts a limit on that induction variable, and finally make sure the limit itself is within the array bounds. You spend three days coding and testing this optimization to make sure you haven't forgotten any corner cases. During your testing, you discover that you forgot to make sure the vatiable array doesn't change between the if-then test and the inner loop.
Now, it occurs to you that you could generalize this so it works for any loop inside any conditional. That means 12 different combinations. You can check the loop and the conditional separately, so that's really just 3+4=7 tests you need. Still, that's 5 more tests than you needed before you generalized it.
Then you realize you could catch another case if you tweak your optimization more:
This is not a loop inside a conditional, but a loop inside another loop. Ok, so you add this to your tests, bringing the total number of tests to around 10. Oops, you just realized that this doesn't work if the outer loop is a do-while loop. Make that 9 tests.
Now you have done all this thinking and all this work. I have two questions for you:
-
Is this optimization as good as it could be? Could further tweaking improve it substantially?
-
Is the optimization correct?
You should find these two questions hard to answer, and that should be very worrisome. This kind of "implementation detail" is enough in practice to turn a poorly-designed optimization engine into a useless pile of crap.Now consider an alternate solution: model the program at a lower level, as a control-flow graph containing quadruples, and annotated with use-def and def-use chains (which can be derived from the CFG and quads, so that's not really cheating). No space to describe these further here; see Google or a text on optimizing compilers.
The optimization becomes a matter of (1) running a dataflow pass that finds all conditional nodes in the CFG and propagates constraints to the blocks inside the graph, and (2) checking the constraints at each array access to see whether the bounds check is necessary.
This has become a fairly routine dataflow analysis. It can find all the unnecessary bounds checks of the first approach, and many more (eg. those that are not within loops), yet it is much simpler to write, to test, and to reason about.
Again, I'm not an optimizer expert (I work on a compiler back-end), but I hope this gives you a feel for why higher-level is not necessarily better when it comes to intermediate languages. It's important not only to have all the necessary high-level information, but also to abstract away irrelevant differences so that the compiler can easily find opportunities for optimization.
And also consider that a lot of very smart people have spent a lot of time on the optimization problem. If you think you can do better, you should make sure you understand the current state of the art first.
Anyway, I am also open to revolution as opposed to evolution, but I don't know what the revolution is that you have in mind. If you can give me an example of some program for which your revolutionary language + optimizer would do a better job than current state-of-the-art static compilation techniques, I would find that most interesting.
Beware, though, that there is a fine line between adding expressiveness to a language versus placing the burden of optimization on the programmer. An example of the former is strong typing, which goes a long way to helping the compiler with alias analysis. An example of the latter is #pragmas that tell the compiler how to do its job.
If you are interested, there is a language called ZPL that tries to help the programmer and optimizer work together more effectively. I think this is quite a good example of a language that does not simply put optimization burden on the programmer, but instead simultaneously eases the job of both programmer and optimizer.
When I said the high-level language would supply branch frequency information, I was talking about things like Java's exceptions. Java compilers tend to assume that exceptions are rare, and so the optimize for the non-exception case. For instance, they assume null pointer exceptions are rare, so they remove most null pointer checks and replace them with a SIGSEGV handler. This makes the non-exceptional path much faster, but the exceptional path becomes substantially slower. In most programs, this is a big win.
One could also imagine a language that provides different conditional statements indicating different branch probabilities. For instance, "if x then y" could indicate that the probability of x is roughly 1/2, while "do y unless x" could indicate that x is more likely to be false than true.
Dynamic compilers (like JIT compilers) can do even better. Even ignoring that they may have branch frequency profiling machanisms, they can use other heuristics that help substantially. For instance, imagine a Java method has been interpreted some number of times (say 1000), and then it is passed to the JIT for compilation. If the compiler finds a reference to an unresolved class, then it can conclude that the code containing that reference never got executed by the interpreter, so it is very likely to be a cold path. It can assume that the other logic in the method is more important, and can focus its optimization efforts there.
Having the programmer annotate programs with branch frequency info seems to me like a desperate last resort.
Anyway, the point is your original statement regarding the optimizer's ability to deal with low-level languages was simply false. High-level languages have the disadvantage that the optimizer must be familiar with each construct of the language and deal with it differently. If the high-level language gets "lowered" a into uniform constructs (eg. if-then, do-unless, exception throws, and loops all become control-flow graphs with branch frequency annotations) then the optimizer can deal with them all uniformly. Otherwise, it needs to deal with an explosion of different language feature combinations to do a good job.
The reason it's relevant is that the input language that Dynamo works on is machine code. It doesn't get much lower-level than that, and yet Dynamo's optimizer is able to do substantial optimizations even at that level. Your assertion that higher-level languages are better for optimizers is dubious, and Dynamo is one piece of evidence to the contrary.
Imagine N high-level languages and M target platforms. A naive approach would wind up creating NxM separate compilers.
Intermediate languages (ILs) allow you to write N "front-ends" that compile the N high-level languages to the IL, and M "back-ends" that compile from the IL to the M target platforms. So rather than needing NxM compilers, you only need N+M.
Even more significant is the optimizer. Front-ends and back-ends are relatively straightforward, but optimizers are very hard to write well. In the naive approach, you need NxM optimizers. With an IL, you only need one. The front-end translates to IL; the optimizer transforms IL to better IL, and the back-end translates to native code.
In summary, to answer one of your questions:
Every optimizing compiler uses an IL anyway. These companies, I presume, are simply agreeing to use the same IL across their products (though I'm only guessing because the article is slashdotted).How about hash table insertion? The time it takes to do an insertion depends on whether there is a collision, but it is still bound by a constant that does not depend on the size of the input.
So if Mars is only slightly larger than the moon, then I suppose I'm only slightly larger than a 20-pound, 3-foot toddler.
But I see your point.
Bzzt, try again. None of these contains the phrase "source-drain gate".
I think this shows exactly how we should all deal with these scammers. The Tale of the Holy Cow is particularly funny.
Show me one such search result and I'll concede the point. A Google search on "source-drain gate" turns up nothing.
Oh good God almighty. If you can make something as simple as a date so complex and broken (floating point???), then please never write any software that I'm going to try to use.
To clarify: leap seconds are a problem in the future, not the past. For the past ones, you need a database of when they occurred, which is a hassle, but it's possible. For future ones, you're hosed, because nobody can predict when they will be needed. (They depend on tiny perturbations of the earth's rotation.)
The central problem of Y2K is that a year is not a 2-digit number, nor a 4-digit number, nor any other number. It is a year. If you happen to store it as a 4-digit number, that's fine, but don't spread that assumption all over your code.
Thanks for the correction. I need to RTFA a bit more carefully.
But seriously, I'd rather believe you're an over-exuberant Mac fanboy than a troll, so let me explain to you that nothing is cut-an-dried when it comes to statements like which processor is "more optimized".
Nice job karma-whoring a link that appeared in the original post.
The two things you quote are very mundane and ordinary ways to get more performance from a CPU. Barring redesign, miniaturization and voltage drops are the ways to make hardware faster, and compiler optimizations are the way to make software faster. These are the bread and butter of performance improvement, and you give Apple/IBM entirely too much credit for doing these things. (And this is coming from someone who works on an IBM compiler.)
Having said that, the PPC compiler team's work has been amazing, and congratulations are due for the sheer magnitude of the performance boost. In a field where a 2% improvement is an achievement, 50% is incredible.
Fewer bugs per line of code means either fewer bugs or more lines of code. So if you blather on using long-winded, repetitive, cut-and-pasted code, you'll score highly on this scale.
Linus is a cool guy, but let's not start worshiping him just yet.