Results of the memswap() smackdown from the thread "Sorting" assignment

Discussion of Ivica's questions concerning a sorting assignment in the
thread "'Sorting' Assignment" led to a debate. Richard Heathfield
posted a buffer based method for fast exchange. spinoza1111 posted a
version that spans over bytes that are the same. Ben Bacarisse posted
a version that handles the small volume common cases in a switch().
Malcolm McLean posted a version that like Nilges/spinoza's avoids
unnecessary swaps.

Below, the test program, which repeatedly exchanged lines and blocks
of text, is followed by the results output.

Here are the CPU rankings

Ben's code took 63 clock() values to do the exchanges 10000 times.

spinoza1111's code took 203 clock() values to do 10000 exchanges

Richard's code took 109 values. to do 10000 exchanges

Malcom's code took 187 clock values. to do 10000 exchanges


This is purely a sporting event and as a single benchmark means ONLY
at this time that Ben's a pretty sharp guy and it is a good idea to
exploit the frequency of small jobs, as Ben does. Please check my
math, since I have a meeting right now and have to run. The clock
values appear in the results.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// ***** spinoza1111's code *****
void spinoza1111_memswap(char *ptrToA,
char *ptrToB,
int intLength)
{
int intIndex1 = 0;
char chrExchange;
while (intIndex1 < intLength)
{
for (;
*(ptrToA + intIndex1) == *(ptrToB + intIndex1);
intIndex1++);
if (intIndex1 >= intLength) break;
chrExchange = *(ptrToA + intIndex1);
*(ptrToA + intIndex1) = *(ptrToB + intIndex1);
*(ptrToB + intIndex1) = chrExchange;
intIndex1++;
}
}


// ***** Ben Bacarisse's code *****
#define BUF_LEN 64
void ben_memswap(void *vleft, void *vright, size_t n)
{
unsigned char buf[BUF_LEN];
unsigned char *left = vleft;
unsigned char *right = vright;
unsigned char t;


switch (n) {
case 7:
t = left[6]; left[6] = right[6]; right[6] = t;
case 6:
t = left[5]; left[5] = right[5]; right[5] = t;
case 5:
t = left[4]; left[4] = right[4]; right[4] = t;
case 4:
t = left[3]; left[3] = right[3]; right[3] = t;
case 3:
t = left[2]; left[2] = right[2]; right[2] = t;
case 2:
t = left[1]; left[1] = right[1]; right[1] = t;
case 1:
t = *left; *left = *right; *right = t;
break;


default:
while (n > BUF_LEN) {
memcpy(buf, left, BUF_LEN);
memcpy(left, right, BUF_LEN);
memcpy(right, buf, BUF_LEN);
n -= BUF_LEN;
left += BUF_LEN;
right += BUF_LEN;
}


if (n > 0) {
memcpy(buf, left, n);
memcpy(left, right, n);
memcpy(right, buf, n);
}
break;
}



}


// ***** Richard Heathfield's code *****

#define BUF_LEN 64 /* adjust to taste */
void *RH_mem_swap(void *vleft, void *vright, size_t n)
{
void *rc = vleft;
unsigned char buf[BUF_LEN] = {0};
unsigned char *left = vleft;
unsigned char *right = vright;


while(n > BUF_LEN)
{
memcpy(buf, left, BUF_LEN);
memcpy(left, right, BUF_LEN);
memcpy(right, buf, BUF_LEN);
n -= BUF_LEN;
left += BUF_LEN;
right += BUF_LEN;
}


if(n > 0)
{
memcpy(buf, left, n);
memcpy(left, right, n);
memcpy(right, buf, n);
}
return rc;

}


// ***** Malcolm McLean's code *****
void MM_memswap(void *ptr1, void *ptr2, size_t N)
{
unsigned char *cptr1 = ptr1;
unsigned char *cptr2 = ptr2;
unsigned char ch1, ch2;
size_t i;

for(i=0;i<N;i++)
{
ch1 = cptr1[i];
ch2 = cptr2[i];
if(ch1 != ch2)
{
cptr1[i] = ch2;
cptr2[i] = ch1;
}
}



}


#define ARRAY_SIZE_1 (10)
#define ARRAY_SIZE_2 (65)
char CHRmemswapTest[ARRAY_SIZE_1][ARRAY_SIZE_2] =
{"This is a test",
"A most egregious test.",
"Now is the time for all good men to come to the aid of the party",
"The quick brown fox jumped over the lazy dog.",
"I am thy Father's spirit",
"Condemn'd by night to walk the earth",
"Hope is the thing with feathers",
"That perches in the soul",
"And sings the tune without the words",
"And never stops at all"};


