Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #9913

Re: My latest magnum opus!

Show all headers | View raw

On Fri, 02 Sep 2011 20:53:34 -0400, Eric Sosman
<esosman@ieee-dot-org.invalid> wrote:

>On 9/2/2011 9:39 AM, Richard Harter wrote:
>> On Fri, 02 Sep 2011 08:21:35 -0400, Eric Sosman
>> <esosman@ieee-dot-org.invalid>  wrote:
>>
>>> On 9/2/2011 1:39 AM, Richard Harter wrote:
>>>> On Thu, 01 Sep 2011 21:13:32 -0400, Eric Sosman
>>>> <esosman@ieee-dot-org.invalid>   wrote:
>>>> [...]
>>>>> 	Given an array A...FR...Z, to arrive at R...ZA...F:
>>>>> 	Reverse the A...F sequence byte for byte
>>>>> 	Reverse the R...Z sequence byte for byte
>>>>> 	Reverse the entire array byte for byte
>>>>>
>>>>>       I have not examined your code closely -- in truth, I have not
>>>>> even examined it cursorily.  The very fact that it's longer than
>>>>> Bentley's solution tells me it's almost certainly inferior; Bentley's
>>>>> is certainly easier to analyze for correctness.
>>>>
>>>> Back in 2004 I did an analysis.  Let n be the number of bytes.  Then
>>>> the reversal trick requires 3n data moves and 3n/u loop tests where u
>>>> is the loop unrolling factor.
>>>
>>>      Where do you get "3?"  Looks like "2" from here.  (Consider what
>>> happens to one particular byte, Q: One of the partial passes moves
>>> it from its original location to a temporary home, the other partial
>>> pass never even looks at it, and the full pass moves it to its final
>>> spot.  When all is done, Q has moved twice, not three times.)
>>
>> In a reversal you have to swap bytes which requires moving one of them
>> to a temporary location.  Reversing "ab" is
>>
>> move a from old loc to temp loc
>> move b to a's old loc
>> move a from temp to b's old loc
>
>     Ah.  Yes, the very first computer I wrote code for worked that
>way.  Strangely enough, no computer I've seen in the ensuing forty-
>four years, not one, has fit that model.  All, without exception,
>would do "load, load, store store" for (depending on how you count)
>either two data moves or four -- but never[*] three.
>
>     [*] Well, the fourth and sixth computers I wrote code for did
>in fact have memory-to-memory copy instructions.  But since they
>would have been both less convenient and slower for pairs of
>single bytes than L-L-S-S, only a less-than-clueful programmer
>would have done the swap that way.

I guess I'm not as up to date on C as I thought I WASS.  I don't
recall the "load, load, store store" statement.  Where would I find it
in the standard?  :-)

I reckon one can always use four machine instructions (or call them
two or one, just as you please) if that is faster and more convenient.
However three moves are necessary.

 

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 19:24 -0400
  Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 21:13 -0400
    Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 22:29 -0400
      Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 22:58 -0400
        Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 00:41 -0400
    Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 00:53 -0400
    Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-02 05:39 +0000
      Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 02:59 -0400
      Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-02 08:21 -0400
        Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-02 13:39 +0000
          Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-02 20:53 -0400
            Re: My latest magnum opus! James Dow Allen <jdallen2000@yahoo.com> - 2011-09-03 03:18 -0700
            Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-03 17:16 +0000
    Re: My latest magnum opus! Andrey Tarasevich <andreytarasevich@hotmail.com> - 2011-09-02 09:21 -0700
  Re: My latest magnum opus! ImpalerCore <jadill33@gmail.com> - 2011-09-06 06:51 -0700
    Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-06 18:36 -0400
    Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-06 21:04 -0400

csiph-web