1.

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.

Here's a simple example:

-----[ Begin ]-----
00: struct SData
01: {
02: SData* next; // Link list
03: int x; // Some data payload
04: };
05: SData* first = NULL;
06:
07: SData* iAlloc_new_sdata(void)
08: {
09: SData* d = (SData*)calloc(1, sizeof(SData));
10: SData* p;
11:
12: if (!first)
13: {
14: first = d;
15:
16: } else {
17: for (p = first; p->next; )
18: p = p->next;
19: p->next = d;
20: }
21: return d;
22: }
23:
24: SData* store_x(int x)
25: {
26: SData* d = iAlloc_new_sdata();
27: if (d)
28: d->x = x;
29:
30: return d;
31: }
-----[ End ]-----

In the above example, a linked list structure is allocated and some data
is stored into it. In this example a single x variable, but in a
real-world case there may be many variables.

The function called by user code is store_x(), but store_x() must call
into iAlloc_new_sdata() to retrieve a new pointer to store its data.

If this were only slightly re-written, a notable improvement could be
achieved eliminating the need for store_x(), with only a slight
extension added to iAlloc_new_sdata().

Example:
-----[ Begin ]-----
// First 6 lines are the same
07: SData* iAlloc_new_sdata(int x)
08: {
09: SData* d;
10: SData* p;
11:
12: if ((d = (SData*)calloc(1, sizeof(SData))))
13: {
14: d->x = x;
15: if (!first)
16: {
17: first = d;
18:
19: } else {
20: for (p = first; p->next; )
21: p = p->next;
22: p->next = d;
23: }
24: }
25: return d;
26: }
27:
28: SData* store_x(int x)
29: {
30: return iAlloc_new_sdata(x);
31: }
-----[ End ]-----

By moving the assignment of x into ialloc_new_sdata(), it greatly
simplifies store_x().

And since store_x() is now effectively a pass-thru function, the
compiler can optimize away all calls to store_x() and make them direct
calls to iAlloc_new_sdata().

-----
2.

We see in the above examples this loop to reach the last element:

20: for (p = first; p->next; )
21: p = p->next;

This iterative component can be a great slowdown if the link list grows
beyond a few trivial elements. But regardless, the compiler could flag
it as an iterative loop where the logic test is based upon an iterative
access to the portion being tested.

If the compiler could identify and understand the purpose of this block
of code, it could extrapolate a need to change the algorithm from
something iterative, into something more direct. And by rearranging it slightly, it would greatly improve performance on growing lists:

-----[ Begin ]-----
00: struct SData
01: {
02: SData* next; // Link list
03: int x; // Some data payload
04: };
05: SData* first = NULL;
06: SData* last = NULL;
07:
08: SData* iAlloc_new_sdata(int x)
09: {
10: SData* d;
11: SData* p;
12:
13: if ((d = (SData*)calloc(1, sizeof(SData))))
14: {
15: d->x = x;
16: if (!first)
17: {
18: first = d;
19: last = d;
20:
21: } else {
22: last->next = d;
23: last = d;
24: }
25: }
26: return d;
27: }
28:
29: // SData* store_x(int x)
30: // {
31: // return iAlloc_new_sdata(x);
32: // }
-----[ End ]-----

The last variable there would've been injected by the compiler, and the iterative loop would've been replaced with a direct assignment plus the
update of the last variable.

Other functions accessing SData (like an iAlloc_delete_sdata()) would
also have to be modified by the compiler to handle first/last processing
as well, and there may be constraints there on what's possible making
this optimization not possible due to those other constraints, even
though it is possible here.

But, in this way, by examining the intent of the algorithm and
recognizing what it's trying to do, alternate routes to achieve the same
type of computing could be determined, and the optimum of them could be
chosen for the application at hand.

It would be nice to have the compiler break things down, analyze them,
and reconstruct the revised algorithms back into source code as in the
above example, the reality is some re-arranging optimizations that could
be injected to address the constraints of logic would be made not just
based on what the language itself is capable of handling syntax-wise,
but would also include that which the target ISA's underlying machine
code would be capable of processing as well.

