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

On Feb 13, 5:23 am, Randy Howard <randyhow...@xxxxxxxxxxxxxxxxx>
wrote:
On Tue, 12 Feb 2008 06:41:21 -0600,spinoza1111wrote
(in article
<def77da1-da1a-4713-9106-3636e78f8...@xxxxxxxxxxxxxxxxxxxxxxxxxxx>):

On Feb 12, 6:39 pm, Randy Howard <randyhow...@xxxxxxxxxxxxxxxxx>
wrote:
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.

goto in C, any "GO TO" feature of a language isn't a threat. A jmp
instruction is a goto. Look at the assembler output of your program
sometime. It's filled with gotos. Language syntax just hides it for
you. Goto isn't /always/ bad.

Goto is *always* bad. Even in assembler, it must be used in a
disciplined fashion, essentially ensuring that all Go Tos flow either
downward, or up to the heads of clear loops, giving the assembler
code, considered as a flowchart, the Bohm-Jacopini structures in such
a way that the program can be rewritten, without any code motion, as a
structured program once you have a structured language. I wrote about
this years ago, and called in "virtually structured programming" in a
1976 Computerworld article.



Yes, almost everyone has read Dijkstra's 1968 paper. He talks about
the "unbridled use of the go to statement", and that is a valid
concern. A lot of people have thought about it a lot more in the last
40 years and have managed to convince themselves that it isn't an
outright ban as some like to pretend. The people claiming such quite
often haven't even read it, they just heard it somewhere, often from an
early CS professor.

An "outright ban" misses the point. In 1401 and 360 assembler, I
couldn't not use Go To, but I could force it to reflect only the Bohm
Jacopini structures of straight line code, if then and do while
without loss of "efficiency".




For some more extensive discussions, consider these:http://www.ecn.purdue.edu/ParaMount/papers/rubin87goto.pdf
(The part by Frank Rubin, starting halfway down the third column)

To which of course Dijkstra wrote the following response:http://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1009.html

David Tribble wrote a more recent take on it, in rather long form:http://david.tribble.com/text/goto.html

There are plenty more of course, but its safe to say that the jury is
still out on it being a "ban". Finding offense because a language
construct like switch() can be used in a fashion that reminds you too
much of a goto is a weak attempt.

The fact is that you have to do it Ben's way means two things. One is
that Ben's a great programmer. The other is that C sucks.

Strings should be black box encapsulated primitives and the
distinction alone between strcpy and memcpy means that they aren't in
C.

And by the way, it's not an "assembler style". You want to see the
real deal? Take a look at memcpy.s on a modern OS with an open source
library. Both of the versions your groaning about are heaps more
readable, not to mention of course being portable. To get anything
like that performance, you have to either suffer inline assembler, or
stop being upset at the notion of calling memcpy() from the lib.

Hacking isn't the only way of increasing performance. The fellow who
realized that if the left hand side of OR is true you need not
evaluate the rhs probably saved more CPU time than any close to the
metal hacker.



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.

Well, at least you admitted it. Isn't amazing how much those bias
blinders can obscure reality and inhibit rational thought?

Excuse me, don't get excited, you're right once in a while.


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?

I understand the issues quite well. You must learn to balance risk,
and the risk of that happening is imo considerably less than the risk
of a home-grown implementation being flawed for something that is
typically heavily optimized on every platform.

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.

So you don't even follow your own advice. Well, I guess that should
have been predicted. Doom on me.

We're talking about C, which doesn't encourage good practice.

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.

Clearly. Your XOR attempt was the proof of that. We do have
relatively simple solutions, that do not involve tricks, merely use of
an existing age old API everyone knows, and they work better to boot.

As soon as I started coding I realized XOR wasn't going to fly, so
drop it. What was really great was my insight that you need to avoid
moving bytes. Wasn't that great? It was great. Except Ben's code ran
faster.


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.

Change what rules? If you think the ability of a program to do
something not already provided on the platform is a downside, then you
would logically conclude that nobody should write any software at all.
I can sort of see why you might arrive at such a conclusion, but many
others, including myself don't see it that way. ;-)

The problem is that C does it the wrong way. It forces the user of
memcpy to get the string length from some other place, conceptually,
than the string itself considered as an object.


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,

If someone goes jogging with a hunting knife hanging on a rope loop
around their neck, and one day they trip and fall, and the knife stabs
them through the heart, is it the knife at fault, or did they simply
employ it in a moronic fashion?

Bad analogy. The problem in C is that it prevents people from
"jogging", learning computer science, without first knowing bad
practises such as "I can modify value parameters" and false
propositions such as "there are two types of strings: strings with
Nul, and strings without Nul".



People misuse tools every single day, a fact which keeps the legal
profession extremely busy, arguing that their morons should be
compensated because an inanimate object couldn't protect said moron
from their own stupidity.

Excuse me, people have the right to a steadily safer and more peaceful
world. I don't hold with the notion that we should have guns and C
compilers just so that men can prove a masculinity that would be
better exercised in solving the world's REAL problems, such as poverty
and global warming.


Programming languages are no better than any other tool at reversing
such problems.

