A container library for the C language

[jacob navia]

Richard Kettlewell a écrit :

10-12k on a couple of Unix platforms I tried.

Yes, because the STL is linked dynamically.
Just do an ldd and see how much the size of
THOSE .so are!

I can make my program 4K if I put the library in a DLL
or a shared object!

 

[Ian Collins]

It has. That building more upon the template system has happened doesn't
mean that alternatives have not been suppressed.

Now are are being obtuse. This discussion is about container libraries,
not language features.

And just surely partly and maybe completely BECAUSE of C++.

Maybe, but C was around for a very long time before before C++ appeared.
It was more likely a case of the right person (Alexander Stepanov) in
the right place at the right time.

It does not. But let's say you are corect: then it necessarily constrains
the solution space for that which is not large-scale development.

A standard library that is only useful for toy projects would be doomed,
as would one which is only appropriate for large scale projects.

 

[Ike Naar]

#include <iostream>
#include <list>
using namespace std;

// Simple example uses type int

int main(void)
{
list<int> L;
L.push_back(0); // Insert a new element at the end
L.push_front(0); // Insert a new element at the beginning
L.insert(++L.begin(),2); // Insert "2" before position of first
// argument
// (Place before second argument)
L.push_back(5);
L.push_back(6);

list<int>::iterator i;

for(i=L.begin(); i != L.end(); ++i) cout << *i << " ";
cout << endl;
return 0;
}

Executable size: 153 008 bytes (windows vista, MSVC 2008 -Ox)

38864 bytes (x86/OpenBSD/g++)
8960 bytes (sparc/Solaris/SunC++)
1852 bytes (alpha/NetBSD/g++)

 

[Ian Collins]

Richard Kettlewell a écrit :

Yes, because the STL is linked dynamically.
Just do an ldd and see how much the size of
THOSE .so are!

I can make my program 4K if I put the library in a DLL
or a shared object!

These size arguments are pointless (unless the difference is extreme).
On a hosted platform, the shared are libraries are just that, shared by
all applications and on embedded systems the linker will only pull in
the functions or objects required by the application.

 

[jacob navia]

Ike Naar a écrit :

38864 bytes (x86/OpenBSD/g++)
8960 bytes (sparc/Solaris/SunC++)
1852 bytes (alpha/NetBSD/g++)

The C++ library is dynamically linked. Just do
ldd <executable name>
and then see the size of the .so.

 

[Ike Naar]

Ike Naar a écrit :

The C++ library is dynamically linked. Just do
ldd <executable name>
and then see the size of the .so.

But then, the C++ library is shared by many users,
so it's size does not really matter.

 

[jacob navia]

Ike Naar a écrit :

But then, the C++ library is shared by many users,
so it's size does not really matter.

Of course it matters. It adds to the total footprint of your
program in RAM.

Sure, with today's machines it is not a VERY important parameter,
but it affects the speed of your program since all that code must be
loaded from RAM into the processor caches.

 

[Moi]

I have been talking about this since quite a long time. It is (maybe)
time to offer the first release.

The URL is:
http://www.cs.virginia.edu/~lcc-win32/container.html

I did not check the specifications, but spent a few minutes browsing the source.
(BTW in unix the code did not link because you omitted -Lm )

IMHO the semantics of your bitstrings are strange.
I would expect the logical AND of two bitstrings of unequal length, that the shorter one
would be extended with '0' bits, not with '1' bits.
011 & 1101101 -->> 010
(if left adjusted or 001 if right ajusted)
, but no more than two '1'bits could *ever* be in the result, because the left operand
only has two '1' bits.

(Similar for logical or)

For the rest: I don't intend to use your container library. I have code for most of the stuff
you present which fits better into my projects and my style of coding. No offense.

Also: for the trivial stuff, most of your code seems useable. (but most of us have
reinvented the trivial stuff several times)
For the nontrivial applications, it is nearly useless, IMO.
For example: consider the case of a LRU chain with a built-in hashtable: this will
have to be handmade, at least to get enough data-density / locality-of reference.
Combining a hashtable container with a doubly linked list container is just not
good enough.

IMO, YMMV,
AvK

 

[robertwessel2]

Sebastian a crit :







I *could* have done a similar thing with macros, but it would
have been very cumbersome and would clutter the interface.

I repeat. The whole list module (single linked) is about 4900 bytes.
Since you have the source you can trim down the functions you do not use,
but I think an overhead of 5K is not that significant.

Yes, C++ *can* be efficient but in practice I wouild be surprised
if a program using the STL would be as efficient (space-wise) as C.

Just to give you an example. This program:
// Standard Template Library example

#include <iostream>
#include <list>
using namespace std;

// Simple example uses type int

int main(void)
{
    list<int> L;
    L.push_back(0);              // Insert a new element at the end
    L.push_front(0);             // Insert a new element at the beginning
    L.insert(++L.begin(),2);     // Insert "2" before position of first argument
                                 // (Place before second argument)
    L.push_back(5);
    L.push_back(6);

    list<int>::iterator i;

    for(i=L.begin(); i != L.end(); ++i) cout << *i << " ";
    cout << endl;
    return 0;

}

Executable size: 153 008 bytes (windows vista, MSVC 2008 -Ox)

A similar program using the container library takes 37 920 bytes

