Re: Algorithm Optimization

From	Elijah Stone <elronnd@elronnd.net>
Newsgroups	comp.compilers
Subject	Re: Algorithm Optimization
Date	2020-09-14 20:47 -0700
Organization	A noiseless patient Spider
Message-ID	<20-09-033@comp.compilers> (permalink)
References	<20-09-032@comp.compilers>

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Algorithm Optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-13 13:00 -0400
  Re: Algorithm Optimization Elijah Stone <elronnd@elronnd.net> - 2020-09-14 20:47 -0700
    Re: Algorithm Optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-15 00:42 -0400
  Re: Algorithm Optimization "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2020-09-15 14:29 +0100
    Re: Algorithm Optimization gah4 <gah4@u.washington.edu> - 2020-09-15 22:25 -0700
      Re: Algorithm Optimization "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2020-09-16 20:11 +0100
      Re: Algorithm Optimization Richard Harnden <richard.nospam@gmail.com> - 2020-09-16 22:45 +0100
      Re: Algorithm Optimization Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-09-17 06:35 +0200
        Re: Algorithm Optimization "A. K." <minforth@arcor.de> - 2020-09-21 02:12 -0700
      Re: Algorithm Optimization "Johann 'Myrkraverk' Oskarsson" <johann@myrkraverk.com> - 2021-04-21 16:29 +0000
  Re: Algorithm Optimization "mwmarkland@gmail.com" <mwmarkland@gmail.com> - 2020-09-16 07:57 -0700
    Re: Algorithm Optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-16 11:44 -0400
    Re: Algorithm Optimization gah4 <gah4@u.washington.edu> - 2020-09-16 13:59 -0700
      Re: Algorithm Optimization Thomas Koenig <tkoenig@netcologne.de> - 2020-09-17 06:39 +0000
  Re: Algorithm Optimization Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-12-13 23:13 +0100
    Re: Algorithm Optimization gah4 <gah4@u.washington.edu> - 2020-12-20 22:45 -0800

csiph-web