Container libraries

Container libraries

[Jano]

Hello people.

I'm examining some container libraries for use. I suppose you'll say
I'm the best suited to know my needs and choose the proper one, but
anyway I look for your experiences of use. I'm particularly interested
in sortcomings/buggy implementations you may have found. Also your
personal preferences can be helpful. It's hard to get a grasp in such
relatively large libraries so your advice can save me handy time.

My requeriments are, basicly: ordering, finding (both time-efficient)
and multitasking support if possible.

I've found:

* Booch components.
     I only miss multitasking support. They are a bit tricky to
instantiate but
     only at first.

* AdaSL.
     They seem very complete. Also without multitasking.

* Mats Weber's Ada component library
     Multitasking support for the relevant types, interesting
(unrelated)
     packages.

* PragmAda reusable components.
     I like the multitasking support and its simplicity, but at the
same time I
     fear they can result too simple in the end.
     
Kind regards,

A. Mosteo.

Re: Container libraries

[Preben Randhol]

Not to forget:

Charles Container Library

   http://home.earthlink.net/~matthewjheaney/charles/
|
-- 
Preben Randhol ---------------- http://www.pvv.org/~randhol/ --
"Violence is the last refuge of the incompetent", Isaac Asimov

Re: Container libraries

[Jano]

En el mensaje <slrnb5n405.5b4.randhol+news@kiuk0152.chembio.ntnu.no>, 
randhol+news@pvv.org dice...
> Not to forget:
> 
> Charles Container Library
> 
>    http://home.earthlink.net/~matthewjheaney/charles/

Just have come across it in another thread. One more to check... I'm 
saturated :)

-- 
-------------------------
Jano
402450[at]cepsz.unizar.es
-------------------------

Re: Container libraries

[Simon Wright]

402450@cepsz.unizar.es (Jano) writes:

> My requeriments are, basicly: ordering, finding (both
> time-efficient) and multitasking support if possible.

What sort of multi-tasking support would _you_ like, then? (the Booch
Components used to have some, but as soon as I tried to actually use
it myself in a serious application it was obvious that no simplistic
approach to multitasking was ever going to satisfy more than a very
few users.

And just at that point I found I couldn't have both a new valuable
feature and concurrency implemented the old way ..

Re: Container libraries

[Hyman Rosen]

Simon Wright wrote:
> What sort of multi-tasking support would _you_ like, then?

People usually want the wrong sort. If someone needs to access
a container simultaneously from multiple tasks, then they should
privide the synchronization, not the container. Only if the
containers share some internal object do they themselves need to
protect it against concurrent access.

Re: Container libraries

[Jeffrey Carter]

Jano wrote:
> 
> * PragmAda reusable components.
>      I like the multitasking support and its simplicity, but at the
> same time I
>      fear they can result too simple in the end.

I'm not sure what this means. Some of the protected data structures have 
been used on large concurrent projects, so they weren't too simple for 
those projects.

-- 
Jeff Carter
"Run away! Run away!"
Monty Python and the Holy Grail

Re: Container libraries

[Chad R. Meiners]

"Hyman Rosen" <hyrosen@mail.com> wrote in message
news:1046214593.420402@master.nyc.kbcfp.com...
> Simon Wright wrote:
> > What sort of multi-tasking support would _you_ like, then?
>
> People usually want the wrong sort. If someone needs to access
> a container simultaneously from multiple tasks, then they should
> privide the synchronization, not the container. Only if the
> containers share some internal object do they themselves need to
> protect it against concurrent access.

I agree with Hyman.  I once used the Booch component for a multitasking
application, but only in the package bodies because the multitasking
interaction needed to be specifically coded into the protected object.  I do
not think that built in task synchronization is all that helpful, but as
always there shouldn't be any nasty global effects in component libraries
that prevents two separately allocated data objects from being used at the
same time by different tasks.

-CRM

Re: Container libraries

[Dmitry A. Kazakov]

On 25 Feb 2003 03:17:44 -0800, 402450@cepsz.unizar.es (Jano) wrote:

>I'm examining some container libraries for use. I suppose you'll say
>I'm the best suited to know my needs and choose the proper one, but
>anyway I look for your experiences of use. I'm particularly interested
>in sortcomings/buggy implementations you may have found. Also your
>personal preferences can be helpful. It's hard to get a grasp in such
>relatively large libraries so your advice can save me handy time.
>
>My requeriments are, basicly: ordering, finding (both time-efficient)
>and multitasking support if possible.

I have a simple component library:

http://www.dmitry-kazakov.de/ada/components.htm
(no multitasking support)

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: Container libraries

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 688 bytes --]


