Re: "Sorting" assignment

spinoza1111 <spinoza1111@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
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.

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.

<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.

<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?

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

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

It does not bother to zero the array (you'd need a clever optimiser
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.

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.

--
Ben.
.

Relevant Pages

  • Swap function driver
    ... various recently proposed memory swap functions. ... Filling the swap buffer with random data. ... unsigned char *right = vright; ...
    (comp.programming)
  • Re: Define SWAP through DUP and arithmetics?
    ... Sometimes just OVER is used instead of SWAP. ... We call it programming with abandon making a little ... loop but save important stack items before the loop ... The inlined 4 opcode version only overwrites one ...
    (comp.lang.forth)
  • Re: String reversing problem
    ... If there is no automatic memory available, ... controling some public service of your country. ... not to change in a live system the stack structure. ... swap you need a local variable". ...
    (comp.lang.c)
  • Re: C to Forth converter?
    ... stack operations to get a lot of stack parameters just right. ... CREATE DOES> SWAP CELLS +; ... ARRAY SEQUENCE #TURNS CELLS ALLOT ... gives you 371 which is the sequence NIP ROT DROP ...
    (comp.lang.forth)
  • Re: [PATCH][RFC] 4K stacks default, not a debug thing any more...?
    ... You'll have to swap, and if you do, you can swap ... two more pages in order to free enough RAM for the stack. ... only a few selected workload/compiler combos ... I guess no Fedora users run md+lvm+xfs then. ...
    (Linux-Kernel)