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

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

Date: 23 Dec 2003 13:09:33 -0800

Ian Woods <newspub2@wuggyNOCAPS.org> wrote in message news:<Xns945A9F07CE465newspubwuggyorg@217.32.252.50>...
> spinoza1111@yahoo.com (Edward G. Nilges) wrote in
> news:f5dda427.0312221931.122266f2@posting.google.com:
>
> > Ian Woods <newspub2@wuggyNOCAPS.org> wrote in message
> > news:<Xns9459CFA734973newspubwuggyorg@217.32.252.50>...
> >> spinoza1111@yahoo.com (Edward G. Nilges) wrote in
> >> news:f5dda427.0312221032.2d6ad4f1@posting.google.com:
> >>
> >> > Richard Heathfield <dontmail@address.co.uk.invalid> wrote in
> >> > message news:<bs5f83$53q$1@hercules.btinternet.com>...
> >> >>
> >> >> Well, I'm a great believer in personal choice. I don't believe in
> >> >> imposing /any/ language on /anyone/. C happens to be /my/ language
> >> >> of choice. That doesn't mean it's right for everybody.
> >> >
> >> > A computer language is not a lifestyle, and the very idea of
> >> > transferable expertise seems to be beyond you. Instead, you judge
> >> > people by fabricated metrics which inappropriately foreground
> >> > transient issues, like a poor head-hunter.
> >> >
> >> > Richard, I was frankly shocked to learn that you are unclear on the
> >> > very idea of a runtime instruction that would scan a string for a
> >> > Nul character, and I was also shocked by Willem's belief that this
> >> > instruction as implemented would consume the same sort of cycles
> >> > consumed in the execution of an instruction by passing over
> >> > characters, typically in firmware.
> >> >
> >> > You need to learn to cease using random posts to judge people's
> >> > capabilities since it reflects badly on you.
> >>
> >> Alternatively, it might just be obvious that whether it's performed
> >> 'in firmware' as you say or elsewhere that scanning for the first
> >> occurance of a certain value in an array is not an O(1) operation.
> >>
> >> On all of the microprocessors I've used which have had instructions
> >> which can do such scanning, the runtime of the instruction itself is
> >> O(n) not O (1). It being a single microprocessor instruction doesn't
> >> make it an O(1) operation.
> >
> > It is order n, but if implemented in firmware, it is n*c where c is
> > smaller than the cycle time of the instruction...usually, much
> > smaller.
>
> It matters not where it's implemented: it's still O(n). If I have special
> hardware to do it, all I change is the constant. This really is very
> basic computer science.

The problem is that there is no "constant" in "O(n)". You are using
mathematics very sloppily. "O(n)" is mathematical slang for on the
order of n and what you mean is n*K where K is the constant time the
firmware string implementation takes to examine one byte in its
implementation of the opcode for "find a character, in the string".

My experience is based on academic theory, and writing the firmware
assembler and compiler for the Nortel SL-1 system, a layered CISC and
stack based architecture, and in that system, the K constant was about
an order of magnitude less than the K constant for the execution of a
non-firmware instruction.

I conclude that it is nonsense to declare that the "O(n)" for a
character search in C code is the same as the "O(n)" for the firmware.
Common courtesy of course dictates that I refrain from impugning your
professional competence based on this oversight.

I am well aware that RISC machines abandon these types of instructions
and actually might compile a strlen to the EQUIVALENT of

for ( intIndex1 = 0; strInstring[intIndex1] != '\0'; intIndex1++ ) { }
return(intIndex1);

But all this means is that in real problems, you are better off either
using a better string representation, or, if your purpose is the
stated purpose of using C code in comp.programming, for communication,
writing clear code, using strlen (which accurately conveys intent),
since competent individuals can so easily change the clear code.

>
> >> >> The line count increment is necessary because the value is used as
> >> >> an offset into the array. The preincrement is not non-standard at
> >> >> all. The Standard defines the behaviour perfectly. The condition
> >> >> is evaluated before each loop iteration, not after. You really
> >> >> don't understand this language at all, do you?
> >> >
> >> > Not true. The increment is NOT performed before each loop iteration
> >> > in the code
> >>
> >> Where in the above paragraph does it say that the increment /is/
> >> performed before each loop iteration? It says clearly that:
> >>
> >> "The condition is evaluated before each loop iteration, not after."
> >
> > Because of Richard's discourtesy, there was some confusion.
>
> Odd, I thought it was because you'd misread the above. It's nothing new:
> reading is a complex skill and no matter how well practiced a person is
> mistakes can and do happen from time to time. I'd have thought something
> along the lines of:
>
> "Whoops! I misread it."
>
> would have been sufficient to explain the confusion.
>
> > I said,
> > repeatedly, that I hoped my understanding of his understanding was
> > wrong. It was, and Richard made it clear that he understands the order
> > of evaluation of a for loop. But at the same time, he claims that the
> > for loop condition is "just an expression" and does not, apparently,
> > even know what the code generated for the for loop looks like and the
> > compiler mechanisms needed.
>
> The 'compiler mechanisms' for handlng for loops in various languages, and
> in C, are trivial. I'm sure Richard can, if he cared to and by now
> probably has, sit down with a *** of paper and devise the obvious
> working scheme for C-like and integer only for-loops.
>
I am not so sure. I would not trust him to write a Fortran or Basic
compiler since the For semantics are different.
 
