Efficency and the standard library

[spinoza1111]

though interesting, how does the stuff about DNA add to this sub-
thread?

Malcolm is describing a real application that needs data structures
above the level of characters and strings. In fact, it sounds ideal
for linked string segments.

 

[Julienne Walker]

<snip>

We'll have to agree to disagree then. Your technical points are valid
in context, but your personality poisons any chance of having a good
debate with you. Any technical discussion inevitably devolves into
veiled insults, condescension, attacks on "corporate behavior",
attacks on individuals, enabling your crusade against Richard
Heathfield, and poetry when you have nothing useful left to say (in my
opinion).

Honestly, I'm tired of talking to a brick wall. Let me know when
you're ready to take me seriously and we may actually be able to chat
in a civil manner.

And don't presume even to say that I've "insulted" your gender. That
is an utter falsehood. I have not patronized nor talked down to you in
the slightest. I am instead arguing for a position: that only an
incompetent would have presented a linked list that copies
unpredictable data into the nodes. This has nothing to do with gender.

You're in no position to tell me not to defend myself when I feel I'm
being "bullied" by a "thug", since you're so adamant about taking that
right for yourself at every turn.

 

[Keith Thompson]

Keith Thompson wrote: [...]

Yes, spinoza1111 is wrong again, and on a topic having nothing
to do either with C or with the supposed subject of this thread.
Is pointing it out really a good use of time and bandwidth?

Put it this way - although I haven't measured it, I would estimate
that the number of his errors that I actually address is significantly
under 1% of the total errors he posts. (If I were to attempt to
address every error he makes, (a) I wouldn't ever get any real work
done, and (b) I'd be plonked by most of this group's subscribers.)

So it could be a lot worse. On the other hand, I acknowledge that it
could be better.

Consider this. I read nearly none of spinoza1111's articles, and
nearly all of yours. I don't see you addressing 1% of his errors;
I see you spending a much larger percentage of your time addressing
his errors. I'm sure I'm not the only one.

 

[Seebs]

Agreed. But let's not forget that you have more than just the link
surgery of a linked list. Consider the following data structure you
described. Each node is a pointer to a block of characters:

"this" -> "is" -> "a" -> "test"

If this string representation were to be useful at all, you'd need to
support deleting parts of each block (such as the "hi" from "this")
and inserting inside each block. I have a hard time believing how this
doesn't add complexity, and depending on your design decisions, it
could easily involve excess or wasted movement of characters.

It could. However:

* Compared to a linked list of single characters, it has much lower
overhead (both allocation and storage overhead)
* Compared to a single giant array, it requires much less copying and
moving to resize, insert, or delete

So there are cases where something like this is worth it. If you're
doing a ton of string inserts of unpredictable lengths, it's probably
worth it.

-s

 

[Julienne Walker]

It could.  However:

* Compared to a linked list of single characters, it has much lower
  overhead (both allocation and storage overhead)
* Compared to a single giant array, it requires much less copying and
  moving to resize, insert, or delete

So there are cases where something like this is worth it.

Absolutely. I wouldn't suggest that it's not a good design. My problem
is with spinoza1111 pushing it as the "best" solution, regardless of
context.

 

[Malcolm McLean]

It could.  However:

* Compared to a linked list of single characters, it has much lower
  overhead (both allocation and storage overhead)
* Compared to a single giant array, it requires much less copying and
  moving to resize, insert, or delete

So there are cases where something like this is worth it.  If you're
doing a ton of string inserts of unpredictable lengths, it's probably
worth it.

I used exactly that strucutre for a text editor I wrote. This was back
in the days when a more experienced programmer told me "you won't get
a full screen editor using just the routines in conio.h".
The text was a linked list of line, rather than words. So wht that
meant was that the user could scroll to the middle of the text, and
start typing. The line at the insertion point expanded, the characters
being moved along O(N) in line length. When the characters fell off
the end of the screen it became a soft newline, and new link was
inserted O(1). Deletes were of course fiddly, because you had to merge
the soft newlines, in fact deleting a character could be O(N) in text
legnth, and the thing slowed down very noticeably.
(He was right about conio.h. I had to write little assembly routines
to poke the screen memory directly).

 

[Seebs]

Absolutely. I wouldn't suggest that it's not a good design. My problem
is with spinoza1111 pushing it as the "best" solution, regardless of
context.