"Jano" <402450@cepsz.unizar.es> a �crit dans le message de news: MPG.18c5e1ca2aa320c9896aa@News.CIS.DFN.DE...
> En el mensaje <slrnb5n405.5b4.randhol+news@kiuk0152.chembio.ntnu.no>,
> randhol+news@pvv.org dice...
> > Not to forget:
> >
> > Charles Container Library
> >
> >    http://home.earthlink.net/~matthewjheaney/charles/
>
> Just have come across it in another thread. One more to check... I'm
> saturated :)
>
Hey, Ada community, did you notice?
A user complaining about having *too many* software components available....

--
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Container libraries

[Jano]

En el mensaje <3E5C1DD7.4050408@acm.org>, jrcarter@acm.org dice...
> Jano wrote:
> > 
> > * PragmAda reusable components.
> >      I like the multitasking support and its simplicity, but at the
> > same time I
> >      fear they can result too simple in the end.
> 
> I'm not sure what this means. Some of the protected data structures have 
> been used on large concurrent projects, so they weren't too simple for 
> those projects.

Uh, my fault. I was not refering to the simplicity of the protection 
mechanism, but to its general simplicity. I was refering simply to an 
"unrational" ;) feeling: that, being comparatively simple in regard to 
other container packages, maybe I could find suddenly that they lack 
some feature.

But as I said, it was simply an impression. If they are easy and with 
all the needed features, that's precisely what I want.

-- 
-------------------------
Jano
402450[at]cepsz.unizar.es
-------------------------

Re: Container libraries

[Jano]

