So what? First of all, I wasn't talking about Perl. Second, I don't see how that's a performance advantage anyway, since in C there is no built-in dictionary (C++ already has is on STL). So you need to get an external dictionary API. Which can do exactly the same trick as the fantastic runtime he talks about.
OK I should have clarified better (maybe I got confused with the language issue because I was replying to multiple threads at the same time). By the two languages I mean something like C and Java, which the author seems to talk about the most in his article.
It makes no less sense than what the article said. Which may have confused me, that's true:)
I really see no difference between the two cases: 1- On both languages, it's obvious that you can't have dynamic dictionaries appearing by magic. 2- On both languages, you can have someone else dealing with them instead of you. 3- On both languages, they aren't part of the core language but are instead an external API anyway, so it's really not a language/runtime issue, but an API one!
Well, the author of the article linked to in this slashdot article has some examples himself, but I can give some other... Ask someone the possible reasons behind the performance differences between calls to interface methods, virtual methods and regular methods in C#. Or ask why generics in C# can overcome the overhead of virtual method calls. Or (regarding debugging now), ask how a mutex works and why it's needed.
About higher level languages (for example, Python), some of those questions are still valid, but I'm not really an expert on any of them so I'll pass that one for someone else.
People can prove the four color theorem, too, but we never will.
Why? Has it been proved that there is no simple proof? If so please let me know because I'd like to read that. I'm not being sarcastic here, just skeptical.
If your assembly was better than his C, then you must have a forgiving definition of the term "good".
My assembly code was done from his C code, I couldn't have done it easily without having the C code first. And the algorithm came from a scientific paper, having been benchmarked against many other algorithms for doing the same thing. Even if it wasn't optimal (as the other guy proved later), it wasn't sloppy or anything like it.
Did you misunderstand me? I alluded that most speedups come from algorithmic shifts, rather than implementation shifts
It WAS a different algorithm for the same routine, not simply a recoding of the same algorithm. Sorry for not having said it so explicitly the first time. Of course algorithms are more important than implementations, which doesn't mean that the effect of the implementation isn't important as well. Everyone with serious knowledge of software performance knows that.
Check the source. It wasn't written in assembly. The entry you point to: Don't modern compilers take care of instruction scheduling? is highly revealing. The fact that djbfft was written in C demonstrates it's still possible to handle these things from C code. It demonstrates that there are more valuable speedups gained from a better algorithm.
Now you start to seem like you have a too broad view of what algorithmic improvement is. Algorithms have nothing to do with code, they're a level of abstraction above (as you can see in any scientific paper presenting a new algorithm, they rarely give anything more than pseudocode). Instruction scheduling is NOT an algorithmic improvement, it's an platform dependent implementation detail. Their FAQ answer which says compilers aren't good at it just shows that they also think a human is better at optimizing code.
So the author knows how to improve the algorithm.
This is, again a sentence coming from your broad view of what algorithmic improvement is.
You'll note that only one of them suggests writing assembly code, and it's to handle an obsolete case.
I didn't paste the whole TODO file, and even on the part I pasted ALL the references are to assembly code. Look at them please. Even the only one which doesn't mention asm explictly is speaking about registers, which you can't manipulate directly in C. I don't want to sound like an ass but at least show some knowledge regarding what we're talking about...
And to clarify: my point is there a good assembly programmer can often do much better than any compiler, and that things will stay that way for some time to come. Eventually the situation may be the opposite, but right now it surely isn't!
Sure, the practicalities of optimizing code are complicated. But we're talking about facts regarding languages and optimizations, not petty practical details:P
Does it even bother you to think for a minute that you might have chosen a slow algorithm to begin with?
Well, the code in question was a tight mathematical routine belonging to a distributed computing of a quite well known project, which was originally programmed by a mathematician and then adapted by another mathematician who is also a very good programmer. Along with the fact that, along with me, people used to optimize code also looked at it. So no, what you say doesn't bother me very much, since I think that possibility is very unlikely.
In fact, someone (later) came up with slightly faster code for the same routine. Unfortunately for your hypothetical argument, also coded in assembly.
Consider djbfft, which is written in C, and yet outruns many FFT implementations that are written in assembly, some of which were written by experts.
Amusingly, check out this excerpt from the FAQ at the page you pointed to:
Don't modern compilers take care of instruction scheduling? Sure, if you don't care about speed.
And, a look at the TODO file reveals stuff such as:
do properly scheduled Pentium/PMMX asm pass parameters in registers organize asm to fall through function entry when possible organize asm to reduce i-cache pressure
That's exactly the kind of thinking which sometimes leads to bad programs and systems. Black-boxes are very nice but aren't the answer for everything, and on those cases (which are much less rare than most people think), knowing what's behind the abstractions is more than nice; it's often necessary.
Funny, I call it "people who made the compiler". Or in fact, some other people as well. Such as people who made the CPU. Such as people taught by people who made the CPU via optimization manuals. Your compiler has still a long way to go to be an expert.
Yes... And the reply to those arguments is pretty easy - people made compilers. Of course, it might take too much work and knowledge to optimize sometimes which is why compilers exist. But it's another matter entirely to say that people can't optimize as well as compilers. We currently can, both in theory and in practice. In theory we'll always be able to. In practice, I think we'll be still be able to for quite some time:)
That doesn't mean that computer science doesn't, in a big sense, exist to support programmers today. Computer science isn't just an end in itself (although it can be in some ways).
Ultimately, I'd say not knowing what happens behind the abstractions is bad. I know (or can at least easily research and think about) everything what happens behind every line of.NET or Java code that you show me, and that is crucial for understanding debugging and optimization techniques. Can you say the same about most programmers out there?
The computer isn't simply a tool for helping computer scientists, it's much more than that. Nowadays, I'd say that it's much more important to have computer science helping computer-related endeavors, than the opposite.
Sorry, but in the context of a rational argument, appeal to authority is a logical fallacy. I respect Dijkstra a lot but that quote doesn't seem particularly accurate. Telescopes appeared to help astronomers. The case with computers/programming and computer science is the opposite.
Of course, an Idiot might write nonsense code in.NET, but that doesn't mean.NET is a bad thing.
I think his point was not that abstractions are bad, but that not knowing what's happening behind the scenes isn't good. Even to optimize.NET code, sometimes it's good to inspect the generated CIL (or even asm!) code in order to know why something isn't going fast.
Use non-portable (between hardware, and often between compilers) intrinsics (or even inline assembly).
Which usually isn't a big problem anyway since the code sections in which that's an advantage are usually quite small and infrequent, so if you really need the performance you can make a very little sacrifice of inserting conditional compiling statements with different code for the platforms which you are interested on.
It's certainly not an ideal solution but it's a very attractive one, and it has the advantage that you can have experts on each CPU optimizing the code of the platform they know best.
Not if you're willing to throw time away on optimizing it. I'm not saying that it's necessarily good to have an expert assembly programmer doing an entire program (because of time, money constraints and because sometimes performance is already good enough). I'm just saying that the compiler is often WORSE than him at optimizing, nothing more than that.
OK, the article isn't bad but contains a few misleading parts... Some quotes:
one assembly language statement translates directly to one machine instruction
OK, this is nitpicking but there are some exceptions - I remember that TASM would convert automatically long conditional jumps to the opposite conditional jump + an unconditional long jump since there was no long conditional jump instruction.
Other data structures work significantly better in high-level languages. A dictionary or associative array, for example, can be implemented transparently by a tree or a hash table (or some combination of the two) in a high-level language; the runtime can even decide which, based on the amount and type of data fed to it. This kind of dynamic optimization is simply impossible in a low-level language without building higher-level semantics on top and meta-programming--at which point, you would be better off simply selecting a high-level language and letting someone else do the optimization.
This paragraph is complete crap. If you're using a Dictionary API in a so called "low-level language", it's as possible for the API to do the same optimization as it is for the runtime he talks about; and you're still letting "someone else do the optimization".
When you program in a low-level language, you throw away a lot of the semantics before you get to the compilation stage, making it much harder for the compiler to do its job.
That's surely true. But the opposite is also true - when you use an immense amount of too complex semantics, they can be translated into a pile of inefficient code. Sure, this can improve in the future, but right now it's a problem of very high level constructs.
Due to the way C works, it's impossible for the compiler to inline a function defined in another source file. Both source files are compiled to binary object files independently, and these are linked.
Not exactly true I think. Yes, the approach on that page is not standard C, but on section 4 he also talks about some high level performance improvements which are still being experimented on, so...
I'm no assembly guru, but I don't think I would have done as well writing assembly by hand
I don't believe this as much as the people who I see repeating that sentence all the time...
Not many years ago (with gcc), I got an 80% speed improvement just by rewriting a medium sized function to assembly. Granted, it was a function which was in itself, half C code, half inline assembly, which might hinder gcc a bit. But it's also important to note that if the function had been written in pure C code, the compiler wouldn't have generated better code anyway since it wouldn't use MMX opcodes... Last I checked, MMX code is only generated from pure C in modern compilers when it's quite obvious that it can be used, such as in short loops doing simple arithmetic operations.
An expert assembly programmer in a CPU which he knows well can still do much better than a compiler.
Slashdot Mirror
So what? First of all, I wasn't talking about Perl. Second, I don't see how that's a performance advantage anyway, since in C there is no built-in dictionary (C++ already has is on STL). So you need to get an external dictionary API. Which can do exactly the same trick as the fantastic runtime he talks about.
OK I should have clarified better (maybe I got confused with the language issue because I was replying to multiple threads at the same time). By the two languages I mean something like C and Java, which the author seems to talk about the most in his article.
It makes no less sense than what the article said. Which may have confused me, that's true :)
I really see no difference between the two cases:
1- On both languages, it's obvious that you can't have dynamic dictionaries appearing by magic.
2- On both languages, you can have someone else dealing with them instead of you.
3- On both languages, they aren't part of the core language but are instead an external API anyway, so it's really not a language/runtime issue, but an API one!
Of course... But if that was what's being discussed here, the discussion would have been over long ago (maybe before starting hehe).
Well, the author of the article linked to in this slashdot article has some examples himself, but I can give some other... Ask someone the possible reasons behind the performance differences between calls to interface methods, virtual methods and regular methods in C#. Or ask why generics in C# can overcome the overhead of virtual method calls. Or (regarding debugging now), ask how a mutex works and why it's needed.
About higher level languages (for example, Python), some of those questions are still valid, but I'm not really an expert on any of them so I'll pass that one for someone else.
Why? Has it been proved that there is no simple proof? If so please let me know because I'd like to read that. I'm not being sarcastic here, just skeptical.
My assembly code was done from his C code, I couldn't have done it easily without having the C code first. And the algorithm came from a scientific paper, having been benchmarked against many other algorithms for doing the same thing. Even if it wasn't optimal (as the other guy proved later), it wasn't sloppy or anything like it.
It WAS a different algorithm for the same routine, not simply a recoding of the same algorithm. Sorry for not having said it so explicitly the first time. Of course algorithms are more important than implementations, which doesn't mean that the effect of the implementation isn't important as well. Everyone with serious knowledge of software performance knows that.
Now you start to seem like you have a too broad view of what algorithmic improvement is. Algorithms have nothing to do with code, they're a level of abstraction above (as you can see in any scientific paper presenting a new algorithm, they rarely give anything more than pseudocode). Instruction scheduling is NOT an algorithmic improvement, it's an platform dependent implementation detail. Their FAQ answer which says compilers aren't good at it just shows that they also think a human is better at optimizing code.
This is, again a sentence coming from your broad view of what algorithmic improvement is.
I didn't paste the whole TODO file, and even on the part I pasted ALL the references are to assembly code. Look at them please. Even the only one which doesn't mention asm explictly is speaking about registers, which you can't manipulate directly in C. I don't want to sound like an ass but at least show some knowledge regarding what we're talking about...
And to clarify: my point is there a good assembly programmer can often do much better than any compiler, and that things will stay that way for some time to come. Eventually the situation may be the opposite, but right now it surely isn't!
The former instruction allows optimization: Maybe the compiler knows a shorter route or even a closer gas station.
:)
Is it ok if the compiler uses carefully placed nuclear bomb in order to arrive there faster?
Sure, the practicalities of optimizing code are complicated. But we're talking about facts regarding languages and optimizations, not petty practical details :P
Well, the code in question was a tight mathematical routine belonging to a distributed computing of a quite well known project, which was originally programmed by a mathematician and then adapted by another mathematician who is also a very good programmer. Along with the fact that, along with me, people used to optimize code also looked at it. So no, what you say doesn't bother me very much, since I think that possibility is very unlikely.
In fact, someone (later) came up with slightly faster code for the same routine. Unfortunately for your hypothetical argument, also coded in assembly.
Amusingly, check out this excerpt from the FAQ at the page you pointed to:
And, a look at the TODO file reveals stuff such as:
So thanks for helping me prove my point...
Probabilities, probabilities...
That's exactly the kind of thinking which sometimes leads to bad programs and systems. Black-boxes are very nice but aren't the answer for everything, and on those cases (which are much less rare than most people think), knowing what's behind the abstractions is more than nice; it's often necessary.
Funny, I call it "people who made the compiler". Or in fact, some other people as well. Such as people who made the CPU. Such as people taught by people who made the CPU via optimization manuals. Your compiler has still a long way to go to be an expert.
Yes... And the reply to those arguments is pretty easy - people made compilers. Of course, it might take too much work and knowledge to optimize sometimes which is why compilers exist. But it's another matter entirely to say that people can't optimize as well as compilers. We currently can, both in theory and in practice. In theory we'll always be able to. In practice, I think we'll be still be able to for quite some time :)
The meaning of smileys is a bit dubious sometimes, but here are some for you then ;)
:P
Are you suggesting that Dijkstra isn't an authority in CS?
Yes, and I have a proof for it! A dead person isn't an authority in anything else than being dead
That doesn't mean that computer science doesn't, in a big sense, exist to support programmers today. Computer science isn't just an end in itself (although it can be in some ways).
Ultimately, I'd say not knowing what happens behind the abstractions is bad. I know (or can at least easily research and think about) everything what happens behind every line of .NET or Java code that you show me, and that is crucial for understanding debugging and optimization techniques. Can you say the same about most programmers out there?
The computer isn't simply a tool for helping computer scientists, it's much more than that. Nowadays, I'd say that it's much more important to have computer science helping computer-related endeavors, than the opposite.
Sorry, but in the context of a rational argument, appeal to authority is a logical fallacy. I respect Dijkstra a lot but that quote doesn't seem particularly accurate. Telescopes appeared to help astronomers. The case with computers/programming and computer science is the opposite.
I think his point was not that abstractions are bad, but that not knowing what's happening behind the scenes isn't good.
Even to optimize
Which usually isn't a big problem anyway since the code sections in which that's an advantage are usually quite small and infrequent, so if you really need the performance you can make a very little sacrifice of inserting conditional compiling statements with different code for the platforms which you are interested on.
It's certainly not an ideal solution but it's a very attractive one, and it has the advantage that you can have experts on each CPU optimizing the code of the platform they know best.
Do you have any credible proof of that extraordinary claim?
Not if you're willing to throw time away on optimizing it. I'm not saying that it's necessarily good to have an expert assembly programmer doing an entire program (because of time, money constraints and because sometimes performance is already good enough). I'm just saying that the compiler is often WORSE than him at optimizing, nothing more than that.
OK, this is nitpicking but there are some exceptions - I remember that TASM would convert automatically long conditional jumps to the opposite conditional jump + an unconditional long jump since there was no long conditional jump instruction.
This paragraph is complete crap. If you're using a Dictionary API in a so called "low-level language", it's as possible for the API to do the same optimization as it is for the runtime he talks about; and you're still letting "someone else do the optimization".
That's surely true. But the opposite is also true - when you use an immense amount of too complex semantics, they can be translated into a pile of inefficient code. Sure, this can improve in the future, but right now it's a problem of very high level constructs.
Not exactly true I think. Yes, the approach on that page is not standard C, but on section 4 he also talks about some high level performance improvements which are still being experimented on, so...
I don't believe this as much as the people who I see repeating that sentence all the time...
Not many years ago (with gcc), I got an 80% speed improvement just by rewriting a medium sized function to assembly. Granted, it was a function which was in itself, half C code, half inline assembly, which might hinder gcc a bit. But it's also important to note that if the function had been written in pure C code, the compiler wouldn't have generated better code anyway since it wouldn't use MMX opcodes... Last I checked, MMX code is only generated from pure C in modern compilers when it's quite obvious that it can be used, such as in short loops doing simple arithmetic operations.
An expert assembly programmer in a CPU which he knows well can still do much better than a compiler.