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?

Comments

This certainly is news to me.

[trudyscousin]

I'd always been told that use of Goto led to a case of the BLAS in my code!

Throwing bricks in glasshouses, anyone?

[trezor]

Ever get the feeling someone wrote an article merely for the pun?

Good thing the headline didn't contribute to that at all.

His code is more stable than Mr. Bluescreen's

[virtigex]

Although he also writes fast code, Mr. Bluescreen was criticised for the poor stability of his code.

I failed a coding test because of this guy

[alta]

It was CIS 150, C++ was the language of the day (pascal before, java after.) I was taking an exam that was all coding. I remember extensive use of GOTO from my commodore days, so I used one in a test (the objective was to code something with as few lines as possible)

I had the shortest working code in the class but the arse hole teacher failed me for it. Said something like "we don't teach goto for a reason. Yeah, it's in the book, but don't ever use it!"

Jerk. I should post his phone number on slashdot ;)

Re:I failed a coding test because of this guy

[CastrTroy]

Obviously this prof was wrong. If he wanted you to code it in as few lines as possible, then he should have expected everyone's code to be completely unreadable, goto's or not. If he wanted your code to be understandable, then he should have asked to make the code as clear as possible, by using as many lines as you may need.

Re:I failed a coding test because of this guy

[Mr Z]

Yeah, that is BS! Especially when you have Donald Knuth, Brian Kernighan and Ken Thompson on record in defense of goto when it's warranted. References: Knuth's "Structured Programming with GOTO" (link appears dead), Kernighan, and Ken Thompson: "If you want to go somewhere, goto is the best way to get there."

And then there was the famous "'GOTO Considered Harmful' Considered Harmful" by Frank Rubin, and a a decent section in Steve McConnell's Code Complete that takes an even-handed view.

Anyway, swinging carefully back on topic, it sounds like Mr. Goto's work is at the instruction level, not the C or Fortran or even really at the algorithmic level (except maybe tricks like tiling). I program in the embedded space, where getting as close to 100% efficiency is a continual challenge. I wonder if any of his techniques scale down...

--Joe

Re:I failed a coding test because of this guy

[Comboman]

Sorry but I gotta side with the professor. Don't use goto in C++.

"Not recommended" and "don't ever use it" are two differenet things. If it was never meant to be used, it wouldn't be in the language. The goal of the test mentioned was to write the shortest possible piece of code, not the most maintainable or most elegant.

"The goto can also be important in the rare cases in which optimal efficency is essential." - Stroustrap, The C++ Programming Language

"Code involving a goto can always be written without one, though perhaps at the price of some repeated tests or an extra variable." - Kernighan & Ritchie, The C Programming Language

If you don't know who Stroustrap and K&R are, you have no right commenting on C/C++ issues. I have to side with the original poster, the prof was a dogmatic asshole (and so are you).

This was a test, aimed at slashdot readers...

[Derang()]

...To see who actually reads the article.

Judging from the replies...not many people ;)

Re:This was a test, aimed at slashdot readers...

[TrappedByMyself]

Anyone who read more than a few words into it

The calls for the obligatory "You must be new here".

Re:This was a test, aimed at slashdot readers...

[veg_all]

Anyone who read more than a few words into it would've realized they're talking about a person

Wow. Slashdot article as Turing Test.

That would mean...

[LoyalOpposition]

Goto Considered Helpful?

-Loyal

DEC Math Library

[boa13]

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.

Thank you very much

[Prince Vegeta SSJ4]

10 Print "oh Mr. K. GOTO" 20 I=I+1 30 If I 5 Print "Domo" Else 50 40 GOTO 20 50 Print "I'm Kilroy! Kilroy! Kilroy! Kilroy!"

Re:So my professors were lying?

[/ASCII]

You might want to read up on this page for some human interaction hints.

Re:goto is obsolete

[fdrake76]

Weren't FUNCTIONS invented for the purpose of finally getting rid of goto and labels?

I believe you are referring to Kazushige's cousin, Mr. Gosub.

Re:No you idiots - it's not about GOTO statements

[91degrees]

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.

Re:30%+ Improvement

[Surt]

Considering the number of scientists who have been looking at this over a number of years, I think it really is a credit to Goto's work. Optimizing at this level is very challenging work on modern processors.

Where does the slashdot effect come from?

[tehanu]

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?

Pah!

[BJH]

Anybody who criticizes Goto Kazushige's Free Software credentials - he created a Linux/Alpha distribution called Stataboware, which among other things included an early version of his hand-tuned math library back in 1999 (it's now defunct, unfortunately).

Another punny name

[Riktov]

From the article:
"Robert A. van de Geijin, a computer scientist who works with Mr. Goto at the Texas Center,..."

All right, a Japanese programmer named Goto, working with a non-Japanese guy name Geijin. That's too much.

Re:Another punny name

[aug24]

Thankfully for my sanity, that one is a typo. It's Van de Geijn (the ij is originally a y with an umlaut - Dutch).

Justin.

Re:30%+ Improvement

[roystgnr]

Which is certainly good, but to me says more about the previous implementation than it does about Goto's work.