En el mensaje <x7vznokrp3g.fsf@smaug.pushface.org>, simon@pushface.org 
dice...
> 402450@cepsz.unizar.es (Jano) writes:
> 
> > My requeriments are, basicly: ordering, finding (both
> > time-efficient) and multitasking support if possible.
> 
> What sort of multi-tasking support would _you_ like, then? (the Booch
> Components used to have some, but as soon as I tried to actually use
> it myself in a serious application it was obvious that no simplistic
> approach to multitasking was ever going to satisfy more than a very
> few users.

I understand it's a complicated matter. I'd like to have protected 
versions, but also consistent iterators. I must think if I'd prefer 
constant snapshots (copy) or simply transparently be unaware if an item 
is removed-added by another task.

I suppose these kinds of doubts are what made you to leave that part to 
each user.

-- 
-------------------------
Jano
402450[at]cepsz.unizar.es
-------------------------

Re: Container libraries

[Stephen Leake]

402450@cepsz.unizar.es (Jano) writes:

> My requeriments are, basicly: ordering, finding (both time-efficient)
> and multitasking support if possible.
> 
> I've found:
> <snip>

You missed SAL:

http://users.erols.com/leakstan/Stephe/Ada/sal.html

It provides a binary sorted tree.

To add "multitasking support", use a protect object or task as
appropriate (there are way too many styles of "multitasking" for me to
make it part of SAL).

The tree is not balanced; feel free to add that and contribute it
(hint, hint :).

-- 
-- Stephe

Re: Container libraries

[Simon Wright]

Jano <402450@cepsz.unizar.es> writes:

> I understand it's a complicated matter. I'd like to have protected
> versions, but also consistent iterators. I must think if I'd prefer
> constant snapshots (copy) or simply transparently be unaware if an
> item is removed-added by another task.
> 
> I suppose these kinds of doubts are what made you to leave that part
> to each user.

Indeed .. it's the "consistent iterators while other folk are
adding/removing elements" that is the killer.

Re: Container libraries

[Martin Krischik]

On Tue, 25 Feb 2003 03:17:44 +0000, Jano wrote:

> Hello people.
> 
> * AdaSL.
>      They seem very complete. Also without multitasking.

I am using AdaSL components. They work quite well for me. As for
Multitasking, I have added my own (see adacl.sf.net).

Still, I am starting to miss some form of access by key.

With Regards

Martin

-- 
Martin Krischik
mailto://Martin@krischik.com
http://www.ada.krischik.com

Re: Container libraries

[Jeffrey Carter]

Jano wrote:
> 
> I understand it's a complicated matter. I'd like to have protected 
> versions, but also consistent iterators. I must think if I'd prefer 
> constant snapshots (copy) or simply transparently be unaware if an item 
> is removed-added by another task.

The PragmARC approach is for iteration over a protected structure to be 
a protected action. Thus, another task cannot modify the structure 
during iteration.

-- 
Jeff Carter
"Every sperm is sacred."
Monty Python's the Meaning of Life

Re: Container libraries

[Dmitry A. Kazakov]

On Wed, 26 Feb 2003 19:17:52 +0100, Jano <402450@cepsz.unizar.es>
wrote:

>En el mensaje <x7vznokrp3g.fsf@smaug.pushface.org>, simon@pushface.org 
>dice...
>> 402450@cepsz.unizar.es (Jano) writes:
>> 
>> > My requeriments are, basicly: ordering, finding (both
>> > time-efficient) and multitasking support if possible.
>> 
>> What sort of multi-tasking support would _you_ like, then? (the Booch
>> Components used to have some, but as soon as I tried to actually use
>> it myself in a serious application it was obvious that no simplistic
>> approach to multitasking was ever going to satisfy more than a very
>> few users.
>
>I understand it's a complicated matter. I'd like to have protected 
>versions, but also consistent iterators. I must think if I'd prefer 
>constant snapshots (copy) or simply transparently be unaware if an item 
>is removed-added by another task.

The problem is the level of integrity you want to achieve. The lowest
(and easy) level is to ensure the container data consistency upon
concurrent updates. But already iterators would require a higher level
depending on the semantics of what the container contains. Sometimes
you would like to lock the container during the whole iteration
process to have a consistent view on it. Probably you would like to
share such views between multiple tasks. Maybe you would like to allow
a read access to the container at this time. And so on. I doubt, that
there could be an universal and simple approach here.

>I suppose these kinds of doubts are what made you to leave that part to 
>each user.

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: Container libraries

[Preben Randhol]

Jean-Pierre Rosen wrote:
> Hey, Ada community, did you notice?
> A user complaining about having *too many* software components available....

Hehe. Well, understandable in the view that the language is usually the
main source of the things you need. When you find several similar
packages you get a bit frustrated about which to choose ;-)

-- 
Preben Randhol ---------------- http://www.pvv.org/~randhol/ --
"Violence is the last refuge of the incompetent", Isaac Asimov

Re: Container libraries

[Marin David Condic]

Yeah. Freedom of choice is what you've got. Freedom *from* choice is what
you want! :-)

There *are* too many component libraries out there. Well, maybe not *too*
many in the sense that they aren't identical and the plurality allows for
specializing to satisfy different needs. But for basic data structures,
there ought to be a single, basic data structure package that was the
conventional answer so we could point students and newbies at it and show
them an Off The Shelf answer to their problems. Other component libraries
might then be aluded to when they satisfy special needs.

MDC
--
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jsf.mil/

Send Replies To: m c o n d i c @ a c m . o r g

    "Going cold turkey isn't as delicious as it sounds."
        -- H. Simpson
======================================================================

Jean-Pierre Rosen <rosen@adalog.fr> wrote in message
news:k2vi3b.of5.ln@skymaster...
> >
> Hey, Ada community, did you notice?
> A user complaining about having *too many* software components
available....
>

Re: Container libraries

[Matthew Heaney]