Ahh, yeah.

Well, I guess, I don't get the impression that he's the sort of person
who deals well with the notion that there is more than one good way
to go about something, but that different approaches would be suited to
different environments.

-s

 

[Moi]

[representing a string with a linked list of ministrings]

Malcolm McLean wrote:

the soft newlines, in fact deleting a character could be O(N) in text
legnth, and the thing slowed down very noticeably. (He was right about
conio.h. I had to write little assembly routines to poke the screen
memory directly).

No, you didn't have to do that. Assuming 80x25 under MS-DOS (fair
assumption?):

void scrwrite(const char *s, int x, int y) {
char *p = (char *)0xb8000000UL; /* use large memory model */ p += y *
160; /* add range checking for y */ p += x * 2; /* add range checking
for x. The 2 is because
video RAM was in byte pairs, for character and
attribute */
while(*p++ = *s++) p++;
}

That's the basic idea, anyway, but obviously you'd want something a
little more sophisticated than that. For example, you might want to
handle the attribute bytes too (colour, blink, etc). And/or you might
want to be able to deal intelligently with word wrap, etc.

By the way, b8000000 was the base address of video RAM for colour VGA
monitors. For monochrome, you would have used b0000000 instead. If you
needed to detect the monochrome/colour status at runtime, that was
possible using an int86() call. No assembly language required.

FYI:
The reason you had to use assembler was because writing to video-ram interfered
with the video ram being accessed simultaniously by the video card.
You had to wait for the vertical retrace to write to the RAM without visual
glitches.

HTH,
AvK

 

[Moi]

Moi wrote:


You could do that in C, too, using the inportb() extension:

void vsync(void)
{
while(inportb(0x3da) & 8)
{
continue;
}
while(!(inportb(0x3da) & 8))
{
continue;
}
}

(Of course, if you try this on a Cray or a mobile phone, you're likely
to be disappointed.)

People with Crays have other things to get excited about.

Yes, you're right of course.
IIRC, the other trick was switching the pages. Hercules had four, except
in graphics mode (which meant: bitmapped with a strange addressing scheme;
bypassing the character generator-ROM)


AvK

 

[spinoza1111]

Ahh, yeah.

Well, I guess, I don't get the impression that he's the sort of person
who deals well with the notion that there is more than one good way
to go about something, but that different approaches would be suited to
different environments.

There was only one question as regards Heathfield's "C Unleashed"
linked list. The problem was "developing a reusable tool for a linked
list of any sort of data". His solution was to copy the value of each
element, which takes O(N) time where N is the number of bytes in the
element.