> <snip>
>
> > He prides himself on "knowing" that using strlen in the for loop
> > terminating condition is bad...but the knowledge cannot be
> > generalized, outside C.
>
> This is nonsense: the generallisation, and why it is bad, isn't about
> using strlen but using an O(n*n) algorithm when there is a trivial O(n)
> algorithm. I don't care what language is being used, if I see a colleague
> or even a student of mine using an O(n*n) algorithm when it takes no more
> programmer effort to use the trivial O(n) algorithm, I'll tell them so.
>
For the last time: strlen communicates intent and courteous
individuals can change it without exhibiting their vanity and
arrogance.
 
> > In most other languages the terminating
> > condition is an end value and in these languages the strlen value
> > would be copied before entrance to the for.
>
> In most of most other languages, the loop can only iterate over values of
> a single type, typically integers. In the languages which aren't part of
> the "most other languages" set, the programmer can choose what type, what
> kind of condition, and whether or not to re-evaluate expensive functions
> used in that condition.
>
> You chose to make an O(n*n) algorithm out of an O(n) algorithm by /not/
> using knowledge trivially available to you as a programmer which isn't
> available (or trivially available) to the optimiser. You then argued
> about the time complexity of the operation. This shows at best that you
> have a misplaced trust in the tools at hand, or at worst that you
> shouldn't be programming.
>
I think I have post facto fully explained my views on this matter. Let
it drop.
 
> > His knowledge is a deviant knowledge of deviant, and passive
> > aggressive language design by Ritchie in which the trivial becomes
> > important.
>
> I don't call using an O(n*n) algorithm where there is a trivial O(n)
> algorithm and then arguing about the time complexity and how awful the
> behaviour of the construct you used to be 'trivial'.
>
It happens to be good practice to create a prototype that best conveys
intent and then make it faster. That's why I used strlen.
 
> Back to the front though. Obviously then, this Algol-60 for loop is also
> "deviant and passive agressive":
>
> for NewGuess := Improve(OldGuess)
> while abs(NewGuess - OldGuess) > 0.0001
> do OldGuess := NewGuess;
>
> It wasn't, of course, designed by Ritchie unless he secretly snuck into
> the committee room without anyone noticing. C certainly doesn't have a
> monopoly on for loops which re-evaluate the condition once per iteration.
>
Thanks for the information concerning Algol-60. At the time it was
designed, its designers were unaware of the need to track meaning, and
so was Ritchie.
 
> > But what is more important than the order of evalution of a for loop
> > is the fact that each time Richard spots a genuine error on my part
> > (which have in most cases been typos and not cognitive events on my
> > part), he then launches into a tirade about my abilities. I then
> > respond, and this creates bad feelings. He is an example of why
> > structured walkthroughs can no longer be conducted.
> >
> > Richard needs to follow my lead,
>
> <quote>dickwad</quote>

In the context I was using it I was not so much angry at Richard as
amused, and the trouble with your literal mind is that you count
words, and seem insensitive to something that cannot be found out by
automated means. It is that Richard in fact knows that I've forgotten
more C than he knows, is angry at me for submitting popular and
well-attended threats, and finds his inappropriate domination of this
newsgroup threatened.
>
> > and courteously refrain from
> > identifying as errors what are usually typos. He does not do so
> > because he feels threatened by broader, "off topic" postings which tax
> > his abilities and which threaten his dominant position.
> >
> > For example, what is "off topic" to him is any reference about which
> > he is uninformed.
>
> Mr Nilges, this is nonsense.

Would it were so. But I find nothing in Richard's posts that manifests
an awareness of either general computing culture or culture outside
computing.
>
> > I have not at this late date learned a single useful thing about C
> > from Richard, because I'll be damned if I start creating extra
> > variables, creating points of potential failure in new versions of
> > code to no end except microscopic efficiency.
>
> Using a trivial O(n) algorithm instead of an O(n*n) algorithm isn't
> micro-efficiency.

I knew that and was the only poster to responsibly post a reference to
an authority, my reference being to Steven Skiena's The Algorithm
Design Manual last month. However, because social factors outside
programming have made programmers into a dysfunctional tribe, the only
knowledge they prize is an oral tradition, in which a "knower"
manifests his "knowledge" by tribal subservience, a feat which I shall
remain incapable of performing.

>
> > It was discovered in the
> > 1970s that nearly all considerations of efficiency should be postponed
> > until the code works because slow code is caused, in nearly all cases,
> > by one or two tight loops; therefore, fretting globally about
> > micro-efficiency is a waste of time.
>
> One or two tight loops, like those which were examples in this thread. If
> you write all the trivial O(n) algorithms as O(n*n) right from the start,
> 'optimising' the code is going to be a rather painfull experience.

My usual method of course is to get it right and then optimize, and I
follow the lead of hero computer scientist Niklaus Wirth in this
regard.

I found his treatment at the 1987 ASPLOS conference distasteful. This
conference was dominated, in tribal-oral style, by John Hennessy of
MIPS who at that date had succeeded in restoring the American ruling
class computing culture of "speed". I saw professor Wirth standing
alone in the middle of the room as losers surrounded Hennessy.

They were losers because in fact the dominant architectures today
remain CISC, and the unix and C sub-culture/tribe is being pushed out
by architectures based in CISC.

They flee to the false promise of linux despite the fact that we now
know that vast sections of linux code were copied from a commercial
unix product, and that companies that use linux are in for a world of
hurt.
>
> Ian Woods