Efficency and the standard library

[Ben Bacarisse]

Well, I've been having way too much fun(?) with this toy problem,
writing multiple solutions and then trying out different strategies
for packaging tests, measuring performance, and so forth.

======== OUTPUT (lightly edited to conserve space) ========

simple version of replace():
scans input twice
does not try to avoid recomputing string lengths
uses C library string functions

performing timing tests (4 repeats)

timing (length 4004, changing 2 occurrences of 2 chars to 2 chars) 20000 times
times (seconds): 0.56 0.54 0.54 0.54

You time each call individually with a timer whose granularity you
don't report (it has a resolution of 1 microsecond, but I don't know
if it has that granularity).

The above times work out at about 26.5 microseconds per call, so your
method is probably OK, but it won't work on faster hardware. On my
2.53GHz Core2 Duo P8700-based laptop a similar function takes 1.6
microseconds per call and summing times individual times is not
reliable. [Aside: you can get it to be more reliable (under certain
assumptions) by taking the granularity into account and doing a little
statistics.]

Anyway, I just wanted to check: is more than 16 times slower than mine
times a reasonable result on your machine?

Note: I am not timing your function but mine although I doubt that
much of the 16 times is due to either my code or my system's libc.

<big snip>

 

[Ben Bacarisse]

spinoza1111 wrote:
<snip>

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.

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.

It seems not, or the above struct would have left and right pointers
as well, just in case.

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.

Why not do the reverse: defined the structure pain and add a pointer
if you need one? It's what most people would do and does not seem any
harder than your strategy.

 

[Andrew Poelstra]

It seems not, or the above struct would have left and right pointers
as well, just in case.

That's what I meant - instead of having next/prev, I would
have left/right. I thought I was clear, but reading my last
message, it seems I wasn't.

In any case, it's merely a naming issue.

Why not do the reverse: defined the structure pain and add a pointer
if you need one? It's what most people would do and does not seem any
harder than your strategy.

Because more often than not, I need a variable number of objects
that I need to traverse linearly and do some amount of processing
(enough to justify the potential cache misses, etc, that come from
not using arrays).

If I needed that /less/ often than not, I would certainly do things
your way.


Andrew

 

[Ben Bacarisse]

That's what I meant - instead of having next/prev, I would
have left/right. I thought I was clear, but reading my last
message, it seems I wasn't.

Your point seemed to be that you always put the links in ("in any
struct I create") and that you "follow the same pattern" with trees
which I took to mean you do to always, just in case.

In any case, it's merely a naming issue.

I did not see it like that. If you just make a judgement about what,
if any, links you need, is that not what most people do (unless they
favour some sort of generic containers of course)?

<snip>

 

[BruceS]

Reading buggy code wastes *my* time unless I can reasonably
predict that the OP will learn something from my comments.

I'm sure I'm not the only one here who looks for certain posters
first. If someone *other* than the person you're responding to learns
something from your post, is it still a wast of your time?

<snip>

 

[blmblm]

You time each call individually with a timer whose granularity you
don't report (it has a resolution of 1 microsecond, but I don't know
if it has that granularity).

I'm not sure I understand what you mean by resolution versus
granularity. But it may not be important, if your point is the
one you're making here:

The above times work out at about 26.5 microseconds per call, so your
method is probably OK, but it won't work on faster hardware. On my
2.53GHz Core2 Duo P8700-based laptop a similar function takes 1.6
microseconds per call and summing times individual times is not
reliable. [Aside: you can get it to be more reliable (under certain
assumptions) by taking the granularity into account and doing a little
statistics.]

I think you're exactly right that I should be timing things in
bigger chunks rather than at the level of individual calls.
What was I thinking .... probably that timing individual
calls would fit nicely with the structure of my code. Well.
Another round of refactoring may be in order.

Anyway, I just wanted to check: is more than 16 times slower than mine
times a reasonable result on your machine?

Note: I am not timing your function but mine although I doubt that
much of the 16 times is due to either my code or my system's libc.

Good question. I did my experiments on a machine that's several
years old and was not high-end to start with. /proc/cpuinfo says
the processor is a 2.4GHz Intel Celeron, and I'm compiling with
gcc 4.0.1

I just re-ran the timing tests on something that according to
/proc/cpuinfo is a 3.33GHz Intel Duo, compiling with gcc 4.4.1,
and times were reduced by factors of roughly 3 for the versions
using my string functions and 2.5 for the versions using the
library string functions. If you're using faster hardware or
a smarter compiler .... I don't know; a factor of 16 does seem
like a lot, but maybe?

 

[Ben Bacarisse]

I'm not sure I understand what you mean by resolution versus
granularity. But it may not be important, if your point is the
one you're making here:

