bcase@amdcad.UUCP (Brian case) (02/14/86)
[Yes, I know this is getting boring, but I think this approach to
solving one of the problems is interesting enough to warrant wide
distribution.]
Here is a direct quote from the "IBM RT Personal Computer Technology"
handbook. It occurs in M.E. Hopkins paper entitled "Compiling for
the RT PC ROMP."
--Start quote
One of the sadder sequences of code is to see a divide by two in a
binary search or heap sort implemented with a divide rather than
a shift instruction. Even on high-performance machines, divide can
take almost ten times a shift. That is a big loss of performance in
a loop that is likely to be very important. This doesn't occur
because compiler writers are unaware that a right shift can sometimes
replace a divide by a power of two. The problem is negative numbers
as dividends. (-1)/2 is 0 on 370. -1 shifted right on bit is still
-1. The substitution of a shift for a divide only works for positive
dividends. For the PL.8 language we decided to implment a true twos
complement divide subroutine using the Euclidean algorithm that rounds
down rather than toward 0. Thus replacing divides with shifts gives
the same result. In this case a low-level instruction set gave us a
new view of source language semantics. We simply implmented the
divide subroutine that we wanted rather than accepting built-in
semantics.
--End quote
I have liked many things that Hopkins has had to say over the years
(even if his language and punctuation leave something to be desired),
and one of closing comments is typically insightful:
--Start quote
As the programming community moves toward languages that are more
powerful than C it becomes even more urgent to rely on basic constructs.
Only the simplest languages can be based on complex, high-level
messages. Thousands of hieroglyphics are much less powerful than an
alphabet of twenty-odd characters. Fast, primitive operations will
be required to efficiently implement the high level languages of the
future.
--End quote
Comparing complex instructions to hieroglyphics is what I like.
bcase
P.S. I have reprinted here without permission the above quotes.
Jeeze, I hope IBM doesn't come after me. These comments and the
act of causing them to be distributed are mine only and are typically
irresponsible. I'm really just a regular, OK kinda guy. You know,
car payments, CD player, sky-high rent, low salary (huh! you vana tauk
low celery), nerd glasses, baggy jeans. What good would it do to sue
me?bcase@amdcad.UUCP (Brian case) (02/16/86)
In article <9559@amdcad.UUCP>, bcase@amdcad.UUCP (Brian case) writes: > Here is a direct quote from the "IBM RT Personal Computer Technology" > handbook. It occurs in M.E. Hopkins paper entitled "Compiling for > the RT PC ROMP." > > --Start quote > One of the sadder sequences of code is to see a divide by two in a > binary search or heap sort implemented with a divide rather than > a shift instruction. Even on high-performance machines, divide can > take almost ten times a shift. That is a big loss of performance in > a loop that is likely to be very important. This doesn't occur > because compiler writers are unaware that a right shift can sometimes > replace a divide by a power of two. The problem is negative numbers > as dividends. (-1)/2 is 0 on 370. -1 shifted right on bit is still > -1. The substitution of a shift for a divide only works for positive > dividends. For the PL.8 language we decided to implment a true twos > complement divide subroutine using the Euclidean algorithm that rounds > down rather than toward 0. Thus replacing divides with shifts gives > the same result. In this case a low-level instruction set gave us a > new view of source language semantics. We simply implmented the > ------------------------ > divide subroutine that we wanted rather than accepting built-in > -------------------------------- > semantics. > --End quote Well, I never thought I would be responding to my own posting, but after thinking about this idea for a few milliseconds, I realized that maybe this is not such a good idea from the point of view of portability. A better solution might be to have data types which by their use allow the compiler to know that a right shift (and by the way, logical right shift, not arithmetic, right?) can safely replace a divide by a power of two. Any comments? bcase
jer@peora.UUCP (J. Eric Roskos) (02/18/86)
> Comparing complex instructions to hieroglyphics is what I like.
This is an interesting analogy. (I, also, like comparing things from
different but similar domains in order to find similarities, in the hope
that they have something common underlying them.)
But are CISC instructions comparable to heiroglyphics? Maybe so. The
heiroglyphics do express "higher-level" ideas, just like CISC instructions.
On the other hand, how do Heiroglyphics compare to a phonetic alphabet?
The phonetic alphabet conveys *no* information at all other than sounds.
Thus, for example, Spanish and English both use the same alphabet, with
a few exceptions, yet you can be the world's expert on English and not
be able to figure out anything at all about a Spanish sentence. This
is because, really, a *word* in English or Spanish is the semantic unit;
if you break a sentence into words, each word still means something, but
if you break a word down into letters, it doesn't mean anything any more.
Each letter is just a sound, and actually *that* isn't even true, since
the sound of the letters actually depends on what word they're used in,
so the letters are somewhat context-sensitive.
So really you'd have to compare the number of different heiroglyphs to the
number of different words in the English language, applying some measure
of "expressive power", to compare the languages.
On the other hand, RISC and CISC instructions are both meaningful units
of their own. Comparing the two is more like comparing two types of
heiroglyphics to see which is more expressive.
The strange irony about this whole RISC/CISC debate is something analogous
to the above. If you read the papers that have been coming out of what
has recently been labeled the CISC community for years, you find theory
that is quite comparable to the theory advanced by RISC advocates -- they
don't always agree, but at least they provide some solid means of
analyzing instruction sets. Read, for example, M. J. Flynn's "Computer
Organization and Architecture" in _Operating_Systems:_An_Advanced_Course_
(Springer-Verlag; ISBN 0-387-09812-7). The RISC/CISC dualism is
essentially artificial, I think, because really there is a continuum of
instruction set "complexity".
Thus I don't think the comparison to heiroglyphics is that useful a
comparison.
--
UUCP: Ofc: jer@peora.UUCP Home: jer@jerpc.CCUR.UUCP CCUR DNS: peora, pesnta
US Mail: MS 795; CONCURRENT Computer Corp. SDC; (A Perkin-Elmer Company)
2486 Sand Lake Road, Orlando, FL 32809-7642