Web site for the containers library

[ImpalerCore]

On 9/01/2011 23:31, jacob navia wrote:

Secondly, is there any method for serialisation in your library? I
certainly could have used one in the past
The documentation mentions Save and Load operations can be performed on
containers, but these take a FILE* as argument and so are useless if you
want to send data over the network[1], for instance, unless your OS
happens to have methods to address a block of memory through a FILE*.
It would be nice if serialisation just wrote to memory, and you
implemented Save/Load based on those serialisation/de-serialisation methods.

I imagine that one could implement a scenario like that using a
container 'foreach' function (I think Jacob's version is 'Apply').

Consider the following 'foreach' function type and an example
container that calls it.

typedef void (*foreach_function)( void* p, void* u );
void array_foreach( struct array* ar, foreach_function fn, void*
user_data );

Consider that 'array_foreach' visits each element (iter = 0->N-1) in
the array calling (*fn)( ar[iter], user_data ). One can pass a
container as 'user_data', and 'fn' would be responsible for both
converting the array element 'ar[iter]' into a string and then
inserting it into the container masquerading under 'user_data'. That
would convert an array of elements into their serialized versions
(let's just say that they're strings). Then one could have another
'foreach' function that visits a container of serialized strings
sending each string over the network to some destination ('user_data'
in that case could contain network destination information like ip
address/port). I think it's feasible, but one example would go a long
way. I think the tricky part is how do you communicate and handle
errors using a 'foreach' mechanism if you need to be concerned about
them (my answer is not to use 'foreach' in those scenarios). And it's
kind of fragile to programmer errors with all the 'void*' pointers
floating around.

Thirdly, what advantage does this project have to just using C++? Do you
really think eventually systems will exist where your library is
present, but a C++ compiler isn't? Yes, I don't like the STL either, but
it does the job and, anyway, there are alternatives[2].

Absent of language restrictions, you'd definitely get better bang for
your buck in the short term investing in learning the STL. However,
some projects do have arbitrarily defined language restrictions; and
other times programmers choose to invest in their own language related
preferences.

Best regards,
John D.

 

[jacob navia]

Le 10/01/11 18:27, Ben Pfaff a écrit :

But in many cases the change of container demands other changes
anyhow. For example, you mention switching from an array to a
hash table. An array doesn't call for a hash function or
(usually--I haven't looked at your container library) a
comparison function, but a hash table needs both. So there is
limited value in making it simple to change the container.

Both changes imply no change at all if you use the default functions.
The default hash function is tailored to character string keys, the
most often used case. The comparison function defaults to memcmp,
and if you are OK with that no change needs to be done.

Otherwise you add:
iDictionary.SetCompareFunction(hash_table,myCompareFunction);
and you are done.

 

[jacob navia]

Le 10/01/11 18:24, Frederik Van Bogaert a écrit :

It looks nice, but I do have a few comments ...

Firstly, any document that aims to set a standard should be impartial.
Rants against, say, a certain Microsoft representative who allegedly
sabotaged the C99 standardisation process do not belong there. It just
doesn't look professional.

Yeah, I gues you are right. I will erase that.

:-(

Secondly, is there any method for serialisation in your library? I
certainly could have used one in the past

Yes:

Save and Load.

The documentation mentions Save and Load operations can be performed on
containers, but these take a FILE* as argument and so are useless if you
want to send data over the network[1], for instance, unless your OS
happens to have methods to address a block of memory through a FILE*.
It would be nice if serialisation just wrote to memory, and you
implemented Save/Load based on those serialisation/de-serialisation
methods.

Mmm, that is a good idea. I would return
typedef struct tagBuffer {
size_t length;
char *data;
} Buffer;

SaveToBuffer would allocate (using the container's allocator)
and LoadFromBuffer would take one and return a container object.

Thanks, I will try to do that.

Thirdly, what advantage does this project have to just using C++?

A big one. This library doesn't NEED C++ at all. You save yourself
a world of complexity and questions about the flavor of vanilla
templates .

> Do you
really think eventually systems will exist where your library is
present, but a C++ compiler isn't?

Yes. All systems that use the C language ONLY. Not because there is
no C++ compiler but because they want to use a simpler language
with less pitfalls.

QT?

Well, it has good ideas (signals, for instance), but it needs a
preprocessor and has some problems in some platforms. For instance,
I am doing a lot of iphone programming and qt is not so good there,
since Nokia doesn't like the iphone, I wonder why

I use C99 and objective C in the iphone, and in the Mac also.

 

[Frederik Van Bogaert]

On 10/01/2011 21:46, jacob navia wrote:
[snip]

The documentation mentions Save and Load operations can be performed on
containers, but these take a FILE* as argument and so are useless if you
want to send data over the network[1], for instance, unless your OS
happens to have methods to address a block of memory through a FILE*.
It would be nice if serialisation just wrote to memory, and you
implemented Save/Load based on those serialisation/de-serialisation
methods.

Mmm, that is a good idea. I would return
typedef struct tagBuffer {
size_t length;
char *data;
} Buffer;

SaveToBuffer would allocate (using the container's allocator)
and LoadFromBuffer would take one and return a container object.

Thanks, I will try to do that.

No problem

Another question: if I save a container to file on one computer, and
then transfer it to one with different endianness, sizeof(int) etc, will
your library successfully load the file into memory? The reason I ask is
I happen to be writing a peer-to-peer file sharing system, and so I
*know* real serialization can be quite hard to do ...

A big one. This library doesn't NEED C++ at all. You save yourself
a world of complexity and questions about the flavor of vanilla
templates .



Yes. All systems that use the C language ONLY. Not because there is
no C++ compiler but because they want to use a simpler language
with less pitfalls.

QT?

Well, it has good ideas (signals, for instance), but it needs a
preprocessor and has some problems in some platforms. For instance,
I am doing a lot of iphone programming and qt is not so good there,
since Nokia doesn't like the iphone, I wonder why

I use C99 and objective C in the iphone, and in the Mac also.

Hmm, yes, that was out of line. There are indeed many situations where
C++ simply isn't an option.

Mes excuses et bonne chance avec ce procédure de standardisation, je
suis sûr que cela n'est pas facile

Frederik

 

[Charles]

You're talking about one type of software, probably bespoke business
systems.

No, not really, though I tend to think of those kinds of projects when
someone brings up requirements and design changes being handed down
rather than some kind of personal or ad-hoc case.

Games programming doesn't work like that, nor does scientific
programming.

Those are highly specialized areas where all the stops are pulled out. A
lot of "scientific programming" isn't done by developers, but rather by
scientists (not of the computer kind). I have spent more time than I care
to remember trying to decipher a 100 (?) thousand lines of Fortan code
created by a few generations of individual scientists. I can't say
anything about game programming, but I have a feeling that commercially
it is much more controlled and honed than the guy in the basement on his
Linux box creating next week's Lan party game edition he and his friends
will be engaged in. Marketing->Creatives->Technical Designers and
Developers.

My current programming is highly exploratory, for
instance. I have datasets and I run scripts over them to see if
there's anything interesting that other people have missed. If there
is, I download more data and slightly modify the scripts, the results
suggesting new analyses. Of course I've also got to keep up with the
experimental side of things as well. Flexibility to write programs
quickly and easily, modifying the code and data in unforeseen ways, is
very valuable to me.

Containers just aren't that interchangeable. Any attempt to unify them
along those lines is an exercise in futility, IMO. At best, a severe
compromise. Tell ya what, why don't you Jacob and Ian get together and do
all the container interchangeability analysis across those 3 domains
(business database apps, games, scientific) and then simply write down an
example scenario from each domain and each interchangeable container
pair. Heck, that could then go on the back of the shrink-wrapped box.
You'll all be gazillionaires! (Sorry, sarcasm again).

Really though, no need to just talk about it in contrived ways, write
down the examples so everyone can see how important and useful it really
is. I mean in comparison to thinking about the problem longer and
choosing containers wisely (that's really what you all are arguing
against); Or even, "god forbid", doing some design (with pen and paper or
something, but not that oxymoronic "designing with source code"!) before
coding.

 

[Ian Collins]

No, you see, just because you and Ian don't know how to run projects,
manage clients, extract and analyze requirements and design software does
not mean that other people don't know how to.

I have been doing all of the above successfully for a very long time.
Unfortunately my clients have to interact with the real world of
changing market requirements.

 

[Charles]

I have been doing all of the above successfully for a very long time.
Unfortunately my clients have to interact with the real world of
changing market requirements.

Oh hush. You were trying to make a case for high-level requirements
changes affecting the very low-level of the implementation. I don't have
to reiterate how silly that sounds. Get your process under control is all
I have to say to you.

 

[Charles]

Le 10/01/11 07:52, Tim Harig a écrit :

In Charles' world, requirements never change, everything is known
on advance, etc.

This is the type of person pontificating (it is very cheap) without
any REAL world experience.

Nice try at "turning the tables" little boy. You always get this way when
someone calls you on your bullshit.

 

[Malcolm McLean]

I have been doing all of the above successfully for a very long time.
Unfortunately my clients have to interact with the real world of
changing market requirements.

The other problem is that programmers appear to be able to make
changes at whim to programs - altering the attack patterns of the
space invaders, for example. So naturally non-programmers start asking
for changes. However the ease of the change is very dependent on the
precise characteristics of the change being asked - speeding up the
space invaders might be trivial if their position is controlled by
reals, it might have all sorts of implications if their position
stored by integers and they move at one pixel per frame.

Often you need to see the reality before requesting the change. It
might not be obvious before the program is written that space invaders
all travelling at exactly the same speed creates a disturbing visual
effect, for instance.

If the non-programmer controls the programmers' salary, naturally the
programmers are anxious to please him, and don't refuse the
instructions unless they are clearly impossible. So flexibility is a
great boon.

 

[Tim Harig]

Nice try at "turning the tables" little boy. You always get this way when
someone calls you on your bullshit.

Don't feed the troll.

 

[Marcin Grzegorczyk]

Le 10/01/11 09:51, copx a écrit :

[...] I always wanted to try Judy arrays for
example:
http://en.wikipedia.org/wiki/Judy_array

Well, the problem is:

<quote>
Judy was invented at HP's UNIX Software Enablement Laboratory at Fort
Collins Colorado. Hewlett-Packard has patents pending on the Judy
Technology.
<end quote>

I do not want to have HP's lawyers knocking at my door.
Besides that, it is really a good technology.

http://sourceforge.net/projects/judy/develop

That code is available under the LGPL.

LGPL won't help against a patent claim.

OTOH, that project is 8 years old now, so if HP hasn't shut it down yet,
I guess whatever patents they may have, they do not apply to that
implementation.

 

[Ian Collins]

Le 10/01/11 09:51, copx a écrit :
[...] I always wanted to try Judy arrays for
example:
http://en.wikipedia.org/wiki/Judy_array

Well, the problem is:

<quote>
Judy was invented at HP's UNIX Software Enablement Laboratory at Fort
Collins Colorado. Hewlett-Packard has patents pending on the Judy
Technology.
<end quote>

I do not want to have HP's lawyers knocking at my door.
Besides that, it is really a good technology.

http://sourceforge.net/projects/judy/develop

That code is available under the LGPL.

LGPL won't help against a patent claim.

OTOH, that project is 8 years old now, so if HP hasn't shut it down yet,
I guess whatever patents they may have, they do not apply to that
implementation.

See the first paragraph in

http://judy.sourceforge.net/downloads/10minutes.htm

 

[Marcin Grzegorczyk]

On 1/10/11 2:59 AM, jacob navia wrote:
Le 10/01/11 09:51, copx a écrit :
[...] I always wanted to try Judy arrays for
example:
http://en.wikipedia.org/wiki/Judy_array

Well, the problem is:

<quote>
Judy was invented at HP's UNIX Software Enablement Laboratory at Fort
Collins Colorado. Hewlett-Packard has patents pending on the Judy
Technology.
<end quote>

I do not want to have HP's lawyers knocking at my door.
Besides that, it is really a good technology.

http://sourceforge.net/projects/judy/develop

That code is available under the LGPL.

LGPL won't help against a patent claim.

OTOH, that project is 8 years old now, so if HP hasn't shut it down yet,
I guess whatever patents they may have, they do not apply to that
implementation.

See the first paragraph in

http://judy.sourceforge.net/downloads/10minutes.htm

Well, the inventor of an algorithm needn't be the owner of a patent on
that algorithm (and let's not forget algorithms can be independently
invented and patented). But yes, it is extremely improbable that he
would LGPL the code without HP's knowledge and consent (especially if
one notices that the HP's publication jacob navia quoted above pre-dates
the SourceForge project).

 

[Alan Curry]

Well, the inventor of an algorithm needn't be the owner of a patent on
that algorithm (and let's not forget algorithms can be independently
invented and patented). But yes, it is extremely improbable that he
would LGPL the code without HP's knowledge and consent (especially if
one notices that the HP's publication jacob navia quoted above pre-dates
the SourceForge project).

Only GPL3 contains an explicit promise not to sue over patents. LGPL is
insufficient. Don't think "they wouldn't do that to me". They wouldn't have
registered a patent without the intent to do it to somebody, and you're
somebody.

Stay away if you want to be safe.

 

[Charles]

Don't feed the troll.

He's not one. (Hmm... is he?). He actually might have some potential if
he'd pull his head out of his ass.

 

[Dag-Erling Smørgrav]

Oh hush. You were trying to make a case for high-level requirements
changes affecting the very low-level of the implementation. I don't have
to reiterate how silly that sounds. Get your process under control is all
I have to say to you.

You are not only an idiot, but an offensive one at that.

Requirements change over time. Programs change over time. For
instance, a client might request an additional feature, either halfway
through development or in a later update, which requires a data
structure to be sorted and / or searchable when it did not previously
need to be. The size of the input set might increase dramatically,
requiring a data structure which is well suited for small data sets (low
overhead but poor scalability) to be replaced with one which is better
suited for larger data sets (high overhead but better scalability). The
nature of the data set might change: some data structures are faster to
access but perform poorly when elements are inserted in order.

This is particularly true in scientific computing, which deals with
ever-increasing data sets and ever-changing requirements.

As a client or a manager, I would be extremely skeptical, to say the
least, of a developer who does not understand that "change happens".

DES

 

[s5n]

That's some "hearty" reasoning! Are you high? ;-)

i agree wholeheartedly with Jacob's point here. i can't count how
often i swap out underlying list/container implementations. In C++,
with the STL, this is trivial. In C it is normally a lot of work
unless one has gone through the trouble of setting up an interface-
based system which lets us swap out the implementations. As Jacob
wrote in another post, changing implementations is not as uncommon as
it sounds. i'm such a huge fan of implementation-based design in C
that i recently published an article on the topic:

http://www.wanderinghorse.net/computing/papers/#oo_c

 

[Nick]

It's a stepping stone. It's where all container library developers start
out. As experience increases with that design, its limitations and
"incorrectness" become clear.


It's not.


Inexperienced and/or unknowledgeable developers or those who won't or
can't analyze and design before jumping in and coding. I see no reason to
build a library in a fashion to support that. Indeed, it is GOOD for
someone to have more tedium when a design change is necessary because of
inadequate capability or preparation, for learning by making mistakes is
a powerful teaching process.

But sometimes designing and coding the final solution just isn't the
right way to do it. Take my website, which is entirely programmed by
me, in my spare time.

Over the 10 years it's been live, the data set has increased by an order
of magnitude, and the data has gone from being read from a static file
to loading from a database.

I did have dreams of the final version, but I'd still be programming it
with nothing to use if I'd set out to write it.

So starting off with the places in a linear list, which then became a
tree and is now a hash table - for example - was been the right design
and build methodology for this.

It, quite clearly, wouldn't be for something with a team of developers
and defined clients, but the world isn't like that (who is the "client"
for Google for example?).

I have very little time for people who push paradigms over pragmatism.

 

[Charles]

i agree wholeheartedly with Jacob's point here. i can't count how
often i swap out underlying list/container implementations. In C++,
with the STL, this is trivial. In C it is normally a lot of work
unless one has gone through the trouble of setting up an interface-
based system which lets us swap out the implementations. As Jacob
wrote in another post, changing implementations is not as uncommon as
it sounds. i'm such a huge fan of implementation-based design in C
that i recently published an article on the topic:

A lot of people operate primarily in an iterative mode. I prefer
well-thought-out approaches. That is, thinking before doing. An example
of "iterative mode of operation" is the fast typist who at the command
line does not bother to learn the different versions of the commands
because he can easy enough just iterate through them until he achieve the
desired result. Surely everyone has seen someone who uses the computer
that way: it's very frenzied and chaotic. Your statement "I can't count
how often I swap out underlying list/container implementations" may be an
indication of such. But, Jacob was talking about swapping out completely
different ADTs rather than just implementations of the correctly chosen
one. Swapping out one list implementation for another is not relevant for
me as I build my own containers, but even if I did not, such micro-level
substitutions are categorized as optimizations for specialized
applications or use. Finally, I think Jacob considers "design" to be an
implementation thing whereas I see it as independent from implementation
details such as containers/algos or which language to use.

 

[Charles]

But sometimes designing and coding the final solution just isn't the
right way to do it. Take my website, which is entirely programmed by
me, in my spare time.

We could go round and round all day on this, and I'm sure JN would
because he is so in love with the idea, which is not novel nor
necessarily even correct, that swapping one type of container for another
is the best thing since sliced bread.

I could say that doing so, even if it was a correct design, is a
compromise in favor of the exceptional case over the mainstream case. I
could volunteer that it is "gold plating", a decidedly negative thing to
do on a project. And then you'd just come back with "well in this case or
that case... yada". YMMV is all I can say.

Bottom-up approaches are good for when it is not known how to do it. It
allows gradual build up of knowledge to incrementally and iteratively get
the job done. It is an inefficient process, but when there is nothing
else available, it's a tool in the process toolbox (note that hiring a
consultant may be much better use of time, money, resources). If you
already know how to do it, then there is no need to seek out compromised
components to help with the iterative/bottom-up approach at all. A list
will look like a list, an array will look like an array and a map will
look like a map. The right thing for the task at hand without compromise.
YMMV.