I just wanted to distinguish between the precision on the counter
(which is 1 microsecond) and the accuracy of the reported time (which
can be as course as 10 milliseconds (though that might be a memory
from a very old system).

The above times work out at about 26.5 microseconds per call, so your
method is probably OK, but it won't work on faster hardware. On my
2.53GHz Core2 Duo P8700-based laptop a similar function takes 1.6
microseconds per call and summing times individual times is not
reliable. [Aside: you can get it to be more reliable (under certain
assumptions) by taking the granularity into account and doing a little
statistics.]

I think you're exactly right that I should be timing things in
bigger chunks rather than at the level of individual calls.
What was I thinking .... probably that timing individual
calls would fit nicely with the structure of my code. Well.
Another round of refactoring may be in order.

Anyway, I just wanted to check: is more than 16 times slower than mine
times a reasonable result on your machine?

Note: I am not timing your function but mine although I doubt that
much of the 16 times is due to either my code or my system's libc.

Good question. I did my experiments on a machine that's several
years old and was not high-end to start with. /proc/cpuinfo says
the processor is a 2.4GHz Intel Celeron, and I'm compiling with
gcc 4.0.1

I just re-ran the timing tests on something that according to
/proc/cpuinfo is a 3.33GHz Intel Duo, compiling with gcc 4.4.1,
and times were reduced by factors of roughly 3 for the versions
using my string functions and 2.5 for the versions using the
library string functions. If you're using faster hardware or
a smarter compiler .... I don't know; a factor of 16 does seem
like a lot, but maybe?

It's possible, I suppose. I'd time in larger chunks. What I do is
loop in sets of 100 calls until some reasonable time as elapsed (say
5 seconds) and then use the exact elapsed time and the number of sets
actually executed. That way I can time very fact calls (replace a
with x in y) and very longs ones (replace and with x in
war-and-peace.txt) with the same driver.

 

[BruceS]

You make an excellent point. Thanks.

You're welcome. I'm often away from clc for long periods, but when
each time I return, I learn something. I won't list the names I look
for (don't want to insult anyone by omission), but you can probably
guess most of them. Thank you for the value you add to clc.

 

[Chris M. Thomasson]

"Nick Keighley" <[email protected]> wrote in message

[...]

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

IMHO, a non-intrusive container tends to work very well when an object "may"
be on several different lists at "indeterminate" times. Simple example: For
an intrusive container, if an object "might be able" to exist within 5 lists
simultaneously, then I would simply have to embed 5 nodes in the object.
This is fairly inefficient if that object is not on all of those lists at
the same time. If my object only happens to be on a single list during its
lifetime, then I will be totally wasting the memory for the other 4 nodes.
This is one case where the non-intrusive container would be a definite win.

 

[Andrew Poelstra]

Your point seemed to be that you always put the links in ("in any
struct I create") and that you "follow the same pattern" with trees
which I took to mean you do to always, just in case.

It is the same pattern - generally I'm aware of whether I need
a linear list or some sort of tree, and I name my pointers
accordingly. Normally I don't need tree structures, so I use 1
pointer named 'next' and be done with it.

But I (almost) always put the pointer in.

I did not see it like that. If you just make a judgement about what,
if any, links you need, is that not what most people do (unless they
favour some sort of generic containers of course)?

Yes. but the discussion was about the merits of generic
containers versus no generic containers, wasn't it?

 

[ImpalerCore]

"Nick Keighley" <[email protected]> wrote in message

[...]

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

IMHO, a non-intrusive container tends to work very well when an object "may"
be on several different lists at "indeterminate" times. Simple example: For
an intrusive container, if an object "might be able" to exist within 5 lists
simultaneously, then I would simply have to embed 5 nodes in the object.
This is fairly inefficient if that object is not on all of those lists at
the same time. If my object only happens to be on a single list during its
lifetime, then I will be totally wasting the memory for the other 4 nodes..
This is one case where the non-intrusive container would be a definite win.- Hide quoted text -

I agree, and the non-intrusive actually *is* better in my
circumstances. I have a list of 128-byte records that consist of
recorded 1553 avionics data, and by using shallow copies of this list,
I can create a multitude of different views of that data based on
time, what system generated the message, a particular data element's
value, etc, without all the overhead of copying these things around.
When you have files of 10+ million of these records for a single
flight, and a ridiculous amount of different parameters to filter on,
I need all the help I can get, and the non-intrusive version works
much better. I can create an initial linked list to a set of records
in a big memory chunk, create a view (shallow copy) of that linked
list based off a filter, and I'm good to go. I can then destroy the
view when the user is done, or filter it to make a more specific view
(i.e. I want to look at the GPS navigation system, subaddress 16, word
4, from time 13:45.00 to 13:50.00 to see what was going on when the
pilot noticed the indicator turn red).

I think that this is the *best* motivating reason that pushes the
design of a generic linked list to use a non-intrusive
implementation. Non-intrusive lists can make deep copies, but it
requires the user to make the deep copy deliberately. That is not to
say that intrusive lists don't have their place, but I believe that
they should be used in specific, rather than generic applications.

 

[spinoza1111]

On Sun, 14 Feb 2010 02:15:15 -0800 (PST),spinoza1111
that was competent. =A0I think you are now some sort of
manager

[snip]

who is today unable, unlike me, to crank this level
of code in the time I took...about two hours for the first
version, and a total of 8..10 hours thereafter.
I certainly hope that I am never able to crank out that
level of code, regardless of the time it takes.

I don't know what you mean. Do you mean you never hope to become as
truly competent as I am, since in programming (which is now a cost
center in which creative and intelligent people are now merely
disruptive) such great code merely attracts envy and infantile rage,
such as we see in Seebach?

Oddly enough, no.  You flatter yourself excessively.  To be fair,
from time to time I have turned out code as bad as yours or
worse.  However I had the grace not to brag about how good it
was.

To a cybernetic mob, or a real mob, people filled with the fear of
their own exposure and shame, all code is "bad" for the same reason
the mob in Julius Caesar tears Cinna the poet apart for his "bad
verses" once they figure out he's not Cinna the conspirator.

Good code is so unfamiliar to people in these newsgroups they have no
idea what it would look like.

[snip]

I think what's best, then, would be to rename them retaining my great
pre-Syzmonyi Hungarian and index followed by a trailer as in
ptrIndex3match.

But: you recognized them as index variables.

I don't have any hope of convincing you that your naming policy
is unsound, but I feel it worthwhile to do it anyway.

Here are the variables that you defined, including the calling
sequence.

    char * strMaster,
    char * strTarget,
    char * strReplacement,
    long * ptrReplacements

    char * ptrIndex0;
    char * ptrIndex1;
    char * ptrIndex2;
    char * ptrIndex3;
    char * ptrIndex4;
    char * strNew;
    char * strNewStart;
    long lngNewLength;
    long lngCount;
    long lngReplacementLength;
    struct TYPsegmentstruct * ptrSegmentStructStarts;
    struct TYPsegmentstruct * ptrSegmentStruct;
    struct TYPsegmentstruct * ptrSegmentStructPrev;

Now let's remove all of the idiosyncractic type specifiers from
the names.  The results are in quotes because some names are
empty.  Names with "Index" in them are problematic; however you
seem to be treating "Index" as a type qualifier despite the
capitalization.

"Master"
"Target"
"Replacement"
"Replacements"

"0"
"1"
"2"
"3"
"4"
"New"
"NewStart"
"NewLength"
"Count"
"ReplacementLength"
"Starts"
""
"Prev"

Some of these names are meaningful, some are not.  A variable
name may have several parts.  The essential part, however, is the
signifier that points to its role or usage.  Well chosen
signifiers are meaningful.  Many of yours are not.

That's just silly. You remove a prefix designed to make the names
meaningful, and conclude that the result is not meaningful. Nice shot.
Everybody say "nice shot".

The reason that "Index" is problematic is that iyt is generic.
It says nothing about what the index is pointing to.  "0" etc

Of course not. You took out the pre-Szymonyi Hungarian.

This newsgroup reminds me of a bunch of competence-challenged
programmers at Hooters, or an episode of The Annoying Orange.

 

[spinoza1111]

The five bugs in the replace() solution were fixed without your help
last week while you obsessed over the unnecessary inclusion of
malloc(), which wasn't a bug. I've concluded that you're not qualified
as a bug finder, since you were motivated to find them in order to
maintain your position.

I'm sure I'm not the only one here who looks for certain posters

That's the problem. Since you've not bothered to really learn your
trade, it's all personalities.

 

[spinoza1111]

spinoza1111wrote:



When you get even trivial things wrong, it's a potential warning sign
that the rest may be problematic. Having said that, everybody gets
trivial things wrong from time to time. But when you take a long time to
get them right even after they've been pointed out to you, that suggests
even more strongly that the rest of the code is likely to have severe
problems. Reading buggy code wastes *my* time unless I can reasonably
predict that the OP will learn something from my comments. Experience
shows me that this is generally not the case with you. If you want me to
try to find non-trivial errors in your code, I will be glad to oblige if
I can, but only after you've fixed the trivial errors. So if you don't
want me to point out the trivial errors, don't make any.

Translation: you weren't qualified to find the non-trivial errors,
whereas other posters were.

Including (or omitting) malloc.h is not an indicator of more serious
problems. What I've shown you is that it's quite possible to know less
about C than you and yet be a better programmer by orders of
magnitude, since you're so full of shit about "standard C" that you've
lost real skill, assuming you ever had it.

I see people here following your lead and taking you seriously who are
wrestling still with problems that were addressed last week, while
boasting, strangely, of how little time their code snippets
take...where it would seem to me that the rage to take a short time is
something for frightened little clerks.

 

[spinoza1111]

spinoza1111wrote:

<snip>




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

They are already "stored", by definition, since we receive them using
your pointer to void.

I could see a role for a linked list that provided copying into each
node as an option, but the most common application points to material
stored elsewhere. For example, a linked list is formed of identifiers
in a one-pass compiler of all identifiers not defined yet. When a
definition is found, the list is searched (linearly or using a more
sophisticated algorithm). The pointers in the list are addresses of
entries in the symbol table. It would be folly to copy the string
identifiers or entire symbol table addresses into nodes of the list,
but your "reusable" linked list processor in C Unleashed provides no
support for what is usually needed.

 

[spinoza1111]

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.

No, Malcolm, it's the sort of thing which happens when you use C,
which has a legacy design that's basically inadequate today. Richard's
*bricolage* doesn't add up to "good code".

I agree that the inclusion was unnecessary and poses a (trivial) risk.
I took it out for that reason. But in fact, "porting" C, given
aliasing, takes a lot of diligence and issues cannot be addressed by
default.

In the example, you just take out malloc.h and test everything.
Competent C programmers (a small set indeed, and one not co-extensive
with "people who know a lot about C") will do as I did with replace()
and provide a comprehensive regression test suite.

 

[spinoza1111]

[...] 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" 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.

Americans say confidently, being denied the free and merit based
university educations available elsewhere by a barbaric economy, that
they can think of a better "mousetrap". The presumption is that the
university is like the job: no critical reception need occur,
therefore the academics will communicate unquestioned information.

There are problems with links. But to know these problems, you have to
know links, and to know them you have to use them (properly). Because
"pointer to void" is not really a pointer in C, you need to either
write a new linked list processor for each different data type (not a
problem for simple applications) or use preprocessor macros to hide
the type detail.

That is, when, and only when, you accomplish what Stepanov
accomplishes, let me know.

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.

Which I've already concluded might be a good idea in a linked list
tool. Likewise, a linking string library should probably allow strings
to be copies in segments OR pure links to mallocated, NUL terminated
strings (string maps).

Heathfield's code gave no evidence that he thought hard on both sides
of the fence. Instead, it appears that he was hag-ridden by folk-lore
about the badness of pointer to void and using the preprocessor. His
thinking about code in general is quite different from that of the
well-educated, since it's driven by myths he's learned second-hand,
the politics of personality, and a nasty Fundamentalism.

 

[spinoza1111]

spinoza1111wrote:


That's your job.

No, I do not work for you,
And I never ever will,
In whatever estaminet or zoo
In which you work as some sort of shill.

 

[spinoza1111]

spinoza1111wrote:


Stored *where*? According to you, it would be incompetent to put them
into a container (e.g. an array or a copy-on-add dynamic data
structure). So where are you going to keep them?

If you have the data for copying, then it's addressible and available
at the time the linked list is created. It's true that there is a new
dependency in the code, and this is that the linked list must be
freed, or considered invalid, if the source data is freed. But as I
have said, making a copy is worse if the source is later freed because
it is no longer correct, because in that case, the linked list data
may only appear to be valid, creating buggy software that only "seems
to run"...which is often standard operational bullshit in business
computing.

Ah, I see - you're going to keep them in a container. Well, how about that?

No, you don't see.

 

[spinoza1111]

spinoza1111wrote:
<snip>

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;



};

A very good solution, but if you have multiple ways of chaining data
together, you're going to have to have arrays of nodes. And it doesn't
solve the problem addressed in C Unleashed which was to create a
reusable tool for handling linked lists.

You could write reusable software for handling pure node structs, but
that would necessitate a "callback" when you get to the problem of
comparing two linked lists for identity, or searching the list for a
value.

The problem of linked lists is elegantly solved in your way in OO
code, since you can inherit a List and put your own data in it.

The problem is that Richard's "reusable" software only seems to have
considered one way, and this was a way that copies O(n) bytes and
creates the risk of having two copies of data. To be truly reusable it
needed to support three alternatives: linked list of copies, linked
list of pointers, or a pure linked list such as yours consisting only
of links to the next element (one with "null" data).

But this would have involved more advanced use of the preprocessor. My
complaint is the implicit presentation of only one way without
discussion of the alternatives, in the manner of the Fundamentalist
that Richard appears to be.