Yeah, that previous implementation must have totally sucked. I know all my linear algebra software is written around an assembly language core, hand tuned for each new version of a half dozen processors, and designed from the start to minimize TLB misses instead of just naively trying to fit a dataset into L1 or L2 cache. I don't know why those retards at the universities and national labs were ever using anything else!

(closing Slashdot, going back to working on my shamefully unoptimized C++ numerics code...)

Re:30%+ Improvement

[mangu]

to me says more about the previous implementation than it does about Goto's work

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.

Re:No you idiots - it's not about GOTO statements

[limabone]

Oh, Goat-toe hell you spoilsport!

Re:If true...

[SatanicPuppy]

My favorite ever comment was, "If I ever saw this in the real world, I'd fire you" attached to an "A" test paper with a programming question on it I'd managed to reduce to one line of nearly incomprehensible recursion.

Re:If true...

[scheming daemons]

Of course GOTO is logical in real life. I experience this all the time:

If wife has headache, GOTO sleep

If boss is on vacation, GOTO strip bar for long lunch

If in-laws are coming over, GOTO work and pretend there is a critical problem that requires your presence all night

If technical conference is in Vegas, GOTO it

loads of examples.

If work is boring, GOTO slashdot to kill an hour or two

Re:Duh...

[Anonymous Coward]

I was involved with the design and the benchmarking effort of #5, #59, #67 and a few others in Top500. The performance of a supercomputer is determined by the number of real FLOPs acheived versus theoretically claimed.

Theoretical FLOPs per processor = Core(s) * Speed_Per_Core (in Ghz) * 2. So for a Dual 3.6 Ghz Xeon, the theoretrical FLOPS is 2 * 3.6 * 2 = 14.4

An easy way to find out actual number of FLOPS a computer can acheive is to ask it to solve a number of Linear Algebra problems and then look at the time it takes to finish solving these problems. The faster the time, better FLOPs obviously.

Now, the reason we chose gotolib was:

1) It works with GCC
2) It is optimized to use the processor cache
3) And therefore fewer cache misses which translates to superior performance
4) And its free (though the source is not exactly open).

Because it uses the processor cache so effectively, it results in a better number than a regular BLAS (which does not use processor cache).

Alternatively, I've also used Intel's MKL which offers comparable performance but then it works best with ICC and its not free. Btw, #59 was benchmarked using gotolib and MKL -- but if I remember correctly, the final result was derived using MKL.

In essence, if you want to use GCC and work with lots of number crunching ie BLAS, gotolib is your best option.

Well Done Slashdotters

[Linker3000]

We have given birth to a new acronym: RPFH Read Past the F**king Headline.

No-registration-required version at CNET

[tobiasly]

http://news.com.com/Writing+the+fastest+code%2C+by +hand%2C+for+fun/2100-1022_3-5972844.html?tag=nefd .top

Libgoto is fast but not open-source

[poszi]

Maybe I should not complain because the guy did a great job and his library is available free of charge but I hesitate to use this library because it is closed-source. I benchmarked it and found it fast and started to use it in my scientific codes. I once found a strange problem in a parallel code I was developing. The program crashed for one specific system I was calculating. It was something weird because it worked for many other systems I tested before. I spent a lot of time trying to find the bug in my program when finally I replaced libgoto with standard blas and the problem disapeared. I knew that the crash was when entering blas but I thought it is because I messed with the arrays that are used as parameters. If libgoto were open-source, I would be able to have a version with debugging info compiled and debug the program and the library. I would probably not fix the bug but I would likely figure out more quickly the problem is in the library and not in my code. After I had known the problem is in libgoto, I dowloaded a new version of libgoto and it worked so the bug has been fixed. There is no changelog on libgoto web page so I don't know what was the problem and how it affacted my previous caclulations.

Atlas is open-source and is a pretty good alternative. It is only a few percent slower than libgoto in most cases.

Re:Libgoto is fast but not open-source

[ufnoise]

From the article: Some programmers have suggested that Mr. Goto has not joined the open-source movement because he wants to protect his secrets and strategies from competitors. That is not so, he said recently, noting that the Goto BLAS software is freely available for noncommercial use. And he said he was preparing an open-source version.

Now, wait for the next (worst) pun

[DrYak]

Wait until you read in an interview about Mr. Kazushige Goto's favorite food.
Italian.
Pasta.
Specially Spaghetti.

[/me ducks and runs away....]

Computed goto

[apankrat]

Not as helpful as computed goto

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 of

if (context->condition)
      foo(context);
else
      bar(context);

one would have

/* one-time initialization */
if (context->condition)
      context->jmp = &_foo;
else
      context->jmp = &_bar;
 
..
 
goto *context->jmp;
 
for (;;)
{
_foo: foo(context); break;
_bar: bar(context); break;
}

If the second part is executed in a loop, the savings of
not making an IF comparison accumulate fairly quickly.

Re:Computed goto

[ChadN]

Yuck! For this example, it'd be much clearer (to me), to simply initialize a function pointer to either foo or bar, and call that in a loop. I'd imagine it is just as fast. Jumping into loops can be clever, but is seriously non-intuitive, IMO.

for more technical info, see goto's personal site

[Trollll]

for more technical info, see his site at the Texas Advanced Computing Center. pretty pictures and software tool downloads even.

GOTOs sometimes make the code *more* readable

[randyflood]

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.