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

Two lines, and a small character string, were exchanged repeatedly,
first by "my" code, then by Ben's, then by Richard's, then by
Malcolms, an even number of times by each version in such a way that
there is no net change.

I used lccwin-32 on a Compaq laptop.

Everybunny's code worked correctly the first time.

Ben kicked *** in this benchmark because the third exchange was only
five characters long, demonstrating the wisdom of handling small
common cases fast. I would have coded it without using switch and
dropthrough if possible but cannot think of a better way that is
idiomatic to C: a recursive call in each switch case for the next
smaller string would be academically elegant but probably suck. The
problem being that C provides no primitive for "moving a string",
which most of my platforms (commencing with the IBM 1401 and
continuing through PL.I, rexx, and VB) do present and in the
scientific computing tradition this is an afterthought, as it is in C.
C Sharp remedies this but at a cost in microperformance (big deal).

Richard's use of a "buffer" is clearly also a win for this benchmark
(but not as good as Ben's optimization) but I remain opposed to it for
the reasons I have given already. It is in a contradictory fashion
relying on the quality of whatever library does memcpy while at the
same time it extends the library; if memcpy starts to suck over the
lifetime of the program (which of course can include changes to the
library) this will suck, meaning that the "library" considered as now
including the Heathfield memswap() will show perverse behavior over
time, adding to the cost of software maintenance. My theorem being
that for the same reason each library function should be a black box,
its performance should be either independent of or smoothly and
predictably related to other library functions, so that change of
platforms don't generate research and rework.

Put as simply as I can, and based on my being down Richard's path in C
in the early 1990s, my saw or maxim would be "don't extend the C
library with your tools while expecting the library to remain the same
and to serve you". C in my experience makes fools out of those who
would create tools because it overexposes things globally, and you
need to be far more expert in C details than I ever became to be a C
toolsmith. Guess what: this is wrong, since creating tools is the best
way to build large software systems, and if you have to fight the
system to do so, the system is at fault.

I know the computer pseudo-science maxim, "the poor workman blames his
tools". Cf. Adorno, The Jargon of Authenticity: in a fashion derived
from the overrated Heidegger, we are mystified and put in our place by
this mythos. I'd say that in Paleolithic times, it was used by homo
erectus to criticise more evolved homo faber for not being content to
pick up the closest bone, and to desire instead to make a better tool.

This is not based on personalities apart from Richard's modus operandi
in coding, which is, at times, and in my opinion, to be clever in a
fashion that for me is no longer useful, especially when you exit C,
as I have and you should. Yes, I know that "many operating systems are
written in C". As I have said, their "C" is rich and strange in my
experience. I'd only add that "many operating systems" freeze up and
piss me off when I am trying to get something done.

Anyway, if I had to extend the C library, I wouldn't do a lot of
"reuse" solely for the purpose of speed as RH has done, at least not
as my first try. I'd try, for each function point, to think of an
algorithm for best speed and I maintain that skipping unnecessary
exchanges should be job one. It saves some time, and isn't exposed to
the way memcpy might work, or fail to work, over the lifetime of the
whole shebang.

Dijkstra asks us from beyond the grave to consider each program not as
a single program but only the first version of a set of versions and
this is driving my thinking on this matter, not any desire to pimp
Richard Heathfield's ***.


On Feb 12, 3:59 pm, spinoza1111 <spinoza1...@xxxxxxxxx> wrote:
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

.