Re: Algorithm Optimization

Path	csiph.com!goblin3!goblin.stu.neva.ru!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	"Rick C. Hodgin" <rick.c.hodgin@gmail.com>
Newsgroups	comp.compilers
Subject	Re: Algorithm Optimization
Date	Wed, 16 Sep 2020 11:44:56 -0400
Organization	Liberty Software Foundation
Lines	56
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<20-09-038@comp.compilers> (permalink)
References	<20-09-032@comp.compilers> <20-09-037@comp.compilers>
Mime-Version	1.0
Content-Type	text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding	8bit
Injection-Info	gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="14292"; mail-complaints-to="abuse@iecc.com"
Keywords	optimize
Posted-Date	16 Sep 2020 13:59:10 EDT
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
In-Reply-To	<20-09-037@comp.compilers>
Content-Language	en-US
Xref	csiph.com comp.compilers:2609

Show key headers only | View raw

On 9/16/20 10:57 AM, mwmarkland@gmail.com wrote:
> On Monday, September 14, 2020 at 9:53:57 PM UTC-5, 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.
>>
> Example elided for space.
>> Rick C. Hodgin
>> [I think the usual way to do this is to provide a way to express higher level
>> algorithms in your programming language so the compiler doesn't have to try
>> to reverse engineer them. -John]
>
> I agree that this should usually be the programmer's domain. However
> there has been some work done in this area. A book I remember is:
>
> Metzger, Robert. _Automatic Algorithm Recognition and Replacement: A New Approach to Program Optimization_
>
> This approaches the issue more from a "I want to replace serial
> algorithms with parallel algorithms." if I recall correctly so it may
> not be exactly what you are looking for.

Matt, thank you for your reply.

I view this almost as a microcode-like task in authoring hardware.

The idea is to break down the actual operation to their most fundamental
components (which for the purposes of a software algorithm are not
governed by internal hardware resources or timings, but are governed by
the size and scope and extent / complexity of the database the compiler
wants to generate and use for its optimizations).

Taking this database and analyzing fundamental patterns of data access
and motion, determining by analysis (and testing during optimization)
what can be shifted around, moved, and still not affect the outcome but
yield a better result, is the goal.

I'm thinking the AST would be used as the source to produce the
fundamental operations database.  The optimizer would work on that
database, adding, updating (changing and moving around), and deleting
records resulting in the new set of optimized operations at all points
that were affected.

This database would require significant / comprehensive knowledge of how
an app is used, including what all calls into every function, what
portions touch external systems outside of our control, etc.

I think moving from the AST generating something intermediate which is
optimized before generating opcodes, to an AST generating this database
where intense analysis and a new type of optimization takes place, is
the way to go.

Will require some R&D.

--
Rick C. Hodgin

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