"Martin Krischik" <Martin.Krischik@T-Online.de> wrote in message news:<pan.2003.02.26.19.39.36.852804@T-Online.de>...
> 
> I am using AdaSL components. They work quite well for me. As for
> Multitasking, I have added my own (see adacl.sf.net).
> 
> Still, I am starting to miss some form of access by key.

Charles has maps, which allow access by an arbitrary key.  There is
also a special map container for keys of type String.  There are both
sorted and hashed versions.

There are also multimaps, which allow multiple elements to have the
same key.  The Equal_Range operation returns an iterator pair that
designates the range of equivalent keys.

Sets are similar, in that the element is its own key.

http://home.earthlink.net/~matthewjheaney/charles/

All the containers are sequential -- there is no built-in support for
concurrency.  However, it is trivial for a client to add such support,
e.g.

Map : Map_Subtype;
Map_Semaphore : aliased Semaphore_Type;

procedure Lookup (Key : Key_Subtype) is
   Lock : Semaphore_Control_Type (Map_Semaphore'Access);
   I : constant Iterator_Type := Find (Map, Key);
begin
   if I /= Back (Map) then ...
end Lookup;

That is one way to implement support for concurrency.  There are many
other ways.

Re: Container libraries

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 846 bytes --]


"Preben Randhol" <randhol+news@pvv.org> a �crit dans le message de news: slrnb5rvks.3nb.randhol+news@kiuk0152.chembio.ntnu.no...
> Jean-Pierre Rosen wrote:
> > Hey, Ada community, did you notice?
> > A user complaining about having *too many* software components available....
>
> Hehe. Well, understandable in the view that the language is usually the
> main source of the things you need. When you find several similar
> packages you get a bit frustrated about which to choose ;-)
>
Right. Similarly, in the former USSR, people did not have to worry about which
brand of butter to buy - if they had one, they were happy. We do have that problem
in our supermarkets. Should we complain ?

--
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Container libraries

[Martin Krischik]

On Thu, 27 Feb 2003 09:19:51 +0000, Matthew Heaney wrote:

> "Martin Krischik" <Martin.Krischik@T-Online.de> wrote in message news:<pan.2003.02.26.19.39.36.852804@T-Online.de>...
>> 
>> I am using AdaSL components. They work quite well for me. As for
>> Multitasking, I have added my own (see adacl.sf.net).
>> 
>> Still, I am starting to miss some form of access by key.
> 
> Charles has maps, which allow access by an arbitrary key.  There is
> also a special map container for keys of type String.  There are both
> sorted and hashed versions.

Thank you very much. Now I know where to look. Took me some time to
discover that his lists can be used for queues as well.

> Sets are similar, in that the element is its own key.
> 
> http://home.earthlink.net/~matthewjheaney/charles/
> 
> All the containers are sequential -- there is no built-in support for
> concurrency.  However, it is trivial for a client to add such support,
> e.g.
 
I have build a concurrend queue in base of AList for AdaCL. As you said it
is realy easy

With Regards

Martin

-- 
Martin Krischik
mailto://Martin@krischik.com
http://adacl.sf.com

Re: Container libraries

[Marin David Condic]

Certainly free markets and lots of choices are the way to go. The better
products end up floating to the top and people have specialized choices for
specialized needs. That said, I'd still think there would be a big advantage
to having some basic containers as a conventional part of Ada - especially
for students. It makes it much easier to point them at an answer and if it
is just there with the compiler, they just use it and presume it *is* part
of the language.

MDC
--
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jsf.mil/

Send Replies To: m c o n d i c @ a c m . o r g

    "Going cold turkey isn't as delicious as it sounds."
        -- H. Simpson
======================================================================

Jean-Pierre Rosen <rosen@adalog.fr> wrote in message
news:ul3n3b.0at.ln@skymaster...
> >
> Right. Similarly, in the former USSR, people did not have to worry about
which
> brand of butter to buy - if they had one, they were happy. We do have that
problem
> in our supermarkets. Should we complain ?
>

Re: Container libraries

[Preben Randhol]

Jean-Pierre Rosen wrote:

> Right. Similarly, in the former USSR, people did not have to worry
> about which brand of butter to buy - if they had one, they were happy.
> We do have that problem in our supermarkets. Should we complain ?

Do we need five different Office packages with five different
fileformats or one fileformat and five different office packages that
all uses this?

My point is that it would be nice with a standard container library and
some container libraries that deal with more special needs. But I don't
complain.
-- 
Preben Randhol ---------------- http://www.pvv.org/~randhol/ --
"Violence is the last refuge of the incompetent", Isaac Asimov

Re: Container libraries

[Alexandre E. Kopilovitch]

Jean-Pierre Rosen wrote:
>... Similarly, in the former USSR, people did not have to worry about which
>brand of butter to buy - if they had one, they were happy.
This is too imprecise a statement. Certainly, people even in the former USSR
were not happy with bad butter, even if they coudn't ... not exactly "buy",
but rather "obtain" or "find" another. The truth is that there were few sorts
of butter, and they were *ordered* in their quality. For example, everbody
knew that "Vologodskoe" (named after city of Vologda) was the best.
  So, although it is true that people in former the USSR had much less to decide
about common things, it was mostly caused not by deficit itself, but by stable
and well-known ordering/ranking in quality.


Alexander Kopilovitch                      aek@vib.usr.pu.ru
Saint-Petersburg
Russia

Re: Container libraries

[tmoran]

> Certainly free markets and lots of choices are the way to go. The better
> products end up floating to the top and people have specialized choices for
> specialized needs. That said, I'd still think there would be a big advantage
> to having some basic containers as a conventional part of Ada - especially
> for students. It makes it much easier to point them at an answer and if it
> is just there with the compiler, they just use it and presume it *is* part
> of the language.
  Unfortunately, as this points out in yet another way, the classic Adam
Smith free market works very poorly for software.  The cost of a piece of
software to a user is mostly not $, but information costs of trying to
find out what's available, how well it does what the user wants, and what
might it do that the user doesn't want.  Something like a brand name or
Official Ada Annex validation is really needed to cheaply and reliably
tell the user "this is a good thing".  How to get the creator of container
package A to agree that container package B should be the "standard", I
don't know.

Re: Container libraries

[steve_H]

Hyman Rosen <hyrosen@mail.com> wrote in message  

> People usually want the wrong sort. If someone needs to access
> a container simultaneously from multiple tasks, then they should
> privide the synchronization, not the container. 
 
But this way you will have duplication of effort. Each client/application
who wants to use the container needs to add code to provide the synch. outside
the container.

What one can do is provide 2 versions of the container, one that is synch. and
one that is not. If the client knows there will be one task only who will
access the container, then use the non-synch. version (which is assumed
to be a little faster), else use the other.

Re: Container libraries

[Hyman Rosen]

steve_H wrote:
> But this way you will have duplication of effort. Each client/application
> who wants to use the container needs to add code to provide the synch. outside
> the container.
> 
> What one can do is provide 2 versions of the container, one that is synch. and
> one that is not. If the client knows there will be one task only who will
> access the container, then use the non-synch. version (which is assumed
> to be a little faster), else use the other.

No. What you are missing is that synchronization is rarely needed for one
container. Instead, an application has a variety of data that must be
maintained consistently. That is why synchronization belongs with the
application rather than with the container.

Re: Container libraries

[Georg Bauhaus]

Marin David Condic <mcondic.auntie.spam@acm.org> wrote:
: Certainly free markets and lots of choices are the way to go. The better
                                                                    ^^^^^^
: products end up floating to the top and people have specialized choices for
: specialized needs.

That was irony, right?

-- Georg

Re: Container libraries

[Simon Wright]

nma124@hotmail.com (steve_H) writes:

> Hyman Rosen <hyrosen@mail.com> wrote in message  
> 
> > People usually want the wrong sort. If someone needs to access
> > a container simultaneously from multiple tasks, then they should
> > privide the synchronization, not the container. 
>  
> But this way you will have duplication of effort. Each
> client/application who wants to use the container needs to add code
> to provide the synch. outside the container.