likewise if it seems to make fools wise.

A mere look at the warning label on a newly purchased clothes iron,
that warns you not to attempt to iron an item of clothing /while you
are wearing it/ should lead you in the right direction. :)




Here, knowing C's mistakes is ersatz for insight, and
posters other than myself have complained bitterly about this.

There is nothing confusing about the functions under discussion. They
are dreadfully simple really. Ben's performance optimization for small
swaps isn't completely novel even, such things have been done in C and
many other languages for ages.

comp.programming should be C-free.

First, practice what you preach. Second, I see no reason for you to
decide what languages can appear in c.p, especially given that C is one
of the most widely used languages on the planet, and has been for
decades.

Hey, I had the balls to step out of my comfort zone and return to C in
order to civilize this newsgroup by using "your" language, and I was
willing to embarass myself to make recruit errors all over again. This
is called being able to walk and chew gum at the same time.

Now it's your turn to submit VB.Net code.


You might as well ask a group discussing automobiles to refuse to talk
about Fords, because the Pinto had a problem with exploding.

Sounds like an excellent idea, not only because the Pinto sucked but
because (cf. David Halberstam, The Reckoning) Ford's whole culture
created untold waste, for example in its refusal to e-coat cars before
delivery, which created a whole industry of "rust-proofing" when the
customer had a right to this as part of a usable product in any wet or
cold climate.


it overexposes things globally,

No, it doesn't.

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

Then you really don't understand "global" at all.

-- xyz.c --

#define FOO 27

/* some more code */
....

-- end of xyz.c --

-- main.c --

#include <stdio.h>
int main(void)
{
printf("%d\n", FOO);
return 0;

}

-- end of main.c --

Hmm, why can't these be compiled and linked, clearly in your universe,
#define is a global. What part of /scope/ do you not understand?

int a()
{
#define FOO 27
return 0;
}
#include <stdio.h>

int main(void)
{
printf("%d", FOO);
}

Sounds to me that you may not understand global. The braces
surrounding the definition of FOO are ignored, aren't they. And your
code compiles once you take the garbage out.

More importantly, why do yo not realize that macro definitions are
optional, and if you want a narrower scope for something, you don't
have to use them. C doesn't /force/ people to use it. You could
easily write the functions under discussion without using them at all.

Cheese, what part of "nested macro definition" don't you understand?
The C preprocessor is line by line and unnested which makes it useless
for its intended purpose, and highly dangerous.

In the code snippet you in fact failed to define FOO properly to
protect it, as much as possible, against conflicts with adjoining
text:

#define FOO (27)

I can't think of any real contexts where FOO as written would fail,
but this is basic good practice as seen in

#define CANOE a+b

which breaks in

CANOE * 3


However, a primary usage of #define macros is to have a convenient way
to eliminate magic numbers from code, so that the same number (64 in
this case) doesn't get splashed all over the place, which is a
maintenance concern.

No, macros were developed inside software companies to generate code
accurately for multiple customers. Their flaw was that they dealt with
source text. The modern answer are generics in OO. Check 'em out. They
are not supported nor never will be in C.



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

I agree.

What do you want me to say? That you're a greater man
that I am? Fat chance at this point, buddy.

I expected nothing of the sort. I simply agreed with you. Sadly, and
as we have seen before, you sometimes get angry when people agree with
you. If this is a transference of anger over you not getting an
argument, or not, I can't tell from here.

I understand better. Thanks for the clarification.

This doesn't change your track record, but it's refreshing.

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.

Unfortunately, /none/ of that has (or ...

read more »

.

Relevant Pages

  • Re: multimethod + multiple inheritance
    ... language) then your programming level will be limited. ... context where optimization allows the object to never exists as such). ... I don't care that I could do most of the work using design ... Predicate dispatch handles logical combination of values to select the ...
    (comp.object)
  • Re: SETF and variable issues in Self Similar program.
    ... The way to get a compiler to optimize a tail-call ... call optimization turned on. ... It changes the semantics of the language in a big way. ... In Common Lisp it has to interact with condition handling, ...
    (comp.lang.lisp)
  • Re: Case sensitivity in programming languages.
    ... is a variable called $foo I expect $Foo and $FOO to mean the same thing, ... Programmers who deliberately create different variables with the same name but different case are bad programmers, but a *proper* language removes the possibility for such bad programming by ignoring case and treating all the variables as a single variable. ... Having $foo, $Foo and $FOO mean different things causes more problems than it solves, as does haing different functions called readfile(), readFileand ReadFile. ...
    (comp.lang.php)
  • Re: Relative merits of Lisp-1 vs. Lisp-2?
    ... confusing things like (foo foo) ... Somewhat simplified language description, somewhat simplified ... For Lisp-2: ... have only Scheme but in the other world you admit that both Scheme and ...
    (comp.lang.lisp)
  • Re: What is the reason for this syntax?
    ... // adding 1 to foo ... language will understand a case statement. ... rigidity however unlike programming languages spoken and written ... adversly affect the readability of the language itself be addressed ...
    (comp.lang.ruby)