Re: Algorithm Optimization

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

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