You're *not* comparing similar programs. The iostream library almost
always has a fair sized footprint. Changing the code to use stdio
instead halves the size of the executable (I'm running a different
version of MSVC, so it's not directly comparable, but 135kb to 68kb).
The C version of the code you present below doesn't appear to even use
stdio (and eliminating that drops the executable to 57kb).

 

[Ian Collins]

Ike Naar a écrit :

Of course it matters. It adds to the total footprint of your
program in RAM.

Sure, with today's machines it is not a VERY important parameter,
but it affects the speed of your program since all that code must be
loaded from RAM into the processor caches.

Only the parts that are used. As I said in another post, unless the
difference is extreme, code size is a red herring.

 

[jacob navia]

(e-mail address removed) a écrit :

You're *not* comparing similar programs. The iostream library almost
always has a fair sized footprint. Changing the code to use stdio
instead halves the size of the executable (I'm running a different
version of MSVC, so it's not directly comparable, but 135kb to 68kb).
The C version of the code you present below doesn't appear to even use
stdio (and eliminating that drops the executable to 57kb).

True, I did not notice that. I just commented the iostream functions and
the code dropped to 58K

I used -Ox, and I hope that it didn't just drop the whole program...
The iostream functions were there to avoid that...

Look, I guess that to have a real example we have to write real code
I wqill do that as time permits. Until then, I will refrain from
stupid comparisons.

Thanks for your contribution.

 

[Keith Thompson]

On 06/30/10 11:44 PM, Malcolm McLean wrote: [...]

A "list" is an ordered series of data items.

No in C++ terms, list is unordered.

Um, are you sure about that?

 

[Ian Collins]

On 06/30/10 11:44 PM, Malcolm McLean wrote: [...]

A "list" is an ordered series of data items.

No in C++ terms, list is unordered.

Um, are you sure about that?

OK, as doubly lined lists, they are ordered (I was reading sorted!).

 

[Ed]

Now are are being obtuse. This discussion is about container
libraries, not language features.

They are intextricably related. You either have language support or you
have kludgy library implementations.

Maybe, but C was around for a very long time before before C++
appeared. It was more likely a case of the right person (Alexander
Stepanov) in the right place at the right time.


A standard library that is only useful for toy projects would be
doomed, as would one which is only appropriate for large scale
projects.

Oh, I see now: there are only large-scale projects and toy ones. Thanks
for the heads-up on that.

 

[Nick Keighley]

we're beginning to repeat our entrenched positions so I'll taper this
off. (Not to mention the fact that we're discussing the design of C++
in comp.lang.c...)

Nice try, but no, not hardly.

so which particular user community is the STL unsuited to? I think you
just don't like standards. Maybe that's why you don't like Jacob's
approach...

Programming Languages as an end instead of a means.

PLs are a useful (indespensible tool) and like any tool I'm interested
in it for what i can do. I use the STL because it's useful not because
I'm some sort of language collector.

It's probably the worst offender in the package. It is THE main "lock my
code into C++" element of C++ or pretty darn close.

sorry? I've heard of portability; but you expect your programs to be
portable *between* programming alnguages?! This "lock in" of which you
speak, might it just be that STL provides something that other
languages don't? Again, what is exactly wrong with std::string or
std::vector? All I'm seeing is a vague prejudice.

It can be, but not hardly for everyone nor all the time. Much of C++
focuses on large-scale development and you don't get in one area without
sacrificing in another (you can build an engine for low RPM torque or
high RPM horsepower, but it's a tradeoff). Parameterization is not a
panacea.

I've used the STL on small (and large) projects I don't see this RPM
stuff you're talking about

<snip>

 

[Nick Keighley]

Jacob, he's trolling you. He is not even remotely interested in C, as he
has made abundantly clear on several occasions, and he's just shooting
his mouth off to see how you react.

he got me to bite as well. Jacob and I have now both used the
prejudice word. I'd noticed that although he replied he never did
anything but reiterate a few canned phrases. He seems to claim to
belong to some guild of "container developers" who develop containers
unconstrained by the limitations of any real programmign language.

The League of Container Developers are feared and respected throughout
the programming world.

 

[Malcolm McLean]

OK, as doubly lined lists, they are ordered (I was reading sorted!).

A "list" means

1: Fred
2: Jim
3: Bert
4: Harry
5: Fred

95% or so of your data will be lists. Whether they are stored as
arrays, linked lists, or in more exotic structures is an implentation
detail. Huge numbers of functions inherently operate on lists.

 

[Nick Keighley]

Templates as glorified macros (or an ancillary program to generate from
them) are still basically the same thing.

as someone on comp.lang.schem once said

"

Callbacks are a form of continuation.

Yes, in the same sense that a shoe is a form of aircraft carrier.
"

which is pretty much the relationship between templates and C macros

 

[ld]

ld a écrit :


This reference applies to Objective C "subclassing" or "method swizzling",
as you name it. In Objective C we have a full fledged class hierarchy,

This is not the important point. Most hierarchies in ObjC are flat
because ObjC is dynamic. Therefore, unless there is some shared
implementation (e.g. NSObject), you fall back to your case.

what in C doesn't happen at all. The container library doesn't use
any class hierarchy and all containers are at the same level.

But your approach uses static typing to reach the interface methods,
which is the same situation as using "super" in ObjC: super doesn't
dispatch.

This is quite a difference, since the problems arise when you do
this "swizzling" within a class hierarchy.

again, the hierarchy is not important. What is important, is that you
break the contract between the interface and the implementation.

Since here there isn't
any, the work around proposed in that reference (calling "super")
doesn't apply either.

it does.

a+, ld.

 

[Seebs]

Ike Naar a écrit :

Of course it matters. It adds to the total footprint of your
program in RAM.

So what?

Sure, with today's machines it is not a VERY important parameter,
but it affects the speed of your program since all that code must be
loaded from RAM into the processor caches.

Shared libraries are typically already loaded. (I point out the BSD/OS
implementation, in which shared libraries could be statically linked to
reduce costs even further...)

-s