Re: Algorithm Optimization

Elijah Stone <elronnd@elronnd.net>
Mon, 14 Sep 2020 20:47:11 -0700

          From comp.compilers

Related articles
Algorithm Optimization rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-13)
Re: Algorithm Optimization elronnd@elronnd.net (Elijah Stone) (2020-09-14)
Re: Algorithm Optimization rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-15)
Re: Algorithm Optimization derek@_NOSPAM_knosof.co.uk (Derek M. Jones) (2020-09-15)
Re: Algorithm Optimization gah4@u.washington.edu (gah4) (2020-09-15)
Re: Algorithm Optimization mwmarkland@gmail.com (mwmarkland@gmail.com) (2020-09-16)
Re: Algorithm Optimization rick.c.hodgin@gmail.com (Rick C. Hodgin) (2020-09-16)
Re: Algorithm Optimization derek@_NOSPAM_knosof.co.uk (Derek M. Jones) (2020-09-16)
[2 later articles]
| List of all articles for this month |

From: Elijah Stone <elronnd@elronnd.net>
Newsgroups: comp.compilers
Date: Mon, 14 Sep 2020 20:47:11 -0700
Organization: A noiseless patient Spider
References: 20-09-032
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="32206"; mail-complaints-to="abuse@iecc.com"
Keywords: optimize
Posted-Date: 14 Sep 2020 23:53:06 EDT
In-Reply-To: 20-09-032

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


Post a followup to this message

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