Lynn H. Maxson
Mon, 17 Jul 2000 10:28:43 -0700 (PDT)
"One difficult part of talking with you is that you
never answer yes or no to a question, nor do you
directly address a statement. You instead discuss
something related to the statement which happened
to be on your mind at the time."
Billy, part of the time it is guessing game. You
realise that you have not communicated well which
leaves you guessing on what it takes to get on
track. Once you done this incorrectly several
times the task gets even more difficult. I've
often considered answering with a simple "yes" or
"no". Maybe you have offered me an easy way out.
"I don't understand how your comment about
"specialties" has any relation to the rest of your
paragraph. How does it?
Optimization is not a specialty -- it's
The paragraph contained a reference to how IBM has
relegated its "optimized" code generation for its
compilers regardless of source language to a group
devoted to that purpose. This to my way of
thinking makes it a specialty.
As to the reference that it is "everything" I must
somehow protest. In order of priority of emphasis
I must place the mapping of the solution set to the
problem set as first. If that means using fixed
decimal integer arithmetic instead of binary, then
so be it.
After doing that I am interested in its most
efficient execution. To do that I need to know "a
priori" the mix of the input data. All programs
are data driven. The greater the knowledge I have
of the input data the better I can organize the
decision logic to as to minimize the average number
of decisions made in the aggregate. This is one
form of optimization available to me with an HLL.
As I cannot optimize an iteration, considering that
its decision logic is necessary and sufficient,
that leaves only sequences. For me to optimize
these in terms of generated code I am dependent
upon feedback from each implementation. For the
same compiler whose implementation varies by the
version that implies that either I go back to all
the source I have written in all programs using
that compiler or I simply accept what it produces
unless its runtime turns out not to be "good
" Everyone who's ever written a program is an
optimiser. Anyone who's ever walked a new route to
an old place is an optimiser."
An optimist, maybe.<g>
"There are many specialties within optimization, of
course. Some of the most rigorous involve the
attempt to translate some aspects of optimization
to a machine-expressible algorithm."
How does it differ as a specialty here from my
"Those responsible for code generators must be,
yes. I see you're bringing in a confusion between
code generation and optimization again; the
ultimate optimiser is also a code generator, but
merely making a fancy code generator doesn't give
you an optimiser. Optimising is FAR more
Well, if everyone who writes a program is an
optimiser, how difficult can it be? One of us
certainly is confused.<g> Optimizing compilers
which internally reorganize the translated source
statement and then seek to minimize the execution
time of the generated code are not merely fancy
code generators, but optimizing code generators.
That it is difficult for people to do consistently
is why you incorporate the rules into software.
If you write in a HLL, you have no control over the
code generated, whether or not you select an
optimizing option. The only control you have,
where you know what code get generated for a
particular expression, is to write in the form of
that expression. Even there the sequence may
change from one version to the next. So you dare
not recompile without reverification.
"The computer won't find the optimum for anything
but the most trivial imaginable program in a week.
I disproved this in my last post."
Maybe we can assert this as Billy's Theorem where
Billy operationally defines the difference between
an "optimiser" (the person), "optimizing" (the
process), "optimum" (the result), and "efficient"
"...and in the process, he'll have changed the
low-level design of the code just a bit to better
fit the architecture, something your computer can't
do in a million years."
You must be running scared here to believe that any
better fit he discovers is not specifiable in
software. We can debate whether or not it is
possible to specify in software a discovery process
that could "discover" this more efficient form in
some reasonable time period. We cannot debate that
once discovered we can specify our discovery in
The point is that the "computer" (for some reason
you still regard this as an independent entity)
does what the software tells it to do. If we tell
the software "with this input produce that output",
it will do it without having to "discover" what to
"Yes, I do. I insist that the programmer will code
NOT the best possible code for the low-level
design, but rather code which is BETTER than
possible for that low-level design."
Now I am not sure which of us is more confused.<g>
"Do you still believe any of that? Then let me
disprove it in ONE WORD:
ONE PERSON can defeat a computer at Go, even
allowing the computer a huge amount of time."
Well, technically no. The human player would have
to pass on the next move to his successor as the
amount of time that the software would need might
exceed his lifetime. To say that we have granted
it a "huge" amount of time is also saying that we
have also set a limit.<g>
However picking an optimal strategy is different
from optimizing a code sequence. That is dependent
upon finding that code sequence which uses the
least number of machine cycles each execution
regardless of the number of executions. While the
number of executions may be large all the machine
logic associated with each iterative execution may
Moreover the fact that a program may never
terminate does not mean that it is not executing as
fast as it possibly can.<g> Stick with the subject
of code optimization.
"You're also mistaken when you associate heuristics
with optimum solutions. Heuristics don't even try
to find optimum solutions; they merely find
solutions which are 'good enough'."
I don't care how humans arrive at a decision, come
to a conclusion. Whether optimum or "good enough",
as long as it can be specified in software it will
suffice. If a better, more optimum way is found,
we can replace the existing choice with the newer
one. We may never discover an optimum, but that
does not prevent us from coming closer and closer
nor preventing our specifying our discovery in
I do not argue that software does anything on its
own, even a discovery process, that is not dictated
by human-determined rules. That which we discover
we specify in software such that we can get maximum
benefit. The software functions as a tool
extending human abilities. I do not go to war with
software or regard it as a competitor when in fact
it is a loyal and blindly obedient servant.
Now it is true that as a human I can master many
machine architectures and discover hundreds and
thousands of rules which apply to expression
evaluation in terms of code generation. However I
have determined that I prefer to write in a HLL
ignorant (independent) of any machine architecture.
Thus I incorporate my rules into software governing
the translation of my language into the machine's
language in the same manner "as if" I had written
it in its language.
Now whether my discoveries are optimum or not is
unimportant. What is important is that among my
discoveries and those of others is at least one in
any given input instance that is equal to or better
than any other in terms of machine cycles required.
It may not be optimum in any absolute sense, but it
represents my best choice at the moment. Until a
new discovery comes along, gets added to the
collection, and a new evaluation changes things it
will have to be "good enough" as it is the best I
"You're also badly mistaken (shockingly so) when
you claim that selecting from an infinitely large
set requires an infinite number of programmers.
The very act of programming IS by definition
selecting a single program from an infinitely large
set (the set of all programs); so is optimization
(the set of all programs which fit the specs).
This is done all the time by a SINGLE programmer."
It's no wonder that I tend to meander a bit in
these responses as I ponder a stratagem to pursue
to get communication back on track.<g> To quote
you in a word "go". The first player makes a move.
The second player concedes defeat. There's no
sense in playing out a game you know you are going
You have great faith in the gestalt abilities of
every programmer. It amazes me then how different
ones come up with different results. Must be
something willy-nilly in the individual selection
process from the same infinite pool of programs.
The fact of the matter is that you can make a
non-optimum selection. To make an optimum
selection you would have to examine an infinite
number. No matter how quickly you eliminated one
from consideration the time would exceed your
I won't even bother that the storage capacity of
the brain would not hold an infinite number even it
were possible to examine each (which by definition
of infinite is impossible). So obviously it does
not occur in this manner by any single or multiples
">Moreover there is no way anyone can develop a
>"secret" heuristic and keep it that way in
>practice. Once it exists in machine code the
>secret is out: it becomes another among a host of
What? That's impossible."
Wrong again.<g> The longer answer would be that
for a given input a new output mapping exists.
That new output is specifiable in software.
"No, it's because heuristics vary. The same
heuristic can be coded in different ways; or the
code to recognise when the heuristic fits might be
better or worse. The compiler's optimiser might be
better or worse (and that's one area where there's
DEFINITELY no one best way).
It's not a technical problem; it's a mathematical
It does not make a difference how you code a
heuristic, by definition it must produce the same
result. The only possible difference is the time
It is true that how people code logic can impact
the application of an heuristic. That's a people
difference which we seek to overcome. That is true
when it comes to the compiler's optimiser.
From a given set of choices, finite or infinite,
there may be no "one" best choice (although there
may be), but there is at least one whose runtime
performance (regardless of its space requirements)
is at least equal or better than any other. For
what it is worth it is logically true.<g>
"Sure, if you want. Of course, that's not true;
optimization is a single process, and performing it
piecemeal will always result in something inferior.
However, it's generally good enough."
Optimization is a process. A process is a set of
stages (sub-processes). Each is a piece. Anytime
a piece makes a change we transfer control back to
the intial sub-process to repeat the process. Once
we get through this iteration, when no piece makes
a change, we terminate the process.
If you believe that because every process must be
executed in a piecemeal manner and therefor must
produce inferior results, then I will exit any
further discussion on the subject.<g>
"Ah, but this isn't true! Ever heard of "loop
unrolling"? It can VASTLY speed up code! Of
course, it increases the bulk of code..."
Loop unrolling can only occur where the number of
iterations is fixed and known at "compile time",
i.e. expressed in the source. As such it is
subject to the embedded optimizing rules which can
account for it as well. If your statement is that
it makes a different directed graph, one of
repetition and not iteration, it still does not
affect the optimization of the repeated code.
"Do you hear what you're saying? Read it again!
Look at what you're saying to me!!!!!!! Please!
You're claiming that you're not trying to find when
a program terminates; what you're actually trying
to find is WHETHER A PROGRAM TERMINATES IN LESS
TIME. Same thing!"
Well, one of us is confused. I don't have any
problem with whether a program terminates or not or
even when it terminates. The only assumption that
I make is that in two executions (which could be
occurring concurrently) that it is possible that
one is executing faster than the other, that
somehow their internal coding differences accounts
for their performance difference.
Strangely enough I can tell you that a program will
terminate if that program contains a sequence only.
I can on a given machine with a given set of code
tell you when it will terminate. I can because I
have done so. I didn't allow somebody's theorem to
get in the way. The fact is that there seems to be
a variation in the runtime between the different
runs, so you have to iterate it in as near isolated
conditions as much as possible a thousand or more
times to have some confidence in the "average" run
This method comes directly from Abrash's "The Zen
of Assembly" which is on my bookshelf along with
the "Tao of Objects" and the "The Art of the
Metaobject Protocol". Fortunately Abrash hadn't
heard of Rice's Theorem either so he could offer a
terminating code wrapper for my code so that we
could determine from a set of given expressions
which one ran faster. Without proving it other
than empirically, which is the only real world
test, I had no other proof in mind.<g>
"... and you profile the program while it's
of the program which run frequently can get
optimised with more
time-consuming optimization processes.
Suprisingly, it seems to work well."
"Have you ever attempted to count the number of
paths in a trivial program? You're correct that
it's finite (by your definition of the word
'path'); however, it's a HUGE number. Using your
algorithm, we'd have to optimise each path
seperately; you miss the fact that any two paths
can overlap, and usually do."
The most trivial program is a sequence of a single
statement. Counting the number of paths is quite
simple: one. I have in fact accounted for the
number of paths in a non-trivial program. When
called upon I depend upon my PL/I compiler to
enumerate the number of paths in a program.
As I write structured code I don't seem to have the
overlap problem you referred to. I do have
reusable paths, but they are logically
non-overlapping. Using my algorithm we would have
to optimize each path separately. If that meant
that reusable portions would differ, then we would
generate multiple versions of each portion. That
may bother your optimizer, but not mine.<g>
"You speak of "finite" additional time -- but are
you sure that the time is finite?"
This gets back to the "infinite possibilities"
thing you laid on me. In any give language we have
only a certain (finite) number of operators. In
order for there to be infinite possibilities at
least one of these operators must fall into this
category. I would be more than happy at some other
time to take each operator in turn for any given
machine architecture to show for each there were
only a finite number of choices.
I understand your definition of logical
equivalence. I also understand the concept of
machine cycles. I also understand how I can use an
heuristic regarding one to restrict what I have to
consider out of the universe of the other, a
restriction which reduces what I produce to a
finite number. It is no more than saying that
while the set of integers is infinite, the set of
those equal to or greater than zero and equal to or
less than 37 is not.
That means all I have to have for each operator is
a "starter set" of machine code. I never have to
consider anything which exceeds its number of
machine cycles. Machine cycles is what determines
from a set of choices which is best, whether
optimum or not. The optimum choice is either equal
to or less than this. If less than this, then it
must be in the "computable" finite set.
"You've said this before, and I don't understand
it. How does your system cause this to happen? I
don't understand at all."
You understand public domain. Here's a
specification language whose definition is
specified in the language, i.e. exists as a set of
specifications. Here's a tool written in that
language. Here's the source for both in the public
What is it that you don't understand? Here is a
language and a tool whose only input is source. It
has rules of syntax and semantics. As long as the
source follows the rules you cannot introduce
incompatibilities. You can introduce
contradictions, but that simply means selecting one
or the other or a process which includes both.
The user owns the tool and the source. When he
wants an application written he finds someone to
write the additional specifications expressed in
the source language. These get added to the user's
source: they remain his property.
This is no more than what occurs in large accounts
with their own IT departments today. All this does
is bring it down to the level of the individual
user. If the minimal claim of "50 times time
reduction, 200 times cost reduction" is valid, it
means that a single user can afford to have a
"build to order" (custom) solution now instead of a
"build to stock" (package) currently.
If users keep adding source into the public domain,
then more and more applications become less and
less expensive. In that manner the current
advantage that vendors have over users disappears.
In such a system the user dictates and the vendor
The beauty of a specification and a formal
specification language lies in its non-proprietary
nature. You cannot own "what" something does, only
"how" it does it. If I personally have a "what" in
mind, and a means of producing an executable on my
own, i.e. not for resale, then nothing or no one
can physically, legally, or otherwise stop me. If
I submit my "what" to the public domain, all of
whose members have the same capability, then
nothing can stop them either.
You cannot introduce incompatibilities. You have
no need for standards other than rules of syntax.
There's no way for anyone to establish a monopoly
and quash competition. You (and maybe a few
friends together) can afford to have custom
specifications written (if you cannot or do not
want to write them yourself). What you have is a
viable market segment down to a single user.
Now what is it that you don't understand?<g>