ckp@grebyn.com (Checkpoint Technologies) (03/02/91)
>Of course, the best optimization for: > for (i = 1; i < 100; i++) > x += i; >is: > x += 4950; OK, so how many more years must it be before a compiler will do this optimization for you? :-) When I did a lot of assembly language, I used to look for constant processing that could be done at assembly time, and do that with macros. (I think it's important to illustrate the algorithm by which you arrive at your constants.) This is ok if you have a powerful enough macro language, but C doesn't. So, as I think of it I was just doing manual "constant folding". The C compiler does some of that. But I'd sure like to see a compiler that could change the following: -------------------------------- int fib_array[1024]; void init_fib(void) { register int i; fib_array[0] = fib_array[2] = 1; for(i = 2; i < 1024; i++) fib_array[i] = fib_array[i-1] + fib_array[i-2]; } int main(int argc, char **argv) { init_fib(); ... -------------------------------- ...into... -------------------------------- int fib_array[1024] = {1, 1, 2, 3, 5, 8, 13, 21, /* you get the idea */ -------------------------------- I know, this is asking a LOT. But hey, I can ask, can't I? -- First comes the logo: C H E C K P O I N T T E C H N O L O G I E S / / \\ / / Then, the disclaimer: All expressed opinions are, indeed, opinions. \ / o Now for the witty part: I'm pink, therefore, I'm spam! \/
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/02/91)
In article <1991Mar2.010049.21044@grebyn.com> ckp@grebyn.com (Checkpoint Technologies) writes: > >Of course, the best optimization for: > > for (i = 1; i < 100; i++) > > x += i; > >is: > > x += 4950; > OK, so how many more years must it be before a compiler will do this > optimization for you? :-) Actually, one of the few optimizations my q2c supports is loop unrolling. If you tell it to, it will even go all the way to 101 separate statements, and there are probably some C compilers that can collapse x += (1 + 5); x += (1 + 6) into x += 13. > int fib_array[1024] = {1, 1, 2, 3, 5, 8, 13, 21, /* you get the idea */ In Q you can use any pure expression as an initializer. (And arrays are first-class objects so a Fibonacci array initialization can be made pure.) Right now I have q2c just stick the initializations at the top of main(), but I'm thinking of changing it to a two-level system where it first compiles the initializer code, then runs it to produce the C initializers. q2c is slowly improving... Expect to see a usable Q language by the end of the summer. ---Dan
dave@cs.arizona.edu (Dave P. Schaumann) (03/02/91)
In article <1991Mar2.010049.21044@grebyn.com> ckp@grebyn.com (Checkpoint Technologies) writes: |[...]I'd sure like to see a compiler that |could change the following: | |int fib_array[1024]; |[code deleted] | |...into... | |int fib_array[1024] = {1, 1, 2, 3, 5, 8, 13, 21, /* you get the idea */ | |I know, this is asking a LOT. But hey, I can ask, can't I? Do you have any idea what the value of fib_array[1024] is??!!!!! You're asking more than just "a LOT" from the compiler... A quick calculation reveals fib_array[1024] is approximately 2.7 E 213. You'd need a seriously capacious int type to hold that... -- Dave Schaumann dave@cs.arizona.edu 'Dog Gang'! Where do they get off calling us the 'Dog Gang'? I'm beginning to think the party's over. I'm beginning to think maybe we don't need a dog. Or maybe we need a *new* dog. Or maybe we need a *cat*! - Amazing Stories
ckp@grebyn.com (Checkpoint Technologies) (03/03/91)
In article <992@caslon.cs.arizona.edu> dave@cs.arizona.edu (Dave P. Schaumann) writes: >In article <1991Mar2.010049.21044@grebyn.com> ckp@grebyn.com (Checkpoint Technologies) writes: >|int fib_array[1024] = {1, 1, 2, 3, 5, 8, 13, 21, /* you get the idea */ > >Do you have any idea what the value of fib_array[1024] is??!!!!! >You're asking more than just "a LOT" from the compiler... > >A quick calculation reveals fib_array[1024] is approximately 2.7 E 213. >You'd need a seriously capacious int type to hold that... oops (red face) You do have a good point there. Make that fib_array[16]. (.. and I won't even mention that fib_array[1024] is one beyond the end...) -- First comes the logo: C H E C K P O I N T T E C H N O L O G I E S / / \\ / / Then, the disclaimer: All expressed opinions are, indeed, opinions. \ / o Now for the witty part: I'm pink, therefore, I'm spam! \/
steve@taumet.com (Stephen Clamage) (03/05/91)
ckp@grebyn.com (Checkpoint Technologies) writes: >int fib_array[1024]; >void init_fib(void) >{ ... dynamic initialization of fib_array ... >} >int main(int argc, char **argv) >{ >init_fib(); >... >...into... >int fib_array[1024] = {1, 1, 2, 3, 5, 8, 13, 21, /* you get the idea */ I certainly would NOT want the compiler to do this, as it changes the meaning of the program. 1. fib_array is a global array which might be set and used elsewhere in the program before init_fib() is called. Replacing the runtime initialization with a static initialization could well result in completely different program behavior. 2. init_fib() is a global function which might be called elsewhere. If the compiler deletes the function, the program will fail to link. You could argue for replacing the loop in init_fib() with a series of constant assignments. ('Loop unrolling' is a standard optimization technique on parallelizing computers with lots of memory.) This would preserve the program's semantics, but might result in a larger program. Depending on instruction caching and look-ahead, the unrolled loop might execute more slowly than the original loop, apart from being larger. -- Steve Clamage, TauMetric Corp, steve@taumet.com
ckp@grebyn.com (Checkpoint Technologies) (03/05/91)
In article <619@taumet.com> steve@taumet.com (Stephen Clamage) writes: >ckp@grebyn.com (Checkpoint Technologies) writes: >>int fib_array[1024]; >> ... dynamic initialization of fib_array ... >>int main(int argc, char **argv) >>{ >>init_fib(); > >>...into... > >>int fib_array[1024] = {1, 1, 2, 3, 5, 8, 13, 21, /* you get the idea */ > >I certainly would NOT want the compiler to do this, as it changes the >meaning of the program. Not to me. Maybe to the compiler; then I would need to have some way to tell the compiler what *I* know about my program. I can certainly see how more information may be needed. >1. fib_array is a global array which might be set and used elsewhere in the >program before init_fib() is called. Replacing the runtime initialization >with a static initialization could well result in completely different >program behavior. I tried to show that init_fib was called directly after the entry point main(). In fact it would be important that the compiler know this, and also the compiler would need to believe that main() is really the very first executable statement reached, and not just another function. >2. init_fib() is a global function which might be called elsewhere. If >the compiler deletes the function, the program will fail to link. I probably should have said 'static void init_fib()' so it *could* be deleted if no other reference were made it it besides the call right after main. But the function itself could be kept, if other calls are made. In any case, it's *my* (hypothetical) program and *I* know that besides that init function, the array contents aren't modified. Somehow the compiler would have to be told this, or glean it from my usage. -- First comes the logo: C H E C K P O I N T T E C H N O L O G I E S / / \\ / / Then, the disclaimer: All expressed opinions are, indeed, opinions. \ / o Now for the witty part: I'm pink, therefore, I'm spam! \/
rjohnson@shell.com (Roy Johnson) (03/12/91)
In article <1991Mar2.010049.21044@grebyn.com> ckp@grebyn.com (Checkpoint Technologies) writes: >>Of course, the best optimization for: >> for (i = 1; i < 100; i++) >> x += i; >>is: >> x += 4950; This doesn't look to be such a bad thing to optimize away (speaking with all the authority of one who doesn't write compilers). You "simply" check each loop to be sure that there are no function calls, and that all variables referenced in the loop are initialized there. Then you can generate appropriate moves instead of a loop. If you want to initialize an array, though, the usual time-space tradeoff is still there: you generate n move instructions to initialize a size n array, rather than probably two moves, an addition/increment, a conditional, and a goto. -- ======= !{sun,psuvax1,bcm,rice,decwrl,cs.utexas.edu}!shell!rjohnson ======= Feel free to correct me, but don't preface your correction with "BZZT!" Roy Johnson, Shell Development Company
bright@nazgul.UUCP (Walter Bright) (03/23/91)
In article <RJOHNSON.91Mar11141459@olorin.shell.com> rjohnson@shell.com (Roy Johnson) writes:
/>Of course, the best optimization for:
/> for (i = 1; i < 100; i++)
/> x += i;
/>is:
/> x += 4950;
/This doesn't look to be such a bad thing to optimize away (speaking
/with all the authority of one who doesn't write compilers).
Actually, it is probably not worth the bother to attempt to optimize away.
In general, a program that needs to be optimized is one that is going to be
run many times. A loop that is determinate (doesn't change from run to run)
generally does not appear in a program that is to be run many times.
There are still lots of unexploited opportunities for optimizations in
code that *does* commonly appear in production programs.jwm712@unhd.unh.edu (Jonathan W Miner) (03/26/91)
I have been following this thread and find it interesting. Are there any good books on optimizing performance at run time? Please E-Mail, I'll post a summary if there is any interest. Thanks. -- Jonathan Miner | I don't speak for UNH, and UNH does not jwm712@unhd.unh.edu | speak for me! (603)868-3416 | Hacking to survive......