Efficency and the standard library

[spinoza1111]

Yeah.  But the general rule seems to be that an area of carelessness suggests
there will be others.  So it's reasonable to infer from <malloc.h> that the
rest of the code is *likely* to be poor.

Wow, is that so? Actually, the inclusion of malloc.h resulted from a
relative ignorance of C and not programming or English on my part. I
have said before that I know LESS about C than the regs here, but MORE
about programming, because I can see that the regs are mentally and
morally corrupted by the bad design of C. So its inclusion could
predict not "carelessness" but its opposite: due diligence in an
unfamiliar language.

Furthermore, Peter, we've seen in your "off by one stringlength" some
far more serious carelessness from a "C expert".

Furthermore, you've never confirmed that the rest of the code *is*
poor. You prefer, in the corporate-shithead register, to stay at the
level of likelihood because for you, "swift boating" people has
completely replaced learning your profession. It only had to be proven
in the 2004 election that John Kerry MIGHT have not been a military
hero in the brown-water riverine Navy during Vietnam, likewise you (on
record as a Bush supporter) need, you think, only to conduct hit and
run raids on people's reputations and standing, starting with Schildt.

 

[spinoza1111]

[snips]

No argument there, none whatsoever. But lemme ask you a question. Where
the **** do you get off criticising people who are, if not perfect,
better than you? People like Schildt?

Would that be the same Schildt who thinks main can be declared however
you damn well please, who thinks feof should be checked _after_ using the
value read from the file, rather than before, who thinks bytes are always
8 bits, who thinks C is restricted to the ASCII character set, who
thinks...

No, because you've bought a set of trivial truths, errata that should
have gone to McGraw Hill, and lies as being == Schildt who in fact is
a generalist whose enemies concede is "clear", which necessarily means
"understandable", which in turn, necessarily means true. The Swift
Boating of Schildt was started by a clown who is present in this
discussion, Seebs, and his lack of diligence or respect for the
standing of others is on display as I write.

 

[spinoza1111]

Lemme jump to a totally unrelated field to explain/support this:

World of Warcraft.  Popular game, many people play it.  There's a broad
range of player skill.  Some players are quite good.  Some are quite bad.

Imagine that you want to know whether someone is good or bad.  Certainly,
watching them play for a while can give you a pretty good idea.  But you
know what else can give you a pretty good idea?  Reading anything they write.
If they can't spell, they're probably bad.  If they can spell, they're
probably good.

This may seem like it ought to be unrelated.  Strictly speaking, it's
not a guarantee; I know some skilled players who can't spell, and I know
some good spellers who don't play very well.

But by and large:

Attention to detail is a character trait.

People who are careful and thoughtful in one area are usually careful and
thoughtful in others.  People who don't care in one area usually don't
care in others.

Thus, someone who includes <malloc.h> is likely to make mistakes based on
a characteristic habit of picking things up without really understanding them,
or various superstitions unsupported by the nature of the language.  For
instance, I'd expect such a person to try to duplicate the features of the
C library, but do it poorly, and introduce multiple bugs into a hundred
line version of something that should have been under twenty lines and not
needed noticeable debugging.

* There were five bugs, all of which have been fixed in the first,
and one of the few, solutions posted (the others were by io_x and
willem, and not you). Those bugs are in the Change Record with the
code for all too see and traceback

* That bug list, and other forms of diligence seldom seen here or on
the job, is why the code isn't twenty lines. If you take out the
TESTER calls (which provide a reusable testing resources that
competent participants in this discussion have found useful) and the
comments there are fewer than one hundred lines and even fewer C
statements, where the lines have been diligently formatted for
readability.

* You lack of standing was evident when you could not post a three
line strlen replacement without a recruit-level error, and when you
triggered this discussion by mistakenly thinking that the correct way
to find the string %s is to find the character &, and punt...even when
string.h provides string search.

* My decision to abandon string.h was after years of using it, back
in the day. It has a bad way of representing strings.

 

[spinoza1111]

[ snip ]

"Theft"?  At worst I think I'm guilty of not being as explicit as
I might have been about sources.  It was certainly not my intent to
"steal" any of your work, or to present it as my own, and I'm sorry
if that's how it comes across.

