Change in C
jacob navia
message from Mr Heathfield that warrants a deeper discussion.
That thread was (for a change) an interesting one.
Richard Heathfield a �crit :
>
> It is perhaps because software is so malleable that we are so tempted
> to change it. I doubt whether *any* computer language exists that
> *exactly* meets the needs of more than a handful of people, so it is
> natural for people to want to change the language(s) they use to suit
> their needs more closely.
>
Software changes not because the people that write it need changes just
for the sake of it. Requirements change. Hardware evolves, people come
and go, the machines and environment where software exists changes.
Only dead things are fixed forever and can't evolve. A computer language
MUST change or it simply dies.
> Changing a language can have advantages, but it also has
> disadvantages.
>
Yes. What *I* see as disadvantages of change is when it is change in the
wrong direction. For instance, let's take the example of the C++
language that was originally designed to improve C and change it for the
better.
In a recent paper, the creator of the language acknowledged that after
3 years (more or less) working in an improvement of C++ it was
impossible for him to realize the requested modification.
The concrete details are not important here. Briefly, it was the
introduction of "concepts" as descriptions of template arguments so that
those arguments could be checked. A reasonable proposal.
The problem is that C++ has grown so complex, that even the creator
and principal force behind C++ was unable to do that change in a
time frame of years.
Change in the wrong direction is, then, a change that complexifies
more than what it is required, without any big simplification to
gain for the effort of introducing a feature.
> One obvious advantage is that the language can be made more
> expressive. For example, there is no doubt (in my mind, at least)
> that operator overloading would make bignums much more palatable. So
> it's natural to want to adapt the language to incorporate changes
> like this.
>
The advantage of operator overloading is that it is a change that
simplifies the language, allowing it to get rid of "ad hoc" stuff.
C99 introduced complex numbers into the language itself. This was
a mistake since not every C user needs complex numbers as a permanent
feature.
With operator overloading, only the people that need (or want) to use
the feature will have complex numbers. What's more, they can use
different implementations of complex numbers that better suit the
needs of their applications instead of being forced to use a single
implementation provided by the compiler vendor that should be perfect
for all usages,what is impossible.
Operator overloading simplifies the writing of counted strings packages
(using the natural '[' ']' syntax already used for strings) instead
of forcing the people that want a diffferent and more advanced string
type to use a horrible syntax that makes porting to the new package
much more difficult.
Operator overloading simplifies the language by adding a framework
where the users themselves can add new numeric types to the application
without requiring a language change for each type. Features like
complex numbers then, can be eliminated, making the resulting language
smaller.
> But there are disadvantages, too. If every proposal for change were
> accepted, we'd soon have a complete mess, a self-contradictory
> language with no consistency in its constructs or syntax. So, even if
> we're in favour of language change, we have to be selective if we're
> going to prevent a descent into chaos.
>
When changing things you must strike a delicate balance between the need
to preserve the language as it is, and the need to change it, to adapt
it to a new environment.
The core features of C (speed of generated code, simplicity, and
transparency) should be maintained at all costs. Operator overloading
makes the language less transparent since it is not obvious when you
read
a=b*c;
that you are using ints or doubles as it is now. As long as the user
of the new feature uses it in the intended manner (for numeric data)
everything will work. That is why, in my implementation of operator
overloading, I explicitely did NOT overload addition to "add" strings.
Normally, a + b <==> b + a. Addition is transitive.
If you use strings
"abc" + "def" != "def" + "abc"
and this is not acceptable. Besides, concatenating strings is not an
addition. It is just that: concatenation and the reader of the program
understands immediately what is going on when he sees:
strcat(buf,"abc");
> And even if we /are/ selective, a high rate of change makes it
> difficult for implementors to keep up. Even the comparatively modest
> changes introduced by C99 have yet to filter through, in their
> entirety, to the real world, ten years after the changes were
> introduced to the Standard.
C99 did not bring any real change into the core problems of the C
language.
It did NOT address:
(1) The problem of a completely obsolete standard library with functions
like gets() or asctime() still there.
(2) The problem of the absence of a counted string data type
(3) The problem of the lack of a standard way of using containers like
lists, hash tables, or similar.
There wasn't any INCENTIVE for the compiler writers to implement the
changes because many of them (complex numbers, syntactic innovations
or similar stuff) didn't bring any substantial improvement.
The problem was not that the changes were difficult to implement but
that they did not bring anything really new that customers were
really asking for.
> The inevitable result will be
> fragmentation, with implementors picking and choosing the changes
> they want to include. Portability suffers enormously, unless you
> stick to the lowest common denominator (if it exists and is
> sufficiently powerful, which - fortunately - is currently the case
> for C).
>
Mr Heathfield's pet subject: C89. Yes, that is the common denominator
and many people are unable to see beyond that and realize that 30
years later you just can't go on like if nothing has happened!
> So it's a trade-off. Every feature you introduce, every change you
> make, has a cost as well as (presumably) a benefit.
>
> Personally, I am of the opinion that anyone who wants to make major
> changes to the language would serve the world better either by
> switching to an existing language that has the desired features or,
> if that isn't possible, by designing a new language, and giving it a
> different name.
>
This conservative conclusion is the opinion of some of people in
this discussion group.
Obviously this leads to the complete destruction of C as a living
language. It ceases to evolve, and it is considered by most people
as a dead language.
I am completely and fundamentally opposed to that point of view. I
think C is a better language than C++ and many others precisely because
of the simplicity it has. Because the speed of the generated code.
Because you see what is going on in your program and within your
software.
But obviously the C++ people will not believe that, and the fossilized
group of programmers that are clustered around heathfield will not
believe that either.
What to do?
I do not know.
Richard Heathfield
<snip>
> Software changes not because the people that write it need changes
> just for the sake of it.
Well, that's not the /only/ reason software changes, but change for
change's sake /does/ happen.
> Requirements change. Hardware evolves, people come and go, the
> machines and environment where software exists changes.
All true. And the problem is that those new requirements are not (or
at least need not be) the same for everybody. So we have the very
real possibility of Powerful Lobby A requiring a change in the
language which is incompatible with the change required by Powerful
Lobby B.
> Only dead things are fixed forever and can't evolve. A computer
> language MUST change or it simply dies.
That's a poor analogy. A tool can be useful even if it doesn't change.
I have several screwdrivers in my toolbox, all of which must be
twenty years old or more. They all still work just fine. They *can't*
change, but they remain useful. If C changes, it will presumably
become better at doing (or rather, facilitating) some tasks, but
there will always be a cost, and that cost may well be a drop in
portability.
> > Changing a language can have advantages, but it also has
> > disadvantages.
> >
>
> Yes. What *I* see as disadvantages of change is when it is change in
> the wrong direction.
That is certainly one disadvantage, yes. It is not the only
disadvantage.
> For instance, let's take the example of the C++
> language that was originally designed to improve C and change it for
> the better.
Whatever the intent, the fact is that C++ is a useful language. It
actually did improve C a little bit, if (as I do) one thinks of, say,
prototypes as improvements. But mostly it just became a new language.
Not "a better C", just a different language originally based on C.
<snip>
> > One obvious advantage is that the language can be made more
> > expressive. For example, there is no doubt (in my mind, at least)
> > that operator overloading would make bignums much more palatable.
> > So it's natural to want to adapt the language to incorporate
> > changes like this.
>
> The advantage of operator overloading is that it is a change that
> simplifies the language, allowing it to get rid of "ad hoc" stuff.
And one obvious disadvantage, for those of us who are not immortal, is
that it will take at least 10 years (and probably more like forever)
to get it into the Standard and a long time after that before it is
universally implemented.
> C99 introduced complex numbers into the language itself. This was
> a mistake since not every C user needs complex numbers as a
> permanent feature.
If complex numbers had met the needs of even a significant minority of
C users, the change might conceivably have been justifiable. But I
don't think it does even that.
<snip>
> > But there are disadvantages, too. If every proposal for change
> > were accepted, we'd soon have a complete mess, a
> > self-contradictory language with no consistency in its constructs
> > or syntax. So, even if we're in favour of language change, we
> > have to be selective if we're going to prevent a descent into
> > chaos.
> >
>
> When changing things you must strike a delicate balance between the
> need to preserve the language as it is, and the need to change it,
> to adapt it to a new environment.
Right.
<hobbyhorses and personal attacks snipped>
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
Seebs
> C99 did not bring any real change into the core problems of the C
> language.
It brought a number of changes that were directly related to core
problems which were significant to implementors.
For instance, restrict pointers, mixed declarations and code, and
variable-length arrays; all of these address real-world problems
which made life harder for compiler writers and coders looking at
high-performance systems.
> It did NOT address:
> (1) The problem of a completely obsolete standard library with functions
> like gets() or asctime() still there.
That problem is not likely to get addressed. Quite simply, the functions
are there to support existing code, but you don't have to use them.
The library DID add several needed functions (snprintf among them) which
make it more possible or practical to write safe and efficient code for
a number of real-world circumstances.
> (2) The problem of the absence of a counted string data type
I solved that problem once. It took me maybe a month to do a library of
self-managing string-like objects, and it's worked fine ever since. I'm
not sure the language needs it, though I wouldn't object.
> (3) The problem of the lack of a standard way of using containers like
> lists, hash tables, or similar.
I don't think this is a problem to be solved at the language level,
although I could be persuaded otherwise if someone had a good demo.
> There wasn't any INCENTIVE for the compiler writers to implement the
> changes because many of them (complex numbers, syntactic innovations
> or similar stuff) didn't bring any substantial improvement.
Only they did. Who do you think proposed those?
> The problem was not that the changes were difficult to implement but
> that they did not bring anything really new that customers were
> really asking for.
Uh.
On the one hand, we have representatives paid for and sent by Sun, SGI,
and IBM. On the other hand, we have you. The people from the large companies
with active compiler development groups and hundreds or thousands of
customers said they needed to provide these features for their customers,
and they wanted standardized forms so customers could use these features
without freaking out.
> Obviously this leads to the complete destruction of C as a living
> language. It ceases to evolve, and it is considered by most people
> as a dead language.
Honestly, if it didn't evolve, it would still remain useful for quite a
while yet. Most of what I do can still be done reasonably in C89.
-s
--
Copyright 2009, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
Keith Thompson
[big snip]
> But obviously the C++ people will not believe that, and the fossilized
> group of programmers that are clustered around heathfield will not
> believe that either.
jacob, is it not possible for you to discuss the language without
personal insults?
"Why not getting positive for a change?"
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Seebs
> jacob, is it not possible for you to discuss the language without
> personal insults?
Oh, geeze. I just realized we're in comp.lang.c., not
alt.richard.heathfield.die.die.die. I bet he was making the same
mistake. Easy to understand, eh?
-s
p.s.: I actually like Richard. I'm not sure I agree with him about
a lot of things, but he's polite, informed, and pleasant to interact with.
BGB / cr88192
"jacob navia" <ja...@nospam.org> wrote in message
news:h8rs80$dea$1...@aioe.org...
I would much rather have a simpler modular language.
in this case, the core language can remain fairly well fixed, and fairly
simple, but implementations are free to dump in "extensions".
it would be nice if many of these extensions were themselves specified, but
essentially optional from the POV of the implementation (much like the
situation with 3rd party libraries).
for the core language, I would actually like a "simpler" core than C, such
as:
context independent and unambiguous syntax;
dropping a few older-style syntax conventions;
...
so, an "extension" could be the addition of a C like pointer and
type-system, but with an implementation free to refuse this (allowing only
opaque types).
another such "extension" could be allowing dynamic types or an object
system.
means could be provided to allow the implementation to cleanly extend the
core syntactic elements, absent having to resort to terrible syntax (for
example, as for many GCC'isms or MSVC'isms).
so, the core language would be simple, and with a few bolted on extensions,
it could transform to be like other languages: C, GLSL, Java, ECMAScript,
...
granted, if done entirely cleanly though, it is unlikely the language could
strictly implement any of them (and, like anything else, the addition of
extensions greatly increases the risk of an inflexible tangled mess).
it would also require specifying the language a lot more at the level of the
parser and compiler internals than is usually done with languages like C,
which if not done well could greatly increase the complexity of an
implementation.
note, the idea would not be here that these extensions would exist "within"
the language (as is the ideal with C++), rather, that the compiler machinery
would be "pluggable" (in a formally defined but likely implementation
dependent manner...).
I don't expect such an idea to generate much interest though.
more something for some of us VM implementors to fantasize about, after
facing the horrors of implementing a compiler framework and attempting to
extend it to handle several different languages.
at nearly every level (from the machine code on up), there are layers upon
layers of tangled mess, little if anything having been cleanly designed
(some things are just ill-designed, others are blatent examples at prior
attempts at over-engineering, ...).
so, the question is how to have clean and flexible designs without adding
unnecessary complexity (or over-engineering things). people have tried, and
all their efforts simply add more to the pre-existing mess (as, like string,
each piece of complexity tangles itself into knots with the other
complexities of other peoples' overengineering...).
I am not sure if, in the larger sense, these problems are actually
solvable...
we just continue to live in a world of knotted string...
(and, in the end, such a language would likely turn into a bigger mess than
that which it was intended to replace...).
<snip, not much to comment>
I will note that operator overloading is a feature, but it is far from being
a silver bullet...
Richard Heathfield
> On 2009-09-16, jacob navia <ja...@nospam.org> wrote:
<snip>
>> (3) The problem of the lack of a standard way of using containers
>> like
>> lists, hash tables, or similar.
>
> I don't think this is a problem to be solved at the language level,
> although I could be persuaded otherwise if someone had a good demo.
The problem is not the lack of a good demo, but the existence of many,
many, many, many, many many many good demos. All different. Choose
any one to standardise, and you cheese off everyone else, because
they will have had good reasons for rejecting it. (One man's meat,
and all that.)
<snip>
jacob navia
> In <slrnhb33gm.4a8...@guild.seebs.net>, Seebs wrote:
>
>> On 2009-09-16, jacob navia <ja...@nospam.org> wrote:
>
> <snip>
>
>>> (3) The problem of the lack of a standard way of using containers
>>> like
>>> lists, hash tables, or similar.
>> I don't think this is a problem to be solved at the language level,
>> although I could be persuaded otherwise if someone had a good demo.
>
> The problem is not the lack of a good demo, but the existence of many,
> many, many, many, many many many good demos. All different. Choose
> any one to standardise, and you cheese off everyone else, because
> they will have had good reasons for rejecting it. (One man's meat,
> and all that.)
>
> <snip>
>
This is just not true. Yes, there are a lot of libraries but there is
no need to make them obsolete, to the contrary. The committee should
just define a common interface, where all those libraries could
communicate. Libraries that are already being used can be used
in the future with no change.
It is the need to rewrite again and again the same list management
functions, hash table management functions, etc, that makes people
leave C as development language. Yes, you can have a library of
your own, or use some library but since there is no established
interface you will need to make adjustements when you have to
interface with code that uses a slightly different convention.
Many standard library functions use the convention:
function(destination,source)
like memcpy, strcpy or similar. This is easy to remember and
improves learning.
lcc-win proposes a (rather primitive, granted) containers library
using a function table approach.
Each container has as first element a table of functions that
can be used to store the functions that apply to that
container. This allows two things:
1) Naming of the function pointers can be simple words like
Append, Remove, whatever, without impacting the user name
space since they are just members of a structure
2) Function pointers can be subclasses, i.e. if some library
function doesn't fill your needs you put at any time
your own that can do some partial job before, or after
or instead of the normal library function.
If you do not like
list->Insert(list,item,position)
because of some reason, you store the existing function pointer
somewhere, do some preprocessing, call the old function pointer and
do some postprocessing. Or you can replace the library function
entirely.
This approach is very flexible and can be done in standard C. There are
NO language modifications needed at all!
Richard Heathfield
> Richard Heathfield a �crit :
>> In <slrnhb33gm.4a8...@guild.seebs.net>, Seebs wrote:
>>
>>> On 2009-09-16, jacob navia <ja...@nospam.org> wrote:
>>
>> <snip>
>>
>>>> (3) The problem of the lack of a standard way of using containers
>>>> like
>>>> lists, hash tables, or similar.
>>> I don't think this is a problem to be solved at the language
>>> level, although I could be persuaded otherwise if someone had a
>>> good demo.
>>
>> The problem is not the lack of a good demo, but the existence of
>> many, many, many, many, many many many good demos. All different.
>> Choose any one to standardise, and you cheese off everyone else,
>> because they will have had good reasons for rejecting it. (One
>> man's meat, and all that.)
>>
>> <snip>
>>
>
> This is just not true.
Um, yes it is. Saying it ain't true doesn't make it untrue.
> Yes, there are a lot of libraries but there
> is no need to make them obsolete, to the contrary.
In which case why standardise?
> The committee
> should just define a common interface, where all those libraries
> could communicate. Libraries that are already being used can be used
> in the future with no change.
Problem is, there are many, many, many, many, many many many
interfaces out there, all different, many of them good. Choose any
one to standardise, and you cheese off everyone else, because they
will have had good reasons for rejecting it. (One man's meat, and all
that.)
> It is the need to rewrite again and again the same list management
> functions, hash table management functions, etc, that makes people
> leave C as development language.
Write once, read many.
> Yes, you can have a library of your own, or use some library
Right.
> but since there is no established
> interface you will need to make adjustements when you have to
> interface with code that uses a slightly different convention.
Right.
> Many standard library functions use the convention:
> function(destination,source)
> like memcpy, strcpy or similar. This is easy to remember and
> improves learning.
Right.
<software advertisement snipped - if you want to talk about this,
fine, but please do it without spamming>
Seebs
> This is just not true. Yes, there are a lot of libraries but there is
> no need to make them obsolete, to the contrary. The committee should
> just define a common interface, where all those libraries could
> communicate. Libraries that are already being used can be used
> in the future with no change.
Uh, no.
The problem is that they are designed to solve the problem in
substantially different ways.
> Each container has as first element a table of functions that
> can be used to store the functions that apply to that
> container. This allows two things:
> 1) Naming of the function pointers can be simple words like
> Append, Remove, whatever, without impacting the user name
> space since they are just members of a structure
> 2) Function pointers can be subclasses, i.e. if some library
> function doesn't fill your needs you put at any time
> your own that can do some partial job before, or after
> or instead of the normal library function.
And
3) Overhead of extra storage (the table) for every single container,
plus overhead of indirect function calls (more expensive on many systems),
plus a huge number of potential problems. Is the table actually stored
in each object? Then it's a huge waste of space. Do we store only a
pointer to the table? Then we have allocation issues with the risk of
dangling pointers or leaked memory, and we have to establish some kind
of pattern for determining whose job it is to allocate the storage.
Oh, and of course, if it's a pointer to the table, you've just added
ANOTHER indirection.
> This approach is very flexible and can be done in standard C. There are
> NO language modifications needed at all!
So go write it and pitch it to people. My guess is that you'll find that
it's sufficiently inefficient and introduces enough extra complexity that
people will prefer to write and use their own.
In short, not a good candidate for standardization.
jacob navia
>
>> Each container has as first element a table of functions that
>> can be used to store the functions that apply to that
>> container. This allows two things:
>
>> 1) Naming of the function pointers can be simple words like
>> Append, Remove, whatever, without impacting the user name
>> space since they are just members of a structure
>> 2) Function pointers can be subclasses, i.e. if some library
>> function doesn't fill your needs you put at any time
>> your own that can do some partial job before, or after
>> or instead of the normal library function.
>
> And
>
> 3) Overhead of extra storage (the table) for every single container,
It depends how do you implement the containers. The overhead in
lcc-win's implementation is one pointer for each container and
one table for every container type.
For a list of 30 elements (say) you have only one pointer
and one table. Since the table is the same for all lists, you
have only one table floating around, so the actual overhead is
one pointer per container what is absolutely nothing. For long
lists (100 elements) the actual size of the objects stored will
overwhelm easily the size of the container structure.
> plus overhead of indirect function calls (more expensive on many systems),
this is very cheap, making it 2-3 instructions more maybe, in most
machines.
> plus a huge number of potential problems.
Sure, there are infintely many *potential* problems. A meteorite can
strike the programmer when he is using the library function, his
mother can call him to remind him to wash the dishes and he can
get nervous and use the library function incorrectly...
and
:-)
> Is the table actually stored
> in each object?
No, of course!
Then it's a huge waste of space.
> Do we store only a
> pointer to the table?
Yes.
> Then we have allocation issues with the risk of
> dangling pointers or leaked memory, and we have to establish some kind
> of pattern for determining whose job it is to allocate the storage.
There is no allocated memory for the pointer! What are you speaking
about? The pointer points to a static global table for all containers
of the same type.
> Oh, and of course, if it's a pointer to the table, you've just added
> ANOTHER indirection.
>
Yes, that allows to replace the whole table easily.
>> This approach is very flexible and can be done in standard C. There are
>> NO language modifications needed at all!
>
> So go write it and pitch it to people.
Then, after having written it, heathfield says that I am spamming :-)
> My guess is that you'll find that
> it's sufficiently inefficient and introduces enough extra complexity that
> people will prefer to write and use their own.
Yes, since there is no support for it in the standard library. C++ could
manage such a leverage because they standardised the containers and
provide code for the most common ones. A similar thing can be done in
C, but we are too busy keeping it "as it is", and rewriting and
debugging thousand times the same stuff!
> In short, not a good candidate for standardization.
You just raised some potential problems that aren't actually there.
jacob navia
> <software advertisement snipped - if you want to talk about this,
> fine, but please do it without spamming>
>
proposal and qualify it as "spam".
Very easy.
Seebs
> lcc-win's implementation is one pointer for each container and
> one table for every container type.
Who owns allocation of the table?
When and where do you do the sanity checks (table pointer valid,
entries in table valid)?
> For a list of 30 elements (say) you have only one pointer
> and one table. Since the table is the same for all lists, you
> have only one table floating around, so the actual overhead is
> one pointer per container what is absolutely nothing. For long
> lists (100 elements) the actual size of the objects stored will
> overwhelm easily the size of the container structure.
So the table's in the container, not the elements? So that doesn't
work for a lightweight list (no container object, just list members).
And if you look at a lot of the list implementations out there,
there's no "container" separate from list elements. (And think
about it; in practice, it seems you're going to need to have a pointer
back to the container in every element, or you're going to have to
pass the container around along with the elements...)
> this is very cheap, making it 2-3 instructions more maybe, in most
> machines.
If there's no sanity checks, sure. But then it's pretty risky and
error-prone.
> There is no allocated memory for the pointer! What are you speaking
> about? The pointer points to a static global table for all containers
> of the same type.
What prevents someone from allocating a table at runtime?
If you don't let people allocate (or modify) the table at runtime, you're
killing flexibility -- the ability to dynamically load a new container
from a library would be awfully useful. If you do, you had better do
sanity checks ALL THE TIME.
>> Oh, and of course, if it's a pointer to the table, you've just added
>> ANOTHER indirection.
> Yes, that allows to replace the whole table easily.
And adds more cycles.
> Then, after having written it, heathfield says that I am spamming :-)
If you're advertising it, and some users would have to pay money to use
it, you probably are.
> Yes, since there is no support for it in the standard library. C++ could
> manage such a leverage because they standardised the containers and
> provide code for the most common ones. A similar thing can be done in
> C, but we are too busy keeping it "as it is", and rewriting and
> debugging thousand times the same stuff!
Compare what you're looking at to, say, the queue implementations in the
BSD kernel headers.
You're not gonna get anywhere claiming that the performance difference
doesn't matter.
> You just raised some potential problems that aren't actually there.
Container items are not necessarily a good implementation at all in C. You've
described something which adds multiple indirections to every operation.
Elements presumably need a pointer back to the container to be used; that
means an extra pointer for every single item, and the pointer back to the
container doesn't necessarily solve everything. There's a number of
questions to look at. Can you figure out the next element given only an
element, or do you need its container, too? If you need the container,
where is the "next element" information stored, in the element or in
the container? Are we going to have the container hold a linked list of
separately allocated items with pointers to their corresponding elements?
Once you add the container, anything you do is going to have pretty
significant costs. You might say "only a few cycles", but... Compared to
a traditional lightweight C implementation of a linked list, suitable
for inlining, you could easily be doubling or tripling the cost of
list operations, and for some lists, you might well be increasing data
storage by 20% or more.
One of the reasons I'm using C is that I get to pick the data structure which
fits the problem requirements most closely. An abstract data type which can
do anything is likely to be too expensive. (If it's not, I'm probably writing
in Ruby anyway.)
Chris McDonald
>Very easy.
I agree; I did not view the technical discuss as spam because I
"subconsciously" replaced
"...in my lcc-win..."
with
"...in a development compiler that I use"....
It's a shame that more readers, possibly writers, can't do the same.
--
Chris.
jacob navia
> On 2009-09-17, jacob navia <ja...@nospam.org> wrote:
>> It depends how do you implement the containers. The overhead in
>> lcc-win's implementation is one pointer for each container and
>> one table for every container type.
>
> Who owns allocation of the table?
>
The library. For each type of container there is a static table
of pointers containing the address of each of the functions for that
container. When you create a container for a certain type (a list
for instance) the creation function initializes the pointer in the
container to point to this table that is shared by all containers of the
same type. There is NO allocation.
> When and where do you do the sanity checks (table pointer valid,
> entries in table valid)?
The table pointer should be valid at all times, and if you replace
the table with a table of your own, you have to provide an equivalent
prototype to the replaced function.
>
>> For a list of 30 elements (say) you have only one pointer
>> and one table. Since the table is the same for all lists, you
>> have only one table floating around, so the actual overhead is
>> one pointer per container what is absolutely nothing. For long
>> lists (100 elements) the actual size of the objects stored will
>> overwhelm easily the size of the container structure.
>
> So the table's in the container, not the elements? So that doesn't
> work for a lightweight list (no container object, just list members).
>
Exactly. If you want no overhead, do not use this. The list container
contains a cursor, a pointer to the last element and a pointer to the
start of the list. This allows for fast access at the expense of a few
pointers. All this can be made optional if not needed.
> And if you look at a lot of the list implementations out there,
> there's no "container" separate from list elements. (And think
> about it; in practice, it seems you're going to need to have a pointer
> back to the container in every element, or you're going to have to
> pass the container around along with the elements...)
>
You pass the container, not the elements for most functions. You can
iterate over the container, and the callback receives a pointer to
each element.
>> this is very cheap, making it 2-3 instructions more maybe, in most
>> machines.
>
> If there's no sanity checks, sure. But then it's pretty risky and
> error-prone.
Absolutely not if you do not mess up with the pointer established by
the creation function.
>
>> There is no allocated memory for the pointer! What are you speaking
>> about? The pointer points to a static global table for all containers
>> of the same type.
>
> What prevents someone from allocating a table at runtime?
>
Nobody since you can replace that static table or parts of it
at runtime, as I explained before.
> If you don't let people allocate (or modify) the table at runtime, you're
> killing flexibility -- the ability to dynamically load a new container
> from a library would be awfully useful. If you do, you had better do
> sanity checks ALL THE TIME.
>
There is not a lot of things the program can do if the pointer in a
container is wrong besides aborting. A crash is better since it will
point exactly to the point of failure.
typedef struct tagListVtable {
int (AppendElement)(List *,void *);
// other function pointers
} ListVtable;
typedef struct tagList {
listVtable *vTable;
// Other fields
} List;
At any time you can replace a table with your own table in a single list
container and the behavior will be modified IN THAT LIST, not
everywhere.
Or you can replace a pointer in the table itself, what will modify the
behavior of ALL lists. As you like.
>>> Oh, and of course, if it's a pointer to the table, you've just added
>>> ANOTHER indirection.
>
>> Yes, that allows to replace the whole table easily.
>
> And adds more cycles.
>
maybe 2-3 cycles. Please, let's be realistic.
In most processors today, we have the computing power of dream
machines just a few years ago. It is obvious that in an
embedded system TODAY we are using 32 bits CPUs and quite
a lot of RAM by yesterday's standards. Obviously in your
eternal coffee machine there aren't cycles and memory
available for this kind of software so they will just
NOT USE IT!
Why do we have to always make the worst machine the absolute
requirement of the WHOLE language?
Let's introduce optional packages that are used in MOST
situations and improve the language in MOST situations. Since
they are optional (as printf for instance) users in microcontrollers
are NOT penalized. They do not use printf/complex numbers/ or
the logarithmic gamma function.
>> Then, after having written it, heathfield says that I am spamming :-)
>
> If you're advertising it, and some users would have to pay money to use
> it, you probably are.
I am distributing it free with the source code included!
I even posted the source code here in this group!
>
>> Yes, since there is no support for it in the standard library. C++ could
>> manage such a leverage because they standardised the containers and
>> provide code for the most common ones. A similar thing can be done in
>> C, but we are too busy keeping it "as it is", and rewriting and
>> debugging thousand times the same stuff!
>
> Compare what you're looking at to, say, the queue implementations in the
> BSD kernel headers.
>
> You're not gonna get anywhere claiming that the performance difference
> doesn't matter.
>
>> You just raised some potential problems that aren't actually there.
>
> Container items are not necessarily a good implementation at all in C. You've
> described something which adds multiple indirections to every operation.
This is never as expensive as a call to printf or fread or many other
functions of the standard library! For instance, to implement a good
printf you have to be able to implement an extended precision package
to be able to correctly print denormalized floating point numbers.
Obviously if you program in a microcontroller with 16K of RAM you can't
use printf. But nobody is complaining here that printf should be
banned.
> Elements presumably need a pointer back to the container to be used;
No. I do not have any backpointers in each element, THAT would be
too intrusive and expensive of course. sizeof(element) MUST be the
same size than the size the user thinks it has, without ANY overhead.
> that
> means an extra pointer for every single item, and the pointer back to the
> container doesn't necessarily solve everything.
Surely not. I do not see where you get that. My implementation
works without that.
> There's a number of
> questions to look at. Can you figure out the next element given only an
> element,
No.
> or do you need its container, too?
Yes. Lists, however do have a "Next" pointer. Flexible arrays not.
> If you need the container,
> where is the "next element" information stored, in the element or in
> the container?
For lists, it is tored in each element since the elemnts of a list are
ordered by their "next" pointers, that's the essence of a list.
For arrays (or flexible arrays) that information is implicit. If you
receive a pointer to some type T, you know that T+1 in C will yield
the next element, and T-1 the previous.
> Are we going to have the container hold a linked list of
> separately allocated items with pointers to their corresponding elements?
>
In my implementation the container manages its own memory and copies the
received data. If you do not do this, the container wont be able to
reorganize the data as needed. Obviously it *could* be done, but it
would be complicated to free the elements when some element is deleted.
> Once you add the container, anything you do is going to have pretty
> significant costs.
A function call and 2 indirections? That is a "pretty significant
cost"?
That's nothing in most machines. In any case, if you use your
OWN functions, the only thing you gain are just 2 indirections
since you have to make a function call anyway.
> You might say "only a few cycles", but... Compared to
> a traditional lightweight C implementation of a linked list, suitable
> for inlining, you could easily be doubling or tripling the cost of
> list operations, and for some lists, you might well be increasing data
> storage by 20% or more.
>
For a linked list, you pay container costs. They are:
1 pointer for each list
1 table for all lists you are going to create.
Suppose you have a list with 100 elemnts of 10 bytes each. (1000
bytes of storage). The overhead per list is 8 bytes for a pointer
(in a 64 bits machine) or 4 bytes for a pointer in a 32 bit machine.
This isn't even 1% of overhead. For longer lists the overhead is even
LESS!
I do not see how you arrive at 20%.
> One of the reasons I'm using C is that I get to pick the data structure which
> fits the problem requirements most closely.
Sure. But sometimes you need to change from a list to a table because
lists are expensive. Now you have to rewrite everything. Using this
approach you can keep MOST of your code intact since
foo->lpVtable->Add(foo,(void *)&data);
will stay the same for the new container!
> An abstract data type which can
> do anything is likely to be too expensive.
"can do anything" probably not. But there isn't any expensive
operations there.
> (If it's not, I'm probably writing
> in Ruby anyway.)
It would be interesting to see the ratio of my library
to ruby...
Always speaking about performance and then... a ruby interpreter!
:-)
jacob navia
I posted the whole source code for the list container here.
There was a discussion about containers and I proposed this solution.
Why can't I say where that solution is implemented? There isn't even
a license, all the source code is shipped with each distribution.
Nick Keighley
> Chris McDonald a écrit :
> > jacob navia <ja...@nospam.org> writes:
> >> Richard Heathfield a écrit :
> >>> <software advertisement snipped - if you want to talk about this,
> >>> fine, but please do it without spamming>
>
> >> Sure sure, this allows you to avoid all the technical points of my
> >> proposal and qualify it as "spam".
>
> >> Very easy.
>
> > I agree; I did not view the technical discuss as spam because I
> > "subconsciously" replaced
I agree too. If a library is being offered as a possible addition
to the standard I see no harm in mentioning where the example
implementation came from.
> > "...in my lcc-win..."
> > with
> > "...in a development compiler that I use"....
>
> > It's a shame that more readers, possibly writers, can't do the same.
>
> I posted the whole source code for the list container here.
> There was a discussion about containers and I proposed this solution.
>
> Why can't I say where that solution is implemented? There isn't even
> a license, all the source code is shipped with each distribution.
can anyone use the container source for any purpose (including
commercial and educational purposes)?
jacob navia
>
> can anyone use the container source for any purpose (including
> commercial and educational purposes)?
There is no license, so you can do as you wish.
If interest is there I will eliminate all lcc-win specific
stuff (again) and post it here (again).
cognacc
Couldnt that be used as base for some standardisation?
link to page with source code download:
http://www.cs.tut.fi/ohj/VARG/TVT/GTKsources.html
after unpacking, go insode directory glib/
forexample something called glist.h|c as an example.
mic
jacob navia
Hi mic
There are two problems with that library:
(1) The more serious one:
http://library.gnome.org/devel/glib/2.20/glib-Memory-Allocation.html
<quote>
Memory allocation functions.
---------------------------
Description
These functions provide support for allocating and freeing memory.
Note
If any call to allocate memory fails, the application is terminated.
This also means that there is no need to check if the call succeeded.
<end quote>
This is completely unacceptable and actually it is a horrible idea.
This precludes any use of the whole library since all functions
that *potentially* allocate memory are tainted.
(2) Another problem (or maybe not) is:
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
I do not know if linking with gtk forces you to disclose your
source code...
In any case the glist functions interface are very similar to
what I propose or to many other lists packagesa around.
Richard Heathfield
If you can't put forward a technical proposal without using it as an
advertising opportunity, I doubt very much whether the technical
proposal is worth reading. I could, of course, be mistaken about
that, but I see no reason why I should waste my time reading your
advertisements, so it looks like I'm not going to find out.
REH
> In a recent paper, the creator of the language acknowledged that after
> 3 years (more or less) working in an improvement of C++ it was
> impossible for him to realize the requested modification.
>
> The concrete details are not important here. Briefly, it was the
> introduction of "concepts" as descriptions of template arguments so that
> those arguments could be checked. A reasonable proposal.
>
> The problem is that C++ has grown so complex, that even the creator
> and principal force behind C++ was unable to do that change in a
> time frame of years.
Concepts was not removed because of any impossibility. It was removed
because the standard committee believed they won't be able to complete
the standard by the deadline with it in. Concepts have not been
dropped. They will be reintroduced in a TR, or possiblity the next
revision of the standard.
REH
jacob navia
> On Sep 16, 7:27 pm, jacob navia <ja...@nospam.org> wrote:
>> In a recent paper, the creator of the language acknowledged that after
>> 3 years (more or less) working in an improvement of C++ it was
>> impossible for him to realize the requested modification.
>>
>> The concrete details are not important here. Briefly, it was the
>> introduction of "concepts" as descriptions of template arguments so that
>> those arguments could be checked. A reasonable proposal.
>>
>> The problem is that C++ has grown so complex, that even the creator
>> and principal force behind C++ was unable to do that change in a
>> time frame of years.
>
> Concepts was not removed because of any impossibility. It was removed
> because the standard committee believed they won't be able to complete
> the standard by the deadline with it in.
In other words, after some *years* working in the problem, it was
impossible to introduce that change in the given time frame.
> Concepts have not been
> dropped. They will be reintroduced in a TR, or possiblity the next
> revision of the standard.
Well, the future is very long. Many things may happen.
I brought that into this discussion because is an example of
where C++ has gone.
It was an example of the
utter complexity of the language, a complexity of such proportions
that people that should be *the* experts in the matter are just unable
to introduce any further change because of the implications can't be
known, the complexity has grown beyond what mere humans are able
to handle.
If the creators of the language are now in such a situation, what
happens with the normal users?
I have this problems very much in my mind when I propose changing C.
C++ is an example that showas us how NOT to change things.
True, it is a big language, but (in my opinion) it is just too big.
Chris M. Thomasson
> Seebs a �crit :
[...]
>> Is the table actually stored
>> in each object?
>
> No, of course!
>
> Then it's a huge waste of space.
>
>
>> Do we store only a
>> pointer to the table?
>
> Yes.
>
>> Then we have allocation issues with the risk of
>> dangling pointers or leaked memory, and we have to establish some kind
>> of pattern for determining whose job it is to allocate the storage.
>
> There is no allocated memory for the pointer! What are you speaking
> about? The pointer points to a static global table for all containers
> of the same type.
Are you doing something like this:
REH
> In other words, after some *years* working in the problem, it was
> impossible to introduce that change in the given time frame.
No, an issue came up and it was felt that it could not be properly
address by next month's deadline. It happens. They wanted to error on
the side of caution then introduce a broken feature. That's a bad
thing? Besides, "impossible in a given time frame" is not
"impossible." Leaving off the qualifier is disingenuous.
> Well, the future is very long. Many things may happen.
No, we can't predicate the future, but the next TR is scheduled for
next year. It is already being worked on.
>
> I brought that into this discussion because is an example of
> where C++ has gone.
Yes, a popular and powerful language used in everything from embedded
systems to games.
>
> It was an example of the
> utter complexity of the language, a complexity of such proportions
> that people that should be *the* experts in the matter are just unable
> to introduce any further change because of the implications can't be
> known, the complexity has grown beyond what mere humans are able
> to handle.
unable? really? Have you compared the new draft standard to the '03
version? I think there are a lot of great changes/additions/fixes in C+
+0x.
Complexity is not necessarily bad. You don't need to--and shouldn't--
use very language feature in every program. I think one of the first
mistakes a learner of C++ (and probably other languages) makes is to
learn a "neat" new feature, and think "hmm, how can I use this in my
program."
Ada and Lisp are also complex, but are still great languages. I think
the changes going into Ada 200y are going to be it even better.
What specifically don't you like about C++? Is it just its size?
>
> If the creators of the language are now in such a situation, what
> happens with the normal users?
C++ is controlled by its standards committee, the same as C. It is not
controlled by its creator (although he is on the committee).
REH
Richard Harter
<r...@see.sig.invalid> wrote:
>In <h8sre2$7s7$1...@aioe.org>, jacob navia wrote:
>
>> Richard Heathfield a �crit :
>>> <software advertisement snipped - if you want to talk about this,
>>> fine, but please do it without spamming>
>>>
>> Sure sure, this allows you to avoid all the technical points of my
>> proposal and qualify it as "spam".
>
>If you can't put forward a technical proposal without using it as an
>advertising opportunity, I doubt very much whether the technical
>proposal is worth reading. I could, of course, be mistaken about
>that, but I see no reason why I should waste my time reading your
>advertisements, so it looks like I'm not going to find out.
If you cannot read ordinary technical discussions without
mistaking them for advertising opportunities that is your problem
and not his.
Richard Harter, c...@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Kafka wasn't an author;
Kafka was a prophet!
Richard Heathfield
> On Thu, 17 Sep 2009 10:04:28 +0000, Richard Heathfield
> <r...@see.sig.invalid> wrote:
>
>>In <h8sre2$7s7$1...@aioe.org>, jacob navia wrote:
>>
>>> Richard Heathfield a �crit :
>>>> <software advertisement snipped - if you want to talk about this,
>>>> fine, but please do it without spamming>
>>>>
>>> Sure sure, this allows you to avoid all the technical points of my
>>> proposal and qualify it as "spam".
>>
>>If you can't put forward a technical proposal without using it as an
>>advertising opportunity, I doubt very much whether the technical
>>proposal is worth reading. I could, of course, be mistaken about
>>that, but I see no reason why I should waste my time reading your
>>advertisements, so it looks like I'm not going to find out.
>
> If you cannot read ordinary technical discussions without
> mistaking them for advertising opportunities
Clearly we disagree.
> that is your problem and not his.
Nope. I lose nothing by it, whether by your interpretation of his
article or by mine.
jacob navia
Well it looks very similar indeed. The software is completely different
apparently (device driver !!!) but the method looks very similar.
I hope I did not iunfringe some copyright!
:-)
jacob navia
> In <4ab23ca3....@text.giganews.com>, Richard Harter wrote:
>
>> On Thu, 17 Sep 2009 10:04:28 +0000, Richard Heathfield
>> <r...@see.sig.invalid> wrote:
>>
>>> In <h8sre2$7s7$1...@aioe.org>, jacob navia wrote:
>>>
>>>> Richard Heathfield a �crit :
>>>>> <software advertisement snipped - if you want to talk about this,
>>>>> fine, but please do it without spamming>
>>>>>
>>>> Sure sure, this allows you to avoid all the technical points of my
>>>> proposal and qualify it as "spam".
>>> If you can't put forward a technical proposal without using it as an
>>> advertising opportunity, I doubt very much whether the technical
>>> proposal is worth reading. I could, of course, be mistaken about
>>> that, but I see no reason why I should waste my time reading your
>>> advertisements, so it looks like I'm not going to find out.
>> If you cannot read ordinary technical discussions without
>> mistaking them for advertising opportunities
>
> Clearly we disagree.
>
>> that is your problem and not his.
>
> Nope. I lose nothing by it, whether by your interpretation of his
> article or by mine.
>
OK Mr heathfield could we stop this and come back to the technical
points?
I propose to use a table of function pointers for all containers, a
static table for each type of container.
In each container object we store a pointer to that table. Access
to function goes like this
MyType Data; // some user data
List *list = newList(sizeof(data)); // Create a container
// Empty at the start
list->lpVtable->Insert(list,&data); // add one element
int count = list->lpVtable->GetCount(list); Should be 1
etc.
Now, since I haven't mentioned anything else please let's GO ON!
What do you think about it?
How would you improve this design?
What are its problems?
Thanks.
Please read the other messages in this thread. I think we
have a good discussion here. Let's abstract for a while from our
differences.
Thanks again.
cognacc
> cognacc a écrit :
>
> > What about glib form the gtk - gnome "suite"
> > Couldnt that be used as base for some standardisation?
>
> (1) The more serious one:http://library.gnome.org/devel/glib/2.20/glib-Memory-Allocation.html
> <quote>
> Memory allocation functions.
> ---------------------------
> Description
> These functions provide support for allocating and freeing memory.
> Note
> If any call to allocate memory fails, the application is terminated.
> This also means that there is no need to check if the call succeeded.
> <end quote>
>
> This is completely unacceptable and actually it is a horrible idea.
> This precludes any use of the whole library since all functions
> that *potentially* allocate memory are tainted.
I see(and agree), but maybe the library have both a behaviours
(looking in to it)
any way, in a program you could use gmalloc or malloc to get "normal"
behaviour.
> (2) Another problem (or maybe not) is:
> * This library is free software; you can redistribute it and/or
> * modify it under the terms of the GNU Library General Public
> * License as published by the Free Software Foundation; either
> * version 2 of the License, or (at your option) any later version.
>
> I do not know if linking with gtk forces you to disclose your
> source code...
Linking with glib can be done without disclosing source. because it
uses the LGPL.
It could still be a problem
for some i guess.
from the glist.c file
---
* GLIB - Library of useful routines for C programming
* Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh
MacDonald
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
---
> In any case the glist functions interface are very similar to
> what I propose or to many other lists packagesa around.
Ok.
I look forward to the technical details.
mic
Seebs
> to function goes like this
> MyType Data; // some user data
>
> List *list = newList(sizeof(data)); // Create a container
> // Empty at the start
>
> list->lpVtable->Insert(list,&data); // add one element
>
> int count = list->lpVtable->GetCount(list); Should be 1
>
> Now, since I haven't mentioned anything else please let's GO ON!
> What do you think about it?
> How would you improve this design?
> What are its problems?
From a design standpoint: What if anything goes in "data" to make it
part of the list? Does the list container maintain a separate linked list
of items with pointers to its data elements? If so, consider the malloc
overhead; you're now adding an additional malloc overhead to each item
in the list, by having a list element in the container. The indirections
are expensive. How do I get from the data element to the container, or
can the same data element be in several containers?
From a practical standpoint: There's no way I'd use this. I am familiar
with code using things like the list operations in the BSD kernel, which
are carefully structured to allow extremely efficient list operations.
Compared to them, for small data elements (the normal case, as it happens,
for most of what they're working on), your implementation looks like it
has a minimum cost of 20-30% or so for data, and probably closer to 50%
for execution time.
jacob navia
> On 2009-09-17, jacob navia <ja...@nospam.org> wrote:
>> In each container object we store a pointer to that table. Access
>> to function goes like this
>
>> MyType Data; // some user data
>>
>> List *list = newList(sizeof(data)); // Create a container
>> // Empty at the start
>>
>> list->lpVtable->Insert(list,&data); // add one element
>>
>> int count = list->lpVtable->GetCount(list); Should be 1
>>
>> Now, since I haven't mentioned anything else please let's GO ON!
>> What do you think about it?
>> How would you improve this design?
>> What are its problems?
>
> From a design standpoint: What if anything goes in "data" to make it
> part of the list?
Nothing. This is the "payload" of the container. This will be stored
in each element of the list. Since the list knows how big each element
is, each element is copied into the container linked list.
Another schema is possible with each element having a DIFFERENT size. In
that case data should NOT be copied, just a void * is stored and the
user is responsible for all data he/she stores
> Does the list container maintain a separate linked list
> of items with pointers to its data elements?
Yes
> If so, consider the malloc
> overhead; you're now adding an additional malloc overhead to each item
> in the list, by having a list element in the container.
If you do not want data to be copied, just use a void pointer and pass
the address.
> The indirections
> are expensive. How do I get from the data element to the container, or
> can the same data element be in several containers?
>
As you like, but you can't get from an element to its container since
there are no backpointers. That would be much too expensive in space
Of course nothing is hindering you from storing YOURSELF a backpointer
in the data if you wish.
> From a practical standpoint: There's no way I'd use this. I am familiar
> with code using things like the list operations in the BSD kernel, which
> are carefully structured to allow extremely efficient list operations.
> Compared to them, for small data elements (the normal case, as it happens,
> for most of what they're working on), your implementation looks like it
> has a minimum cost of 20-30% or so for data, and probably closer to 50%
> for execution time.
>
This is completely bogus. You have no measurements to justify such an
assertion. Suppose worst case that you have a list of chars. Each of
size 1.
And you want to store 100 of them. You have 100 chars, and in a 32
bit machine an overhead of 4 bytes for the lpvtbl pointer, and maybe
3 more pointers for cursor, root and last. 16 bytes would be an
overhead of just 16%!
And, who is going to build a list of chars of only 100 chars?
You just allocate a buffer of 512 and you have all your needs covered.
You do not need a list for this case.
The same for integers or even doubles. For very small lists just
using a buffer is much more efficient.
Another container is the flexible array. This is a growable array,
of elements of the same size, or an array of void pointers if
you want different size.
There, the overhead is less since there is no "next" pointer in each
element.
Seebs
> Obviously if you program in a microcontroller with 16K of RAM you can't
> use printf. But nobody is complaining here that printf should be
> banned.
The point is, list operations are very often the inner loop of a
program.
> > or do you need its container, too?
> Yes. Lists, however do have a "Next" pointer. Flexible arrays not.
Where's the "Next" pointer? Is it in the data element? If it is,
then how does the user declare that pointer?
> For lists, it is tored in each element since the elemnts of a list are
> ordered by their "next" pointers, that's the essence of a list.
Okay.
So what's the container get you, given that you don't need it to find the
next item? It seems as though this isn't doing much good for lists.
> In my implementation the container manages its own memory and copies the
> received data. If you do not do this, the container wont be able to
> reorganize the data as needed. Obviously it *could* be done, but it
> would be complicated to free the elements when some element is deleted.
... So if I have an object which I need to create, I have to allocate one,
then copy it into the container, which allocates space for it and copies
it.
If the address of the object is significant, I can't put it in a container
at all.
> A function call and 2 indirections? That is a "pretty significant
> cost"?
Yeah.
> That's nothing in most machines. In any case, if you use your
> OWN functions, the only thing you gain are just 2 indirections
> since you have to make a function call anyway.
Not if they're inline or macros, which list ops often are.
> Suppose you have a list with 100 elemnts of 10 bytes each. (1000
> bytes of storage). The overhead per list is 8 bytes for a pointer
> (in a 64 bits machine) or 4 bytes for a pointer in a 32 bit machine.
Okay. So you're not keeping a pointer to the container, and the list
pointers are in the objects.
But you are requiring me to pass around a container AND a list element
any time I need to be able to do operations on the list element...
> Sure. But sometimes you need to change from a list to a table because
> lists are expensive. Now you have to rewrite everything. Using this
> approach you can keep MOST of your code intact since
> foo->lpVtable->Add(foo,(void *)&data);
> will stay the same for the new container!
If I want that kind of flexibility, I write in Ruby.
> It would be interesting to see the ratio of my library
> to ruby...
> Always speaking about performance and then... a ruby interpreter!
Exactly. If I am writing in C, I probably care about the cost of a couple
of indirections (you're not thinking about the cache miss cost of that,
which is probably going to dominate the execution cycles). If I'm not that
concerned, I'll write in a much higher level language.
Richard Heathfield
<snip>
> OK Mr heathfield could we [...] come back to the technical
> points?
Gladly.
>
> I propose to use a table of function pointers for all containers, a
> static table for each type of container.
I am assuming that you are proposing this as a change to the standard
language. So my first observation is that your proposed function
names are trampling on user namespace. But that's a minor point,
easily fixed by choosing implementation-reserved names.
> In each container object we store a pointer to that table. Access
> to function goes like this
>
> MyType Data; // some user data
>
> List *list = newList(sizeof(data)); // Create a container
> // Empty at the start
>
> list->lpVtable->Insert(list,&data); // add one element
>
> int count = list->lpVtable->GetCount(list); Should be 1
>
> etc.
>
> Now, since I haven't mentioned anything else please let's GO ON!
> What do you think about it?
> How would you improve this design?
> What are its problems?
For the list to own the data (which, personally, I think is a good
idea), it is going to have to make its own copy if it is to persist
past the point where the feed data goes out of scope. That means a
malloc, obviously (or some dark equivalent thereof), and some people
will object purely on those grounds. That's your first major problem
- some people will want the list to own the data, and others will
very much want it *not* to own the data.
Assuming it does own the data, you then have the problem of pointers
within that data. Do you do a deep copy, or a shallow copy? If you do
a shallow copy, you risk ownership confusion and of course dangling
pointers. If you do a deep copy, you will probably need the user to
provide copying semantics. This complicates the interface.
One way to obviate this problem is to have a sort of registration
process when setting up a new list, so that all the complication is
up front. You could also use the opportunity to register destructors,
comparators, and iterators. For example:
List *list = newList(sizeof Data,
MyTypeCopyConstructor,
MyTypeDestructor,
NULL, /* we happen not to need a comparator */
MyTypeIterator);
A copy constructor would be of type int(const void *, void *);
A destructor would be of type int(void *, void *);
A comparator would be of type int(const void *, const void *, void *);
An iterator would be of type int(void *, void *);
In each case, the last (optional - NULL is okay) pointer is to an
arbitrary structure that can carry or even accept side channel
information.
These function pointers (the non-NULL ones, anyway) would then be
called whenever the standard data structure is called upon to do
whatever. For example, list->iterate(&myvars) would call
*MyTypeIterator for each item in the list, handing it a pointer to
the current item and the pointer we passed to it.
You would also need to have functions to allow these defaults to be
updated - e.g. list->SetNewIterator(MyTypeAnotherIterator).
(This is pretty much how my own library works, by the way.)
The problem is that it's all getting very complicated, and that in
itself is very likely going to make it unacceptable to a standards
committee.
But every way of simplifying it will lead either to complications in
other areas or insufficient power and flexibility.
Bottom line: there are a great many ways to do this, and every way has
its advocates and detractors. Getting a consensus within ISO for
adopting any single proposal is a Sisyphean task.
<snip>
jacob navia
> On 2009-09-17, jacob navia <ja...@nospam.org> wrote:
>> Obviously if you program in a microcontroller with 16K of RAM you can't
>> use printf. But nobody is complaining here that printf should be
>> banned.
>
> The point is, list operations are very often the inner loop of a
> program.
>
Mmmm I wouldn't do that in inner loops. Much better to use an array
then. Lists are more expensive than arrays.
>>> or do you need its container, too?
>
>> Yes. Lists, however do have a "Next" pointer. Flexible arrays not.
>
> Where's the "Next" pointer? Is it in the data element? If it is,
> then how does the user declare that pointer?
>
The container manages a list of stuff. Each list element contains
two fields:
(1) a Next pointer
(2) Data. If the list is homogeneous (all elements of the same size)
the data is right after the next pointer. If not, just a void * is
stored.
>> For lists, it is tored in each element since the elemnts of a list are
>> ordered by their "next" pointers, that's the essence of a list.
>
> Okay.
>
> So what's the container get you, given that you don't need it to find the
> next item? It seems as though this isn't doing much good for lists.
>
If you want you can manage the list directly and use the "next" pointer.
In that case the container is unnecessary. You do your own list. But
if you want to use a cursor, a pointer to the last element (for
fast appending) etc, you will want the container.
Obviously this containers aren't good for ALL situations in all
circumstances. Like printf. It is MUCH slower that puts()
isn't it? Avoid it in inner loops.
>> In my implementation the container manages its own memory and copies the
>> received data. If you do not do this, the container wont be able to
>> reorganize the data as needed. Obviously it *could* be done, but it
>> would be complicated to free the elements when some element is deleted.
>
> ... So if I have an object which I need to create, I have to allocate one,
> then copy it into the container, which allocates space for it and copies
> it.
>
As before, if you do not want that, you create a container that manages
void pointers to your data.
> If the address of the object is significant, I can't put it in a container
> at all.
>
>> A function call and 2 indirections? That is a "pretty significant
>> cost"?
>
> Yeah.
>
In all modern CPUs that's nothing. Maybe in a slow microcontroller but
then, do not use containers in those slow machines. Build your own
lists. You can't use printf, you do your own simple formatting.
You can't use sqrt because there isn't any floating point, you write
your own approximation for integers. ETC.
But you are not really proposing to eliminate printf and sqrt from the
language isn't it?
>> That's nothing in most machines. In any case, if you use your
>> OWN functions, the only thing you gain are just 2 indirections
>> since you have to make a function call anyway.
>
> Not if they're inline or macros, which list ops often are.
>
I thought you were memory constrained. Inline functions and long macros
for handling lists are memory intensive...
>> Suppose you have a list with 100 elemnts of 10 bytes each. (1000
>> bytes of storage). The overhead per list is 8 bytes for a pointer
>> (in a 64 bits machine) or 4 bytes for a pointer in a 32 bit machine.
>
> Okay. So you're not keeping a pointer to the container, and the list
> pointers are in the objects.
>
> But you are requiring me to pass around a container AND a list element
> any time I need to be able to do operations on the list element...
You use the indexing functions. GetNth(list,int);
>
>> Sure. But sometimes you need to change from a list to a table because
>> lists are expensive. Now you have to rewrite everything. Using this
>> approach you can keep MOST of your code intact since
>
>> foo->lpVtable->Add(foo,(void *)&data);
>
>> will stay the same for the new container!
>
> If I want that kind of flexibility, I write in Ruby.
>
Ahh OK. That flexibility is OK when in Ruby. In C we are
doomed to write:
ptr = ListHead;
n = 23;
while (ptr && n > 0) {
ptr = ptr->Next;
n--;
}
assert(n == 0);
ptr->Data = "This is element 23";
Why can't we write
List->lpVtbl->Assign(List, 23, "This is element 23");
Ben Bacarisse
> Seebs a écrit :
>> On 2009-09-17, jacob navia <ja...@nospam.org> wrote:
>>> Obviously if you program in a microcontroller with 16K of RAM you can't
>>> use printf. But nobody is complaining here that printf should be
>>> banned.
>>
>> The point is, list operations are very often the inner loop of a
>> program.
>>
>
> Mmmm I wouldn't do that in inner loops. Much better to use an array
> then. Lists are more expensive than arrays.
No, sometimes arrays are more expensive. If a list is the right
structure, switching to array will often make matters worse.
Take a merge sort for example. A linked list is the right structure
and the list operations will be in an inner loop. Switching to an
array does not fix anything in this situation.
<snip>
--
Ben.
jacob navia
> For the list to own the data (which, personally, I think is a good
> idea), it is going to have to make its own copy if it is to persist
> past the point where the feed data goes out of scope. That means a
> malloc, obviously (or some dark equivalent thereof), and some people
> will object purely on those grounds. That's your first major problem
> - some people will want the list to own the data, and others will
> very much want it *not* to own the data.
>
This is easily solved. If you do not want the list to own the data
you do not give any data to the list. You make a list of void pointers
to your data. Then, you own the data and no copies are done.
> Assuming it does own the data, you then have the problem of pointers
> within that data.
Shallow copy since the list container can't know what are pointers
and what are just integers.
> Do you do a deep copy, or a shallow copy? If you do
> a shallow copy, you risk ownership confusion and of course dangling
> pointers. If you do a deep copy, you will probably need the user to
> provide copying semantics. This complicates the interface.
>
Exactly. What is important here is that we keep it simple. Not
ALL possible uses MUST be covered. Just 90% of all uses. Why
should the list container care about what it has to copy?
Instead of passing a pointer to a copy-constructor the user
of the list is responsible for copying and THEN passing that to the
list. Good design goes through keeping tasks separated and
responsibilities clear. The container cares about its data elements,
but it doesn't know ANYTHING about them.
PERIOD. End of story.
> One way to obviate this problem is to have a sort of registration
> process when setting up a new list, so that all the complication is
> up front.
Not necessarily. Comparison defaults to memcmp. Destructors are not
provided but you can use an iterator to iterate all elements of the list
when it is destroyed. This is not C++, it is C. The compiler does
much less for you, but the language is easier to learn and use.
> You could also use the opportunity to register destructors,
> comparators, and iterators. For example:
>
> List *list = newList(sizeof Data,
> MyTypeCopyConstructor,
> MyTypeDestructor,
> NULL, /* we happen not to need a comparator */
> MyTypeIterator);
>
Copy constructors defaults to memcpy. If you want a fancy one
you can have it but it would add overhead.
> A copy constructor would be of type int(const void *, void *);
I assume this means
int (*copyconstructor)(const void *,void *);
Note that you use copy(source , destination) what is the contrary of
copy functions in C. (memcpy strcpy). I would rather have it the
other way. I do not think that this is needed though. The user
copies the data because the user knows what the data is storing,
where are the pointers what do they point to, etc.
Division of reponbsabilities. Again, this is VERY important in
software design.
> A destructor would be of type int(void *, void *);
I do not see why you need a destructor *in the list*. If you want to
destroy an item to the list, you call GetElement, you do whatever you
need to do when the item is destroyed, and then you call Delete
with the index of the item.
Yes, it is not as "nice" but it is just as good.
> A comparator would be of type int(const void *, const void *, void *);
OK. You need that. It defaults to memcmp but you should be able to
change it. By the way, what is the third argument?
> An iterator would be of type int(void *, void *);
>
Wait. It is much simpler to pass the callback at each call to
the iterator.
> In each case, the last (optional - NULL is okay) pointer is to an
> arbitrary structure that can carry or even accept side channel
> information.
>
Ahh OK. That's clever. I will add it to my implementation.
> These function pointers (the non-NULL ones, anyway) would then be
> called whenever the standard data structure is called upon to do
> whatever. For example, list->iterate(&myvars) would call
> *MyTypeIterator for each item in the list, handing it a pointer to
> the current item and the pointer we passed to it.
>
Correct. I do that, but I receive the function pointer at each
call to the iteration function to avoid storing it in the
list and increasing the fixed overhead. You are NOT going to
iterate all lists, only some of them. Then, it is more
space efficient to pass the iterator to the iterate list
function.
> You would also need to have functions to allow these defaults to be
> updated - e.g. list->SetNewIterator(MyTypeAnotherIterator).
>
Not if you pass it at each call.
> (This is pretty much how my own library works, by the way.)
>
> The problem is that it's all getting very complicated, and that in
> itself is very likely going to make it unacceptable to a standards
> committee.
>
Complicated???
Too complicated???
This is NOTHING. I am sure you have designed software that is MUCH MORE
complicated than this stuff!
And most of us have. Including committee members.
> But every way of simplifying it will lead either to complications in
> other areas or insufficient power and flexibility.
>
What is important to have clear at the start is that it is not
possible to achieve PERFECTION. Each user will have some
special needs. Since all those function pointers are writable,
users can add or eliminate features as they wish, always MAINTAINIG
the same interface!
> Bottom line: there are a great many ways to do this, and every way has
> its advocates and detractors. Getting a consensus within ISO for
> adopting any single proposal is a Sisyphean task.
I would not aim so high right now. I would aim to develop here in this
group a consensus implementation that is widely distributed and
with no strings attached at all.
After it has spread around, we have experience with it, it becomes
CURRENT PRACTICE!
and ISO will gladly adopt it.
:-)
Thanks for paricipating
Richard Heathfield
> Richard Heathfield a �crit :
> > For the list to own the data (which, personally, I think is a
> > good
>> idea), it is going to have to make its own copy if it is to persist
>> past the point where the feed data goes out of scope. That means a
>> malloc, obviously (or some dark equivalent thereof), and some
>> people will object purely on those grounds. That's your first major
>> problem - some people will want the list to own the data, and
>> others will very much want it *not* to own the data.
>>
>
> This is easily solved. If you do not want the list to own the data
> you do not give any data to the list. You make a list of void
> pointers to your data. Then, you own the data and no copies are
> done.
But now you've got all these void pointers adding overhead to the
story. Not necessarily a bad thing to some people, but others will
see it as a waste of resources.
>> Assuming it does own the data, you then have the problem of
>> pointers within that data.
>
> Shallow copy since the list container can't know what are pointers
> and what are just integers.
Then you expose the programmer to the risk of dangling pointers.
Again, not everyone will see this as a showstopper - but many will.
(In this case, I'm one of them - I'd prefer to provide deep copy
facilities.)
>> Do you do a deep copy, or a shallow copy? If you do
>> a shallow copy, you risk ownership confusion and of course dangling
>> pointers. If you do a deep copy, you will probably need the user to
>> provide copying semantics. This complicates the interface.
>
> Exactly. What is important here is that we keep it simple. Not
> ALL possible uses MUST be covered. Just 90% of all uses. Why
> should the list container care about what it has to copy?
Fair point. Here's another fair point. Why should the user go to the
inconvenience of typing the code for copying a structure instead of
just passing the darn thing to the list interface - fire and forget.
Some will see your way as a good way, and others will perceive it as
being a design flaw.
> Instead of passing a pointer to a copy-constructor the user
> of the list is responsible for copying and THEN passing that to the
> list. Good design goes through keeping tasks separated and
> responsibilities clear. The container cares about its data elements,
> but it doesn't know ANYTHING about them.
>
> PERIOD. End of story.
That's one possible design, but others are possible too, and calling
them bad designs doesn't make them bad designs. Allowing the list to
deep-copy a datum with user-specified semantics is a perfectly
reasonable thing to do. You may not want to do it that way, and
that's fine, but some other people /will/ want to do it that way.
This is the problem - lack of consensus.
>> One way to obviate this problem is to have a sort of registration
>> process when setting up a new list, so that all the complication is
>> up front.
>
> Not necessarily. Comparison defaults to memcmp. Destructors are not
> provided but you can use an iterator to iterate all elements of the
> list when it is destroyed.
That is *one* possible design. You presumably see the lack of
destructors as a strength. I see it as a weakness. I'm not just being
contrary - there are lots of trade-offs in a container design, and on
some of them I actually agree with your choices. But not all. And
some people won't agree with any of your choices.
> This is not C++, it is C. The compiler
> does much less for you, but the language is easier to learn and use.
Yes, but we have that /now/. Adding containers is not going to make
the language any simpler.
>> You could also use the opportunity to register destructors,
>> comparators, and iterators. For example:
>>
>> List *list = newList(sizeof Data,
>> MyTypeCopyConstructor,
>> MyTypeDestructor,
>> NULL, /* we happen not to need a comparator */
>> MyTypeIterator);
>>
>
> Copy constructors defaults to memcpy. If you want a fancy one
> you can have it but it would add overhead.
Right. So some people will want to add one, and others will want not
to add one, and will resent the space taken for the pointer.
>> A copy constructor would be of type int(const void *, void *);
>
> I assume this means
> int (*copyconstructor)(const void *,void *);
Well, I was talking about the function itself, but yes, the list
structure would contain a pointer of that type, except...
>
> Note that you use copy(source , destination) what is the contrary of
> copy functions in C.
Just a screwup - I missed a rather important parameter!
int (*copyconstructor)(void *this, /* dest */
const void *that, /* src */
void *theother); /* optional side channel */
> I do not think that this is needed though.
Sure. I can see that. But /I/ think it's needed. So we disagree.
That's fine, we should be able to disagree without coming to blows,
but we can't have both support for a constructor /and/ absence of
support (and absence of overhead) for a constructor. It's one or the
other, really. The point is that either design is defensible, and
whichever one you choose, you're going to cheese off a lot of people.
<snip alternate destruction technique>
> Yes, it is not as "nice" but it is just as good.
Fine, I can accept that you think so, and I can even accept that you
have a good and solid point. Trouble is, so do I. Both designs are
possible and practical and viable and workable - but presumably we
can't have them both, so we have to choose one or the other. Whoever
makes the choice and however they choose, a lot of people are going
to think the wrong choice was made.
>> A comparator would be of type int(const void *, const void *, void
>> *);
>
> OK. You need that. It defaults to memcmp but you should be able to
> change it. By the way, what is the third argument?
Whatever you like, or NULL. I added this because there have been times
when I have sorely missed it in qsort and bsearch! I also added it to
the constructor etc.
>
>> An iterator would be of type int(void *, void *);
>>
>
> Wait. It is much simpler to pass the callback at each call to
> the iterator.
Well, you could, but it's slightly easier to do it this way, because
now you can just say list->iterate(list, &sidechannel); and you're
done. Again, the problem is that either way is fine, but you can't
have them both (or can you?).
<snip>
>> (This is pretty much how my own library works, by the way.)
>>
>> The problem is that it's all getting very complicated, and that in
>> itself is very likely going to make it unacceptable to a standards
>> committee.
>>
>
> Complicated???
>
> Too complicated???
Not for me. After all, this is how my library does it already. But
some people /will/ find it too complicated, and will object to its
standardisation on that basis.
Seebs
> Nothing. This is the "payload" of the container. This will be stored
> in each element of the list. Since the list knows how big each element
> is, each element is copied into the container linked list.
Memory copies are expensive. Furthermore, now the container is allocating
things.
So:
I allocate an object, populate it, add it to the list...
... which allocates an object, copies mine into it
...and then I free my allocated object.
That's only doubling the number of allocations.
> Another schema is possible with each element having a DIFFERENT size. In
> that case data should NOT be copied, just a void * is stored and the
> user is responsible for all data he/she stores
And that still means there's two allocated objects per list item.
>> If so, consider the malloc
>> overhead; you're now adding an additional malloc overhead to each item
>> in the list, by having a list element in the container.
> If you do not want data to be copied, just use a void pointer and pass
> the address.
Doesn't matter, you're still going to have an extra allocation; one for
the hidden list-object item the container keeps track of, and one for the
user's object.
> As you like, but you can't get from an element to its container since
> there are no backpointers. That would be much too expensive in space
Right.
Which means that the elements are less useful than traditional list members
in a naive C implementation.
> This is completely bogus. You have no measurements to justify such an
> assertion. Suppose worst case that you have a list of chars. Each of
> size 1.
> And you want to store 100 of them. You have 100 chars, and in a 32
> bit machine an overhead of 4 bytes for the lpvtbl pointer, and maybe
> 3 more pointers for cursor, root and last. 16 bytes would be an
> overhead of just 16%!
And where's the list? You need the information about the ordering, too.
> And, who is going to build a list of chars of only 100 chars?
I'm not.
But.
I have 100 objects. Each of them is a separate malloc buffer.
Now I use your library, and as suggested, just store the (void *) in the
container.
Your library has to maintain a list of 100 objects, in which case, it's
storing ANOTHER 100 separate malloc buffers. Which isn't helping me any.
There's also extra copies going on, etcetera.
> You just allocate a buffer of 512 and you have all your needs covered.
> You do not need a list for this case.
You might want to look up mbufs.
> Another container is the flexible array. This is a growable array,
> of elements of the same size, or an array of void pointers if
> you want different size.
> There, the overhead is less since there is no "next" pointer in each
> element.
True. But if I'm using the pointers, I'm still dealing with malloc overhead.
Don't forget that there's at least some extra space used by each allocated
object for the malloc internals.
jacob navia
> In <h8tsub$j4b$1...@aioe.org>, jacob navia wrote:
>
>> Richard Heathfield a �crit :
>> > For the list to own the data (which, personally, I think is a
>> > good
>>> idea), it is going to have to make its own copy if it is to persist
>>> past the point where the feed data goes out of scope. That means a
>>> malloc, obviously (or some dark equivalent thereof), and some
>>> people will object purely on those grounds. That's your first major
>>> problem - some people will want the list to own the data, and
>>> others will very much want it *not* to own the data.
>>>
>> This is easily solved. If you do not want the list to own the data
>> you do not give any data to the list. You make a list of void
>> pointers to your data. Then, you own the data and no copies are
>> done.
>
> But now you've got all these void pointers adding overhead to the
> story. Not necessarily a bad thing to some people, but others will
> see it as a waste of resources.
>
No. There is no overhead. A list has AT LEAST two elements:
(1) Next element pointer
(2) data. In this case if you do it yourself you will have
a list of void pointers ANYWAY, the container doesn't change
ANYTHING to that fact.
The extra overhead in this case is only one container object per list.
>>> Assuming it does own the data, you then have the problem of
>>> pointers within that data.
>> Shallow copy since the list container can't know what are pointers
>> and what are just integers.
>
> Then you expose the programmer to the risk of dangling pointers.
Yes, better avoid them :-).
(1) You do NOT maintain copies of the data you passed to the container.
(2) When needing to copy an element you do the copy yourself, THEN you
pass it through.
> Again, not everyone will see this as a showstopper - but many will.
> (In this case, I'm one of them - I'd prefer to provide deep copy
> facilities.)
>
This is a valid point. Happily the design is flexible enough to
accomodate your wishes. You subclass the functions you need. To do
that you:
(1) Save the current pointer to the function you need
(2) Set your own function that does the copying using some private
data and then
(3) calls the pointer that was in the table to perform the rest of the
functionality you have just subclassed.
This works since a lot of time and has been used a lot of times in many
different contexts. You can do it under windows for instance, by
subclassing the windows procedure for a window. And I am sure
other window systems allow this too. It is very common concept.
>>> Do you do a deep copy, or a shallow copy? If you do
>>> a shallow copy, you risk ownership confusion and of course dangling
>>> pointers. If you do a deep copy, you will probably need the user to
>>> provide copying semantics. This complicates the interface.
>> Exactly. What is important here is that we keep it simple. Not
>> ALL possible uses MUST be covered. Just 90% of all uses. Why
>> should the list container care about what it has to copy?
>
> Fair point. Here's another fair point. Why should the user go to the
> inconvenience of typing the code for copying a structure instead of
> just passing the darn thing to the list interface - fire and forget.
Exactly, you are right. Happily the design is flexible so you
can do that if you wish. Just subclass the functionality. See above.
>
>> This is not C++, it is C. The compiler
>> does much less for you, but the language is easier to learn and use.
>
> Yes, but we have that /now/. Adding containers is not going to make
> the language any simpler.
>
Of course it will make the language simpler!!!
That's the main reson of this prtoposal. All that code
handling lists that is EVERYWHERE IN ALL C PROGRAMS of some
complexity will disappear, replaced by a uniform interface
that is standard and will be present in all run time environments.
>> Copy constructors defaults to memcpy. If you want a fancy one
>> you can have it but it would add overhead.
>
> Right. So some people will want to add one, and others will want not
> to add one, and will resent the space taken for the pointer.
>
No, they can subclass, as I said above.
>>> A copy constructor would be of type int(const void *, void *);
>> I assume this means
>> int (*copyconstructor)(const void *,void *);
>
> Well, I was talking about the function itself, but yes, the list
> structure would contain a pointer of that type, except...
>
>> Note that you use copy(source , destination) what is the contrary of
>> copy functions in C.
>
> Just a screwup - I missed a rather important parameter!
>
> int (*copyconstructor)(void *this, /* dest */
> const void *that, /* src */
> void *theother); /* optional side channel */
>
>> I do not think that this is needed though.
>
> Sure. I can see that. But /I/ think it's needed. So we disagree.
> That's fine, we should be able to disagree without coming to blows,
> but we can't have both support for a constructor /and/ absence of
> support (and absence of overhead) for a constructor.
YES WE CAN!
(pun intended)
We can subclass each of those functions if we want to. We can use
our subclassing at the individual list level (this list will need
a copy constructor but that one won't) or we can subclass at the
global level (ALL my lists will use a copy constructor)
The most important part of this design is that IT IS VERY FLEXIBLE!
> It's one or the
> other, really.
No. I want the cake and the money of the cake too.
:-)
[snip since you repeat the same arguments]
jacob navia
> On 2009-09-17, jacob navia <ja...@nospam.org> wrote:
>> Nothing. This is the "payload" of the container. This will be stored
>> in each element of the list. Since the list knows how big each element
>> is, each element is copied into the container linked list.
>
> Memory copies are expensive. Furthermore, now the container is allocating
> things.
>
> So:
>
> I allocate an object, populate it, add it to the list...
> ... which allocates an object, copies mine into it
> ...and then I free my allocated object.
>
> That's only doubling the number of allocations.
You build an object in a buffer. You populate it and when ready,
you give it to the list. Then, for the next object you reuse
the same static buffer. Only one allocation.
Elementary my dear Watson...
:-)
>
>> Another schema is possible with each element having a DIFFERENT size. In
>> that case data should NOT be copied, just a void * is stored and the
>> user is responsible for all data he/she stores
>
> And that still means there's two allocated objects per list item.
>
ANY list needs two object for each item.
(1) The first one has at least two fields: the "next" pointer, and the
pointer to the data.
(2) The actual data that the list holds.
This stays the same. There is NO extra overhead.
>>> If so, consider the malloc
>>> overhead; you're now adding an additional malloc overhead to each item
>>> in the list, by having a list element in the container.
>
>> If you do not want data to be copied, just use a void pointer and pass
>> the address.
>
> Doesn't matter, you're still going to have an extra allocation; one for
> the hidden list-object item the container keeps track of, and one for the
> user's object.
Well, THAT'S ALL LISTS IN THE WORLD!
>
>> As you like, but you can't get from an element to its container since
>> there are no backpointers. That would be much too expensive in space
>
> Right.
>
> Which means that the elements are less useful than traditional list members
> in a naive C implementation.
>
Mmm you stoire backpointers to the root of the list at each element?
WoW That is really overhead.
>> This is completely bogus. You have no measurements to justify such an
>> assertion. Suppose worst case that you have a list of chars. Each of
>> size 1.
>
>> And you want to store 100 of them. You have 100 chars, and in a 32
>> bit machine an overhead of 4 bytes for the lpvtbl pointer, and maybe
>> 3 more pointers for cursor, root and last. 16 bytes would be an
>> overhead of just 16%!
>
> And where's the list? You need the information about the ordering, too.
But that is not different as lists now! ANY list needs two elements
see above.
>
>> And, who is going to build a list of chars of only 100 chars?
>
> I'm not.
>
> But.
>
> I have 100 objects. Each of them is a separate malloc buffer.
>
> Now I use your library, and as suggested, just store the (void *) in the
> container.
>
> Your library has to maintain a list of 100 objects, in which case, it's
> storing ANOTHER 100 separate malloc buffers. Which isn't helping me any.
>
No, because the list software has a pool of list elements that decreases
the likehood of using malloc...
> There's also extra copies going on, etcetera.
>
No, as I told you before, there are no copies when you just use void
pointers.
> Don't forget that there's at least some extra space used by each allocated
> object for the malloc internals.
No, since the list software allocates many lists elements at once in
blocks.
Seebs
>> The point is, list operations are very often the inner loop of a
>> program.
> Mmmm I wouldn't do that in inner loops. Much better to use an array
> then. Lists are more expensive than arrays.
mbuf
> The container manages a list of stuff. Each list element contains
> two fields:
> (1) a Next pointer
> (2) Data. If the list is homogeneous (all elements of the same size)
> the data is right after the next pointer. If not, just a void * is
> stored.
Okay.
So each list element is an allocated object.
Which means that, to use the container, I have to double the number of
allocations I perform.
>> ... So if I have an object which I need to create, I have to allocate one,
>> then copy it into the container, which allocates space for it and copies
>> it.
> As before, if you do not want that, you create a container that manages
> void pointers to your data.
... So if I have an object which I need to create, I have to allocate one,
then copy its address into the containner, which allocates space for the
list element object plus a void pointer, and copies the address.
It's still an extra allocation.
> In all modern CPUs that's nothing.
"Nothing" is a pretty big deal if you're trying to saturate gigabit ethernet
links while doing substantial packet processing. :)
> Maybe in a slow microcontroller but
> then, do not use containers in those slow machines. Build your own
> lists. You can't use printf, you do your own simple formatting.
> You can't use sqrt because there isn't any floating point, you write
> your own approximation for integers. ETC.
printf is actually a pretty lightweight formatter -- it's very well built
to do the simple cases quickly.
> But you are not really proposing to eliminate printf and sqrt from the
> language isn't it?
No.
But I am suggesting that your "container" design is going to be useless for a
BIG chunk of the use cases I've seen for lists in the real world.
> I thought you were memory constrained. Inline functions and long macros
> for handling lists are memory intensive...
I never said I was particularly memory constrained. Also, I never said
the macros were long...
On x86, anyway, the most likely implementations of the most common list
operations are not noticably longer than the calling sequence for a function
to implement them. Keep in mind that trivial functions SAVE space when
you inline them!
>> But you are requiring me to pass around a container AND a list element
>> any time I need to be able to do operations on the list element...
> You use the indexing functions. GetNth(list,int);
Yup. That's two arguments, now. Worse, that's going to be a pretty expensive
operation on a list of a thousand items; on average, it'll be 500 loops (and
loops are usually expensive, because branches are expensive).
> Ahh OK. That flexibility is OK when in Ruby.
Design-tradeoffs are a big part of effective engineering. If I am writing
in C, I am doing it because I have a real reason to work at the machine level,
and I'm probably counting cycles. If I want convenient high-level
abstractions to save programmer time, I'm usually in the area where my
work is utterly dominated by I/O waits, and I will use shell or ruby.
> ptr = ListHead;
> n = 23;
> while (ptr && n > 0) {
> ptr = ptr->Next;
> n--;
> }
> assert(n == 0);
> ptr->Data = "This is element 23";
This example is unreasonable, for a very simple reason:
If you care about "element 23", you shouldn't be using a list.
> Why can't we write
> List->lpVtbl->Assign(List, 23, "This is element 23");
Honestly, the capitalization here makes me feel like you don't quite
"get" the Spirit of C. There's a reason that all the library calls
are lowercase...
Anyway, your example highlights a key problem in both cases:
Who determines whether or not to free the pointer associated with a
list element? You're obviously assigning pointers, not arrays, so
there's implicit allocation somewhere. Who owns that allocation?
If it's the container library, what happens if I allocate some space
and want to assign the pointer? The library has to duplicate the thing
I copied. If I own it, how do I track which list elements have allocated
space and which have string literals?
In short, I don't think this is a good use case.
Go read the BSD mbuf code. If you understand that code, I think you'll
get a lot of insight into the requirements for an effective list
implementation in C.
Seebs
> I am assuming that you are proposing this as a change to the standard
> language. So my first observation is that your proposed function
> names are trampling on user namespace. But that's a minor point,
> easily fixed by choosing implementation-reserved names.
Jacob's already said that he intends these to be in a struct, so it
doesn't trample user namespace.
Richard, though, is right -- because that namespace is still available
for user #defines.
> For the list to own the data (which, personally, I think is a good
> idea), it is going to have to make its own copy if it is to persist
> past the point where the feed data goes out of scope. That means a
> malloc, obviously (or some dark equivalent thereof), and some people
> will object purely on those grounds. That's your first major problem
> - some people will want the list to own the data, and others will
> very much want it *not* to own the data.
More succinct that my own explanation, and thus better.
There are good reasons for both. I think you'd need to support both,
but...
> Assuming it does own the data, you then have the problem of pointers
> within that data. Do you do a deep copy, or a shallow copy? If you do
> a shallow copy, you risk ownership confusion and of course dangling
> pointers. If you do a deep copy, you will probably need the user to
> provide copying semantics. This complicates the interface.
Good catch, hadn't thought about deep copies yet.
> The problem is that it's all getting very complicated, and that in
> itself is very likely going to make it unacceptable to a standards
> committee.
Pretty much -- especially because it's not at all clear that there's
enough benefit from standardizing something like that to justify it.
> Bottom line: there are a great many ways to do this, and every way has
> its advocates and detractors. Getting a consensus within ISO for
> adopting any single proposal is a Sisyphean task.
Not necessarily. The snprintf proposal, so far as I can tell, had instant
consensus that everyone wanted it and agreed it was necessary, and all
that remained was making sure that it would work.
(IMHO, we botched part of that spec, and I think "we" is at least
partially my fault; the solution we came up with to "how do you avoid
doing multiple allocations" is not, IMHO, very clean.)
Seebs
That won't work for structs, in general.
> Ahh OK. That's clever. I will add it to my implementation.
It is a very good idea to have a sideband thing for iterators.
I didn't do it in my list library.
For reference:
ls_list *ls_append(ls_list *dest, ls_list *src);
void ls_free(ls_list *list, void (*deinit)(ls_list *));
ls_list *ls_iter(ls_list *list, int (*fn)(ls_list *));
ls_list *ls_new(size_t size, void (*init)(ls_list *));
ls_list *ls_push(ls_list *dest, ls_list *src);
ls_list *ls_rev(ls_list *list);
ls_list *ls_sort(ls_list *list, int nelem, int (*cmp)(const ls_list *, const ls_list *));
I wrote this some time back, I've used it for ages on and off, it's never
given
me any trouble.
> Correct. I do that, but I receive the function pointer at each
> call to the iteration function to avoid storing it in the
> list and increasing the fixed overhead. You are NOT going to
> iterate all lists, only some of them. Then, it is more
> space efficient to pass the iterator to the iterate list
> function.
In my implementation, iteration was a quality of ls_list objects, but
you could provide your own function to apply to the list. (It stops iterating
when the function returns nonzero.)
> Complicated???
> Too complicated???
Yes.
> This is NOTHING. I am sure you have designed software that is MUCH MORE
> complicated than this stuff!
> And most of us have. Including committee members.
Yup. Frequently.
But I never proposed my list library, or my string library, as standard
features, because I don't think they're suitable for standardization.
(My string library does self-space-managing strings which can contain
null bytes and preserve string semantics.)
> I would not aim so high right now. I would aim to develop here in this
> group a consensus implementation that is widely distributed and
> with no strings attached at all.
>
> After it has spread around, we have experience with it, it becomes
>
> CURRENT PRACTICE!
>
> and ISO will gladly adopt it.
This is actually a very good approach to the issue.
My own impressions are that:
1. This design is too top-heavy and full of things that sound general but
are not quite general enough to be worth extra cost.
2. In general, the simple cases are simple enough that a "standard library"
doesn't buy you much, and the complex cases are complex enough that the
"standard library" wouldn't be able to handle them.
FWIW, my list library has been used maybe twice. It dramatically beat qsort
for at least one real-world use case, and that plus not needing to convert
to an array and back made it, apparently, useful to one researcher somewhere
around 1992 or so. I don't even bother to use it if I'm doing trivial lists
now, because it's usually more than I need and I don't want to deal with
including it. :)
Bart
> Richard Heathfield a écrit :
> > Sure. I can see that. But /I/ think it's needed. So we disagree.
> > That's fine, we should be able to disagree without coming to blows,
> > but we can't have both support for a constructor /and/ absence of
> > support (and absence of overhead) for a constructor.
>
> YES WE CAN!
>
> (pun intended)
>
> We can subclass each of those functions if we want to. We can use
> our subclassing at the individual list level (this list will need
> a copy constructor but that one won't) or we can subclass at the
> global level (ALL my lists will use a copy constructor)
This is starting to sound a bit like C++ with all this new jargon. To
get people to use this they have to solidly understand it.
Explain again what these containers do, are they just flexible arrays?
Or linked lists?
--
Bartc
jacob navia
>
>>> Sure. I can see that. But /I/ think it's needed. So we disagree.
>>> That's fine, we should be able to disagree without coming to blows,
>>> but we can't have both support for a constructor /and/ absence of
>>> support (and absence of overhead) for a constructor.
>> YES WE CAN!
>>
>> (pun intended)
>>
>> We can subclass each of those functions if we want to. We can use
>> our subclassing at the individual list level (this list will need
>> a copy constructor but that one won't) or we can subclass at the
>> global level (ALL my lists will use a copy constructor)
>
> This is starting to sound a bit like C++ with all this new jargon. To
> get people to use this they have to solidly understand it.
>
The library comes with a pointer to a predefined function.
If you need to do something before the call to the library or
later you read the function pointer in your list.
Then, you replace it with a pointer to YOUR function.
For instance, you want to make a deep copy of an object
stored in the list, as Mr heathfield wanted.
You read the pointer, and you store a pointer to your function
MyAppend. That function does a deep copy of the
object it receives then calls the stored function pointer
to make a npormal call to the library function.
If you program under window you should remember how window
subclassing works. Clearer now?
> Explain again what these containers do, are they just flexible arrays?
> Or linked lists?
>
Lists aren't flexible arrays since storage is not necessarily
contiguous. That's why they need a "next" pointer.
Flexible arrays look very much like lists since you can insert
items but storage is contiguous
OK?
Sorry about the confusion.
Mark McIntyre
>
> Only dead things are fixed forever and can't evolve.
That's both incorrect and pejorative.
> A computer language
> MUST change or it simply dies.
Something evolves if and only if there is a purpose to that evolution.
Change for changes' sake is both pointless and dangerous.
The argument seems to be "I cannot do X in C, therefore C should change
to do X". Perhaps. But I cannot anchor a battleship with string, yet
still I see no general upswell of popular opinion demanding string you
can anchor battleships with. If string were the only possible material -
but luckily we have chain. Similarly, we have C++, C#, Java, and so forth.
> The problem is that C++ has grown so complex, that even the creator
> and principal force behind C++ was unable to do that change in a
> time frame of years.
So now you're arguing that because in your opinion C++ has become too
complex, we must abandon it and start making C more complex? But
naturally, only in the ways that you wish for.
Why not follow Bjarne's lead and write a new language which meets your
criteria? Call it C2 or something.
> What to do?
>
> I do not know.
And yet you incessantly attempt to tell people.
(I know, selective snipping. See if I care)
--
Mark McIntyre
CLC FAQ <http://c-faq.com/>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
Seebs
> You build an object in a buffer. You populate it and when ready,
> you give it to the list. Then, for the next object you reuse
> the same static buffer. Only one allocation.
I might not know what size it will be in advance -- in which case, you're
allocating a list object to hold the pointer to my allocated object.
> ANY list needs two object for each item.
No, it doesn't.
> (1) The first one has at least two fields: the "next" pointer, and the
> pointer to the data.
> (2) The actual data that the list holds.
> This stays the same. There is NO extra overhead.
Uh.
struct list {
struct list *next;
size_t len;
int data[];
};
We fixed that a LONG time ago, and even before C99 formally blessed a syntax
for this, everyone knew it worked with 'int data[1];' or 'int data[999999];'
on real compilers. :)
> Well, THAT'S ALL LISTS IN THE WORLD!
No, it isn't.
An awful lot of lists written in C store the 'next' pointer in the data
object.
That's the point.
> Mmm you stoire backpointers to the root of the list at each element?
Nope.
I don't usually find myself needing any hypothetical "root" of the list.
The list isn't a separate object. Each allocated item capable of
being in a list has a next pointer. That's it.
> But that is not different as lists now! ANY list needs two elements
> see above.
Nope.
> No, because the list software has a pool of list elements that decreases
> the likehood of using malloc...
This changes very little; it's still allocation, even if it's a streamlined
allocator.
>> Don't forget that there's at least some extra space used by each allocated
>> object for the malloc internals.
> No, since the list software allocates many lists elements at once in
> blocks.
And then tracks which ones it's used...
Yeah, not seeing an advantage here.
Richard Heathfield
> On 2009-09-17, Richard Heathfield <r...@see.sig.invalid> wrote:
<snip>
>
>> Bottom line: there are a great many ways to do this, and every way
>> has its advocates and detractors. Getting a consensus within ISO
>> for adopting any single proposal is a Sisyphean task.
>
> Not necessarily. The snprintf proposal,
My apologies for not being clearer. I meant any single proposal along
the lines that the OP was suggesting - i.e. fighting to get ISO to
endorse a standard linked list interface would itself be a tough
battle. Then you've got hash tables, BSTs (balanced/no?
red-black/AVL/something else? Just binary? How about quad-trees and
oct-trees?), tries, B+-trees, sparse arrays...
Bart
> Bart a écrit :
> > Explain again what these containers do, are they just flexible arrays?
> > Or linked lists?
>
> Lists aren't flexible arrays since storage is not necessarily
> contiguous. That's why they need a "next" pointer.
>
> Flexible arrays look very much like lists since you can insert
> items but storage is contiguous
>
> OK?
OK, so these are ways of dealing with linked lists in a generic
manner.
Although, I've looked at some of my linked lists, and I usually start
with a struct of some sort then add a .next field for a simply-linked
list. The trouble is I usually have several of these .next fields
(with different names) as a list node can exist simultaneously in one
than one linked list. (And often there are up and down pointers so
technically making these trees too.)
Getting back to a single, simply-linked list, I think what you are
suggesting is to start with any list node struct S, without /
any/ .next fields, and supply this struct to your library which
inserts it (as a pointer to S) in a generic linked list framework.
Yes, that sort of seems like a good idea, although nothing that needs
language changes. But I suspect in practice individual requirements
mean your method cannot always be used.
--
Bartc
Flash Gordon
> cognacc a �crit :
>> What about glib form the gtk - gnome "suite"
>> Couldnt that be used as base for some standardisation?
>>
>> http://www.cs.tut.fi/ohj/VARG/TVT/GTKsources.html
>>
>>
>> after unpacking, go insode directory glib/
>> forexample something called glist.h|c as an example.
>
> There are two problems with that library:
>
> (1) The more serious one:
> http://library.gnome.org/devel/glib/2.20/glib-Memory-Allocation.html
> <quote>
> Memory allocation functions.
> ---------------------------
> Description
> These functions provide support for allocating and freeing memory.
> Note
> If any call to allocate memory fails, the application is terminated.
> This also means that there is no need to check if the call succeeded.
> <end quote>
>
> This is completely unacceptable and actually it is a horrible idea.
> This precludes any use of the whole library since all functions
> that *potentially* allocate memory are tainted.
I agree, and from previous discussions here I believe a lot of others
here do as well.
> (2) Another problem (or maybe not) is:
> * This library is free software; you can redistribute it and/or
> * modify it under the terms of the GNU Library General Public
> * License as published by the Free Software Foundation; either
> * version 2 of the License, or (at your option) any later version.
>
> I do not know if linking with gtk forces you to disclose your
> source code...
Try reading the license. In any case, I'm shre that I've pointed out in
the past that it does NOT mean you have to disclose your source code,
you can keep your application closed source and sell it. Many companies
do this.
> In any case the glist functions interface are very similar to
> what I propose or to many other lists packagesa around.
Well, I've seen servers hitting 100% CPU and *also* hammering the disk
interface, and in code like that we don't want to add more indirections
than we need. This is code running on high spec server, not embedded
systems, so 8GB RAM minimum, high performance CPU etc.
--
Flash Gordon
websnarf
> On 2009-09-16, jacob navia <ja...@nospam.org> wrote:
> > C99 did not bring any real change into the core problems of the C
> > language.
>
> It brought a number of changes that were directly related to core
> problems which were significant to implementors.
>
> For instance, restrict pointers,
This is just so some implementors could claim their code was compliant
and still win some esoteric benchmark. It also allowed implementors
to throw the responsibility of aliasing issues to the developers
rather than the system vendor.
> [...] mixed declarations and code,
That is so retarded. This *ONLY* applies to C++ code. If I see mixed
code and declarations, I always assume its either wrong or its C++,
with the expected differences in semantics. Mixing the declarations
and code in C never serves any useful purpose.
> [...] and variable-length arrays;
In which you broke compatibility with gcc, which is the mostly widely
used compiler that implement variable length arrays. Good job.
> [...] all of these address real-world problems
> which made life harder for compiler writers and coders looking at
> high-performance systems.
Which explains why oh so many people were clamoring for these features
as can be evidenced by the massive volume of technical articles and
books describing them and the need for the transition and ... oh
wait. None of that happened. Most real world developer don't even
have a clue about C99, what its substantive differences are, not could
they imagine why they would need or want its features.
In the exact same period of time security (the various viruses, worms,
buffer overflow exploits etc), portability (as evidenced by Java,
HTML, Perl, Samba and other portability solutions), and unicode (now
that its clear that the Chinese and the rest of the world will adopt
it) were become extremely hot topics that system level programmers and
application developers were really focusing on. Furthermore there was
a general transition from 32 bit systems to 64 bit systems looming.
Take a look at the C99 standard in light of that.
> > It did NOT address:
> > (1) The problem of a completely obsolete standard library with functions
> > like gets() or asctime() still there.
>
> That problem is not likely to get addressed. Quite simply, the functions
> are there to support existing code, but you don't have to use them.
You don't get out much do you? Microsoft's latest compiler actually
issues a warning if you use those functions. gcc issues a linker
warning if you use gets(). The implementors are going beyond the
standard, because the issue is too important.
> The library DID add several needed functions (snprintf among them) which
> make it more possible or practical to write safe and efficient code for
> a number of real-world circumstances.
None of the printf class of functions should ever be put in the same
sentence as the word "efficient". If you want efficiency, you need to
do compile, or code-time expansion of such code directly. If you put
printf-like semantics in the *PRE-PROCESSOR* then we could discuss
efficiency.
> > (2) The problem of the absence of a counted string data type
>
> I solved that problem once. It took me maybe a month to do a library of
> self-managing string-like objects, and it's worked fine ever since.
Yeah, I've seen it. You use memory patterns in the contents to detect
the countedness. Its like you don't even understand why \0
termination is such a bad idea in the first place.
> [...] I'm not sure the language needs it, though I wouldn't object.
Well, technically it doesn't. The Better String Library, is a
complete implementation which is portable to any C or C++ compiler I
have encountered. Just download it and use it, and stop worrying
about it: http://bstring.sf.net/ . The important point is to stop
using the old functions.
> > (3) The problem of the lack of a standard way of using containers like
> > lists, hash tables, or similar.
>
> I don't think this is a problem to be solved at the language level,
> although I could be persuaded otherwise if someone had a good demo.
[Comment withheld]
> > There wasn't any INCENTIVE for the compiler writers to implement the
> > changes because many of them (complex numbers, syntactic innovations
> > or similar stuff) didn't bring any substantial improvement.
>
> Only they did. Who do you think proposed those?
*Particular* vendors with an agenda. Not surprisingly, gcc was slow
with the uptake. Does the standard committee even take feedback from
gcc?
> > The problem was not that the changes were difficult to implement but
> > that they did not bring anything really new that customers were
> > really asking for.
>
> Uh.
>
> On the one hand, we have representatives paid for and sent by Sun, SGI,
> and IBM. On the other hand, we have you. The people from the large companies
> with active compiler development groups and hundreds or thousands of
> customers said they needed to provide these features for their customers,
> and they wanted standardized forms so customers could use these features
> without freaking out.
Lol! Do you buy all the products you see in all the TV commercials
too?
Those vendors representative are paid to *RIG* the language so that
they can win a benchmark against their competitors, and that is all.
The "customers" that they are telling you about are selected as those
which happen to be the authors of said benchmarks which helps to
highlight the performance of these particular systems.
Do you have people on your committee that are from Metrowerks,
Borland, WATCOM or the Free Software Foundation? No, they are from
IBM, Intel and Sun. While both classes of entities make compilers,
one class has a blatantly obvious conflict of interest (i.e., they are
willing to harm the language if it harms their competitors more than
it harms themselves). And guess which you are taking advice from?
> > Obviously this leads to the complete destruction of C as a living
> > language. It ceases to evolve, and it is considered by most people
> > as a dead language.
>
> Honestly, if it didn't evolve, it would still remain useful for quite a
> while yet. Most of what I do can still be done reasonably in C89.
What that's an understatement. In fact there is nothing you can do in
C99 that you couldn't do in C89.
The C99 committee didn't even try to make the language better. There
are obvious candidates like a ranged memory expansion (like realloc,
but resizes to a size in a given range, to improve the chances of a
non-moving realloc) and widening multiply (multiply two 32 bit inputs
to get a 64 bit result, or two 64 bits to get a 128, etc) which you
didn't bother to consider (and would have truly made the language more
powerful). No coroutines (that would have been nice -- alas, I see it
show up in language like Lua and Python, first). No attempt at type
safety (see gcc) or lambda capabilities in the pre-processor.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
Chris M. Thomasson
news:slrnhb4peb.rbv...@guild.seebs.net...
I am quite fond of the method used in the Linux kernel. I will do a simple
stack using the technique:
< pseudo-code typed in news reader; please forgive any typos ;^o >
____________________________________________________________________
#define CONTAINS(mp_this, mp_struct, mp_member) ((mp_struct*)( \
((unsigned char*)(mp_this)) - offsetof(mp_struct, mp_member) \
))
struct slist
{
struct slist* next;
};
#define SLIST_INIT { NULL }
void
slist_init(struct slist* const self)
{
self->next = NULL;
}
void
slist_push(struct slist* const self,
struct slist* node)
{
node->next = self->next;
self->next = node;
}
struct slist*
slist_pop(struct slist* const self)
{
struct slist* node = self->next;
if (node)
{
self->next = node->next;
}
return node;
}
____________________________________________________________________
You can even create "generic" functions to operate on the stack; example:
____________________________________________________________________
void
slist_reverse(struct slist* const self)
{
struct slist* n;
struct slist rslist = SLIST_INIT;
while ((n = slist_pop(self)))
{
slist_push(&rslist, n);
}
self->next = rslist.next;
}
____________________________________________________________________
This `slist_reverse()' procedure will work no matter what type of data the
user stores into the stack. You can use everything like this:
____________________________________________________________________
static struct slist g_slist = SLIST_INIT;
struct data
{
int blah;
struct slist node;
char blah;
};
void
foo(void)
{
size_t i;
struct data* d;
struct slist* n;
for (i = 0; i < 10; ++i)
{
if ((d = malloc(sizeof(*d))))
{
slist_push(&g_slist, &d->node);
}
}
slist_reverse(&g_slist);
while ((n = slist_pop(&g_slist)))
{
d = CONTAINS(n, struct data, node);
free(d);
}
}
____________________________________________________________________
Pretty straight forward and fairly "efficient" right?
;^)
Chris M. Thomasson
news:h8v8t2$24ik$1...@news.ett.com.ua...
[...]
You can use everything like this:
> ____________________________________________________________________
> ____________________________________________________________________
>
>
>
>
> Pretty straight forward and fairly "efficient" right?
>
> ;^)
You can even store the same data in more than one stack; something like
this:
____________________________________________________________________
static struct slist g_slist[2] = { SLIST_INIT, SLIST_INIT };
struct data
{
int a;
struct slist node1;
char b;
struct slist node2;
double c;
};
void
foo(void)
{
struct slist* n;
struct data d;
slist_push(&g_slist[0], &d.node1);
slist_push(&g_slist[1], &d.node2);
n = slist_pop(&g_slist[1]);
assert(CONTAINS(n, struct data, node2) == &d);
n = slist_pop(&g_slist[0]);
assert(CONTAINS(n, struct data, node1) == &d);
}
____________________________________________________________________
This is a intrusive container which means there are some caveats. The object
size will be increased for each stack it must be stored in simultaneously.
If objectA needs to be stored in N stacks, then it will need at least N
embedded `struct slist' objects. It sounds like Jacob is writing about
non-intrusive stacks, which are more flexible, but have their tradeoffs as
well. Which one is better? Well it depends on what you're going to use it
for...
Seebs
> This is just so some implementors could claim their code was compliant
> and still win some esoteric benchmark. It also allowed implementors
> to throw the responsibility of aliasing issues to the developers
> rather than the system vendor.
I don't buy this analysis. Do you have some kind of basis for it?
The impression I got was that, through the magic of separate compilation,
it could be just plain impossible to determine while compiling a given
module whether or not aliasing of arguments was possible, but that, if you
had the qualifier, you could then optimize some code better.
> That is so retarded. This *ONLY* applies to C++ code. If I see mixed
> code and declarations, I always assume its either wrong or its C++,
> with the expected differences in semantics. Mixing the declarations
> and code in C never serves any useful purpose.
Not true:
* VLAs actually care.
* Other stuff could actually care, although it probably usually doesn't.
(And actually, the for-loop-declarator was done pretty much at the same
time, and for the same reasons.)
So, while you may not think the benefit is particularly *significant* outside
of C++, it's still useful to some developers.
>> [...] and variable-length arrays;
> In which you broke compatibility with gcc, which is the mostly widely
> used compiler that implement variable length arrays. Good job.
Yeah, that was definitely a clusterfsck. Back then, there was some
general distrust of standardization in GNU land. (This was back when
the gcc docs claimed that some exceptionally bogus behavior was
mandated by ANSI, so far as I can tell simply out of spite; it wasn't,
and never had been, mandated by ANSI.) As a result, there were no gcc
implementors active in the standards effort. I do agree that it woulda
been better to be more aggressive about researching that, but to be
fair, I believe we did have other implementations to look at... Which
had, of course, decided things differently.
> Which explains why oh so many people were clamoring for these features
> as can be evidenced by the massive volume of technical articles and
> books describing them and the need for the transition and ... oh
> wait. None of that happened.
I didn't say these features were demanded by the vast majority of users, only
that there were users who pushed for them.
> Most real world developer don't even
> have a clue about C99, what its substantive differences are, not could
> they imagine why they would need or want its features.
Probably true.
> In the exact same period of time security (the various viruses, worms,
> buffer overflow exploits etc), portability (as evidenced by Java,
> HTML, Perl, Samba and other portability solutions), and unicode (now
> that its clear that the Chinese and the rest of the world will adopt
> it) were become extremely hot topics that system level programmers and
> application developers were really focusing on. Furthermore there was
> a general transition from 32 bit systems to 64 bit systems looming.
> Take a look at the C99 standard in light of that.
Okay. Let's see. We adopted UCNs in identifiers and string literals,
gave reasonable support for UTF-8, 16, and 32, and dramatically improved the
quality of support for character sets uther than 7-bit ASCII. C99 not only
added a 64-bit type, but added a massive rework of the integral promotion
system to make it scalable and durable in the face of possibly-larger types,
clarified and standardized how to store pointers in an integer of large
enough size if possible, reserved a suitable namespace with suitable patterns
for expressing concepts such as "at least 32 bits" or "exactly 32 bits" or
"fastest thing you have with at least 16 bits". Security, and buffer
overruns? snprintf solves a HUGE chunk of that problem space, if used
competently. (VLAs actually help a lot with some common use cases, too.)
In short, a whole lot of these were issues that got specific attention and
improvements. The Unicode support and better support for larger bit sizes
and systems with a broader range of types both looked like serious work
that addressed those problems, apparently well enough to be of use to
people.
Also, some of the limit-raising has made life a lot easier for people writing
portable code.
>> That problem is not likely to get addressed. �Quite simply, the functions
>> are there to support existing code, but you don't have to use them.
> You don't get out much do you?
Heh.
> Microsoft's latest compiler actually
> issues a warning if you use those functions. gcc issues a linker
> warning if you use gets(). The implementors are going beyond the
> standard, because the issue is too important.
That's fine, and that's what I'd expect. It's a quality-of-implementation
issue. (That said, you're arguably wrong; gcc doesn't issue that warning in
and of itself, that's managed by, or not managed by, the system C library
and additional linker magic.)
You can't take those things out without at the very least deprecating them
first. You can, however, encourage implementors to issue diagnostics.
Say, by deprecating gets, and calling it "obsolescent", warning about it
in future language directions, and so on.
> None of the printf class of functions should ever be put in the same
> sentence as the word "efficient". If you want efficiency, you need to
> do compile, or code-time expansion of such code directly. If you put
> printf-like semantics in the *PRE-PROCESSOR* then we could discuss
> efficiency.
Compare snprintf to what you had to do before it existed. It's substantially
more efficient, even if it's not efficient "enough".
> Yeah, I've seen it. You use memory patterns in the contents to detect
> the countedness. Its like you don't even understand why \0
> termination is such a bad idea in the first place.
It's not a perfect design, certainly, but on the other hand, it does
noticably reduce the *likelihood* of collisions. (In fact, the
"memory patterns" thing has no impact unless you want to try to take
advantage of the magic implicit conversions; if you don't use those,
it isn't an issue.)
> *Particular* vendors with an agenda. Not surprisingly, gcc was slow
> with the uptake. Does the standard committee even take feedback from
> gcc?
If they offer it, absolutely! At the time, the people working on gcc
weren't that interested -- this was pre-egcs, remember.
> Lol! Do you buy all the products you see in all the TV commercials
> too?
Nope.
> Those vendors representative are paid to *RIG* the language so that
> they can win a benchmark against their competitors, and that is all.
Your cynicism fascinates me, but it does not persuade me. I spent a
while talking to these people and seeing what they thought was important.
I am pretty sure they were not trying to partake in some huge crazy
conspiracy.
> Do you have people on your committee that are from Metrowerks,
> Borland, WATCOM or the Free Software Foundation? No, they are from
> IBM, Intel and Sun.
Anyone can participate. I did it out of my own pocket for about a decade
just because I thought it was fun -- and I got just as much of a vote,
and I got listened to. If someone from the FSF wanted to go, I don't
think anyone would complain at all.
> While both classes of entities make compilers,
> one class has a blatantly obvious conflict of interest (i.e., they are
> willing to harm the language if it harms their competitors more than
> it harms themselves).
You say this, but again, I see no evidence. The people I saw participating
were, consistently, devotees of C who really wanted it to succeed.
> What that's an understatement. In fact there is nothing you can do in
> C99 that you couldn't do in C89.
Well, strictly speaking, there's nothing I can do in any language that I
can't do in any other.
But there's a ton of stuff that works enough better in C99 than C89 that
I've mostly switched to specifying that and using those features.
> The C99 committee didn't even try to make the language better. There
> are obvious candidates like a ranged memory expansion (like realloc,
> but resizes to a size in a given range, to improve the chances of a
> non-moving realloc) and widening multiply (multiply two 32 bit inputs
> to get a 64 bit result, or two 64 bits to get a 128, etc) which you
> didn't bother to consider (and would have truly made the language more
> powerful).
Fascinating to hear from someone who wasn't there what we did or didn't
consider.
> No coroutines (that would have been nice -- alas, I see it
> show up in language like Lua and Python, first).
I've seen them implemented successfully often enough that I'm not sure this
is as fatal as it might seem.
> No attempt at type
> safety (see gcc) or lambda capabilities in the pre-processor.
There was some discussion of the pre-processor thing, which I personally
liked, but there was a pretty strong consensus that the pre-processor was
bad enough laready.
> Paul Hsieh
> http://www.pobox.com/~qed/
... Aren't you the guy who made it to Chapter 7 in the IAQ suggesting
"corrections"? (chromatic.com?) If so, I remain stunned; it's not just
the failure to recognize the jokes, it's that in several cases the answers
were technically correct (albeit carefully phrased poorly), and my
correspondant "corrected" them with errors.
I bring this up partially because I still wonder to this day whether the
epic set of corrections was intended as some kind of joke, and also because
it would be relevant to the question of whether I should trust your statements
about other peoples' intent...
Phil Carmody
> In <slrnhb544i.lon...@guild.seebs.net>, Seebs wrote:
>
>> On 2009-09-17, Richard Heathfield <r...@see.sig.invalid> wrote:
> <snip>
>>
>>> Bottom line: there are a great many ways to do this, and every way
>>> has its advocates and detractors. Getting a consensus within ISO
>>> for adopting any single proposal is a Sisyphean task.
>>
>> Not necessarily. The snprintf proposal,
>
> My apologies for not being clearer. I meant any single proposal along
> the lines that the OP was suggesting - i.e. fighting to get ISO to
> endorse a standard linked list interface would itself be a tough
> battle. Then you've got hash tables, BSTs (balanced/no?
> red-black/AVL/something else? Just binary? How about quad-trees and
> oct-trees?), tries, B+-trees, sparse arrays...
Given the not-necessarily-quick nature of qsort, there is precedent
for them providing an abstract interface with no specification of
internal implementation. The same could happen here. On creating
the structure you could specify whether you minded/wanted reading
being a potentially-writing operation, for example. If you had done,
it might construct a splay-tree instead of an AVL, for example.
Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
Herbert Rosenau
wrote:
Jacob naiva proves once again that he is a twit.
>
> Software changes not because the people that write it need changes just
> for the sake of it. Requirements change. Hardware evolves, people come
> and go, the machines and environment where software exists changes.
Now he will tell us that softare must be changed because it must be
changed because ....
I use lots of tools written 25 years ago. I will use the same software
without any change the rest of my life because it does exactly what it
should do. No change needed.
> Only dead things are fixed forever and can't evolve. A computer language
> MUST change or it simply dies.
Look naiva buy monthly all it hand tools because he needs news becaus
the old does not work anymore because it is old.
Yes, really some of the software I have in daylky use is really old 16
bit - but it works well, it does it was designed for 5 generations of
the OS prior the current 32 bit one - but it works, it fullifies the
needs perfectly like the day it went GA.
Why should it be replaced? Only because it is old? Only because it was
originally written for 16 bit even as it runs very well natively now
inside my 32 bit OS? Yes, it does because the developers of my OS
decided some versions ago that it should be natively 100% compatible
to 16 bit because portability requirements to avoid senseless
rewriting anything usefull.
Yes, some tools gets replaced multiple times in a year because there
are new versions with less bugs, resolved security problems and
sometimes extended functionality. So there are 2 different kinds of
software:
-one that is written and tested once - and works absolutely unchanged
until compatible processors does not more exist.
- one that needs dayly rewritten or changed because security
requirements teeds that or extended functionality makes sense.
But jacob naiva thinks that even a simple knive must be replaced
because it is old, even as it is new like it was builded 1 minute ago.
--
Tschau/Bye
Herbert
Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!
Tech07
> In the thread "When will C have an object model?", I found a
> message from Mr Heathfield that warrants a deeper discussion.
>
> That thread was (for a change) an interesting one.
>
> Richard Heathfield a �crit :
>>
>> It is perhaps because software is so malleable that we are so tempted
>> to change it.
That is blather. Or are you calling me stupid? "You talkin' to me?"
>>I doubt whether *any* computer language exists
I don't "doubt that" and haven't for umpteen years.
> that
>> *exactly* meets the needs of more than a handful of people,
Propoganda!
>> so it is
>> natural for people to want to change the language(s) they use to suit
>> their needs more closely.
Nothing beyond your propaganda bomb is relevant. Hello! Propaganda bombing
doesn't work or someone is a rapist or dumb. Are you a rapist or dumb?
Tech07
> In the thread "When will C have an object model?", I found a
> message from Mr Heathfield that warrants a deeper discussion.
>
> That thread was (for a change) an interesting one.
>
> Richard Heathfield a �crit :
>>
>> It is perhaps because software is so malleable that we are so tempted
>> to change it.
Noted: you want to masturbate.
Richard Heathfield
> jacob navia wrote:
>> In the thread "When will C have an object model?", I found a
>> message from Mr Heathfield that warrants a deeper discussion.
>>
>> That thread was (for a change) an interesting one.
>>
>> Richard Heathfield a �crit :
>>>
>>> It is perhaps because software is so malleable that we are so
>>> tempted to change it.
>
> That is blather. Or are you calling me stupid?
I see no reason why I should want to call you stupid. You seem
perfectly capable of informing people of that fact, all by yourself.
Tech07
> In <ErAAm.1268$Ku5....@newsfe04.iad>, Tech07 wrote:
>
>> jacob navia wrote:
>>> In the thread "When will C have an object model?", I found a
>>> message from Mr Heathfield that warrants a deeper discussion.
>>>
>>> That thread was (for a change) an interesting one.
>>>
>>> Richard Heathfield a �crit :
>>>>
>>>> It is perhaps because software is so malleable that we are so
>>>> tempted to change it.
>>
>> That is blather. Or are you calling me stupid?
>
> I see no reason why I should want to call you stupid. You seem
> perfectly capable of informing people of that fact, all by yourself.
>
> <snip>
Richard Heathfield
<snip>
> Leave me alone.
I take it you are offering to leave me alone, too?
Tech07
> In <kHBAm.98952$u76....@newsfe10.iad>, Tech07 wrote:
>
> <snip>
>
>> Leave me alone.
>
> I take it you are offering to leave me alone, too?
whoa on that... "gag me with a spoon". If you're raping, I'm all over you.
It's a yes or no "question".
Tech07
> In <kHBAm.98952$u76....@newsfe10.iad>, Tech07 wrote:
>
> <snip>
>
>> Leave me alone.
>
> I take it you are offering to leave me alone, too?
Are you entitled like your president? pfft. cry me a fucking gestapo.
Richard Heathfield
> Richard Heathfield wrote:
>> In <kHBAm.98952$u76....@newsfe10.iad>, Tech07 wrote:
>>
>> <snip>
>>
>>> Leave me alone.
>>
>> I take it you are offering to leave me alone, too?
>
> whoa on that...
So you expect from others behaviour which you are not prepared to
observe yourself. Okay, noted.
As for leaving you alone: you have the right to start threads here,
and you have the right to reply to articles posted here. I have the
same rights. But of course I have no particular desire to get on your
case (whereas the reverse does not appear to be true).
<nonsense snipped>
Richard Heathfield
> Richard Heathfield wrote:
>> In <kHBAm.98952$u76....@newsfe10.iad>, Tech07 wrote:
>>
>> <snip>
>>
>>> Leave me alone.
>>
>> I take it you are offering to leave me alone, too?
>
> Are you entitled like your president?
I wasn't aware that I had a president.
> pfft. cry me a fucking gestapo.
Learn some adjectives.
Tech07
> In <_RCAm.32959$lR3....@newsfe25.iad>, Tech07 wrote:
>
>> Richard Heathfield wrote:
>>> In <kHBAm.98952$u76....@newsfe10.iad>, Tech07 wrote:
>>>
>>> <snip>
>>>
>>>> Leave me alone.
>>>
>>> I take it you are offering to leave me alone, too?
>>
>> Are you entitled like your president?
>
> I wasn't aware that I had a president.
>
>> pfft. cry me a fucking gestapo.
>
> Learn some adjectives.
That is keen of you. I have no use for them.
Tech07
> In <cQCAm.226582$sC1.1...@newsfe17.iad>, Tech07 wrote:
>
>> Richard Heathfield wrote:
>>> In <kHBAm.98952$u76....@newsfe10.iad>, Tech07 wrote:
>>>
>>> <snip>
>>>
>>>> Leave me alone.
>>>
>>> I take it you are offering to leave me alone, too?
>>
>> whoa on that...
>
> So you expect from others behaviour which you are not prepared to
> observe yourself. Okay, noted.
>
> As for leaving you alone: you have the right to start threads here,
> and you have the right to reply to articles posted here. I have the
> same rights. But of course I have no particular desire to get on your
> case (whereas the reverse does not appear to be true).
>
> <nonsense snipped>
lighten up dude.