void printArray(void)
{
int intIndex1;
int intIndex2;
int intCount = 0;
for (intIndex1 = 0; intIndex1 < ARRAY_SIZE_1; intIndex1++)
{
for (intIndex2 = 0;
intIndex2 < ARRAY_SIZE_2;
intIndex2++)
{
printf("%c",
CHRmemswapTest[intIndex1][intIndex2]);
intCount++;
}
printf("\n");
}
printf("\n\nNumber of lines: %d: Number of characters: %d\n\n\n",
intIndex1,
intCount);
}

#include <time.h>
#define ITERATIONS 100000

int main(int argc,char *argv[])
{
printArray();
int intIndex1;
printf("%d\n", clock());
for (intIndex1 = 0; intIndex1 < ITERATIONS; intIndex1++)
{
spinoza1111_memswap(&(CHRmemswapTest[0][0]),
&(CHRmemswapTest[5][0]),
ARRAY_SIZE_2);
spinoza1111_memswap(&(CHRmemswapTest[2][0]),
&(CHRmemswapTest[7][0]),
ARRAY_SIZE_2);
spinoza1111_memswap(&(CHRmemswapTest[3][14]),
&(CHRmemswapTest[8][25]),
5);
}
printf("Nilges' result %d\n", clock());
printArray();
printf("%d\n", clock());
for (intIndex1 = 0; intIndex1 < ITERATIONS; intIndex1++)
{
ben_memswap(&(CHRmemswapTest[0][0]),
&(CHRmemswapTest[5][0]),
ARRAY_SIZE_2);
ben_memswap(&(CHRmemswapTest[2][0]),
&(CHRmemswapTest[7][0]),
ARRAY_SIZE_2);
ben_memswap(&(CHRmemswapTest[3][14]),
&(CHRmemswapTest[8][25]),
5);
}
printf("Ben's result %d\n", clock());
printArray();
printf("%d\n", clock());
for (intIndex1 = 0; intIndex1 < ITERATIONS; intIndex1++)
{
RH_mem_swap(&(CHRmemswapTest[0][0]),
&(CHRmemswapTest[5][0]),
ARRAY_SIZE_2);
RH_mem_swap(&(CHRmemswapTest[2][0]),
&(CHRmemswapTest[7][0]),
ARRAY_SIZE_2);
RH_mem_swap(&(CHRmemswapTest[3][14]),
&(CHRmemswapTest[8][25]),
5);
}
printf("Richard Heathfield's result %d\n", clock());
printArray();
printf("%d\n", clock());
for (intIndex1 = 0; intIndex1 < ITERATIONS; intIndex1++)
{
MM_memswap(&(CHRmemswapTest[0][0]),
&(CHRmemswapTest[5][0]),
ARRAY_SIZE_2);
MM_memswap(&(CHRmemswapTest[2][0]),
&(CHRmemswapTest[7][0]),
ARRAY_SIZE_2);
MM_memswap(&(CHRmemswapTest[3][14]),
&(CHRmemswapTest[8][25]),
5);
}
printf("Malcolm's result %d\n", clock());
printArray();
return 0;
}



This is a test
A most egregious test.
Now is the time for all good men to come to the aid of the party
The quick brown fox jumped over the lazy dog.
I am thy Father's spirit
Condemn'd by night to walk the earth
Hope is the thing with feathers
That perches in the soul
And sings the tune without the words
And never stops at all


Number of lines: 10: Number of characters: 650


31
Nilges' result 234
This is a test
A most egregious test.
Now is the time for all good men to come to the aid of the party
The quick brown fox jumped over the lazy dog.
I am thy Father's spirit
Condemn'd by night to walk the earth
Hope is the thing with feathers
That perches in the soul
And sings the tune without the words
And never stops at all


Number of lines: 10: Number of characters: 650


234
Ben's result 297
This is a test
A most egregious test.
Now is the time for all good men to come to the aid of the party
The quick brown fox jumped over the lazy dog.
I am thy Father's spirit
Condemn'd by night to walk the earth
Hope is the thing with feathers
That perches in the soul
And sings the tune without the words
And never stops at all


Number of lines: 10: Number of characters: 650


297
Richard Heathfield's result 406
This is a test
A most egregious test.
Now is the time for all good men to come to the aid of the party
The quick brown fox jumped over the lazy dog.
I am thy Father's spirit
Condemn'd by night to walk the earth
Hope is the thing with feathers
That perches in the soul
And sings the tune without the words
And never stops at all


Number of lines: 10: Number of characters: 650


422
Malcolm's result 609
This is a test
A most egregious test.
Now is the time for all good men to come to the aid of the party
The quick brown fox jumped over the lazy dog.
I am thy Father's spirit
Condemn'd by night to walk the earth
Hope is the thing with feathers
That perches in the soul
And sings the tune without the words
And never stops at all


Number of lines: 10: Number of characters: 650


.