From my point of view (as a container maintainer) there are lots of
problems.

If the only thing you need is a "secure-release" protocol, where it's
the users' responsibility to secure before accessing and to relase
when done, that's easy enough.

But it's not what most people want, especially when they get the bit
between their teeth (and they don't have to pay for it):

* they want "multiple-reader/single writer"

* they want the individual container operations to be safe

* they want multiple iterators over the container at the same time

* they want to be able to add and delete from the container in the
  presence of multiple iterators (who knows what the semantics of that
  are supposed to be!)

and the whole enterprise just falls apart.


Consider also Queues as they were supported by the BCs before I
removed the concurrency: if you try to read from an empty queue, then

* if it's not concurrent, you get an exception

* if it is concurrent, you block until some other task adds something.

And for some reason, Sets had the same behaviour (but Bags didn't).


No, it's best if users add their own concurrency support.

Re: Container libraries

[Dmitry A. Kazakov]

On Fri, 28 Feb 2003 08:27:52 +0100, "Jean-Pierre Rosen"
<rosen@adalog.fr> wrote:

>"Preben Randhol" <randhol+news@pvv.org> a �crit dans le message de news: slrnb5rvks.3nb.randhol+news@kiuk0152.chembio.ntnu.no...
>> Jean-Pierre Rosen wrote:
>> > Hey, Ada community, did you notice?
>> > A user complaining about having *too many* software components available....
>>
>> Hehe. Well, understandable in the view that the language is usually the
>> main source of the things you need. When you find several similar
>> packages you get a bit frustrated about which to choose ;-)
>>
>Right. Similarly, in the former USSR, people did not have to worry about which
>brand of butter to buy - if they had one, they were happy. We do have that problem
>in our supermarkets. Should we complain ?

It depends. We can be well sure that the market would find an optimal
form of fashion shoes. But could we in the case of a fusion reactor?

Ergo, top-down is not always worse than bottom-up.

---
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: Container libraries

[Marin David Condic]

You have a point. I'm not sure that it is a fair critique of Adam Smith, but
it is valid to say that some of the cost associated with software is the
cost of acquiring information. A "better" product would be one that is well
documented - saving the consumer some time in figuring out what the product
does and what uses it might be suited to. But even then, a user has to
invest some time in trying to learn all about it. "Better" might also mean
"more intuitive" so that less time is spent figuring it out. "Better" might
also come from establishing a user base where a font of knowledge is
available. (Gnat, for example, is a "better" product than some other
compilers because there are a large number of people one can tap for
answering questions about it - even if it is not as good in some other
respects.) The better products still rise to the top, but the definition of
"better" in the mind of the consumer isn't always based on some sort of
technical advantage.

I think it would be hard - not impossible - but hard to get a container
library into an annex of the ARM. Mostly, it isn't "better" because it takes
so long to get changes into the ARM and it would suffer from Least Common
Denominator Syndrome. I think the appropriate answer is to get some kind of
"official" consensus on the need for a general library of utility code and
establish a mechanism for building & maintaining it. A library that is
endorsed by some significant portion of the compilers out there and
subsequently shipped (or at minimum, referenced) with the compiler would go
a long way toward establishing something as the basic starting point for
containers for those new to the language and without some specialized needs.

MDC
--
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jsf.mil/

Send Replies To: m c o n d i c @ a c m . o r g

    "Going cold turkey isn't as delicious as it sounds."
        -- H. Simpson
======================================================================

<tmoran@acm.org> wrote in message
news:mR68a.310596$Ec4.308950@rwcrnsc52.ops.asp.att.net...
>   Unfortunately, as this points out in yet another way, the classic Adam
> Smith free market works very poorly for software.  The cost of a piece of
> software to a user is mostly not $, but information costs of trying to
> find out what's available, how well it does what the user wants, and what
> might it do that the user doesn't want.  Something like a brand name or
> Official Ada Annex validation is really needed to cheaply and reliably
> tell the user "this is a good thing".  How to get the creator of container
> package A to agree that container package B should be the "standard", I
> don't know.