Re: Letter to US Sen. Byron Dorgan re unpaid overtime

From: Edward G. Nilges (spinoza1111_at_yahoo.com)
Date: 12/21/03 

Date: 21 Dec 2003 13:57:35 -0800

Richard Heathfield <dontmail@address.co.uk.invalid> wrote in message news:<bs3sn1$hv1$1@sparta.btinternet.com>...
> Edward G. Nilges wrote:
>
> >> >>
> >> > Unlike a For loop in Basic or Fortran, the condition in C has to be
> >> > repeatedly evaluated.
> >>
> >> You make "has to be" sound like a problem, whereas it is generally
> >> considered to be a convenience by those who use the C language.
> >>
> >> I just tested your assertion re Basic in VB.NET; the assertion is
> >> correct,
> >
> > You had to test it. You should have known it.
>
> Don't be silly. I make no claims to being a VB.NET programmer. Of course, if
> VB.NET were standardised, I could have looked the answer up in the
> Standard. But it isn't, so I couldn't.

You'll notice no campaign of libel based on your not being a VB.Net
programmer. Nonetheless, when I resumed, in response to a request
(made I now know in bad faith) by Chris Sonnack, with C code,
confessing at the time to having abandoned C, I was subject to a
campaign of libel. I suggest in future you emulate my conduct which is
truer than yours to the ethics of posting. Thank you.

>
> >> which makes a pleasant change. Note that it doesn't really matter which
> >> of these choices the language makes, as long as the choice is clearly
> >> documented, and as long as the programmer knows which choice was made. If
> >> the choice is clearly documented, it is not the fault of the language if
> >> the programmer screws it up.
> >>
> > This is nonsense. Ritchie SCREWED UP in designing the for loop because
> > the expression of the limit condition, in evaluating variables, is
> > both less efficient and less safe than the Fortran and Basic standard.
>
> I beg to differ. If you wish the limiting expression to be calculated once,
> you need only calculate it once. If you wish it to be calculated each time,
> you have that choice. It's a CHOICE.
>
> If you want Fortran or Basic, you know where to find them.

No, I want Algol. I shall have to develop a Windows compiler myself it
appears (Fujitsu may have one).

I also want an END to a tribalized and regressive culture which is
based upon C, and a dreamlike inability to get beyond the passive
aggression of C.

>
> > The C for loop is actually trying to do what a do loop does. In Basic
> > and Fortran there is a clean conceptual separation between the for and
> > the do, but in C, you can express a complex condition, which takes
> > into account changes in variable values, in a for. This is messy, to
> > say the least.
>
> C programmers do not find it so. If you don't like C, don't use it. But to
> try to impose your likes and dislikes on others is an exercise doomed to
> failure.
>
It appears to me that this is what you do, the only difference happen
to be that your opinions coincide with those of the tribe.

 
> > It means that the C programmer has to think in Fortran terms to write
> > clear code.
>
> No, it means that the C programmer had jolly well better be able to think in
> C terms to write clear code.
>
I find the use of "clear" disturbing since it is NEVER qualified with
respect to a reader response.
 
> > It's also less efficient since the possibly changed variables have to
> > be re-accessed each time through each of the billions of for
> > statements executed around the world, time which could be better used
> > to find a cure for aids. Or something.
>
> I have not found C to be wanting in the speed department.
>
>
> >> > but you are right, to a limited extent: the C code will
> >> > repeatedly evaluate the strlen function.
> >>
> >> Yes. That the condition is evaluated afresh on each iteration is useful,
> >> provided you know it happens.
> >>
> > Only if you engage in the unsafe practice of modifying for loop limits
> > inside a for loop.
>
> I often invoke the terminating condition of a for loop manually inside the
> loop, and do not find it even remotely unsafe. Example follows (E&OE - this
> is hand-typed, not an extract from an actual program):
>
> for(thisline = 0; SUCCESS == rc && thisline < numlines; ++thisline)
> {
> rc = ProcessLine(line[thisline]);
> }
>
This is not a for loop in the Fortran sense and it shows the kind of
sloppy thinking that results from confusing a programming language
with programming.

