Re: Algorithm Optimization

On Tuesday, September 15, 2020 at 7:24:11 PM UTC-7, Derek M. Jones wrote:


> > I've been pursuing the idea of what I call algorithm optimization. It's
> > the idea that algorithms coded by individuals may not be optimal, and
> > may require refactoring / re-engineering to be made optimal based on
> > what's trying to be achieved.


> Compilers had done to death figuring out how best to optimize what
> the developer wrote. The future is optimizing what they intended to write.


(snip)


> A while back I had the idea of trying to figure out what floating-point
> calculation was being attempted, e.g., using a Taylor series when a Chebyshev
> series would be more efficient.


I think I remember this being discussed many years ago.


One thought was that someone codes bubblesort, and the compiler
generates quicksort. Small complication that bubblesort is stable, and
quicksort isn't. (Add an array with the original position to break
ties.)


Now, say someone is doing their CS project for class, where they are
supposed to write, and time, bubblesort?


I suppose you can find a Chebyshev series that closely approximates
the series coded, but takes fewer terms.


But what about the person who wants to compare two series'?
If you replace one or both, then the comparison will be wrong.


Not that there haven't been problems since the beginning of
optimizing compilers, where the results were different than
expected.


This is also reminding me of the optimizing compilers that
figure out the whole result at compile time, much slower than
it would be at run time. That one was from a benchmark program.
[Back when people cared about Whetstone and Dyrystone benchmarks,
compilers recognized code sequences from those benchmarks for, uh,
special processing. But it doesn't generalize very well. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.