Re: strlen(), K+1: clarification
- From: amorgan@xxxxxxxxxxxxxxxxxx (Alan Morgan)
- Date: Tue, 26 Feb 2008 10:38:03 -0800 (PST)
In article <372f666d-c81e-4568-88db-9898c829880c@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
spinoza1111 <spinoza1111@xxxxxxxxx> wrote:
The phrase "constant time" is a property of algorithms, as I have
repeatedly pointed out, not of code.
Well, it's a property of the run-time of the code and not the code
itself, I guess, but that seems like a very fine distinction. It's
like someone correcting me when I say I speak English by pointing
out that I speak my own personal idiolect of English which is
(a) technically correct and (b) really annoying.
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.
Heavens to Knuth, you rake a guy over the coals for brain farting and
confusing && and || and you won't admit that using strlen(s) in a for
loop condition is a bad idea. A simple "Oh yeah. I figured that the
compiler could optimize that out, but it turns out it's harder than
it looks. Here's a correction" would have satisified everyone, but
you can't even do that.
"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.
"Human right"? We are talking K&R not John Stuart Mill.
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.
You are delusional. Almost none of the str operations are CT' (I'd say
none, but there might be one that I've forgotten). printf isn't, fputs/gets
aren't, malloc may or may not be and there are certainly no promises one
way or the other.
As Malcolm has pointed out, using fgets()
means that you have a bug.
Using gets() means that you have a worse one. fgets() at least *can*
be used correctly.
As Richard unintentionally demonstrated,
using memcpy means you need to check for overlap yourself to avoid a
bug.
Wow. They should really document that somewhere...
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.
I don't see this as a major improvement. Oh, sure, strlen() is much faster,
but how often do you call strlen()? strcat(), strcmp(), and most other
str functions are still O(n) (did you see what I did there??? I'm such a
scamp!) so I'd hardly call this an overall win.
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.
Only if by "constant time" you mean "really fast", in which case I have
no argument except with your use of the English language.
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.
A rational human being would admit that putting strlen(s) where you
did was a mistake, correct it, and move on. Your refusal to do this
is illuminating.
But as opposed to forgetting
the behavior of memcpy and confusing && and || under pressure, this
error is de minimis.
I've interviewed a lot of people for programming jobs. I'll excuse
a lot of errors in an interview if the interviewee admits/notices
the mistake and fixes it. Heck, I've had someone write Pascal code
instead of C code (they noticed it, commented on the fact that they'd
been using Delphi for some personal projects, erased the code, and
rewrote it in C). It happens.
Alan
--
Defendit numerus
.
- Follow-Ups:
- Re: strlen(), K+1: clarification
- From: spinoza1111
- Re: strlen(), K+1: clarification
- From: Richard Heathfield
- Re: strlen(), K+1: clarification
- References:
- strlen(), K+1: clarification
- From: spinoza1111
- Re: strlen(), K+1: clarification
- From: Richard Heathfield
- Re: strlen(), K+1: clarification
- From: spinoza1111
- strlen(), K+1: clarification
- Prev by Date: Re: Dealing with ad hominem attacks in comp.programming
- Next by Date: Re: C Sharp sorting considered superior to C by an order of magnitude
- Previous by thread: Re: strlen(), K+1: clarification
- Next by thread: Re: strlen(), K+1: clarification
- Index(es):
Relevant Pages
|