Also, this is an ugly piece of code. It increments the line counter
unnecessarily since rc is set to a value, then thisline is incremented
(for some strange reason, in a nonstandard fashion, in a
preincrement), then the condition is evaluated.

Following the code thisline points EITHER one past the bad line or one
past the number of lines. To process the bad line for an error report,
you have to undo the final increment of thisline.

The left and right braces are useless unless you have a consistent
standard that dictates their use even around loops that contain one
statement.

Why not just use a separate test and a break? Here is better and
cleaner code.

for (intLineIndex = 0; intLineIndex < intLineCount; intLineIndex++)
   if (processLine(strLine[intLineIndex]) != SUCCESS) break;

>
> > The original intent of the grandfather construct,
> > the Do loop of Fortran, was to make processes using vectors and arrays
> > predictable.
>
> Who cares? The discussion here is about C loops, not Fortran loops. If you
> want to discuss Fortran loops, that's fine, but do it with someone else,
> okay?
>
Not okay at all. This newsgroup's charter is general programming.
Therefore discussion of programming as labor, its interface with
society, and comparative programming language linguistics are all
on-topic. Defense of C and its commercial promotion is not on-topic
under the charter.

The charter is not what you think it is and it is not to be twisted at
your convenience.

> > Basic does this because changes to control variables are not reflected
> > in the evaluation of its For clause. C does not.
>
> I consider that to be a strength of C, in that it does what I expect. I was
> surprised to find that VB.NET does things differently.
>
Your expectation is malformed by overexposure to C.

The original motivation of the Fortran Do loop was to trip through
arrays of fixed size, known in advance, either as a constant or as a
value calculated prior to the for loop.

Because C was never designed, its for loop reinvents what its do loop,
does.

You have normed what is in fact a design flaw.

 
> >> > The problem is that 9 out of ten "competent" programmers are
> >> > completely unaware of how C versus Fortran and Basic evaluate what
> >> > looks like the same statement,
> >>
> >> Looks like you were one of the nine, Mr Nilges.
> >>
> > You reminded me of a C fact which I knew when I implemented a C
> > compiler in 1993.
>
> I do not believe that you are capable of writing a conforming C compiler.
> Please provide evidence that you have done so, if you wish to be
> persuasive.
>
I've clarified this. I wrote a subset compiler for business rules that
doesn't support typedef.
 
> > The phenomenon is that I have forgotten more about C
> > than you may know.
>
> Yes, we established that this is trivially true, because I don't actually
> know everything there is to know about C. (I despair of your actually
> understanding this reply.)
>
> > When I implemented the for loop I looked up the ANSI standard and
> > realized that I had to evaluate the for.
>
> What on earth does that mean? "evaluate the for"? It's a meaningless
> statement in terms of C. And anyway, if you're writing a C compiler, you
> don't have to do /anything/ special for the for-loop condition. It's just
> an expression-opt, like any other expression-opt. No Special Treatment
> Required. Duh.
>
Duh? Give me a break.

To implement a for loop in Basic, you have two choices. You can create
temporary variables for the limit value and the step or you can create
a "frame" on the runtime stack.

The C implementation means you have to generate code for the
initializer, an assembly language label for the start of the actual
loop, code to evaluate the expression in the loop condition, a branch
if the expression is false (branch on zero), the code for the block or
statement in the body of the for, and the expression in the increment
part. You must then generate the assembler label for the end of the
for, and back up to the loop condition, and update the branch taken
when the expression is false.

However, there is a further complexity. You need to maintain in fact a
stack in the compiler for all nesting constructions including fors,
dos, and ifs. Objects in this stack need to contain a type indicator.

