Xref: utzoo comp.arch:7765 comp.misc:4607 comp.lang.misc:2452
Path: utzoo!attcan!uunet!nuchat!steve
From: steve@nuchat.UUCP (Steve Nuchia)
Newsgroups: comp.arch,comp.misc,comp.lang.misc
Subject: Re: "big endian" and "little endian" - first usage for computer
Message-ID: <2795@nuchat.UUCP>
Date: 6 Jan 89 06:47:14 GMT
References: <2766@cbnews.ATT.COM> <10147@well.UUCP> <13045@cup.portal.com> <20264@ames.arc.nasa.gov> <20293@ames.arc.nasa.gov>
Reply-To: steve@nuchat.UUCP (Steve Nuchia)
Organization: Houston Public Access
Lines: 38

In article <20293@ames.arc.nasa.gov> lamaster@ames.arc.nasa.gov.UUCP (Hugh LaMaster) writes:
[supposed advantages of little-endian]

>I was assuming an equality comparison.  Most people seem to assume strcmp(),
>for which it does make a difference (this could lead to a very long discussion
>of how important strcmp-like comparisons are, etc., which I will avoid.)

Well, I won't.  :-)

The literature on sorting algorithms focuses on the use of a "<=" oracle,
by analogy with the mathematical definition of "well order", which is what
a sort is supposed to do.  In a previous life I derived a sort algorithm
that used a three-way oracle (strcmp, in fact) to good advantage.

I based the work on the fact that a large part of the comparison expense
for strings is in scanning the initial equal part; the three-way answer
comes for free after that.  My algorithm maintained in-core data in a
trinary tree with a degenerate (linear) subtree for the equals case.  The
expected data had significant clumping around discrete values so the extra
space was well justified.  The disk-resident format for intermediate runs
included a bit for "known equal" so the tests didn't have to be repeated
during merging.  It was a very fast sort, given the expected input
distribution.

(It used a number of other tricks, including bidirectional run management
 and very-high-order merging.  The other tricks exploited the unavoidable
 disk block cachine in unix, but the trinary tree is quite general.)

So, don't discount strcmp's value.  Very many progams use it for
an equality test only, but sorting still consumes a great deal of
computer time in the real world, and when sorting we need to
know which way it went.  It would be a good idea for computer
architects to bear this in mind:  As mundane as sorting may
seem, it is the benchmark of choice for a great many check-signers.
-- 
Steve Nuchia	      South Coast Computing Services
uunet!nuchat!steve    POB 890952  Houston, Texas  77289
(713) 964 2462	      Consultation & Systems, Support for PD Software.