Things would have to be broken down to their component parts at the
targeted ISA level, examined, and then reconstructed back up from that,
being refactored where possible to improve things.

I can easily see a way to do this with patterns and use cases seen in
taking gobs of existing source code in popular products and re-compiling
it through these compilers to identify common logic flow examples, and
then manually analyzing the code and creating alternatives which allow
the optimizing compiler to pattern-match use cases and replace them with manmade alternatives ... but I'd like it to be its own thing, where it
could know what's happening data/flow-analysis-wise, and then revise the
input to achieve the same processing/compute, but with something that is greatly simplified and optimal for the target.

I view this in my CAlive compiler as three levels:

3) CAlive, a C/C++ like language with similar syntax.
2) BAlive, a language like C with only fundamental types.
1) AAlive, an intermediate assembly language which addresses the
needs of a virtual processor, which is also then constrained
by the limitations of the target ISA.
0) Emitted opcodes for the target ISA.

The framework takes CAlive source code, compiles it into BAlive source
code, which compiles it into AAlive source code, which emits opcodes for
the target ISA. Optimization takes place at the BAlive level, and
keyhole optimization takes place at the AAlive level and (more limited)
at the opcode level.

Are these all standard optimization techniques which exist, or is this something else I'm pursuing with the big push to have optimization take
place at the BAlive level to revamp algorithms based on fundamental data
types and data/flow analyses of the intent of the algorithms?

Note: All of this is my original thinking this all through. I have not
read books or articles or papers from others on how to do things. I
look at the code and I think things. I used to discuss them with Walter
Banks, but he passed in late 2019.

--
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]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 9/14/20 11:47 PM, Elijah Stone wrote:

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 goal is to figure out a way to build a compiler which can determine
what's happening and why, and then look for ways to tweak and improve
what it's doing, and without resorting to a static algorithm library.

There are certain types of data access, and there are patterns of access within. There are certain types of logic flow.

These things all factor in to a finite set of abilities the compiler
would need to know about to be able to fully express an algorithm.
Abstract Syntax Trees and their cousins do this today.

The step I'd like to work on is the way to take that expression and
analyze it, to break it down into another more fundamental layer which
can be analyzed and reorganized altering it yet without breaking the
final output result, and to finally reassemble it back into the same
original expression form again, but with the new changes that were made.

By looking at various sections of code, by looking for a flow analysis
with data for what happens in what function, where and ultimately why,
things could be moved from here to there, shifting the various burdens
around to address the fundamental needs.

A human can do this by studying an algorithm and looking for ways to
improve the code. I'd like to try to come up with a way for a compiler
to do this as well (albeit more mechanically, less capably at first, but
to be able to contribute something substantial to the world of
optimization).

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.)

I grew up on Microsoft compilers. They have two default modes: Debug
and Release. Debug mode emits unoptimized code that works, and Release
mode applies various types of optimizations.

I think that approach would work for developers. It doesn't really
matter how long it takes to compile something that's optimized once you
get it working. You could even spin it in a week if that's what it
took, because that version you have that does X, Y, or Z, could be
released in its Debug, or Release-1 state (traditional optimizations
like we see in GCC or whatever today), and then let it bake for that
week while it goes into a Release-2 state.

Release-2 would be intensive, but if it ultimately finds 35% better
performance ... it would be worth it.

--
Rick C. Hodgin

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Rick,

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.

Compilers had done to death figuring out how best to optimize what
the developer wrote. The future is optimizing what they intended to write.

Are these all standard optimization techniques which exist, or is this something else I'm pursuing with the big push to have optimization take
place at the BAlive level to revamp algorithms based on fundamental data types and data/flow analyses of the intent of the algorithms?

A while back I had the idea of trying to figure out what floating-point calculation was being attempted, e.g., using a Taylor series when a Chebyshev series would be more efficient.

http://shape-of-code.coding-guidelines.com/2010/02/28/using-numeric-literals-to-identify-application-domains/

Note:  All of this is my original thinking this all through.  I have not read books or articles or papers from others on how to do things.  I
look at the code and I think things.  I used to discuss them with Walter Banks, but he passed in late 2019.