When this stack top contains a for and you arrive at the end of the
block for the for, you must get the location of the for test branch
from the top of the stack.

Have you ever written a compiler? What is your university degree in?
All due respect but you may not be qualified to argue for C (which is
need I remind you contrary to the ng charter) if you cannot describe
how it is compiled.
 
> > Whereas in the Basic compiler for my book I simply load the stack with
> > the constant or nonconstant value.
> >
> > In other words, C, like James Joyce's history, is a nightmare from
> > which I would like to awake.
>
> C is clearly not the right language for you. I'm beginning to think ITA
> might be the right language for you, but C definitely isn't. I think you'd
> be happier playing in a BASIC sandbox.
>
> > My point was that the entire issue is ignored in most programming
> > circles other than this.
>
> There is /no/ real issue here. You wrote some crap C code. Those who know
> the C language and who read your code saw it was crap. You blamed C. We
> showed that C is not to blame. End of story.
>
> >> > but will still feel qualified to tell
> >> > you all about what is efficient or not
> >>
> >> Yes, it /still/ looks like you're one of the nine. You are describing
> >> your own behaviour perfectly.
> >
> > No, we're not talking about rote memory of one language.
>
> Rather, we're talking about common sense macro-efficiency gains (or, in your
> case, losses).
>
> > We're talking
> > about the awareness of the very issue itself. I am completely not
> > interested in your continued sniping since when I need the knowledge I
> > go to the book.
>
> THEN WHY DIDN'T YOU?
>
Because you are not worth the time.
> Fcol.
>
>
> >>
> >> > Furthermore, it is only micro-inefficient in code otherwise
> >> > well-organized to use strlen in the for condition,
> >>
> >> **splutter!!!**
> >
> > splut. Your point being?
>
> Can you say O(n*n)?

Again, you appear to know nothing about runtime. To find the end of
the string a single instruction, which scans a string for a character,
is needed.

>
> >> > because determining
> >> > the strlen is the execution of one instruction, that which scans for
> >> > Nul.
> >>
> >> But the scanning takes time.
> >
> > Read Kant. Everything takes time. And if you would disabuse yourself
> > of the very idea that everything must happen at once, and that we
> > should learn one language, and remember all of its silly details, you
> > would be a better person.
>
> We don't need everything to happen at once, but on the other hand we cannot
> ignore efficiency. You seem to be arguing that it's okay for your code to
> be O(n*n) when anyone with half a brain could achieve the same objective in
> O(n) (for significant n). Well, if that really is what you're arguing, few
> here will continue to wonder about your competence.
>
>
> >> > If the code is otherwise well-organized you can be certain that
> >> > (1) the string will not be overlong, for you will know the programmer
> >> > hasn't misused strings to contain what should have been data bases
> >>
> >> O(n*n) doesn't need a huge n for things to get very slow very fast.
> >> Furthermore, it is not always possible for the programmer to know in
> >> advance just how big a string his program will be expected to handle. The
> >> grep program is a fine example of this.
> >>
> > If you are truly writing a truly general tool, then, consider writing
> >
> > for ( intLength = strlen(strInstring), intIndex1 = 0;
> > intIndex < intLength;
> > intIndex++ )
>
> Don't be silly. intLength is a hopeless name, which suggests that the object
> is of type int whereas any competent C programmer knows that strlen returns
> size_t.
>
This knowledge it is now plain is foregrounded and replaces knowledge
independent of language. size_t, FYI, is easily converted, probably,
again, by a single instruction, to int.
 
