Re: "Sorting" assignment

On Feb 11, 8:15 pm, "Clive D. W. Feather" <cl...@on-the-
train.demon.co.uk> wrote:
In article
<e17b318e-31b2-46ac-9963-e47625bb6...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,spinoza1111<spinoza1...@xxxxxxxxx> writes

No, the best solution would be a simple for loop that XORs each byte
(the following is extempore and written in a C based pseudo code and
not C; it is untested):

for (intintIndex1= 0;intIndex1< length; intIndex1++)
*(ptrToA+intIndex1) = *(ptrToA+intIndex1)  ^ *(ptrToB+intIndex1);

Why do you write "*(array + index)" rather than the more normal
"array [index]"? It just makes the code hard to read.

You later admit that you got the inner body wrong and it should be:

    {
    *(ptrToA+intIndex1) ^= *(ptrToB+intIndex1);
    *(ptrToB+intIndex1) ^= *(ptrToA+intIndex1);
    *(ptrToA+intIndex1) ^= *(ptrToB+intIndex1);
    }

Good for you for making the admission.

This algorithm is in Knuth, and it's a pretty trick. However, is it
actually worth doing?

An optimised byte-for-byte exchange loop will generate code something
like this (I've made no attempt to save registers):
    LD R1,ptrToA
    LD R2,ptrToB
    LD R3,0
    LD R4,length
    JMP LE
L:  ; start of loop body
    LD R5,(R1)
    LD R6,(R2)
    XOR R7,R5,R6
    ;  LD (R1),R7  ; would be removed by the peephole optimiser
    XOR R8,R6,R7
    LD (R2),R8
    XOR R9,R7,R8
    LD (R1),R9
    ; end of loop body
    INC R1
    INC R2
    INC R3
LE: CMP R3,R4
    JLE L

A simple exchange using a temporary variable would be:

    LD R5,(R1)
    LD temp,R5
    LD R6,(R2)
    LD (R1),R6
    LD R7,R5
    LD (R2),R7

which the peephole optimiser would turn into:

    LD R5,(R1)
    LD R6,(R2)
    LD (R1),R6
    LD (R2),R5

So your code simply does three XORs to no benefit.

The next optimization step is not to use a "buffer". It is to SEARCH
AHEAD starting at a and to SEARCH AHEAD starting at b for a pair of
characters that are different so that we avoid unnecessary XOR.

For random data, the probability of two values being the same is
(1/(2^B-1)), where B is the number of bits in the object type. That
means it is at most 1/255.

For English text, the probability of two characters in separate strings
being the same is 0.067 (see Kahn). The test is probably going to cost
more than avoiding the work will gain.

See the new thread "Results of the memswap() smackdown from the thread
"Sorting" assignment" I have created to evaluate this. I used English
text and had a small gain, because the brute force took 203 clock
thingies while avoiding unnecessary moves using a for loop to span
ahead to 187 clock thingies in the single benchmark I've had time to
run at this time.

--
Clive D.W. Feather                       | Home: <cl....@xxxxxxxxxx>
Tel: +44 20 8495 6138 (work)             | Web:  <http://www..davros.org>
Fax: +44 870 051 9937                    | Work: <cl....@xxxxxxxxx>
Please reply to the Reply-To address, which is:  <cl...@xxxxxxxxxx>

.

Relevant Pages