A better solution (which takes constant time for each element and
which doesn't "break" if presented with unusually long elements) would
have been to use pointers to void in each node to point to the
elements.

An even better solution would be to use the preprocessor in a
disciplined way to make sure the pointer is strongly typed as in this
extempore, untested, uncompiled example:

#define NODE(datatype, structName)
structName node { datatype * nodeValuePtr; node * nextPtr; };
#define ADDNODE(lastNodePtr, newNodePtr, newNodeValue) \
{ \
if ((newNodePtr = malloc(sizeof(node)) == 0) abort();
(*newNodePtr)->nodeValuePtr = &newNodeValue; \
(*newNodePtr)->nextPtr = 0; \
(*lastNodePtr)->newNodePtr; \
}

Note that the ADDNODE runs in constant time, whereas Richard's plan
runs O(N).

Weasel words ("different environments") aren't an argument. The
"environment" is strictly defined: it is one in which the programmer
needs or wants a reusable tool for linked lists.

 

[spinoza1111]

(Cue Twilight Zone theme) Come with us now to another dimension, that
of Kiki, who's killed spinoza but knows all the same how many errors
he makes (Twilight Zone theme reaches its climax)

 

[spinoza1111]

spinoza1111wrote:



Declining to enter your "challenge" shows not incompetence but good
judgement.

Why? But I agree. It doesn't show incompetence. Try cowardice.

Rubbish. In the code you're talking about, every single link in the list
points to data. Bozo.

Richard (a Christian Fundamentalist) uses literal reading
strategically, in the manner of Fundamentalists. That is, Christian
Fundamentalism, by insisting that the Bible is literally true, enables
"pastors" (older men) to make, in fact, any ridiculous interpretation
they like. For example, some say that Cain and Abel mated with
subhumans (Neanderthals in some "scientific creationism" accounts) in
order to give Adam and Eve grandchildren without doing the nasty with
their sisters.

Here, he uses the fact that to be a linked list at all, every node
must point to the next node. Fortunately, he's not so stupid as to
present an array as a linked list although as our Pastor he might pull
such a stunt rather than let us think.

But, of course, 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".

 > Seebach presented a "strlen" with a serious


He had an off-by-one error which he acknowledged the moment it was
reported. You, on the other hand, have to have your errors explained to

That's because my errors (testing an invariant in a for, etc.), are
matters of interpretation and style and not massive boners.

you in noxious detail before you manage to get your head around them.
Then it takes you a few more days, in some cases, to correct them. And,
if we're patient enough, we'll find you making the *same* errors a few
months or years down the road, and having to have them explained to you
*again*.

You're talking here, probably, about the fact that I unnecessarily
included malloc.h and capitalized H. These were trivial errors, and
you showed us that you were completely incompetent to read code, since
we know that it would have established your sagging chops to find an
important bug. As it happened, there were five real bugs, and I fixed
them all in a few hours, no thanks to any of your efforts.

Rubbish. You're a sexist and everybody knows it; I cannot recall ever
seeing a reply from you to a woman that wasn't outrageously
condescending in tone. That would be bad enough even if you had
something to be condescending about.

When all else fails, Sir Richard Heathalot mounts his nag and defends
fair lady.

 

[spinoza1111]

We'll have to agree to disagree then. Your technical points are valid
in context, but your personality poisons any chance of having a good
debate with you. Any technical discussion inevitably devolves into
veiled insults, condescension, attacks on "corporate behavior",
attacks on individuals, enabling your crusade against Richard
Heathfield, and poetry when you have nothing useful left to say (in my
opinion).

Good poetry, too. I taught myself how since I teach creative writing,
from the Norton Anthology and John Lennard's The Poetry Handbook. It
comes in handy in these newsgroups since like my programming skills,
nobody can even come close:

There is a fine Lady named Julienne
Who feels not a little frustracienne
Owing to spinoza's replies:
They make her give vent to Sighs,
That discombobulated Lady, named Julienne

Julienne, in civil discourse, it is not an insult to demur. In the
corporation, for a very good reason that low-level people in
corporations (which all data processing people are) are almost never
given resources by the CEO class to do what needs to be done, a
Leninist rule is applied that cuts civil discourse and demurral off at
arbitrary times. It is understandable that this results in a general
wound, and wounded spirits.

But I simply refuse to acknowledge that here, where no corporate
Leninism need cut off discussion unless people have internalized
corporate slavery, it is insulting to maintain a position with vigor.

What's insulting are people like Richard Heathfield who can't read
code and seizes upon trivia such as malloc.h in order to waste my
time, while enabling bullying. Or Keith Thompson, a zany, who thinks
he can count my errors while not reading my posts, in his sleep as it
were. Or Peter Seebach, who calls me, an Apress colleague of his, a
"moron" to third parties in a way that would get him punched out in a
social event by a real man.

The cowardice of these people is matched by their narcissism in which
they make the stupidest possible errors while expecting forgiveness,
while creating here a permanent record of uncalled for attacks on
professional credibility.

So no, dear lady, I am not insulting you.

Honestly, I'm tired of talking to a brick wall. Let me know when
you're ready to take me seriously and we may actually be able to chat
in a civil manner.


You're in no position to tell me not to defend myself when I feel I'm
being "bullied" by a "thug", since you're so adamant about taking that
right for yourself at every turn.

If questioning your conclusions politely and urbanely is bullying you,
then you have a strange definition of bullying. If you were my
supervisor and ordered me to use Richard's technique for creating a
linked list, I'd air my objections briefly, and then do it your way.
But here I am under no such obligation.

 

[Malcolm McLean]

What's insulting are people like Richard Heathfield who can't read
code and seizes upon trivia such as malloc.h in order to waste my
time, while enabling bullying.

So I write code using malloc.h. As it turns out, my compiler uses
alloc.h. It takes all of a second to hit the backspace and delete the
"m".
But what happens when we shop the code. It refuses to compile. So
someone who knows C edits it. But that means its got to go into a
different version. Then it hops to machine that takes malloc.h. So its
now in version 3.
The someone finds a bug with the code. He thinks, "obviously, this is
version 3, whilst we were shipped version 1. So let's test the code
with version 1." So he digs out version 1, recompiles, same bug. OK,
the bug was in the original version. As a matter of routine he diffs
the code. Version 1 and version 3 are identical. So maybe what he
thought was version 3 wasn't the real version 3. So he's on the phone,
talking to a guy who left the company who made the original version 2,
trying to find out what went on.
Eventually it will be sorted. But that's the sort of thing that
happens when you have tiny glitches in code.

 

[Nick Keighley]

[...] 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
computer science? The STL is "value based" and copies the data. You
can make the data a pointer if you want to, but you don't have to.

<snip>

 

[Chris M. Thomasson]

spinoza1111 wrote:


And where, pray tell, are you going to *store* your elements?

In another object? Well, I personally enjoy embedding list nodes directly
into elements:
__________________________________________________________
struct node
{
struct node* next;
};


struct element
{
struct node node;
/* [whatever] */
};
__________________________________________________________



This way I do not have to allocate a seperate node to hold a pointer to the
element. Humm... I think there are basically three ways to do this.


1. Store a pointer to element:

struct node
{
struct node* next;
void* element;
};




2. Store a copy of the element in a node and have the container manage all
the memory:

struct node
{
struct node* next;
void* element;
size_t size;
};




3. Store nothing in a node and let the user "extend" it as nessesary:

struct node
{
struct node* next;
};




I tend to prefer method 3 over anything else because, IMHO, its the most
flexible. For instance, you can easily implement methods 1 and 2:


1.


struct node_ex
{
struct node node;
void* element;
};



2.


struct node_ex
{
struct node node;
void* element;
size_t size;
};

 

[Chris M. Thomasson]

spinoza1111wrote:

[...] 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
computer science? The STL is "value based" and copies the data. You
can make the data a pointer if you want to, but you don't have to.

IMHO, the C++ STL is missing an entire class of fairly important containers:

http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intrusive_vs_nontrusive.html

C++ is all about non-intrusive containers, which have unnecessary overheads
in some usage cases. If I want to push an object onto a list, why does the
damn container have to allocate anything at all? If I know that the object
is only ever going to be on one or two, perhaps three lists, I can embed the
nodes for said lists directly into the object. Of course this has some
caveats, but it gets around unnecessary memory allocations/deallocations in
certain cases.

 

[Nick Keighley]

Malcolm is describing a real application that needs data structures
above the level of characters and strings. In fact, it sounds ideal
for linked string segments.

ok, fair point. DNA analysis would be an application where you
couldn't afford to copy the data.

 

[Nick Keighley]

spinoza1111wrote:

Heathfield wrote a "linked list tool"
without pointing to data,

[...] 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
computer science? The STL is "value based" and copies the data. You
can make the data a pointer if you want to, but you don't have to.

IMHO, the C++ STL is missing an entire class of fairly important containers:

http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intrusive_vs_...

C++ is all about non-intrusive containers, which have unnecessary overheads
in some usage cases. If I want to push an object onto a list, why does the
damn container have to allocate anything at all? If I know that the object
is only ever going to be on one or two, perhaps three lists, I can embed the
nodes for said lists directly into the object. Of course this has some
caveats, but it gets around unnecessary memory allocations/deallocations in
certain cases.

yes, but the point is a copying container isn't ***necessarily*** a
stupid design decision only made by people without a computer science
education

 

[Andrew Poelstra]

spinoza1111 wrote:


And where, pray tell, are you going to *store* your elements?

In another object? Well, I personally enjoy embedding list nodes directly
into elements:
__________________________________________________________
struct node
{
struct node* next;
};


struct element
{
struct node node;
/* [whatever] */
};
__________________________________________________________

With any struct I create (when memory usage is not a primary
concern), I add a *next pointer to it, just in case I need to
use it in a list.

struct element {
char *name;
char *desc;
long hash;

struct element *next;
}


If it turns out it's using too much memory, or I never need
a linked list, or stack, or queue, then I'll delete the next
pointer. Or maybe add a prev pointer, if I need that.

With trees I follow the same pattern.

Then for any "simple" list structure, I can do list operations
inline. Some of these are one line of code, others as many as
three, but they're all pretty idiomatic, or at least easy to
understand.