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

On Feb 12, 6:39 pm, Randy Howard <randyhow...@xxxxxxxxxxxxxxxxx>
wrote:
On Tue, 12 Feb 2008 03:15:43 -0600, spinoza1111 wrote
(in article
<57710a40-730f-4349-9433-0918703b0...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>):

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.

A few very short test lines doesn't really offer much chance for an
inline memswap() to be a win over versions making function calls, but
if you're happy with it...  Odds are memcpy is actually highly
optimized instead (despite the little game below), so I sort of suspect
you used small strings for a reason.  Perhaps the same as with the old
example we shall not name.  :P

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.

Unless you happen to know that you're always going to be calling it
with 64KB chunks, in which case it isn't a benefit.  Match the solution
to the data set when possible.  

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.

That's pretty amazing to see, given that Ben's "version" is basically
the one you're complaining about with an optimization up front for
small swaps.

The problem was that C forces the use of an assembler style, with the
threat of a return to GO TO, to implement Ben's optimization.

Did you really not notice?

It is in a contradictory fashion
relying on the quality of whatever library does memcpy while at the
same time it extends the library;

Hmm, apparently you really didn't.  Look at them both again.  How does
the one calling memcpy() that you do like not suffer as the one calling
memcpy() that you don't like?   That's some interesting bias you have
showing there.

Ben should have ended with Malcolm's or my own code and not used the
Heathfield stunt. So you're right.


if memcpy starts to suck over the
lifetime of the program (which of course can include changes to the
library) this will suck,

Yeah, it's so incredibly common in practice for memcpy() to be
deoptimized by updates and nobody bothers to notice or fix it.  No wait
a minute, it's not common at all.  

I've seen it, and the real problem is that it can be done. What part
of "risk and exposure costs through data systems that we don't know
about, yet" don't you understand?



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.

If you follow through on this, you wind up reinventing all of the
wheels in the libc, so as not to be "dependent" upon them for this goal

Actually, that won't happen, mostly because I won't do it. I would say
that a more optimized library won't do a lot of internal reuse.

of yours.  More chance for errors, less chance for taking advantage of
platform specific improvements without diving into unportable assembler
tricks, code reuse, etc.  One of the key benefits of using standard
functions in many cases is that the implementation is highly optimized
for the target hardware, so that you don't have to roll, benchmark and
test a hand-optimized (or inline assembler) version for every platform
you care about.  Of course it also simplifies your own code to not
rewrite versions for everything in the library to avoid using the
library.  That's pointless.

Trading all of that for some mythical concern over the remote chance of
a future version of the library suddenly getting much worse and nobody
noticing it, seems completely misdirected, imo.

It remains a mistake to confuse cleverness with a better algorithm.


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

Fortunately, it's not difficult to combine small functions in the
standard library to perform more complex actions.  In fact, that's the
whole point.

It is the whole point, but if any one C program can change the rules,
it's a waste of time.


C in my experience makes fools out of those who would create tools

It does seem to do a good job of making the fools obvious, I'll grant
you that one.  

I don't know who you are talking about. Certainly, if a language
moronizes people, it's the language's fault, likewise if it seems to
make fools wise. Here, knowing C's mistakes is ersatz for insight, and
posters other than myself have complained bitterly about this.

comp.programming should be C-free.


it overexposes things globally,

No, it doesn't.

Yes (sigh) it does. What part of #define don't you understand? What
part of "scope"?

you need to be far more expert in C details than I ever became to be
a C toolsmith.

I agree.

I would suggest that while microdominance games are in Foucault a
motor of power, actually playing them makes the rich richer and the
poor poorer. What do you want me to say? That you're a greater man
that I am? Fat chance at this point, buddy.



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

By your own admission, Ben's improvement on Richard's code was even
more clever, but for some reason you like it anyway, and even forgive
it for the very same traits that you find fault with in Richard's
original.  Even a complete noob programmer could recognize the bias
there.

I am biased, if that's the word, against Richard's lack of general
culture, his superficial corporate-level view of the world, his
religious enthusiasms, his confusion of clever code with a better
algorithm, and his continuing efforts to control this newsgroup.
Outside of all this, I am neutral and open-minded about Richard.



I'd only add that "many operating systems" freeze up and
piss me off when I am trying to get something done.

Get a better one.  I'm extremely pleased with the one I'm using atm,
but I have seen some real bad ones.  Most came from the same vendor in
the northwestern part of the US.  Think that's coincidence, or perhaps
climate related?  ;-)

The Mac freezes and goes boing too. I have no brief here for Windows,
but OSes are exhibit A when it comes to unmastered complexity, because
they are made for profit and not for use outside of Open Source, where
the problem is that they are made by slave labor. Willingly, but still
in chains.



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.

You miss the point.  I don't think he even mentioned speed originally.
That was your addition, iirc.  

You sleaze! He had to be otherwise he had no case. He was saying, in a
patronizing way and to McLean, that C could do multibyte memswaps. But
unless his code is faster than a simple for loop, his claim had no
value or truth content, because C can do multibyte memswaps only by
virtue of Turing's result, that any computer can do anything
computable in some amount of time and with some amount of memory.

I am getting real tired here of unscientific claims being made
selectively to wage campaigns of personal destruction. Clive got away
with using strlen in a for clause without so much as a peep from you
thugs whereas when I did so in 2003, you were libeling me to Apress,
because you respect him, because he tried to destroy Schildt. Here,
all that seems to matter to you is Richard's ability to confuse the
separate subjects of computer science and algorithms versus clever ape
coding in C by making a false claim about C.

