Re: Thinking assembly?

From: Beth (BethStone21_at_hotmail.NOSPICEDHAM.com)
Date: 01/20/04 

Date: Tue, 20 Jan 2004 07:15:48 -0000

T.M. Sommers wrote:
> The Half A Wannabee wrote:
> > Then of course shooked by this fact, after a while you (me) get to
learn a
> > little assembly, and starts rewriting a piece of brute force code.
Spending
> > a lot of time to understand even the simplest things ; you mind
must stay
> > with the problem longer...e.g you sometimes *must* understand the
problem
> > deeper. While you understand the problem deeper, you see other
often better
> > solutions. This is one part of thinking in assembler to me.
>
> It is ususally not necessary, or desireable, to rewrite a bad
> algorithm in assembly. The better course is to find a better
> algorithm and implement it in the higher-level language.

Absolutely; But why exactly must we stop there?

The even better course still is to find that better algorithm and then
_ALSO_ implement it in _assembly_...remembering, also, that some forms
of algorithm can only be fully appreciated and implemented using
assembly language...and that whatever "better algorithm" you discover
in your higher-level language is _always_ perfectly implementable in
assembly language also...but once you have this "better algorithm"
coded in assembly language, you have the option of taking it further
still with, of course, _better code_ as well...

It seems, in both cases, strange that we just stop and only accept
some "half solution"...even more so when, due to the relationship
between these higher-level languages and ASM, assembly language is
_always_ capable of equally implementing _any_ algorithm in the
higher-level language...

Plus, even if "portability" is a concern that makes you feel a
preference towards the higher-level language solution, then there is
nothing particularly stopping you with most C compilers, for instance,
from compiling your HLL solution to ASM for each target platforms and
then "tweaking" that further to take more specific advantage of that
particular architecture...there is nothing at all to suggest that, in
doing so, one can't simply _retain_ the original "higher-level
framework" on disk somewhere so that, yes, when you wish to "port" to
some new platform, you can't merely go back the HLL code to obtain
that and then, for this new platform, again compile to assembly and
"tweak" it to perfection...

You see, _IF_ we were talking about a mutually exclusive position
(which, for some really strange reason, people will continue to insist
on viewing it as...despite the _clearly known_ relationship that all
HLLs ultimately boil down to an assembly solution and all the compiler
does is automate that process) then you could understand the "half
solution" as a compromise...

But why compromise at all? There's no particular reason to, is there?
Well, other than time constraints...but, of course, if everyone worked
this way and pre-planned that it should work this way, then such
constraints - time necessary to "fine-tune" and "polish" a product -
would be automatically factored into the deal? Why isn't the actually
_very necessary_ process of "polishing" and "fine-tuning" - what turns
an "amateur production" into a _professional_, _quality_ product -
ever factored in?

Money for nothing?

> An
> O(n**2) algorithm is O(n**2) regardless of what language it is
> written in.

Absolutely correct; Except the _units of measurement_ between
languages now _differ_, often substantially so...

This algebraic "representation" masks the arithmetic _reality_ below
(as I like to say, "don't confuse your _notation_ with the actual
_physical thing_ you are notating")...the exact same "O(n**2)"
algorithm implemented in BASIC and in assembly language can
potentially _differ substantially_ in the _actual physical amount of
time_ it takes to complete (and this is the ultimate measure of the
program, as "untheoretical" as it may be...algebra is just a
convenient way to manipulate mathematics but, in the end, it's the
_arithmetic_ it represents that counts)...this is not related to its
"O(n**2)" nature but to the underlying difference in the "units"
between languages...

"O(n**2)" in "BASIC units" is a _different amount of time_ to
"O(n**2)" in "ASM units"...in order to make comparison between
algorithms, though, these "units" are usually abstracted out of the
equation...this is useful for "algorithm comparison" but it should be
remembered that the "units" should always be _put back in_ for the
final answer...

[ In fact, at school, there was a policy of docking a mark from an
answer if the final answer was not correctly given with its
appropriate units...the _number_ could be entirely correctly
determined but, as numbers are merely abstract and thus have no
_meaning_ on their own at all, then the answer was strictly _WRONG_
unless the units were returned to the final answer...of course,
marking something with zero marks merely for forgetting the units -
which, technically, would be _correct_ to do so because, lacking the
units, the answer is NOT correct and, were we so pedantically cruel
about things, it should be awarded a big red "WRONG" cross - would be
far too harsh and unrepresentative of the method being essentially
correct that questions were awarded multiple marks (so that they could
be awarded marks on differing criteria such as "correct method",
"correct answer", etc. which a single "right or wrong" mark couldn't
represent ;) and but a single mark was lost for forgetting the units
on the answer... ]

So, when we arrive at our final answer, the _units_, presumably, are
something like "seconds" (or "milliseconds" or some other time-based
measurement, depending on the "scale" of the response :)...this unit -
being a universal measurement of time - is independent of the
programming language used and brings back a "like for like" comparison
between the two implementations...

And, generally speaking, "ASM units" are usually smaller than "HLL
units"...and, in fact, logically the best that HLLs could ever manage
is merely _EQUALLING_ "ASM units"...they are, by definition of what
"ASM units" actually, a "unit" that "HLL units" may _NEVER_ exceed
(how can a HLL which compiles down to machine instructions, ever
exceed machine instructions? Even if something in a HLL compiles down
to a single "MOV" instruction, say, it cannot ever compile _further_
than that...in which case, it's "very best" is the units of
measurement that ASM _always_ occupies)...

Thus, if we equal the "algorithm" - use the same one for both - then,
presuming reasonable and correct implementation of that algorithm in
both languages, the very best that the HLL can expect, logically, is
to _EQUAL_ the ASM implementation...otherwise, which is the more
likely case probability-wise, the HLL solution is going to be a
"lesser" implementation...

And if you consider the concept of "equal or better", then - other
factors like time permitting - it's _ALWAYS_ a prospect worth
pursuing...the reason being that, at worst, you end up in no worse
position than you began with (and it must be remembered that
probability-wise, this best "equal" case is but _one_ possibility
among a massive amount that the chances of this being the case are
actually "exceedingly unlikely" in general)...but, otherwise, you have
a _guaranteed_ improved solution...if you cannot lose but only gain -
and other factors like time permits it to be attempted - then there
exists no logical reason whatsoever to refuse to pursue that
possibility...plenty of prejudiced _human_ reasons about "I don't want
to do that because I don't like it!" and so forth but no reason that
has logic backing it up as a correct decision...your _ONLY_ excuse,
basically, is the other practical factors that enter into the
equation: not enough time, can't be bothered, etc....the "time" factor
is legitimate (though, one does sometimes have to question whether
some deadlines are _truly real_ or merely imagined for "political
reasons" within an organisation), most others are NOT legitimate at
all...at least, to put that more clearly: They are _cheap excuses_,
not "legitimate reasons"...

> Replacing it by an O(n) algorithm in a HLL will give
> better results than simply reducing the constant factor with
> assembly.

Without a shadow of a doubt; But, as I mention, replacing it with an
"O(n)" algorithm in ASM will give even better results again...because
we can improve _BOTH_ the algorithm _AND_ reduce that constant factor
as well...

Beth :)