jrv@mitre-bedford.ARPA (08/27/84)
I'd like to see a statement added to C to let the programmer
declare the fraction of the time he expects an expression to be
nonzero (true). A typical use might be:
root=x/2; next_root=x;
while(root!=next_root \.90)
{root=next_root;
next_root=(root+x/root)/2.;
}
...where the programmer expects the completion test to fail
90% of the time. (By the way, I have no particular love for
this syntax.)
This feature would have the following uses:
(1) The COMPILER, when trying to optimize loops, normally
tries to take expensive operations out of a loop and move them
before or after the loop ("strength reduction"). If the loop
is hardly ever executed, this is a bad idea. The programmer
ought to be able to advise the compiler of this situation.
(2) The PROGRAM TESTER (whether human or software) could
check the correctness of the programmer's guess and warn him
if it were out of line. The particular value 1 (always true)
could signal an invariant for which a proof might be attempted.
(3) A READER of the program, on the first pass, could
follow only the "most of the time" paths, thereby getting an
overview of the program without getting confused by such
things as error handling and garbage collecting.
Does anybody else think this is a good idea?
- Jim Van Zandtgwyn@BRL-VLD.ARPA (08/27/84)
From: Doug Gwyn (VLD/VMB) <gwyn@BRL-VLD.ARPA> C really doesn't need bells and whistles. In the case of the "percentage true", do you contemplate extending this to loop breaks, etc. too? Why not just comment your code if you care about reader understanding: while ( root != next_root /* 90% */ ) ... The amount of speed improvement possible by letting the optimizer know which outcome of a test is more likely is miniscule indeed. The latest PCC will generate extra loop condition tests at both the "top" and the "bottom" of do & while loops when appropriate, which saves a very small amount of loop overhead comparable to worrying about percentage trues.
smh@mit-eddie.UUCP (Steven M. Haflich) (08/28/84)
It has been remarked that program flow-control advice given to a compiler will rarely yield significant speed increase. This is true for much code running on normal architectures. However, pipelined and/or vector processors can profit greatly by knowing which path to lookahead. The programmer needn't bother providing advice except for code fragments of his choosing. A significant drawback is that programmers are probably too lazy to provide advice as often as they should. Some pipelined RISC machines (which *need* such advice) solve this problem marvelously by keeping some sort of branch-frequency record right in the running object code, the microcode updating it on the fly. Now for a bit of arcane ancient history: In the middle (early?) 1960s, IBM 1620 FORTRAN II had a FREQUENCY statement which allowed the programmer to give branch advice. (Let me tell you, with the speed of a 1620, the code generator needed all the advice it could get!) So far as I know, the FREQUENCY statement was ignored by the compiler and was never implemented. But it suggested a principle which still holds: A compiler amplifies a programmer, but cannot be truly efficient unless programmers are willing to tell it enough so it can figure out what needs to be done. Steve Haflich
minow@decvax.UUCP (Martin Minow) (08/30/84)
The FREQUENCY statement was included in FORTRAN I and II. As far as I know, only the IBM 709 compiler implemented it. Other variants, such as Fastran from the U. of Indiana, ignored it and, as was noted, it didn't give enough of an advantage to offset the implementation difficulties. Martin Minow decvax!minow
BLARSON@ecld.#eclnet (08/31/84)
From: Bob Larson <BLARSON@ecld.#eclnet> The Prime 9950 and 9750 are examples of non-RISC pipelined architectures that handle this problem (branch lookahead) by utilizing a special branch cashe with an 80% success rate (according to sales literature). Most programmers could probably not beat this, especially since the branch cashe is updated on the fly. Note that a pipeline architecture can only take the most probable path, so only one bit of the programmers guess would be significant (which path is most probable). The Prime 9950 and 9750, being object code compatible with the rest of the 50 series, have no provision for a programmers guess of the most probable path. Do you have an example of a (commercially produced in quantity) machine that does expect a guess of the most probable path? I feel that this problem is best solved in the machines that need it by additional hardware rather that expecting all programs to be updated to run on it. Bob Larson <Blarson@Usc-Ecl.Arpa> -------