Re: "Sorting" assignment

On Feb 11, 1:36 am, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
spinoza1111<spinoza1...@xxxxxxxxx> writes:
On Feb 10, 11:23 pm, moi <r...@xxxxxxxxxxxxxxxxxxx> wrote:
On Sun, 10 Feb 2008 06:04:01 -0800,spinoza1111wrote:
<snip>
My xor looks I agree more and more like a brain fart.

Yes, it was not a good idea.  The trouble is, you have not offered
anything better.

My point,
however, was different. Heathfield's code was a vanity tool. It might
optimize on some platforms, but not on others.

How can that be anything other than always true of all code?  The
point you've missed is that it is likely to be fast on most systems

Probability not a single number. The problem is that it's
unpredictable with in all probability (sic) a large std deviation.

with good implementations, and that is about the best you ask for.  If
you think using memcpy a block at a time is not the best way to swap
arbitrary data, suggest something better.

I did. The Nike philosophy: Just Do It. And if efficiency is a
consideration, use your head and not a buffer, and reflect that data
to be swapped is likely to have a great deal of commonality.


McLean was right in his
initial claim, that C, as a language, doesn't have memswap, and
Heathfield, as usual, screwed the pooch in attempting to refute him.

There was no attempt at refutation as far as I could see.  It is a
matter of fact that C has no swap operation and no one has denied
that.  The problem is not too hard to get round, that is the point.

Heathfield said it did using his usual strange logic: C can do
anything because it's Turing complete! Alert the media!

<snip>

asking for trouble given what passes for good taste here) in a global

It was allocated on the stack.

area. This could be fixed easily by making it a local array, although

It was allocated on the stack.

Right. Boom, there goes the stack again, eating memory.

That is just sniping.  64 bytes.  If memory is so very tight, use a
smaller buffer (it was, after all, configurable) but a small local
array is perfectly reasonable in almost all situations.

Let's all be "perfectly reasonable". In actuality, UNNECESSARY small
local arrays are a heap clutter nightmare and if you can avoid them by
exploiting the fact that in maybe 60% of cases the bytes are the same,
then do so.


<snip>

My point remains: that instead of using a global buffer which provides

It was on the stack.

I believe it was global in the original code.

Reference?

It wasn't part of an enclosing block.

But as you concede,
there are performance issues either way in grabbing the storage, and
my solution (or just swapping byte by byte without using Xor) doesn't
have this problem.

Byte-by-byte swapping will almost certainly be slower for anything but
the very smallest objects (or the very worst C implementations).

There you go again. "I'm perfectly reasonable: you're slower than
***". I don't have to believe you. My apriori reasoning tells me that
allocating a buffer to do what the library should do is asking for
trouble now or later.


In the spirit of being practical, here is what I'd do if I needed
a portable, flexible and fast swap routine:

void mem_swap(void *vleft, void *vright, size_t n)
{
     unsigned char buf[BUF_LEN];

Oh no

     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;

I guess this is untested extempore since don't case statements have to
be blocks? Admittedly just a detail, but do you intend this to be C,
and am I right in thinking that each case must be a block? Or did I
get into the habit of doing this in 1990 just to keep things neat?

     case 6:
          t = left[5]; left[5] = right[5]; right[5] = t;

Omigod we're falling through a case statement. I think I'm gonna be
sick. Ben, you're the C expert. What are we doing here?

     case 5:
          t = left[4]; left[4] = right[4]; right[4] = t;

You're pulling my leg, right?

     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;

So, I guess the addresses are precomputed here and this handles the
most frequent cases, if C falls through in the absence of a break
(yecchhhhh). You're overdrawn at the Benefit of the Doubt Bank and
pushing your luck.

     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);

This is just Richard's code. Are you putting me on?

               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;
     }

}

It does not bother to zero the array (you'd need a clever optimiser

You don't need to.

for that not to cost something) and it special cases small object
swaps in a portable way, but otherwise it is just Richard Heathfield's
code.

...which sucked...


In production code, I'd have a macro for the numbered cases and a
configuration parameter so the number of them can be tuned from one
system to another.  On my Pentium laptop, RH's code is faster than byte
copying at object sizes of 8 and above, so I've special-cased 7 and
below.

I agree that handling special cases is a good idea and I'm amazed that
the above compiled and worked, since I thought, not being a current
and *au fait* C expert, that (1) each case must be one statement,
perhaps a compound but single statement and (2) it's bad practice to
fall through in a case. C Sharp requires a break and this is a Good
Thing, since the C case statement was such a mess.

My biggest objection is that you've written the key operation of
exchange so many times that if it itself is changed it needs to be
changed in too many places. A clever maintenance nightmare.

Here's my solution, again:

void memswap(char *ptrToA, char *ptrToB, int intLength)
{
intIndex1 = 0;
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.

.