Slashdot Mirror
Goto Leads to Faster Code
pdoubleya writes "There's an article over at the NY Times (registration required) about Kazushige Goto, the author of the Goto Basic Linear Algebra Subroutines (BLAS, see the wiki); his BLAS implementation is used by 4 of the current 11 fastest computers in the world. Goto is known for painstaking effort in hand-optimizing his routines; in one case, "when computer scientists at the University at Buffalo added Goto BLAS to their Pentium-based supercomputer, the calculating power of the system jumped from 1.5 trillion to 2 trillion mathematical operations per second out of a theoretical limit of 3 trillion." To quote Jack Dongarra, from the University of Tennessee, "I tell them that if they want the fastest they should still turn to Mr. Goto."" Ever get the feeling someone wrote an article merely for the pun?
DEC had an ultra-optimized math library (calculations on arrays, Fourier transforms, etc.), improved over decades by generations of PhDs. There were different versions of the routines for the different generations of CPUs, for the different cache sizes of a same model, maybe even for various speeds of RAM. Needless to say, the simple fact of linking against that library instead of the standard one improved the speed of math intensive code by a good 10 to 20 percent (those numbers out of my fuzzy memory, but that far from insignificant).
Add to that compilers that were producing top-notch machine language for the target architecture (producing images that ran twice as fast as what gcc gave you at best), CPUs that were spanking the rest of the world as far as floating-point performance was concerned, and you can understand why the scientific community has kept using Alphas for so long.
No, it is about structured programming. At least indirectly through use of the pun. It's more on topic than a lot of the discussion on this site.
A lot of people complain about people never reading the actual articles before they comment, but it seems worse than that. People don't even bother reading the blurbs.
I wonder where the slashdot effect comes from then?
Which only goes to show that you haven't considered the implications of optimization in modern processors. A Pentium 4 can operate above 3 GHz. This means that light can travel no more than 10 centimeters in the duration of one clock pulse. With the spacing in the motherboard, this isn't enough for a pulse to go from the CPU to the RAM and come back. Even if the memory could operate at the same rate as the CPU, the computation would still be limited by light speed alone.
Optimization to get the full advantage of a Pentium 4 doing floating point calculations is one of the most difficult tasks one can do in computing. A P4 can do, in one clock pulse, four multiplications and four additions. To get 100% of this speed one needs to have a sophisticated handling of cache memory, among other requirements.
Not to mention that code using GOTOs instead of more elegant control structures does, in fact, run faster since the machine doesn't have to worry about maintaining a call stack, etc.
Propably because, being scientists first and programmers second, they simply don't have the time neccessary to learn the characteristics of the processor to the degree neccessary to even match, let alone overcome, the output generated by the compiler. It could also be that the algorithms are under active development, in which case writing them in assembler doesn't really make sense, since it will increase the time needed to write and test new versions. And if the scientists find that some function is unacceptably slow, and can't figure out a more efficient algorithm, they can always just hire a code monkey to hand-tune it with assembler.
Speaking of compiler optimizations, if simply replacing control structures with goto made the function 30% faster, then either the compiler truly sucks, or the previous implementation was something horrible.
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
As few lines as possible?
I'm surprised the teacher didn't get obfuscated codes, could'a been a fun way to practice for the IOCCC!
While it might not be smart, whenever I get assignments like this from my teachers, I always will write exactly to the letter. No one SAID I had to have line breaks at the end of a "line". So it'll be an 80 char row, no extra spacing. I won't go so far as to obfuscate it horribly, just take out the spacing.
I have have teachers give that assignment, and I've given them right back something in as few lines as possible. Most just kind of glare at me and grade it anyways, but one professor just laughed, realized his mistake, and gave me credit for the shortest answer, much to the chagrin of the other students in the class.
Want to find other gamers to play board and role playing game
Of course, these "tweaks" are related the global numerical scheme. Reordering a loop here and there then running to see if it made a difference is simply not practical as you point out.
Sam
Seriously. Computed goto is very useful for low-level
optimizations in things like high-throughput ethernet
drivers and such. It basically eliminates conditional
checks in cases where the condition stays the same
for a particular set of data. So instead ofone would haveIf the second part is executed in a loop, the savings of
not making an IF comparison accumulate fairly quickly.
3.243F6A8885A308D313
You wish. Truth is that real programmers use languages where GOTO is part of each instruction
"The way we can tell it's C# instead of Haskell is because it's nine lines instead of two." -- wadler
I like everyone else was trained *never* to use the dreaded goto statement. I'll grant that Pascal was more readable than Basic (with unlabeled gotos).
But, sometimes, it is actually better to use a goto to make the code more readable. The Linux Kernel, for example, uses gotos. I was pretty sceptical at first because it had been drilled into my head how unreadable code was with gotos in it. But, reading the code, I have to admitt is is much more readable for exception handeling, for example.
If the goto would not make your code more readable then don't use it. But, in the cases where it would avoid a bunch of sillyness trying to get out of a bunch of nested loops in case some error happened, then it makes a lot of sense.
Linus Torvalds (and others) explain the reasoning for this at:
http://kerneltrap.org/node/553
In short, there are both readability and efficiency reasons to use gotos.
Randy.Flood@RHCE2B.COM
Don't forget the kitsch painter Odd Nerdrum! Odd nerd, yes indeed.