> > But your comments on strlen suggest you may be ignorant of modern
> > compiler optimization.
>
> Here is a simple program which hashes each line in a file. As you can see, I
> have implemented it in two ways. The first way caches the length of the
> string in a temp, a la Heathfield. The second does not, a la Nilges.
>
> I compiled each version using gcc's -O2 optimisation switch. Let's have a
> look at the code, and then the results:
>
> $ cat foo.c
> #include <stdio.h>
> #include <string.h>
>
> unsigned long hash(const char *s)
> {
> unsigned long n = 0;
> size_t len = strlen(s);
> size_t i;
> for(i = 0; i < len; i++)
> {
> n *= 33;
> n += s[i];
> }
> return n;
> }
>
> int main(void)
> {
> char buf[2048] = {0};
> while(fgets(buf, sizeof buf, stdin))
> {
> printf("%lu\n", hash(buf));
>
> }
> return 0;
> }
>
> This version uses strlen-caching.
>
> (test.in has 7752 lines and is 219554 bytes in size.)
>
> $ time ./foo < test.in > test.out
>
> real 0m0.053s
> user 0m0.040s
> sys 0m0.020s
>
> Here is the uncached equivalent:
>
> unsigned long hash(const char *s)
> {
> unsigned long n = 0;
> size_t i;
> for(i = 0; i < strlen(s); i++)
> {
> n *= 33;
> n += s[i];
> }
> return n;
> }
>
> Same optimisation level - fairly aggressive but not dangerously so:
> $ time ./foo < test.in > test.out
>
> real 0m0.113s
> user 0m0.100s
> sys 0m0.010s
>
> Your technique is still way slower, you see.

Trivia.

>
> > A good optimizer would not track invariants in loops as variables, it
> > would extend the tracking to expressions including
> > strlen(strInstring).
>
> Having seen your C code, I am not prepared to accept anything you say about
> optimisation at face value. Note that the compiler /cannot/ legitimately
> make this assumption without understanding what strlen actually /is/. That
> would mean putting code in specifically for optimising strlen calls in the
> particular case where the length of the string doesn't change between
> invocations. Are you seriously suggesting this? Does anyone here know of
> /any/ compiler that does this?

Cf. Stephen Muchnick, Advanced Compiler Design and Optimization,
Morgan Kaufman.

>
> > It would add strInstring to its table of invariant variables in the
> > for, or conversely make a short table of pointers to variables which
> > change in the loop.
> >
> > If the loop does not contain any calls to external functions and no
> > aliased references, this short table is "safe" therefore the optimizer
> > can create in effect the above code, and a temp variable for
> > intLength, thus avoiding discovering strlen each time.
>
> But strlen /is/ an external function.

Might be redefined: but the compiler KNOWS when this happens, and in
99.999% of cases, strlen means...strlen.

>
> > C's unrestricted semantics make this harder but still possible. If the
> > body of the loop is something like { a = b } and a and b are simple
> > variables then there is I think no chance that the assignment might
> > conceal an alias.
>
> The loop body you supply here won't actually compile. Note that few C loops
> are that simple (and in general, they do in fact compile).
>
> > In general the fact that C allows aliasing does not mean that the
> > compiler cannot do a sort of symbolic evaluation of the text inside
> > the loop and conclude either that "the effect of this loop is known"
> > or else "the effect of this loop is not known".
>
> More to the point, it makes sense to perform this trivial optimisation in
> one's own code, so that we don't have to assume that our end
> user-programmer has access to an all-singing all-dancing whizzy optimising
> compiler.

The problem is that each temporary variable is a point of possible
failure in a further evolution of the code. As the for loop expands,
it might be used invalidly inside the for loop. The tersness of my
example is therefore a point in its favor.

>
> <snip>
>
> >> > In fact, the over-generality of the C for loop is a major problem
> >>
> >> <grin> First, C isn't powerful enough - and now it's /too/ powerful. Make
> >> your mind up, Mr Nilges! Are you really saying that:
> >>
> >> for(expression-opt; expression-opt; expression-opt) statement
> >>
> >> is so difficult to understand that it is actually beyond your grasp?
> >>
> > It's an irresponsible hack because Kernighan if not Ritchie had as a
> > model the Algol and Fortran work.
>
> Brian Kernighan wrote (most of) the *book* - not the language. As for
> "because", are you ***serious***? There's nothing inherently irresponsible
> about doing something differently to the way it's been done before. If
> Dennis Ritchie had wanted to write an Algol compiler, he'd have written an
> Algol compiler.
>
Nobody knew how to write an efficient Algol compiler in 1971 in a
reasonable amount of time.
 
