Re: strlen(), K+1: clarification

On Feb 26, 6:57 pm, Willem <wil...@xxxxxxxx> wrote:
spinoza1111wrote:

) If you'd actually read a book on algorithms, you'd realize that
) computer scientists did not develop the big O notation for programmers
) to use in reference to real programs. It was designed to discuss
) abstract algorithms.

Another example of an intentional falsehood with the purpose of drumming
up as much (bad) attention as possible.  This is a nice example, because
it is an assertion without any factual backing, therefore making it
difficult to address becaus the troll will obviously demand hard facts
as counter arguments.  Note that even if hard facts are presented, he
will probably ignore these or dismiss them as 'fascist nazi lies'.

As an example, I will present some facts here.  Note the tactics the
troll will use to attack this proof.

Theorem: Computing the length of a C string cannot be done in constant time.

(N, in this case, is the length of the C string.)

Proof:
Fact: The length of a C string is determined solely by how many characters
      it has before the first '\0'.
Fact: In order to find which character is the first '\0' requires reading
      all the characters before it.  In other words, it requires reading N
      characters.
Fact: A computer cannot access an unbounded number(N) of characters in
      constant time.

The phrase "constant time" is a property of algorithms, as I have
repeatedly pointed out, not of code. Every book on computational
complexity I've looked at contains this disclaimer. Because, as Knuth
said recently, a program is properly understood as a message
predicting computer behavior, from one human to another, it makes
sense to sacrifice what you so ignorantly and pretentiously mislabel
with formulae you don't misunderstand to show, in an extempore sample
for loop, the all-important for loop bound, rather than obscure it in
a temporary variable. This is why Clive didn't precalculate K-1 in his
bubble sort, and it's why I used strlen(s) in the condition.

"Constant time with respect to running code" (CT') is the only
intellectually responsible way of using borrowed terminology.

If microcode implements a scan and test instruction an order of
magnitude faster than code, then if strlen(s) is compiled to a single
code instruction that calls the microcode, then even if the microcode
loops (which it must), the non-microcode instruction is said to run at
CT prime.

The C programmer has in fact the human right to expect that trivial
library functions run at CT prime. He shouldn't have to even use fgets
for this reason, and responsible C programmers generally avoid non-CT-
prime functions, not only for performance reasons but also because of
their hidden bugs which are by definition inherited by his code,
making it buggy in term. As Malcolm has pointed out, using fgets()
means that you have a bug. As Richard unintentionally demonstrated,
using memcpy means you need to check for overlap yourself to avoid a
bug.

And if you have to work with strings longer than cache length, it's
probably a good idea to redo all strings as

struct TYPstring
{
long intLength;
char * strValue;
}

with an inspect function to make sure that the value is the length
claimed. It is obscene that this has to be done, but that's C for you.

RISC architectures are not typically microcoded: but what part of
"cache" don't you understand? Because of the design errors in the C
language (such as placing the length on the wrong end of a string),
design errors which, as I've said, would have caused Thompson and
Ritchie to be laughed at had they worked in Iowa or Bangalore, RISC
chips have been overdesigned to execute C. If strlen(s) is used in a
for loop, and the optimizer doesn't change it, s will be in the cache
and, in the only responsible usage of "constant time", it will operate
in constant time.

Sure, careful C programmers writing real code (not extempore code that
was posted to establish a non-performance-related point) would put
strlen(s) in a variable before the for. But as opposed to forgetting
the behavior of memcpy and confusing && and || under pressure, this
error is de minimis. To go into a court of law claiming it was
anything else would amuse judge and jury once the science was
explained to them clearly.

If this can be empirically shown not to be the case, and I believe it
cannot, then C is even more of a joke than I thought.

The issue was blown out of proportion in 2003 with respect to
extempore code. Programmers who actually write large working programs
as I have do NOT misuse computer science terms they do NOT properly
understand, nor make absurd claims in order to harass people and
maintain control of a newsgroup.

All people can establish here is that strlen(s) doesn't work well on
their platforms because they have chosen a poor language. This isn't
science, it's postmodern folklore and it's being used to destroy
people like Schildt.

Stop trolling me on this issue. If there's anything worse than
trolling, its mass trolling. You're trying to eliminate me because my
sentence structure alone humiliates you.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.

Relevant Pages

  • Re: Brian Kernighan, maybe Im not worthy, maybe Im scum
    ... It's a critique of the "Beautiful" code authored by ... Rob Pike and discussed by Brian Kernighan in a new O'Reilly book. ... string, as we'll see, whence the scare quotes). ... C programmers claim that their language is unicode-aware because they ...
    (comp.programming)
  • Re: J4 - presentation/discussion on "Future of the COBOL Standard"
    ... programmers are opposed to dynamic structures. ... Suppose you're flying a kite and someone asks the size of the tether string. ... You say 1,000 meters. ... This seldom comes up in ODO discussions. ...
    (comp.lang.cobol)
  • Re: Latest on Windoze Navy software
    ... > it had defined a proper string type like Fortran and Basic, ... Well, I haven't used Fortran since F77, but base don that your now ... but because programmers don't really care. ... many 1979 BSD 4.0 systems do you think had any compiler other than the C ...
    (comp.os.vms)
  • Re: strlen(), K+1: clarification
    ... well -- both TR and TRT were notoriously slow instructions. ... even if the actual string being translated never ... Optimizing string retrieval for the DEC was to ignore Moore's Law, ... programmers use ...
    (comp.programming)
  • Re: Brian Kernighan, maybe Im not worthy, maybe Im scum
    ... It's a critique of the "Beautiful" code authored by ... Rob Pike and discussed by Brian Kernighan in a new O'Reilly book. ... string, as we'll see, whence the scare quotes). ... C programmers claim that their language is unicode-aware because they ...
    (comp.programming)