Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.lang.misc Subject: Re: Aggressive optimization Message-ID: <24232:Nov905:50:0690@kramden.acf.nyu.edu> Date: 9 Nov 90 05:50:06 GMT References: <5351@lanl.gov> Organization: IR Lines: 48 In article <5351@lanl.gov> jlg@lanl.gov (Jim Giles) writes: > From article , by misha@ai.mit.edu (Mike Bolotski): > > In article <7659:Nov620:58:5990@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >> pointers (arrays) are pre-indexed appropriately. Could one of you CS > >> types please illustrate to Jim that finding optimal addition chains in a > >> general computation is equivalent to solving the halting problem? > > [...] > > Optimal addition is NP. Halting problem is undecidable (ever). > > You can argue practicality, but not theory. (Note that I have demonstrated in another article that Mike is wrong.) > Besides, the problem under discussion originally wasn't the optimal > addition chain problem anyway. The original question was whether > there were cases when a pointer _could_ be precomputed but a compiler > _couldn't_ find the same optimization. So, the issue is this: > p = expression + &x; i = expression /* same as pointer version*/ > ...real far away...` ...real far too... > a=*p; a=x[i] That's exactly what I'm talking about! The i's and j's and other integers used to index the arrays are *added* together. The program could have x[i + j - 17] and lots of other weird expressions, all evaluated conditionally through the control structure of the program. But I didn't need even this in my undecidability proof: all I needed was x[0], x[1], and control flow. [ Jim waxes prolific: ] > The only question is "can the compiler promote the add of the base > of array 'x' up to the point where 'i' is precomputed and therefore > get the same efficiency as the precomputed pointer?" Turns out that > this problem is not even NP, it's O(N^2) for languages which permit > arbitrary GOTOs and it's O(N) for "structured" languages I simply don't understand where you and Mike are getting this ridiculous assertions from. What problems are you fantasizing you've solved here? Where are your purported proofs? > Note2: having pointed out that the optimization is possible, I should > say that it's not always desireable. If the array 'x' is statically > allocated, many mainframes and minis have address modes which would > do the add in the memory unit for free. Good point. All the problems, reappear, though, as soon as you have more than one addition. In x[i + 1], do you precompute *x + 1? Or *x + i? Or the whole thing? Or maybe *x + j, because x[j] is referenced a lot more? ---Dan