I'm sorry to hear this news about Walter.

--
Derek M. Jones
blog:shape-of-code.coding-guidelines.com

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tuesday, September 15, 2020 at 7:24:11 PM UTC-7, Derek M. Jones 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.

Compilers had done to death figuring out how best to optimize what
the developer wrote. The future is optimizing what they intended to write.

(snip)

A while back I had the idea of trying to figure out what floating-point calculation was being attempted, e.g., using a Taylor series when a Chebyshev series would be more efficient.

I think I remember this being discussed many years ago.

One thought was that someone codes bubblesort, and the compiler
generates quicksort. Small complication that bubblesort is stable, and quicksort isn't. (Add an array with the original position to break
ties.)

Now, say someone is doing their CS project for class, where they are
supposed to write, and time, bubblesort?

I suppose you can find a Chebyshev series that closely approximates
the series coded, but takes fewer terms.

But what about the person who wants to compare two series'?
If you replace one or both, then the comparison will be wrong.

Not that there haven't been problems since the beginning of
optimizing compilers, where the results were different than
expected.

This is also reminding me of the optimizing compilers that
figure out the whole result at compile time, much slower than
it would be at run time. That one was from a benchmark program.
[Back when people cared about Whetstone and Dyrystone benchmarks,
compilers recognized code sequences from those benchmarks for, uh,
special processing. But it doesn't generalize very well. -John]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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 Markland

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wednesday, September 16, 2020 at 8:14:44 AM UTC-7, mwmar...@gmail.com wrote:

(snip)

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.

That might make more sense. So, an algorithm that it mathematically equivalent, but not necessarily numerically equivalent.

One of the more obvious is matrix multiplication, which seems
so simple, but the traditional ones aren't so good. For one, they
have poor cache performance on many machines.

It takes just a little more than parallelizing the usual algorithm
to get it right.

Replace matrix inversion with LU decomposition?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 16/09/2020 06:25, gah4 wrote:

Now, say someone is doing their CS project for class, where they are
supposed to write, and time, bubblesort?

I don't think student projects should be a factor in implementation of industrial compilers.

I suppose you can find a Chebyshev series that closely approximates
the series coded, but takes fewer terms.

But what about the person who wants to compare two series'?
If you replace one or both, then the comparison will be wrong.

More edge cases.

I'm sure you know about Herbie: https://herbie.uwplse.org/

Not that there haven't been problems since the beginning of
optimizing compilers, where the results were different than
expected.

There probably won't be too many places where savings can be made.
The compiler could highlight them.

There are always people willing to pay for faster code, and there will
be compiler writers willing to implement go faster stuff.

[Back when people cared about Whetstone and Dyrystone benchmarks,
compilers recognized code sequences from those benchmarks for, uh,
special processing. But it doesn't generalize very well. -John]

Intel and ??? have both been caught doing this. See chapter 13 oof
this book: http://www.knosof.co.uk/ESEUR

Benchmarking these days has gotten to be very unreliable: https://shape-of-code.coding-guidelines.com/2015/02/24/hardware-variability-may-be-greater-than-algorithmic-improvement/

http://shape-of-code.coding-guidelines.com/2020/01/05/performance-variation-in-2386-identical-processors/

--
Derek M. Jones
blog:shape-of-code.coding-guidelines.com

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 16/09/2020 06:25, JL wrote

[Back when people cared about Whetstone and Dyrystone benchmarks,
compilers recognized code sequences from those benchmarks for, uh,
special processing. But it doesn't generalize very well. -John]

And can backfire badly for the company involved ...

many VW cars being sold in America had a "defeat device" - or software -
in diesel engines that could detect when they were being tested,
changing the performance accordingly to improve results.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

gah4 <gah4@u.washington.edu> schrieb:

On Wednesday, September 16, 2020 at 8:14:44 AM UTC-7,
mwmar...@gmail.com wrote:

(snip)

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.

That might make more sense. So, an algorithm that it mathematically equivalent, but not necessarily numerically equivalent.

Hic sunt dracones.

Re-arranging mathematically equivalent operation can lead to
surprising side effects, and are prohibited by many language
standards. Yet, compilers very often have optimizations to switch
off the guarantees of these standards, and they are often used by
users ignorant of the issues (and for benchmarks).

An example is Kahan summation, which is an algorithm for reducing
numerical errors in summing up terms. It is mathematically
equivalent to straightforward summation, so a compiler which
operates on mathematical equivalence across statements
can in fact convert Kahan summation back to simple summation.

This, of course, loses the benefit that the programmer (presumably)
wanted.

Gcc, for example, will happily do that transformation if given
the -funsafe-math-optimization flag (which, despite what the name
implies, is neither fun nor safe). The problem is that this is one
of the flags enabled with the catch-all option with the suggestive
name -Ofast.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Am 16.09.2020 um 07:25 schrieb gah4:

One thought was that someone codes bubblesort, and the compiler
generates quicksort. Small complication that bubblesort is stable, and quicksort isn't. (Add an array with the original position to break
ties.)

Right, algorithm or control flow optimization should be located in an
earlier project stage, not in compilation. It also smells like the dream
of automated "proof of correctness", whose basics I learned 50 years ago
but never found usable results yet. How shall a tool suggest other
algorithm(s) without knowing (having determined - how?!) about the goals
of a piece of code?

DoDi

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Am Sonntag, 20. September 2020 03:06:00 UTC+2 schrieb Hans-Peter Diettrich:

Am 16.09.2020 um 07:25 schrieb gah4:

One thought was that someone codes bubblesort, and the compiler
generates quicksort. Small complication that bubblesort is stable, and quicksort isn't. (Add an array with the original position to break ties.)

Right, algorithm or control flow optimization should be located in an
earlier project stage, not in compilation. It also smells like the dream
of automated "proof of correctness", whose basics I learned 50 years ago
but never found usable results yet. How shall a tool suggest other algorithm(s) without knowing (having determined - how?!) about the goals
of a piece of code?

On a much higher level, (semi)automatic algorithm selection can increase application productivity enormously.

F.ex. look at the Wolfram language
https://www.wolfram.com/language/principles/

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 13.09.20 19:00, Rick C. Hodgin wrote:

1.

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.

[...]

In the above example, a linked list structure is allocated and some data
is stored into it.  In this example a single x variable, but in a
real-world case there may be many variables.

A linked list may be the best solution by itself, but not in some
algorithm. How shall a compiler find out that a linked list here is the
best solution, due to some list features used somewhere else?

[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]

+1

What's the best language to express algorithms in?
Or, how many languages claim that already...

DoDi

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Sunday, December 13, 2020 at 3:16:03 PM UTC-8, Hans-Peter Diettrich wrote:

(snip on algorithmic optimization)

[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]

What's the best language to express algorithms in?
Or, how many languages claim that already...

C has qsort(). While the name seems to suggest quicksort, that isn't
a requirement of the implementation. It does suggest an algorithm
independent way to write programs that need sorting.

Java has classes like List, and subclasses like ArrayList and LinkedList.
One can write a program using List, and easily switch later between
ArrayList, LinkedList, or any other implementation of List.

Hopefully, in addition to the specific cases supplied, these suggest
ways to implement new problems independent of the specific
underlying algorithm.

But the urge to reinvent solutions to already solved problems is
sometimes too great.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 16/09/2020 5:25 am, gah4 wrote:

I think I remember this being discussed many years ago.

One thought was that someone codes bubblesort, and the compiler
generates quicksort. Small complication that bubblesort is stable, and quicksort isn't. (Add an array with the original position to break
ties.)

Here are even more dragons.

What if you're sorting exactly three elements? In that situation, I'll
be very surprised if bubblesort doesn't outperform all other algorithms.

How does the /compiler/ decide that an algorithm is better, based
on data it never sees? Even if we account for profile guided optimi-
zations, we shouldn't allow the compiler to adjust for /what if this is
run with more data in production?/ kind of questions.

If you want to go down this rabbit hole, I'd much prefer warnings than
outright algorithm changes.

--
Johann

I'm not from the internet, I just work there.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)