Re: Algorithm Optimization

On Sun, 13 Sep 2020, Rick C. Hodgin 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.


I agree with John: generally, it should be the programmer's job to choose
the right algorithm. Otherwise, the compiler just becomes an algorithm
library, and--well, if you're going to build an algorithm library, why not
just expose it directly to your language's users?


The main problem is that algorithms are /heavily/ dependant on data
structures. So if you want to change an algorithm significantly, you'll
need to change its data structures, and usually the compiler can't tell if
external code is going to look at those data structures.
In the case of your example, though it's hard to tell, I expect that the
optimal structure would be a freelist, but because 'first' is a global
variable, modifications to it have to be the same with and without
optimizations. (You might be able to get around this by making 'first' a
static variable local to iAlloc_new_sdata; but this approach doesn't
scale, and it's already putting pressure on the programmer's algorithms,
which is what you were trying to avoid.)


A secondary problem is compile time: recognizing algorithms is likely to
be very expensive, which is not a great user experience. (Though llvm/gcc
do recognize some things, like algorithm for triangle numbers.)


--
time flies like an arrow;
fruit flies like a banana

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