[ snip ]

But if you want to claim that I should have been more explicit
that these were your tests and not mine, well, fair enough, and
I do apologize for that.

If I post further versions of my code I will do what I can to
make sure credit is given where due.  

Looking over what I posted ....  Oh dear.  I really *should* have
put something at the top of the file "spinoza-tests.c" indicating
that those lines were copied verbatim from your test suite -- but
the intent, again, was to keep to a common frame of reference,
and perhaps provide an easy way for others to run your tests,
rather than to plagiarize.

Proposed comments for the file containing the tests:

/*
 * The "spinoza1111tests", as developed by Edward Nilges.
 * This version is copied from Usenet post Message-ID [whatever].
 */

(I'm not actually sure I correctly copied and pasted the latest
version of your tests.  Something else to fix.)

Proposed comments for the file containing the driver code:

/*
 * Correctness tests use the TESTER macro interface proposed
 * by Edward Nilges in [another reference to a Usenet post].
 */

[ snip ]

Thanks for this, I appreciate it.

 

[spinoza1111]

[ snip ]

[ snip ]

[ snip ]

(For the record, the part of my post you quoted includes only about
about half of my code, since apparently Google by default doesn't
present the entirety of long posts .... )

While thanking Ben, and rightfully so, for his help, you might have
had the common decency to also acknowledge theft of ideas (TESTER
macro, test suite, etc.) from me.

"Theft"?  At worst I think I'm guilty of not being as explicit as
I might have been about sources.  It was certainly not my intent to
"steal" any of your work, or to present it as my own, and I'm sorry
if that's how it comes across.

I call your attention to the following lines from my code, first
where I define my implementation of a TESTER macro:

/*
 * macro to perform one correctness test
 *
 * conforms to thespinoza1111interface to allow easy copy/paste of his tests;
 * first parameter is unneeded for my code
 */
#define TESTER(ignored, in, old_text, new_text, expected) \
    one_test(in, old_text, new_text, expected, &test_count, &error_count, 1);

I would have thought that the above comments at least make it clear
that my implementation of a TESTER macro conforms to an interface
defined by someone else -- identified somewhat cryptically as
"spinoza1111", but I thought that would be enough for anyone who
follows this group at all.  It didn't really occur to me that the
idea of such a macro was startlingly original and something one would
need to give credit for, but if you think it is -- oh, I don't know.

If I were really intending to steal your ideas, would I have
mentioned you at all?  I suppose that comment about making it easy
to copy/paste might come across that way, but really -- my intent
was to make it easy to keep up with your evolving test suite and
thereby demonstrate that my proposed solution(s) "work" according
to your criteria.

And then at the point where I actually invoke your tests:

    fprintf(stdout, "spinoza1111tests\n\n");

I suppose I thought this would make it clear enough to anyone
following the relevant discussion that I was proposing to run
tests proposed/invented/something by thisspinoza1111entity.

Thanking you ....  Before I did that I would want to examine the
actual tests more closely; I have not looked at them carefully
enough to have an opinion about their quality.  My idea was to
use your tests rather than inventing my own as a way of keeping
to a common frame of reference.

But if you want to claim that I should have been more explicit
that these were your tests and not mine, well, fair enough, and
I do apologize for that.

If I post further versions of my code I will do what I can to
make sure credit is given where due.  

I understand that you're probably
afraid of the regs here who use "the politics of personal destruction"
so readily, and part of their strategy is to make people afraid to
associate with their target do jour...here a person who's exposed
their incompetence. But you might have acted like a man.