It is intellectual dishonesty of the first order to say that a
computer or programming language is the only one you'll ever need
because it can do anything. It's a salesman's claim.

The question was, not whether C can memswap (by way of Turing we know
it can). It was "what is the best algorithm in abstract C, factoring
out the many different library implementations, of swapping memory?"
The answer is from Nilges, Bacarisse and McLean and not Heathfield. It
is that you skip unnecessary and costly exchanges where possible and
optimize small moves. And if you use a *** ugly dropthrough switch to
do the latter, admit that this shows a flaw in C.

It may in fact be the case to be bad practice to write a C library
which uses any other library function. This is because you could never
ensure that the reused function would not be redefined somewhere in
the library source. My understanding is that conceptually, the source
of the library is presented every time any program is compiled in such
a way that I can redefine any library function by a macro.

Now, correct me if I'm wrong, but wouldn't this apply to the library
if the definition was presented before the library #include? And
doesn't this mean I can redefine the entire C library in any
application program?

Even if I am wrong about this, C provides a "power" to redefine so
inapprorpriately that you cannot seriously suggest that if it were
proposed today as a new language, it would be laughed out of court.

Therefore it is professional malpractice to make such overblown claims
as RH frequently makes for C. It is personal discourtesy to base
campaigns of personal destruction on these false claims. It is
vandalism to dominate comp.programming with C programming.

RH clearly meant to show that C could do it fast IF you used a buffer.
This was an admission that C in fact provides no fast path without
jiggery-pokery to a fast hardware move and will be in consequence
slower than optimized Java...because the string encapsulation in the
latter means that specific implementations have a clear way, one not
dependent on the competence of applications programmers, of optimizing
large string moves. Nor can this competence be rendered for naught by
some clown redefining memcpy.

An object oriented memswap with state could remember, with complete
safety, previous swap jobs such that the string lengths are suitably
bounded using RH's trick with far less risk. This code would operate
not as redefined potentially by some clown but according to the Java
or C sharp contract.



He could have written his own memcpy() implementation to avoid using
the libc function, but odds are in a cross-platform test, it would lose
out to many, if not all of them since they would be tuned for the
target architecture in ways often not possible with pure portable code
that doesn't leverage the standard library implementation.  

This certainly shouldn't be news today.  Most knew it ages ago.

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

A trend is emerging in these drag races you keep encouraging.  Do you
see it?

I'm not encouraging NASCAR meets. That would be you. You are
continually viewing too many issues through the lens of dominance and
control.

Do you suppose I would have posted the results if I'd been playing
your stupid games? I'm showing you that your whole world-view is
completely flawed, because to get what speed he was able to get, your
buddy Heathfield can only think as a coder, and trade space for time
in such a way that the resultant product is top-heavy with
optimizations that don't belong in application code and which
constitute hidden exposures during ports.

I wanted Visual Basic, before and after .Net, to process strings in
the way Rexx processes strings. In particular, I wanted to be able to
pick out individual words in strings independent of the number of
extra spaces between words. So, I wrote a tool to do so.

But this doesn't mean that VB can pick out words in strings
independent of the number of extra spaces between words.

Nor does RH's code prove Malcolm wrong.

Game, set and match.


// ***** Ben Bacarisse's code *****
#define BUF_LEN 64
void ben_memswap(void *vleft, void *vright, size_t n)
{

[snip]









Ê Ê Ê Ê Ê Ê Ê Êmemcpy(buf, left, BUF_LEN);
Ê Ê Ê Ê Ê Ê Ê Êmemcpy(left, right, BUF_LEN);
Ê Ê Ê Ê Ê Ê Ê Êmemcpy(right, buf, BUF_LEN);
[snip]
}
// ***** Richard Heathfield's code *****

#define BUF_LEN 64 /* adjust to taste */
void *RH_mem_swap(void *vleft, void *vright, size_t n)
{
[snip]
Ê Ê memcpy(buf, left, BUF_LEN);
Ê Ê memcpy(left, right, BUF_LEN);
Ê Ê memcpy(right, buf, BUF_LEN);
[snip]
}

Isn't it weird how the "good one" and the "bad one" both call memcpy(),
which you tell us is wrong?  And they both do it the same way too.  How
can this be?

#include <time.h>
#define ITERATIONS 100000

int main(int argc,char *argv[])
{
Ê Ê Ê Ê printArray();
Ê Ê Ê Ê int intIndex1;
Ê Ê Ê Ê printf("%d\n", clock());

What type does clock() return?  

Yes, we need to take your suggestion and divide it by clocks per
second. That was left to the reader. The lccwin-32 documentation
mentions this but I was too lazy to implement it. You are aware that
mathematically, that division would not change anything unless some
clown sneaks on to my computer and changes my library.

What type does %d imply for its argument?  

All we really know portably is that it is an arithmetic type.

See also the other slew of such calls.  

You might sample clock_t values before and after each, then use the
difference, divided by CLOCKS_PER_SEC (using double throughout the
calculation) to get an elapsed time value and display that with %f.  
Then when somebody runs the same test on another architecture, (or a
system with another timer tick rate) the results can be reasonably
compared.

That, or use some other method to measure it, like Ben did.

--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
 who have not got it."  - George Bernard Shaw- Hide quoted text -

- Show quoted text -

My solution, and Malcolm's, are the best because they buy speed
WITHOUT any dependencies on a legacy library and programming language
that cause more trouble then they are worth. Ben's will be the best
once he figures out a way of not falling through a case statement,
since this is bad style from the point of view of the casual program
reader who, in this day and age, may not understand the details of a
poorly designed construct.

.