Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Engineering a list container. Part 1.

Reply
Thread Tools

Engineering a list container. Part 1.

 
 
jacob navia
Guest
Posts: n/a
 
      12-09-2013
Le 09/12/2013 12:17, BartC a écrit :
> "jacob navia" <(E-Mail Removed)> wrote in message
> news:l832pm$63l$(E-Mail Removed)...
>
>> It is actually very simple.
>>
>> http://code.google.com/p/ccl/

>
> I've looked at the PDF, and one word I wouldn't use to describe it is
> simple! (Comprehensive, perhaps.)
>
> Its 370 dense pages are 100 more than K&R 2 which describes the entire
> language.
>


If you look at any book about the STL it is much thicker. Obviously
writing detailed documentation for each function is not a strength
of the package in your opinion.

In those 370 "dense" pages there is a lot of repetitions to facilitate
reading, a lot of diagrams, a rationale, and comparisons with other
languages like Java, C# and C++.

And if K&R 2 is 270 pages, the language standard is 683 pages.
 
Reply With Quote
 
 
 
 
Malcolm McLean
Guest
Posts: n/a
 
      12-09-2013
On Monday, December 9, 2013 12:58:12 PM UTC, jacob navia wrote:
> Le 09/12/2013 12:17, BartC a �crit :
>
> > I've looked at the PDF, and one word I wouldn't use to describe it is
> > simple! (Comprehensive, perhaps.)

>
> If you look at any book about the STL it is much thicker. Obviously
> writing detailed documentation for each function is not a strength
> of the package in your opinion.
>