Why would I want to act like a man?  (I'm not one.)

Because in fact men have been in most societies definitional of full
humanity. This is unfair to women but the fact is that in patriarchal
societies most women haven't been independent enough for us to make
all but a few (Joan of Arc, Marie Curie, Sophie Germaine) into
exemplars of what it is to be human.

When I use the words, "act like a man" I mean acting like a free and
independent moral agent who tries to do the right thing, like my
father for example, or me at my best. I think most of the male posters
here are not men but guys.

I think I won't address the question of whether I want to associate
with you, or be perceived as associated with you, and why.

I think these newsgroups are being misused by people who find their
ease of access useful in establishing chops they don't have, and I
think these people do this by trying to ruin reputations.

 

[spinoza1111]

So we've got version 1 which uses malloc.h. The person who receives
the code say "Oh Oh, no good" and makes it stdlib.h.
Now the code isn't the same. So if we give a bug report to the writer
of version 1, we have to say that we were using a different version,
and he might say "well it's no longer my problem". So you need to
repeat the bug with version 1, which takes an extra day. Even with
perfect goodwill, you create layers of bureaucracy.

Naturally, when you make a change, you test everything. The problem is
that the person doing the testing "knows" that all he's done is
repalce a non-standard header. So nothing can go wrong, right? And 99%
of the time, he'll be right. So it creates a sort of sense of
unnecessary work, mandated by pointless regulations. We need the code
urgently, so tester skimps on the unit tests. Again 99% of the time
he's right. But discipline has slipped. We no longer have a bullet-
proof testing system.

That's the way with code. The trivial is important, because the whole
point of computers is that they can perform trivial tasks, without
human intervention.

All very true, and well-expressed. But my conclusion has already been
expressed: don't use C for this level of industrial code. When you
have OO languages, "including the right libraries" simply isn't as big
of a problem. Libraries, as compared to objects, are too crude for
modern development because they redefine too much.

Were we doing the sort of collaborative development for which Richard
and Seebs aren't qualified, we would have to agree to include a high-
level .h file which would do all of the standard includes in turn, and
we'd then forget what's needed and have to look it up when outside of
the collaborative development environment. The industrial and
collaborative development of C code in my view always requires
considerable work on idiomatic approaches to the point that shippable
source code looks nothing at all what people here think is C. It looks
more like my code, in fact, minus trivial blunders like malloc.h
(which was removed when Heathfield pointed it out).

 

[spinoza1111]

spinoza1111wrote:
<snip>
Heathfield wrote a "linked list tool"
without pointing to data,
<snip>
[...] my point was that the DATA in the list is the DATA and
not a link, and nobody with a halfway decent education in data
structures would have proposed such a stupid design, save, perhaps,
for a linked list of data elements whose type is simple and fixed in
length...not a "reusable tool".
Alex Stepanov, the designer of the C++ STL library is untutored in

Again, these constant appeals to older men "untutored"

Did you read Nick's whole sentence before starting to type your
response?  he said

which to me says nothing at all about whether he thinks Stepanov
is "untutored in computer science", but is instead an attempt to
suggest that if Heathfield's approach is indeed faulty, he's in
good company.

Heathfield's crude code is nothing like Stepanov's accomplishment.

are sickeningly
ignorant excuses for ignorance, because many of them (such as
Dijkstra) went to universities before universities had computer
science programmes, and others (such as Stepanov) were self-educated
because of life events. Dijkstra most certainly, and probably
Stepanov, never engaged in anti-intellectual assaults and the politics
of personality which are in this newsgroup the tropes of the
malignantly uninformed.

[ snip ]

(And you even retained the text ....  "Whatever", maybe.)

I would not dignify Heathfield as "value based". Instead, I think he
didn't know how to do the job, since to do it you have to use the
preprocessor *safely* to abstract the node pointer type.

A competent programmer would have reasoned:

1. Although some C programmers use pointers to void, this is not safe

2. But copying the bytes in unpredictable code makes node creation
O(n) in all cases

3. I can use the preprocessor to make the node type an abstraction

4. There might be applications where my caller wants node values in
nodes, so this will be an option

5. Using the preprocessor avoids any void* pointers.

But note that the above propositions have a form radically different
from the usual corporate programming proposition, which is today more
expressed with NOT as a major operator owing to the destruction of
knowledge by institutions and money, or, when positive in form, is
grave and folkloric in tone and content. To issue propositions in the
above form is in fact dangerous in corporations, because Enlightenment
knowers kneed kno longer apply to corporations in which irrationality
reigns...as in the bank bailout.

[ snip ]

 

[spinoza1111]

[snips]

No argument there, none whatsoever. But lemme ask you a question. Where
the **** do you get off criticising people who are, if not perfect,
better than you? People like Schildt?

Would that be the same Schildt who thinks main can be declared however
you damn well please,

He doesn't believe that, but most competently written OSen allow you
to declare main in different ways.

who thinks feof should be checked _after_ using the
value read from the file,

This isn't what he "believes" in the worst case. In the worst case, he
may have believed, as have many competent C programmers, that feof's
design wasn't fucked up, and that you could use it BEFORE the read
that fails owing to eof.

rather than before, who thinks bytes are always
8 bits,

Most sane programmers *know* that most bytes are 8 bits, and that
precisely because C is a low-level language, it should not be ported
to other environments without considerable diligence of the sort that
most code monkeys don't have.

who thinks C is restricted to the ASCII character set, who
thinks...

Anyone who has read even a basic introductory text on C is qualified to
critize Schildt.

It's spelled "criticize", Mr. Foaming at the Mouth.

One document, which should have been submitted to McGraw Hill prior to
publication, created a distorted image of Schildt-as-scapegoat for the
very real incompetence of most C programmers, using the insane logic
that "because Schildt made so many errors, I make fewer". The author
of that document, Peter Seebach, is present here in these discussions
as I write. Last week, he submitted an implementation of strlen which
was gravely approved by another reg here (Keith Thompson) but which
contained an obvious off by one bug, which I found in seconds.

The problems in the Schildt books are an artifact of the way in which
McGraw-Hill dev edits books at worst. Their philosophy, which is
shared by most other computer publishers, is that bugs in printed code
are not really important, since "no warranty, express or implied" is
made of this code. Although buggy code in printed books (as opposed to
shipped software systems which are also under the "no warranty" rule)
is regrettable, no professional programmer uses such code blindly,
because "no warranty" is made.

Arguably, McGraw Hill should (or should have, when the book was
published) devote/d more resources to debugging, and that they were
inclined to do so was indicated that they offered Peter Seebach, who
they did not know, money to participate. He refused their offer, he
tells us, because it wasn't enough...money. Instead, he created one
silly document of errata and coined the neologism "Bullschildt" in an
unwarranted personal attack in order to make him seem more qualified
than he actualy is (he has NO academic preparation in CS, whereas
Schildt has both a BS and MS in CS).

This document went "viral" and became the sole source of the Schildt
canard. It lists 20 "errors", most of which are matters of style and
interpretation and dishonestly implies that because Seebach identified
these, there must be hundreds more, and that Schildt doesn't "know C".

There are better books on C. However, the feof() issue and others make
it clear that there's something like knowing TOO MUCH about C in the
sense that it teaches a mistaken approach towards programming.

 

[spinoza1111]

spinoza1111wrote:



No, you don't have to use the C preprocessor, safely or unsafely, to
abstract any pointer type.

Why? Because you say so? You'd need more credibility for that, I'm
afraid.

Well, so far so good.


Not so good. There's nothing inherently unsafe about a void *; it is
open to abuse, like many features in many programming languages, but the
fact that something may be abused does not mean that it must be abused.

Sometimes you say this, other times you say that: we must do things a
certain way because "it's the right way" or at other times we must
avoid features. It's all based on your say-so.

I don't get the "but". Yes, copying arbitrary objects is O(N). So what?
If the program needs to store the data, it's going to have to read it
in, and that's an inherently O(N) process.

No, it doesn't have to "read it in". It merely has to point to it, and
"pointing to it" is O(1).

Bully for you. I can use void * to make the data type an abstraction.

No, void * doesn't make the data type an abstraction, since it is not
checked.

With void *, everything is an option exception function pointers, and
you can even have those if you wrap 'em up in a struct.


Using void * avoids clumsy use of the preprocessor.

By means of something prone to error, clumsy, and O(N). Nice shot.

 

[spinoza1111]

This sure makes a mockery of your quest for a collaborative
effort. You admit here that you used other ideas without credit.

Well, dear boy, I don't know who first said "parenthesize formal
parameters" or "use reusable test suites". But I sure know that nobody
here, in this workgroup, said to do this, and I was asking for my
contributions to this thread to be locally acknowledged, which Ms
Massengil has graciously agreed to do.

Variations of your tester macro are found in many public domain
and open source software tools they have not been credited.

We're talking about something specific, and that is the vindictiveness
of people like yourself, Heathfield, and Seebach who instead of
contributing to the discussion are concerned with destroying and
excluding people. In order to counteract that, I asked that my
contribution be locally acknowledged, which it has been.

 

[Malcolm McLean]

No, void * doesn't make the data type an abstraction, since it is not
checked.

It's C's way of making operations generic.
It's not safe, of course. If I pass the wrong sort of comparison
routine to qsort, the routine will blindly reinterpret bits. Quite
likely the sort will run, but I won't actually get sorted output.

However I use void pointers extensively. A few routines work on bytes
(memswap, compress, shuffle) and take a void *. Far more often, the
void * is used to pass back data to function pointers. It's a very
clean and efficient mechanism, and its much more flexible and easy to
use than most object-oriented languages, which require you to derive
from a base class. (Java interfaces aren't quite as bad).

It's not perfect. My main nit is that, often, the void *is a pointer
to a pointer. However, because the function doesn't know this, you end
up calling memcpy() and the like for single pointer values.
Another potential problem is that, on machine with 32-bit only
addressing, char *'s are faked up by adding bits to pointers. void *s
have to be char *s, because they can represent any type. Therefore you
end up using the less efficient representation for non-char data.

 

[Ike Naar]

The ideas I put
forth a solidly expressed enough to be stealable, and part of the
theft of intellectual property is the mockery and marginalization of
the original producer.

Priceless ;-)

 

[Ike Naar]

But I sure know that nobody
here, in this workgroup, said to do this, and I was asking for my
contributions to this thread to be locally acknowledged, which Ms
Massengil has graciously agreed to do.

Gentlemen don't mess with people's names.

 

[Dennis \(Icarus\)]

Gentlemen don't mess with people's names.

He's not a gentleman. Lower your expectations.

Dennis

 

[Malcolm McLean]

Show me. I have an arbitrarily long list of arbitrarily long words,
stored in a file. I wish to use this list as a lookup for a
spell-checker. Please demonstrate how to write C code to store that
information in memory without reading it in, and do it in O(1) time.
Cries of "do your own homework" will be met with scorn and derision,
since I already have code to meet my needs. You claim you can do the
impossible, though, and store the data without reading it. This I have
to see.

I think I can meet this challenge.
The words are English-language words, so the vast majority are under
31 characters in length. You just get a few oddballs (which we do have
to accomodate).
So structure the file with fixed-width fields of 32 bytes. If the
field is not nul-terminated, the suffix to the word is stored, with
horribly messy contrivances to cope with the case of N words having
the same 31-letter prefix. But this is doable.
We also store the number of words somewhere in the file.

So on initialisation, we simply declare a big array of char *s, all
set to NULL. (OK, maybe this is a cheat, we'll suppose that on system
boot the memory is zeroed).
Now every time someone wants to look up a word, we do a binary search.
If the pointer is null, we retrieve the word from the file. Eventually
our memory will fill up, if the dictionary is being used intensively,
with commonly-needed words (and the ones needed to lead to them) far
more likely to be cached. In fact we can do better than O(log_2 N) by
exploiting known inital and second letter frequencies in English.
So we've got your spell-checker up and running in O(1) time, with very
attractive random access time, and with performance that will be
identical to the read-in at initialisation model if the dictionary is
very intensively used.

 

[spinoza1111]

spinoza1111wrote:


No, because the Standard says so. You can abstract any object pointer
type using void *, and any function pointer type (with a cast), using
any function pointer type you like (e.g. void  (*)(void)).



You make the claim, but provide no evidence to support it. That comes as
no surprise to those who have read your many previous false claims. In
all my articles, I try to make clear the distinction between my
expressing an opinion and my stating a matter of fact. No doubt
sometimes I fail, but I do at least make the attempt. About the only C
features I would urge people to avoid at all costs are those that are
inherently broken (gets(), unadorned scanf("%s", etc). My style
preferences are relatively well-known by regular subscribers to this
newsgroup, but I am never (except in jest) dogmatic about such things; I
might argue, and even argue passionately, for my style choices, but I
don't dictate to people how they must write code. That you should think
that I do merely demonstrates that you are less familiar with my
personality and writing style than you seem to imagine. I save the
dogmatism for when I am talking about the requirements of the Standard
itself.



Show me. I have an arbitrarily long list of arbitrarily long words,
stored in a file. I wish to use this list as a lookup for a
spell-checker. Please demonstrate how to write C code to store that
information in memory without reading it in, and do it in O(1) time.

It's already in memory when your linked list is called. It is
therefore usually a waste of time to make a copy. Just point to it.

Cries of "do your own homework" will be met with scorn and derision,
since I already have code to meet my needs. You claim you can do the
impossible, though, and store the data without reading it. This I have
to see.

It's amazing how in corporate sessions people are able to get away
with bullshit such as this.

The job of a linked list tool is NOT to "read" data. It's to link
data. Using links. Links are addresses. If the data is addressable by
the time it gets to your linked list tool, it is not necessary to read
anything. Sure, if the original data is about to go out of scope, you
MIGHT want to copy it for posterity.

This might be necessary for a good reason, but in my experience many
corporate programmers make unnecessary copies of data because it gives
them a warm, fuzzy, feeling of ownership. One can only speculate that
this makes them feel good because they don't, in fact, own the tools
of production.

It doesn't need to be checked to be an abstraction. It just needs to be
abstract. You can't get a lot more abstract than void *.

Eye roll.

Crotch grab.

The code needs to be abstract in a language (C) that doesn't permit
the sort of abstraction tools found in OO. The source needs to express
the operation of creating a node that points to an unspecified data
type. Instead of a void pointer, a preprocessor macro ensures that a
class of divergent operations (setting pointers to all sorts of
different types) are expressed in one place one way.

You have yet to demonstrate your O(1) non-reading data storage facility.

You have yet to demonstrate that you understand the conversation. If I
am passed a pointer to a real type through a macro interface, and all
I need to do is insert a pointer into a new node, then the creation of
each node consists of constant time operations:

Get storage
Set a pointer

Whereas in your solution I must

Get storage (lots more, too)

Copy the pointed-to value into the storage byte by byte order the
length of the data. Oh, and by the way, dear boy: if a user of your
"reusable" code passes bytes that constitute links, your objections to
links apply to that use of your code.

Order(n).

 

[spinoza1111]

Gentlemen don't mess with people's names.

No, they don't. I apologize for the haste in which I misspelled her
name. The Ms was honorific, intended to be polite.

 

[spinoza1111]

Priceless ;-)

Perhaps, but it's also true. I've seen it happen all too often: the
real contributors forced to work for free by deadlines set so as to
force them to work 16 hours a day and get paid for 8, and then called
"narrow technicians" when they try to contribute time-saving ideas.
The savage bullying of Ted Nelson for disagreeing with Berners-Lee's
flawed Web design, in which "saving a pointer" back to the originator
of content ensured that producers of intellectual content could be
deprived of their work by thugs and criminals like Jimmy Wales of
wikipedia.

Don't ignore the Dark Side.

 

[santosh]

[ ... ]

Show me. I have an arbitrarily long list of arbitrarily long words,
stored in a file. I wish to use this list as a lookup for a
spell-checker. Please demonstrate how to write C code to store that
information in memory without reading it in, and do it in O(1)
time. Cries of "do your own homework" will be met with scorn and
derision, since I already have code to meet my needs. You claim you
can do the impossible, though, and store the data without reading
it. This I have to see.

I don't know about O(1), but under Unix-like systems, mmap() is a
possibility

And yes, I know it isn't standard C and of course, under the hood,
there will still likely be one or more read ops done by the OS, but
from the program's POV, you can "store" the file in memory without
having read it in.

 

[Richard Tobin]

I was unaware that OSen defined what constitutes correct C.

Really?

Many implementation-defined features are commonly determined by the
operating system.

-- Richard