New release of the C Containers Library (CCL)

[jacob navia]

Le 01/11/10 12:26, MartinBroadhurst a écrit :

You would use a *pointer* to an abstract base class, just as we're
using pointers here in C.

Martin

Well, then it corresponds exactly to an abstract structure in C.
(struct foo

Do an abstract class force a performance penalty in C++?

When I call an abstract class, does the generated code have more to do?

Thanks for your contribution.

jacob

 

[MartinBroadhurst]

Well, then it corresponds exactly to an abstract structure in C.
(struct foo

Do an abstract class force a performance penalty in C++?

Yes, because there is an extra level of indirection. When a method is
called on a pointer to an abstract base class, the vtable is retrieved
from the address point of the object, and then the derived class
method pointer is retrieved from the vtable.

When I call an abstract class, does the generated code have more to do?

Yes, for the same reason. In addition, there is some overhead in
constructing objects with virtual functions because the vtable needs
to be set up.

Martin

 

[jacob navia]

Le 01/11/10 12:46, MartinBroadhurst a écrit :

Yes, because there is an extra level of indirection. When a method is
called on a pointer to an abstract base class, the vtable is retrieved
from the address point of the object, and then the derived class
method pointer is retrieved from the vtable.

That is exactly what I do:

For instance to call the generic function "newIterator":

Iterator *newIterator(GenericContainer *gen)
{
return gen->VTable->newIterator(gen);
}

I call the vtable of the object. Since the vtables of all
containers contain the function "newIterator" at the same position,
this works.

I do it with ONE indirection, and not two, as you can see.

OK, then if I am at the same level of C++ it is OK.

Yes, for the same reason. In addition, there is some overhead in
constructing objects with virtual functions because the vtable needs
to be set up.

Since I do only one indirection, this is not necessary. Derived objects
are just the same as before.

The only thing that the derived object needs to ensure is that all
functions that are part of the interface are at the same position in
their vtables.

After that, there are no constraints, in fact, the existence of the
abstract class is completely transparent to them.

What is relly nice when working in C is the absolute freedom to do as
you want. In this case, not having ANY object oriented framework is a
bonus in some ways since you can lay out your object as you want.

jacob

 

[Ben Bacarisse]

Le 01/11/10 11:49, Malcolm McLean a écrit :

Interesting...

In my implementation, the generic functions aren't virtual really
since they call the container specific function. This costs an
indirection and an indirect function call in C.

I would be interested to know what the cost of virtual base classes is
in C++ (if any)

I think you're going to be end up with the wrong view of C++ if you take
your information from this group.

I am not a C++ expert, but I believe Malcolm is wrong about how "you
make" containers in C++. Using inheritance and virtual base classes is,
I think, regarded as how *not* to do it. The STL uses template classes
and though inheritance is used (particularly for types with a lot of
shared behaviour like iterators) there is no ultimate container virtual
base class.

Of course, you have no reason to believe me rather than Malcolm. A quick
post in comp.lang.c++ would get you highly trustworthy information about
C++'s standard containers.

<snip>

 

[MartinBroadhurst]

That is exactly what I do:

For instance to call the generic function "newIterator":

Iterator *newIterator(GenericContainer *gen)
{
     return gen->VTable->newIterator(gen);

}

I call the vtable of the object. Since the vtables of all
containers contain the function "newIterator" at the same position,
this works.

If you want to know how C++ abstract base classes are actually laid
out in memory, get hold of the Windows SDK and look in the Include
directory for a header file that has a corresponding .idl file with
the same name, say oledb.h. Search the file for the string "C style
interface". What you will see is a vtable, and a C struct containing
it, that have been laid out to be identical to a C++ abstract base
class. This is provided so that C programmers can write COM
components.

There is also an article about COM programming in C on MSDN that I
found quite informative here:

http://msdn.microsoft.com/en-us/library/ms809982.aspx

Martin

 

[MartinBroadhurst]

I am not a C++ expert, but I believe Malcolm is wrong about how "you
make" containers in C++.  Using inheritance and virtual base classes is,
I think, regarded as how *not* to do it.  The STL uses template classes
and though inheritance is used (particularly for types with a lot of
shared behaviour like iterators) there is no ultimate container virtual
base class.

The STL has a concept hierarchy, while Java and the .NET framework opt
for a class (and interface) hierarchy.
I think in both cases the hierarchy is more about classification than
substitutability.

Martin

 

[BartC]

Le 31/10/10 22:48, BartC a écrit :

I run a search about append in /usr/share/man and the only place where it
is used is in curl_slist_append, that adds a string to a list of strings.
That supports your idea.

The other is that "strcat" (probably from string conCATenate) does the
equivalent for strings

'Append' and 'Concatenate' are sometimes used interchangeably (and for
strings, they do the same thing), but there is a subtle difference. This is
how I use them:

(10,20,30) concat (40,50,60) => (10,20,30,40,50,60)
(10,20,30) append (40,50,60) => (10,20,30,(40,50,60))

(10,20,30) concat 40 => (10,20,30,40)
(10,20,30) append 40 => (10,20,30,40)

In a general language, both should be available. In your C library where
lists likely have homogeneous element types, appending a list probably isn't
too useful, while you seem to be using 'Add' to append a single item. So
it's just a question of naming.

(In Python, "+" does the "concat" operation I've described for two lists,
while "append" does the equivalent of my "append", although as an in-place
modifier rather than a general operator).

 

[Ian Collins]

I think you're going to be end up with the wrong view of C++ if you take
your information from this group.

I am not a C++ expert, but I believe Malcolm is wrong about how "you
make" containers in C++. Using inheritance and virtual base classes is,
I think, regarded as how *not* to do it. The STL uses template classes
and though inheritance is used (particularly for types with a lot of
shared behaviour like iterators) there is no ultimate container virtual
base class.

That's a fair summary.

The cost of the C++ approach is it requires some form of generics
(templates) and the benefit is performance. While removing indirect
function calls only contributes a small performance gain, the ability to
optimise away those calls can make significant performance gains.

 

[Jon]

For instance to call the generic function "newIterator":

Iterator *newIterator(GenericContainer *gen)
{
return gen->VTable->newIterator(gen);
}

You see?

If you write
Iterator *n = iList.newIterator(container);

You call directly the right function, but then you have to know
that your container is a list.

It costs a function call + indirection + indirect function call.

It costs, apparently: a function call + indirection + indirection +
function call.

Your "notation" makes it seem like it is twice removed whereas it
actually is thrice so.

I haven't found any way to avoid that extra call.

#define newIterator(generic_cont)
generic_cont->VTable->newIterator(generic_cont)

Macros: the "poor man's" inline function.

 

[Jon]

I think you're going to be end up with the wrong view of C++ if you
take your information from this group.

I am not a C++ expert, but I believe Malcolm is wrong about how "you
make" containers in C++. Using inheritance and virtual base classes
is, I think, regarded as how *not* to do it. The STL uses template
classes and though inheritance is used (particularly for types with a
lot of shared behaviour like iterators) there is no ultimate
container virtual base class.

Maybe the C++ people rejected the design Jacob is proposing for a good
reason ya think? It's not good enough for C++ but good enough for "second
class" C?

 

[Jon]

That's a fair summary.

The cost of the C++ approach

C++ is much much broader in scope than a single library (STL) or the C++
standard. There's that "little" think called *programming* that seems to
escape "language lawyers" quite regularly. You should have said "STL
approach" instead of "C++ approach".

is it requires some form of generics
(templates) and the benefit is performance. While removing indirect
function calls only contributes a small performance gain, the ability
to optimise away those calls can make significant performance gains.

And, "of course", since Lamborghini's are available, SUVs are irrelevant.

http://www.lamborghinihouston.com/
http://automobiles.honda.com/cr-v/price.aspx

 

[Jon]

No, a virtual base class is one that can be inherited more than once
without duplication of members.
You are talking about an abstract base class.

At 2 levels: The language implementation level (very hard/complex) and
the language usage level (inelegant/kludgy).

No it doesn't because you are inheriting from abstract base classes.
The problems with multiple inheritance manifest themselves when you
inherit from multiple concrete classes - hence the need for virtual
base classes.

Virtual derivation from C++ ABCs is still required when faced with "the
diamond of death" (at least with VC++ I know that it does).

 

[Jon]

You would use a *pointer* to an abstract base class, just as we're
using pointers here in C.

Yes, the polymorphic behavior (passing a derived class to something
specifying a base class) in C++ is via pointers and references.

 

[Jon]

Yes, because there is an extra level of indirection. When a method is
called on a pointer to an abstract base class, the vtable is retrieved
from the address point of the object, and then the derived class
method pointer is retrieved from the vtable.


Yes, for the same reason. In addition, there is some overhead in
constructing objects with virtual functions because the vtable needs
to be set up.

You are assuming the obvious simplistic implementation (like the one
presented in "The C++ Object Model"). I wouldn't be surprised to find
"zero overhead" implementation in certain scenarios. Anyway, my point is
that there are a number of ways to implement OO and C++ does not specify
*how* to do it, only that the resultant behavior be as specified.

 

[Jon]

Le 01/11/10 12:46, MartinBroadhurst a écrit :

That is exactly what I do:

For instance to call the generic function "newIterator":

Iterator *newIterator(GenericContainer *gen)
{
return gen->VTable->newIterator(gen);
}

I call the vtable of the object. Since the vtables of all
containers contain the function "newIterator" at the same position,
this works.

I do it with ONE indirection, and not two, as you can see.

OK, then if I am at the same level of C++ it is OK.

Don't kid yourself. I don't think you'd be likely to find any commercial
compiler that implements C++ OO characteristics like a college student in
course called OO 101 would implement it. Basically though, if you are
working at the language level (rather than the implementation level) in
C, the *best* you can achieve is to *approach* that OO 101 thing. What
your comparison should be against is "zero overhead" and not some toy
implementation of OO, because I think that *is* achieved in some
instances in commercial C++ compilers (not always, but for certain
constructs in certain cases).

What is relly nice when working in C is the absolute freedom to do as
you want. In this case, not having ANY object oriented framework is a
bonus in some ways since you can lay out your object as you want.

Of course though, what you end up with, no matter how clever your C
language-level OO implementation, is still just a hack.

 

[Jon]

If you want to know how C++ abstract base classes are actually laid
out in memory, get hold of the Windows SDK and look in the Include
directory for a header file that has a corresponding .idl file with
the same name, say oledb.h. Search the file for the string "C style
interface". What you will see is a vtable, and a C struct containing
it, that have been laid out to be identical to a C++ abstract base
class. This is provided so that C programmers can write COM
components.

There is also an article about COM programming in C on MSDN that I
found quite informative here:

http://msdn.microsoft.com/en-us/library/ms809982.aspx

MS COM objects != C++ objects! MS had to invent COM because it was
concerned with cross-language OO. COM is at a much higher level than
language implementation. Apples and oranges.

 

[jacob navia]

Le 06/11/10 05:56, Jon a écrit :

You are assuming the obvious simplistic implementation (like the one
presented in "The C++ Object Model"). I wouldn't be surprised to find
"zero overhead" implementation in certain scenarios. Anyway, my point is
that there are a number of ways to implement OO and C++ does not specify
*how* to do it, only that the resultant behavior be as specified.

C compilers can optimize this constructs too, and end up with a zero
overhead implementation. That is why is important that it be standardized.

 

[jacob navia]

Le 06/11/10 06:11, Jon a écrit :

Don't kid yourself. I don't think you'd be likely to find any commercial
compiler that implements C++ OO characteristics like a college student in
course called OO 101 would implement it. Basically though, if you are
working at the language level (rather than the implementation level) in
C, the *best* you can achieve is to *approach* that OO 101 thing. What
your comparison should be against is "zero overhead" and not some toy
implementation of OO, because I think that *is* achieved in some
instances in commercial C++ compilers (not always, but for certain
constructs in certain cases).

That will be the case for C compilers too if these propositions are
standardized. They can also optimize away the indirections since all
those procedures are open for a given implementation.

When writing the sample implementation hoewever, that should compile in
ALL compilers (include C90 onees) without ANY implementation hack, it is
impossible to use inline or macros, as you propose elsewhere.

Of course though, what you end up with, no matter how clever your C
language-level OO implementation, is still just a hack.

I am not implementing any OO language. It is an OO based design, but it
requires no language changes whatsoever.

The interfaces that I propose are very similar to the "protocols" of
objective C.

 

[Jon]

Le 06/11/10 06:11, Jon a écrit :

That will be the case for C compilers too if these propositions are
standardized. They can also optimize away the indirections since all
those procedures are open for a given implementation.

Wouldn't it be quite "demeaning" for the comittee to standardize
*decidedly* implementation-level things in some kind of clever hack? "C
the *clever* language"? It sounds like modifying that old junker car and
taking it to the dragstrip to have fun with because it's not the daily
driver and it doesn't matter. There really is no way to start
standardizing clever hacks without changing the face and identity of C.
There really isn't. It's fine to do things like that outside of the
standard but I really don't see C morphing to that kind of new
exististence and giving up its place as a real programming language. It
has to stay "as it is" because it *is* what it is. Mechanisms can't be
introduced at the library level without it being a "fork" of C prior to
the hypothetical introduction. Mechanisms and libraries are orthogonal.
Your proposal would constitue a fork of C, not a continuation or
evolution of it. You'd have a better, though still not likely, idea by
trying to introduce the mechanisms which your library hints at than
trying to introduce something that does not fit the definition of "C
library". Do you understand the difference between "library" and
implementation-level mechanism and are you able to categorize
appropriately (seemingly not)?

I am not implementing any OO language. It is an OO based design, but
it requires no language changes whatsoever.

The interfaces that I propose are very similar to the "protocols" of
objective C.

"Good luck" trying to fork C.

 

[Jon]

Le 06/11/10 05:56, Jon a écrit :


C compilers can optimize this constructs too, and end up with a zero
overhead implementation. That is why is important that it be
standardized.

That would be working backwards though. If you constrain your
language-design space to be that with which you can implement with the
high level language that exists, well, you *constrain* inappropriately
and the implications for the implementation (*compiler*) level are
severe. Step 1 is getting the go ahead. Step 2 is getting the right
semantics/syntax (or deciding whether anything elegant can even be had
given all of the issues or maybe that was in Step 1), cognizant of what
can be had given *implementation-level* (not current-high-level-language)
constraints.

I think you need to back up and ask "what X would it take at the compiler
level to enable Y?" (assuming Y is indeed wanted and approved) and
champion that thing rather than a specific thing that would be built upon
it. Once that X is "in there" (and it may just be "in there" in academia
or research compilers or prototypes for quite some time before X becomes
"standard" fare in mainstream compilers), comes investigation into the
use of X and the things built on top of X. Time passes then and X evolves
as to the things like Y that are built on top of X. After "proven in the
field" (probably more years of time) and acceptance by a very significant
population of the user group, *then* talk of standardization of Y, given
the industry rally around those Y's "left standing", may commence.

Now you know why I have chosen to develop my own language. It's much
easier. (And the result isn't kludgy).