It's obviously not acceptable for someone to need to read 370 pages before
they can use the package.
You need two layers of documentation. In layer one, an overview of the scope
of the package, what it can do, and it's also convenient though sometimes a
bit embarrassing to point out what it cannot do. (Nothing wastes time so
much as looking for the "serialise" method when there isn't one). You also
need to tell the user how to achieve common tasks, eg set up a list, iterate
through it, add and delete items, get its length, destroy it, usually with
source code. He should be able to glance at the docs, and within a minute or
so have a functioning linked list.
In layer two, you need the 370 pages of detail. For instance what's meant to
happen if you add or delete elements from a list whilst iterating through it?
There's no good, obvious, or simple answer to that. In fact you increment an
edit counter field. So is the field reset to zero if we take a copy of the list? It's unlikely that many people will want to know the answer to that
question, but for someone it's going to be vital. So that needs to be buried
away somewhere.
 
Reply With Quote
 
 
 
 
Andrew Cooper
Guest
Posts: n/a
 
      12-09-2013
On 09/12/2013 01:42, Ben Bacarisse wrote:
> jacob navia <(E-Mail Removed)> writes:
>
>> Le 08/12/2013 22:02, Johann Klammer a écrit :
>>> Did you look at the linked lists inside linux(include/linux/list.h...
>>> types.h... struct list_head)? AFAIK they use a header structure, that
>>> gets included in structures that want to use it. Then there's usually
>>> some pointer arithmetics(usually things involving offsetof) to get from
>>> the header pointer to the containing struct and vice-versa. It has the
>>> advantage to be able have some struct in multiple lists (perhaps a rare
>>> use-case.. but sometimes..), by using several header vars..
>>> Any particular reason not to do it that way? I always thought, it was
>>> rather clever...

>>
>> Well, the idea of having a header in each element is too heavy
>> for the containers since it is of the order of:
>>
>> sizeof(elementHeader) * N
>>
>> In my case this is just
>>
>> sizeof(void *) * N // the "next item" pointer

>
> The Linux lists are doubly linked, so two pointers are needed. The
> overhead, though, is just that: two pointers plus any required padding.
> Using the same technique for singly linked lists would presumably have
> the same overhead as yours: one pointer plus any required padding.
>
> <snip>
>


A linux list_head is two pointers (plus whatever padding the compiler
deems is necessary - 0 for the common architectures)

In addition, you have an ability to turn an arbitrary structure into
linked list by embedding a list_head. You can put an arbitrary number
of list_heads into a structure, and have the structure in an arbitrary
number of independent lists.

The standard iteration tools will issue hardware preload instructions
for the subsequent entries as you walk the list, meaning fewer cache misses.

Judging from the presented code, the entire Linux implementation is
substantially smaller, and involves no function pointers.


The proposal presented here is desperately trying to be C++, and is
completely over engineered for the problem it is trying to solve; It is
not like lists are hard.

It seems silly to be concerned about an extra pointer in the structure,
with a vtable that large for each type of list.

~Andrew
 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      12-10-2013
"Andrew Cooper" <root@127.0.0.1> wrote in message
news:vgspu.10410$(E-Mail Removed)4...

> The proposal presented here is desperately trying to be C++, and is
> completely over engineered for the problem it is trying to solve; It is
> not like lists are hard.


The idea of using a common set of functions to work with linked lists is
good - if you do just want a simple linked list.

However, I use linked lists a lot, and they are rarely simple! For example,
one struct I had I think was linked seven different ways to other structs
(mostly sideways, some up and down to form a tree).

The point is, my data structures, as many as I needed, were superimposed on
the struct, rather than the struct being shoe-horned into a (single) data
structure, which is less flexible.

I'd imagine it would also be awkward to point into the middle of a list, or
somehow share the same data with several list headers. And if I wanted to
insert a pointer to a list into a struct, it's no longer a pointer to the
first element, but a pointer to a formal header, which then points to the
data. It's just extra stuff to be aware of and which can complicate matters
rather than simplify them.

But, maybe it's a mistake to try and adapt existing code to use these
containers...

> It seems silly to be concerned about an extra pointer in the structure,
> with a vtable that large for each type of list.


There is just one instance of the vtable (for all singly-linked lists). And
one list-header for each entire list. But any extra fields per-element can
have a much bigger impact.

--
Bartc

 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-10-2013
Le 10/12/2013 00:22, Andrew Cooper a écrit :
>
> A linux list_head is two pointers (plus whatever padding the compiler
> deems is necessary - 0 for the common architectures)
>


The same in the ccl.


> In addition, you have an ability to turn an arbitrary structure into
> linked list by embedding a list_head. You can put an arbitrary number
> of list_heads into a structure, and have the structure in an arbitrary
> number of independent lists.
>


You can store any data type into an arbitrary number of lists with the
ccl too.


> The standard iteration tools will issue hardware preload instructions
> for the subsequent entries as you walk the list, meaning fewer cache misses.
>


That is an implementation detail easily done in an architecture where
that is relevant. The code presented in the ccl is generic for *ANY*
architecture.

> Judging from the presented code, the entire Linux implementation is
> substantially smaller, and involves no function pointers.
>


The linux implementation is not the ccl, it is a kernel list
implementation that has only lists.


If you write code with the ccl, you can easily change your container
from a list to a flexible array just by changing a few lines. You
can do it if you measure that lists are taking too much CPU time.

I do not see how you would do that in a container that is isolated from
the others!

>
> The proposal presented here is desperately trying to be C++, and is
> completely over engineered for the problem it is trying to solve; It is
> not like lists are hard.
>


No, it is not C++ even if I use some of the concepts of object oriented
programming. And mocking about it by saying "desperatly" doesn't really
convey any argument. By the way I am not "against" C++. I consider the
language as a whole a huge mistake, but there are good ideas within it.


> It seems silly to be concerned about an extra pointer in the structure,
> with a vtable that large for each type of list.
>


The vtable is shared by ALL lists. The elements do not have any pointer
to the vtable, only the list head.

And yes, lists are easy, that is why I presented them FIRST.

Next are the flexible arrays.


 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      12-10-2013
On Tuesday, December 10, 2013 10:38:55 AM UTC, Bart wrote:
> "Andrew Cooper" <root@127.0.0.1> wrote in message
>
> However, I use linked lists a lot, and they are rarely simple! For example,
> one struct I had I think was linked seven different ways to other structs
> (mostly sideways, some up and down to form a tree).
>

That's often a problem with a library that "sits over you" rather than "sits
under you". By "sits over you", I mean provides structures that you plug
the subroutines and data items into, rather than calling with your data
items. It works fine, until you need two libraries that "sit over you".

Then they start interfering. Both want to control your main loop, both
want to deallocate your structures when they die, both want to insert a
special field at the head of the structure.
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      12-10-2013
Andrew Cooper wrote:
>
> Judging from the presented code, the entire Linux implementation is
> substantially smaller, and involves no function pointers.


But it is just a list.

> The proposal presented here is desperately trying to be C++, and is
> completely over engineered for the problem it is trying to solve; It is
> not like lists are hard.


It isn't trying to be C++, it is striving to provide a subset of the C++
standard library in C. Making a small list is trivial, making a
collection of interchangeable containers isn't.

Lists are widely used in C because they are so simple. In C++, vector
(flexible array) is more common. It is more complex to implement, but
in most use cases it offers better performance. Having a standardised
collection of containers saves an awful lot of wheel reinventing. Being
able to quickly swap between them when requirements or the environment
changes is a big bonus.

--
Ian Collins
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-11-2013
Le 11/12/2013 20:09, http://www.velocityreviews.com/forums/(E-Mail Removed) a écrit :
> Anything particularly wrong with CoreFoundation?
>
> http://en.wikipedia.org/wiki/Core_Foundation
>


Yes.

1) The Apple license. The CCL is in the public domain, it has
in fact no restrictions of any kind, and no, it is free, not GNU
so the FSF has nothing to say either.