> > They ignored it because they were
> > sort of passively-aggressively engaged with the computing
> > Establishment in the context of the early 1970s, and wanted to make
> > their own construct. They managed to screw up because the semantics of
> > the For statement aren't clear and temporarily confuse smart people
> > like me.
>
> It's a poor workman who blames his tools.
>
Its a worse workman who makes pronouncements about C without having
any experience in the development of a C compiler, even a partial one.

> >> > that
> >> > is inherited by C++ and C#, precisely because it forces the compiler
> >> > to re-evaluate values.
> >>
> >> Depends on the values. The optimiser has quite a lot of leeway. But it
> >> draws the line at anticipating the results of function calls!
> >
> > strlen is probably generated inline.
>
> Inlining ***doesn't help*** here! The problem is not in the *call*, but in
> the *code*! I mean, DUH, do you really not understand this? I can't believe
> that even you are this stupid! The problem is that you have to count the
> number of characters OVER and OVER and OVER. In comparison, the function
> call overhead is trivial!
>
You really don't get it, do you?

The runtime doesn't count the characters in a loop until it finds a
null character. It executes one instruction to scan for the character
in nearly all cases.

 
> >> > In fact, these defects in C MEAN that skill-at-programming is NOT
> >> > skill-at-C,
> >>
> >> They're not defects in C, Mr Nilges. They're defects in your
> >> understanding of C.
> >>
> > An understanding which comes and goes when I need it.
>
> Well, no: you needed it last year, and it didn't come.
>
> <sociology snipped>
>
> > I concede that insofar as I sit down and write C it is absolutely
> > essential for me to understand these issues just in time
>
> Just too late, in your case.
>
> > (and I claim
> > that 9 out 10 programmers don't bother their heads with these issues
> > at all).
>
> Sturgeon's Law. So what? Here in comp.programming, we assume that the 9 out
> of 10 are too busy debugging to bother with Usenet.
>
> <silliness snipped>
>
> > I abandoned C and adopted object oriented VB because I wanted to
> > organize larger problems and conveniently forgot the semantics of for
> > until you reminded me.
>
> It should not be assumed that, just because you say you are incapable of
> using C to "organize larger problems", others would necessarily have the
> same problem. C has been used successfully on extremely large problems.

Yes, in part because it doesn't generate linear searches for the NUL
character at the end of the string. Usable compilers generate a single
instruction.

I suggest you bone up on how C is compiled in usable compilers and
cease fantasizing.

Relevant Pages

  • Re: Coding in Fortran
    ... I would like to start some programming in fortran. ... a loop got performed at least once. ... In fact, the f66 compiler we were required to use by a certain employer, until I resigned in 1985, had 3 different run-time loop counts for a certain source code example with different levels of optimization set. ...
    (comp.lang.fortran)
  • Re: Coding in Fortran
    ... I would like to start some programming in fortran. ... a loop got performed at least once. ... That f77 feature was one of the last to be implemented uniformly. ...
    (comp.lang.fortran)
  • Re: Letter to US Sen. Byron Dorgan re unpaid overtime
    ... The MAXIMUM size of a working string, accessed in its entirety, is ... compiler would generate a loop), ... > natural incompetence in the field of programming. ...
    (comp.programming)
  • Re: Fortran vs. C (was Re: Ken & Klaus.)
    ... > greatly improved on Fortran 77 and maintained full backward ... > loop of C because you are guaranteed that the loop variable does not ... Maybe if I had to do serious scientific programming again, ... language needs that a scientific programming language doesn't ...
    (sci.physics)