2)
<quote>
Core Foundation is a library with a set of programming interfaces
conceptually derived from the Objective-C-based Foundation framework but
implemented in the C language. To do this, Core Foundation implements a
limited object model in C. Core Foundation defines opaque types that
encapsulate data and functions, hereafter referred to as “objects.”
<end quote>

This makes very strong assumptions about the objects being stored.
Basically the core foundation is just objective C "compiled" to C.

The CCL should be able to run in very limited memory setups, and be
portable to any machine. As far as I know the Core Foundation has been
only ported to windows, not to linux.

That said, many specifications of the ccl (for instance the observer
interface) have been influenced by the work of Apple's engineers.


 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-19-2013
Le 19/12/2013 07:36, Gareth Owen a écrit :
> jacob navia <(E-Mail Removed)> writes:
>
>> If you look at any book about the STL it is much thicker. Obviously
>> writing detailed documentation for each function is not a strength
>> of the package in your opinion.

>
> The STL container section of the C++ standard is around 100 pages.
> Granted, its terse standardese, and almost entirely free of diagrams,
> comparisons, examples etc.
>


Yes, I will write a shorter documentation, in 100 pages or so.

> But the real saving is that the error handling (i.e. the interaction
> between destructors and exceptions) is part of the language, not part of
> the library.
>


It can be "savings" if you want the bloated code that this produces.
Granted, it is the compiler that writes that, but it does take
space.


 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      12-19-2013
Le 19/12/2013 18:14, Gareth Owen a écrit :
> jacob navia <(E-Mail Removed)> writes:
>
>>> But the real saving is that the error handling (i.e. the interaction
>>> between destructors and exceptions) is part of the language, not part of
>>> the library.

>>
>> It can be "savings" if you want the bloated code that this produces.

>
> [citation needed]
>


Exception handling has a long history in C++.

The first solutions were just a glorified longjmp that the compiler
inlined at each entry of a protected block.

This solutions is now obsolete but still used in some systems like
gcc under windows. Since each protected block needs to establish a
context (the setjmp call) you pay even if there is no exception.

The solution that evolved later is a table approach.

You build tables relating code points to stack descriptions, so that
the run time can call a bye code machine that interprets the tables
to unwind the stack searching for an exception. Lcc-win generates
this tables to be compatible with C++, and I can tell you those
tables are HUGE since each function entry/exit needs a lot of
descriptions for each instruction being emitted.

There isn't a big literature on this subject since only Microsoft
has really documented this stuff in a meaningful way. Gcc refers
always to the DWARF specifications where a documentation exists
but gcc doesn't follow their own specs for unknown reasons. So,
you have just to fgure out what gcc generates and then do the same.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
A container library in C Part 4. The arraylist container jacob navia C Programming 10 10-01-2009 02:26 PM
A container library in C: Part 3. List container implementation jacob navia C Programming 5 09-28-2009 08:19 PM
Call for Papers: World Congress on Engineering WCE 2007 (IAENG conferences with Engineering Letters) imecs__2007@iaeng.org Java 0 12-19-2006 06:51 AM
CFP: Special Issue on Web Engineering (The journal Engineering Letters) imecs_2006@iaeng.org Java 0 01-07-2006 04:48 AM
std::container::iterator vs std::container::pointer Vivi Orunitia C++ 11 02-04-2004 08:09 AM



Advertisments