Hi,
In article <8frktq$5kd$1@nnrp1.deja.com>,
  sirwillard@my-deja.com wrote:
> In article <8fp8aj$gs5$1@nnrp1.deja.com>,
>   Dietmar Kuehl <dietmar.kuehl@claas-solutions.de> wrote:
[Pointer to an approach using implicit, external locks removed]

> As you pointed out, however, this approach won't be compatible with
the
> standard, which prevents the return of proxy objects.  The same thing
> can be (somewhat) achieved by using a wrapper instead of a returned
> proxy.  Many attempts have been done on this scheme, most revolving
> around a "smart pointer" that manages the locks.  This scheme,
however,
> requires a very large amount of knowledge on what exactly the wrapper
> will do in order to avoid many pitfalls ranging from prematurely
> releasing the lock to holding the lock too long.  It's honestly much
> easier (and so usually much safer) to use an external lock with a RAII
> mechanism.  This approach also has the added benefit that it's as
> trivial to implement as it is to use.  KISS principle in action here.

I think we are in violent agreement and I wasn't contradicting you,
just pointing out that the approach using implicit locking also solves
the problem with external locks. The difference between your external
locks and mine being basically that yours are manipulated explicitly
while mine are manipulated implicitly. When I say "mine" I'm only
refering to a potential technique I have described in this thread, not
necessarily something I would propose. In fact, I see more problems
with the implicit locking mechanisms (mainly lock-lifetime, ie. it is
easy to make this too short or too long, and performance) as with the
explicit locking mechanism (mainly the potential of forgetting to lock
a container which can be checked in the container's methods at runtime,
though). I'm currently not using threaded programs but I think that I
would bundle locks with allocators and use explicit, external locking.

> > > However, the thread
> > > synchronization has been simplified to look like something similar
> to
> > > what you have in Java.
> >
> > ... and the semantics have been improved to provide control at a
> > reasonable level while the Java 'synchronized' approach only
provides
> > this control if you define lots of classes and methods.
>
> I don't follow this.  I'm not an expert on Java, let alone on Java
> threading issues, but it seems to me that this approach and the
> Java "synchronize" key word should be identical (except that the Java
> keyword is built in).  After all, you can use "synchronize" in Java to
> protect either a method or an object.  Seems to be the same thing
> here.  What am I missing?

Well, lock lifetime is the obvious problem: With external locks you can
acquire the lock when you start needing it. For example, consider a
function doing lots of computation and finally inserts the results into
a shared container. You would acquire the lock after the computation,
right before accessing the container. In Java, the lock would be
acquired at function entry (basically, you can view 'synchronized' as
a key word working around the lack of destructors for a special
purpose: it allocates an object acquiring a lock at the beginning of a
function and destructs it at the of the function). You can work around
this problem by splitting the function into two function, one doing the
computation, finally calling the other to do the update. If the
function is indeed that clear cut, this is a viable approach, in
general it can become much harder to use.

Another problem of Java's approach to synchronization is, of course,
that you cannot lock some object, eg. when having multiple objects
which are to be updated from one thread. Again, this can be work around
(eg. using synchronized static methods of some auxiliary class and only
accessing the corresponding object through this auxiliary class). Using
external locks, you can easily just acquire locks to multiple objects.
Of course, you still have to take care of dead locks...

But then, I'm not an Java expert and it is well possible that I'm just
missing something more or less obvious.
--
<mailto:dietmar.kuehl@claas-solutions.de>
homepage: <http://www.informatik.uni-konstanz.de/~kuehl>


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> > I have reservations about THIS particular point.  If 98% of the
people
> > do NOT want the locks, then those people don't need to use the
locks.
> > The solution would be, of course, to seperate those features that
> > increase overhead and make them optional for those 2% who DO want
it.
> > I haven't seen any comments to the contrary
>
> You misread what I wrote.  Read the quote above carefully.  Here's an
> example:
>
> std::copy(vt1.begin(), vt1.end(), std::back_inserter(vt2));
>
> In order to make this call thread safe we _MUST_ use an external lock.
> There's no way around this.  So, we get (psuedo code, since c++
doesn't
> have thread primitives).
>
> lock(vt1);
> std::copy(vt1.begin(), vt1.end(); std::back_inserter(vt2));
> unlock(vt1);
>

I can see your point... the whole organization of thread safe STL
collections no longer seems straightforward... and the fact that thread
safety no longer allows algorithms to be developed blindly outside of
collections really makes things tough -- your example shows this all
too well.

Back to the trenches I have gone to lick my wounds and think up a
different approach.  :-)


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

sirwillard@my-deja.com wrote:
>
> In article <8f76im$uua$1@nnrp1.deja.com>,
>   Michael Hays <icarus_rising@yahoo.com> wrote:
> >
> > > Creating a thread safe library is a all or nothing thing: Either you
> > > are protecting all entities or your thread safety would be dwarfed.
> > > Also, thread safety means different things to different people and I
> > > think the only reasonable form of thread safety for the C++ standard
> > > library is the lowest form of thread safety: All global resources
> used
> > > by the library are protected but the objects themselves are not.
> >
> > Hmmm... perhaps the construct to which I was referring is unfamiliar.
> > After reading the comment about putting different types of collections
> > into different namespaces, I'm rather sure of it.
>
> I wouldn't be.  Mr. Kuehl has written an implementation of the
> <iostream> classes, so he's very much familiar with the traits idiom.
> Why he chose to use namespaces instead of traits is anyone's guess, but
> I do know he understands traits.
>
> > First, I am not asking for the standard to change to support thread
> > safety.  Not at all.  I stand by the standard's support of exception
> > safety and its efficiency.
>
> I'm not sure why you mention exception safety here.  Different topic
> all together.
>
> > Second, take a look at the std::basic_char definition.  One of the
> > template parameters is another template called char_traits.  Take a
> > look at the definition for char_traits.  A user wishing to expand the
> > usability of the std::string functions (for example) could change the
> > underlying way in which a string works by providing a char_traits
> > object (and overriding the lt (less than), equal, length, etc).  An
> > example I remember from Herb Sutter's book, "Exceptional C++" shows
> how
> > to create a case-insensitive string class WITHOUT overriding
> > std::string along with every one of its members... In addition, said
> > programmer could pat himself on the back when he goes to write a case-
> > insensitive ostream and istream class only to find out that, waa-hoo,
> > char_traits are used in those as well.
> >
> > This same technique could be applied to a "collection_traits" object.
> > In fact... it ALREADY partially exists inside the Allocator class.
> > However, if there were hooks into the insert and delete functions,
> then
> > a designer could arbitrarily assign more complicated activity to a
> > container as his/her project might require, WITHOUT bring in a whole
> > new library of classes for EVERY collection that he/she wanted to
> > mutate.  In other words -- write the thread safety locks for insert
> and
> > delete for a vector, using ITS collection_traits object, then reuse
> > that collection_traits object inside map, deque, ... whatever...
>
> I'm not sure that a collection_traits object would ever be useful.  In
> any case, you missed Mr. Kuehl's point, since such a trait object is
> next to useless here.  This is too low of a granularity for thread
> synchronization.

It doesn't relief you from doing synchronisation yourself - but
it helps for synchronizing those parts which the user isn't
even aware that it is shared (think ref counted strings, f.ex.).

I think a traits class could be quite useful; not only with
synchronisation - f.ex. do you want vector<bool> to be packed
(as in the standard) or unpacked (as in the original STL)?

A possible container_traits could look like this:

template<class T> struct container_traits
{
  typedef implementation-defined mutex;
    // supports members lock and unlock; for unsynchronized
    // implementations, those can be empty inline calls

  typedef typename T::value_type storage_type;
    // the type that is really stored in the container;
    // for all standard containers except vector<bool>
    // this is just the container type

  static const int values_per_storage = 1;
    // how many value_type objects can be stored per
    // storage_type object. For standard containers,
    // this is always 1

  void copy_value(storage_type* p, int n,
                 typename T::value_type const& v)
  // creates object n in storage_type
  {
    new(p) typename T::value_type(v);
  }

  void assign_value(storage_type* p, int n,
                    typename T::value_type const& v)
  // copies to object n in storage_type
  {
    *p = v;
  }

  void destroy_value(storage_type* p, int n)
  // destroys object n
  {
    typedef typename T::value_type vtype;
    p->~vtype();
  }

  typename T::reference get_value(storage_type const* p, int n)
  // get value
  {
    return *p;
  }

  void copy_in_storage(storage_type* pd, int nd,
                       storage_type const* ps, int ns)
  // copy from one storage object to another
  {
    typedef typename T::value_type vtype;
    new (pd) vtype(*ps);
  }

  void move_in_storage(storage_type* pd, int nd,
                       storage_type* ps, int ns)
  // move from one staorage object to another
  {
    typedef typename T::value_type vtype;
    new (pd) vtype(*ps);
    ps->~vtype();
  }

  void copy_storage(storage_type* pd, storage_type const* ps)
  // copy one complete storage
  {
    copy_in_storage(pd, 0, ps, 0);
  }

  void move_storage(storage_type* pd, storage_type* ps)
  // move one complete storage
  {
    move_in_storage(pd, 0, ps, 0);
  }
};

template<class Alloc> struct container_traits< vector<bool, Alloc> >
{
  typedef ... mutex;
  typedef unsigned char storage_type;
  static const int values_per_storage = CHAR_BITS;

  void copy_value(storage_type* p, int n, bool v)
  {
    if (v) *p |= 1<<n; else *p &= ~(1<<n);
  }

  void assign_value(storage_type* p, int n, bool v)
  {
    if (v) *p |= 1<<n; else *p &= ~(1<<n);
  }

  void destroy_value(storage_type*, int) {}

  typename vector<bool, Alloc>::reference
   get_value(storage_type const* p, int n)
  {
    return (*p & (1<<n)) != 0;
  }

  void copy_in_storage(storage_type* pd, int nd,
                       storage_type* ps, int ns)
  {
    if (*ps & (1<<ns)) *pd |= 1<<ns; else *pd &= ~(1<<ns);
  }

  void move_in_storage(storage_type* pd, int nd,
                       storage_type* ps, int ns)
  {
    if (*ps & (1<<ns)) *pd |= 1<<ns; else *pd &= ~(1<<ns);
  }

  void copy_storage(storage_type* pd, storage_type const* ps)
  {
    *pd = *ps;
  }

  void move_storage(storage_type* pd, storage_type* ps)
  {
    *pd = *ps;
  }
};

The copy/move distinction is so that you could f.ex. make
a container_traits class for smart pointer containers, so
that the container in reality contained raw pointers and
did the complete management itself, adjusting reference
counters only when doing a real copy, not a mere move.

The copy_storage/move_storage are for optimizing the
special case where a complete storage has to be
copied/moved; for the performance of packed containers
such as vector<bool>.

>  It will add tremendous speed costs while addressing
> only a very small subset of uses of the object.

Since the standard traits class would have empty inline
lock/unlock, the performance hit would be close to zero.
Only if a (non-standard) syncronisation container_traits
is given to the container, it will cost any time for that.

>  For instance, imagine
> trying to use std::copy to copy items from one container to another.
> If the locks were left at the level you've specified with
> container_traits then seperate threads could add/remove/etc items
> between each insertion within the copy algorithm, resulting in
> something very much unexpected.

If your program does this, yopur program is broken.
But without thread safety, it could happen that two
containers make concurrent calls to the same allocator,
and therefore f.ex. both get the same memory back.

>  Worse still, it's possible that things
> could even lead to a deadlock with this level of granularity on some
> constructs.

With _which_ level of granularity?
Just protecting the common ressources of different containers
should be possible without the danger of deadlocks.

>  No, what's needed is an object level lock.  You apply the
> lock before your first access to the object and after the last access
> to the object (don't misread what I'm saying here... you'll want to
> unlock ASAP, but not until the last access that's a part of
> the "transaction" you're attempting on the object).

This type of lock may be needed if you share the same
user_visible object between threads. But if two containers
share internal data structures (f.ex. ref counted strings),
_they_ are responsible for protecting. But given that
threads are not standardized, they cannot do that without
help from the user. And container_traits would allow the
user to help (as well as doing some other things, like
defining their own packed containers (say enum Direction
{ North, South, East, West } packed to two bits per enum),
or defining optimized containers for smart pointers.
Indeed, even containers of auto_ptr would be possible
with container_traits (although you still wouldn't be
able to use all algorithms on them).

[...]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,
In article <8f76im$uua$1@nnrp1.deja.com>,
  Michael Hays <icarus_rising@yahoo.com> wrote:
> Hmmm... perhaps the construct to which I was referring is unfamiliar.

No, it is not and I went down the same road until I realized that I'm
walking into the wrong direction: It looks like the easier path but it
has serious pitfalls and is looming users into a false feeling of
security.

> After reading the comment about putting different types of collections
> into different namespaces, I'm rather sure of it.

I know that I don't want to address the problem at the same level you
want to address it. What I'm talking of is basically using namespaces
to select between a thread safe standard library and a fast library.
Using namespaces for this purpose has some neat effects:

- Users can't accidentally link thread safe code with unsafe code.
- The thread safe implementation can use the fast one where appropriate.
- If really desired (due to performance considerations and a deep
  analysis of the situation) both libraries can be mixed (with care!).

However, the result of making the standard library thread safe are in
no case "thread safe containers" because there is no such thing in the
first place! It is an attempt to deal with threads at the completely
wrong level of granularity. However, there can be thread supporting
containers and all necessary mechanisms for this are already in place
in the standard library. The basic idea is to hijack allocators putting
lock objects into the allocator: This way you can associate additional
data with a container which is all you need to deal with threading when
you want to code thread safe. There is a minor caveat though: The same
lock is shared between all objects having an allocator which is created
by copying an allocator created with the default constructor or a copy
thereof. Just make sure you are not distributing your allocators too
much
because otherwise you would lock too many objects at once. This is not
a problem to thread safety but creates a fair potential for dead-locks
and can also imact performance.

Note, that thread safety goes far beyond thread safety of containers
locked per operation: Using basically an arbitrary standard algorithm,
eg. 'find()' or 'copy()' can fail miserably if another threads modifies
the container during their executation. Since with the kind of thread
safety you envision each individual container operation is protected
(and nothing else!) the objects used by one thread during an algorithm
might get moved somewhere else by another thread. This can be dealt with
but only at even higher performance costs: People would start speaking
of
"crawling a program" rather than "running a program".

The "right" approach to thread safety is to guarantee that any global
data used underneath (eg. the memory allocation facilities, the global
locale, the 'std::ios_base::xalloc()' IDs etc.) are accessed in a
thread safe way. Since this already adds additional costs, it makes
sense not to burdon the implementation running in a single threaded
environment with the extra overhead, thus providing basically two
distinct implementations which will, of course, share most of their
implementation.

This, of course, does not yet make accesses to containers thread safe.
How to go about this? You specify a special allocator which does two
things:

- It provides thread safe access to the memory allocation mechanism
  which is kind of global resource. Thus, whenever memory is allocated
  or release, these operations are protected by suitable locks.

- It provides a reference to a lock. This is actually a little bit
  tricky because the 'get_allocator()' method returns a copy of the
  allocator, not a reference. Thus, copies of an allcoator have to
  share a common lock which somewhat unfortunate but probably
  acceptable.

Allocators are not intended for this use but it looks as if you can
hijack this mechanism for this purpose in a portable fashion! That is,
the thread safe allocator can be provided by a third party library and
the implementation is only required to deal with their internal thread
safety which is a reasonable requirement and does not make the user
dependent on whatever interfaces the impelmenter chooses.

Now that every container has a suitable lock, you are using them very
much
like you are using data base transactions: Immediately before starting
using a container you acquire a lock using a suitable lock class which
releases the lock on destruction and probably with a 'release()' method
much ealier. The lock associated with the container is obtained from
the container's allocator which is never changed for the life-time of
the container (otherwise there would be thread safety problem with the
access of the lock...).

A tricky part about all this is when needing locks to more than one
container, eg. when copying: In this case you can produce a dead-lock
by locking the containers in an arbitrary order because one container
might do this operation in one order while another does it in a
different
order. I'm not that deep into thread programming (yet) but I know that
basically the same approaches to dead-lock elimination can be used as
are
used for data base transaction (no, I don't think that dead lock
detection
and resolution is the right approach to take!). A simple approach is
to define a partial order and to acquire locks in the order as defined
by this partial order and never acquiring locks which are incomparable
according to this partial order. OK, this is relatively simple to state
but it is sometimes *much* harder to really use this in practise.

> First, I am not asking for the standard to change to support thread
> safety.  Not at all.  I stand by the standard's support of exception
> safety and its efficiency.

I'm not at all assuming you are asking for a standard change. However,
to support thread safety the library implementation has to be changed:
You
cannot create thread safe programs using a normal library implementation
because internally the library access global resources and these access
have to be synchronized for thread safety.

> Second, take a look at the std::basic_char definition.

You are probably refering to 'std::basic_string' as there is no such
thing as 'std::basic_char'.

> One of the
> template parameters is another template called char_traits.  Take a
> look at the definition for char_traits.  A user wishing to expand the
> usability of the std::string functions (for example) could change the
> underlying way in which a string works by providing a char_traits
> object (and overriding the lt (less than), equal, length, etc).

Thanks for filling me in on the use of 'char_traits': Having
implemented the IOStreams library which makes heavy use of character
traits I'm well aware of the traits approach and, yes, it is handy to
do certain things. It is tempting to use a traits class for thread
safety but: Look closer and you will find that there is no character
traits object! There is a character traits class with a bunch of type
definitions and a bunch of static functions but no object. This is very
different from something like the allocator class for which there are
indeed objects! ... and to associate a lock with a container it is
useful
to have an object where the lock object can be stored. Traits don't have
such a place.

>  An
> example I remember from Herb Sutter's book, "Exceptional C++" shows
> how to create a case-insensitive string class WITHOUT overriding
> std::string along with every one of its members... In addition, said
> programmer could pat himself on the back when he goes to write a case-
> insensitive ostream and istream class only to find out that, waa-hoo,
> char_traits are used in those as well.

Note that using a different traits class will also cause lots of
problems, eg. when writing a case insensitive string to, say,
'std::cout', eg. for debugging. The output operator defined for
'std::basic_string' uses same the traits class as the stream! Of course,
you can still write the string using a special character traits by using
'str.c_str()' which is still acceptable effort but the key point is that
the types are not really compatible.

On the other hand, streams are not templatized on an allocator type
and you can use a string with an arbitrary allocator type with the
standard streams. Thus, changing the allocator for a container is
much less trouble. Of course, the stream classes also need to be
protected for thread safety. A possible option to put the lock in
for streams are the arrays accessed by 'std::ios_base::pword()' and
'std::ios_base::iword()'. However, here the user has to be somewhat
careful to install the locks in a thread safe manner.

> This same technique could be applied to a "collection_traits" object.
> In fact... it ALREADY partially exists inside the Allocator class.
> However, if there were hooks into the insert and delete functions,
then
> a designer could arbitrarily assign more complicated activity to a
> container as his/her project might require, WITHOUT bring in a whole
> new library of classes for EVERY collection that he/she wanted to
> mutate.  In other words -- write the thread safety locks for insert
and
> delete for a vector, using ITS collection_traits object, then reuse
> that collection_traits object inside map, deque, ... whatever...

You are asking for thread safety at the completely wrong level! You
don't want thread safety on an container method level although you
apparently think you really want it. Apart from being inefficient to
lock
the container for *ANY* operation you are applying to the container, it
doesn't help at all. For example, you have just obtained the container's
size in a thread safe way and now you are trying to, say, read the last
element of the container.  Unfortunately, another thread came along
between these two operations and has removed the last element. So you
have a thread safe container but it doesn't buy you anything! All this
locking for nothing. This is hardly effective.

For thread safe use of objects you need to obtain locks to the objects
process them and release the locks. Obtaining locks should be done at
latest possible time before accessing he object and the locks should be
release as soon as possible. However, you should view obtaining a lock
and releasing as if you were using a data base transaction: A lock is
not
just for one operation but for a whole sequence of operations. Locking
individual operations does not provide the necessary consistent data.

> The alternative is to encapsulate the collection totally and write a
> thread-safe wrapper.  Currently, this is how I have to do it...

*DON'T* do it this way! You are getting nothing in return. There may be
some container uses where you really only need individual operations but
actually the C++ containers are not designed for this purpose.
Basically,
you got a thread safe approach to add new elements to a container
eg. by using 'push_back()'. But this is about it! There is not even a
way for thread safe retrieval of an object from a container for typical
containers.  For 'std::vector' there is 'at()' which checks for out of
bounds errors... All other container accesses require that the accessed
object is just there and fail if another thread just decided to remove
the object between eg. reading the size and accessing a corresponding
element (please, don't nail me down if I forgot to mention the few other
methods I can't remember at the moment: these wouldn't change the real
problem in any way!).

> however, because I loathe writing this sort of stuff repeatedly, I use
> a threadsafe_adapter which takes a collection template and a
collection
> traits parameter and screws thread safety into the mix...

I'd rather formulate the last part of the above paragraph as "... and
screws a false sense of thread safety into the mix..." Forget about it!
This kind of "thread safety" is worthless. Well, it has some value for
some very specific applications but for a general approach it is
useless.

> This also bring to light one glaring problem... you DO, in fact, gain
> thread safety,

Can you please explain me how the following statements are thread safe
assuming that 'thread_vector' protects its operations:

  thread_vector<int> global_vector; // global so another thread can
access it

  void monitor() {
    while (1)
      if (global_vector.size() > 0 && global_vector[0] != 0)
        break;
    std::cout << "global_vector[0] != 0\n";
  }

Here is another function which is running in a separate thread:

  void process() {
    while (1)
      if (global_vector.size() > 0) {
        int first = global_vector[global_vector.size() - 1];
        global_vector.pop_back();
  }

Do you think a program having your "thread safe" containers running
these
two function is thread safe? Well, hopefully you are only programming
things which will not cause harm to living things...

BTW, my favorite form of threading is non-preemptive threading! Huh,
what is this good for? Well, the executing thread give up control
on a volunteering basis when it knows that everything is in a consistent
state. If another thread is ready to run it is resumed until this one
gives away control again. The tricky part about non-preemptive threading
is that there are situations transferring control which are not
explicit,
eg. when reading from a file a thread is stopped at least until the
corresponding page is swapped in. But basically most problems of
synchronization just go away...

> but at the expense of adding a lot of exception handling
> overhead to release the locks on the collection if an exception is
> thrown.  Not doing so reduces the exception guarantee to "weak" or
> potentially "none".  I have this crazy suspicion that if there *WERE*
a
> collection_traits object in the standard, they wouldn't be able to
give
> the "strong" exception safety we've come to expect... (FYI - "strong"
=
> the object is still intact after the exception.  "weak" = the object
> could dies but it won't leak resources after an exception.)

Thread safety and exception safety are orthogonal if there are per
thread
exceptions (ie. multiple thread can have simulataneous exceptions or
the implementation at least synchronizes them). Also, it is obvious
that locks have to be acquired by an object which releases the lock on
destruction automatically.

OK, enough strong opinions on an issue I have no practical experience
with...
--
<mailto:dietmar.kuehl@claas-solutions.de>
homepage: <http://www.informatik.uni-konstanz.de/~kuehl>


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> However, the result of making the standard library thread safe are in
> no case "thread safe containers" because there is no such thing in the
> first place!

My original idea for the container_attributes was to emulate an old old
idea of ":before" and ":after" methods which were
implicitly called for the user at the beginning and end of a method
(not ctor's or dtor's) to allow the locking and unlocking of
resources  (of course, for the container_traits, I would have to fit
into the standard collections calls to
"readbefore/readafter" and "writebefore/writeafter" which would call
those functions as defined in the traits object.  Heck...
even the routines in algorithms could make use of these.  Remember
though that the default function for these before and
after calls is an empty inlined function, which translates to a "pay
for what you use" kinda of feature.  This is an attribute of a
few languages outside of C++ and it was for this exact purpose
(resource locking) that they seemed so useful.  I really
wanted to emulate this behavior in the containers... (heck, I think
this was a feature Stroustrup was trying to get into the
language... at least according to his D&E book). And besides, it really
isn't JUST for the readbefore/readafter, but for
other things as well (I won't get into it here though... we'll keep the
thread topical)

Now, having said that, I can think of ways to break the thread safety
paradigm.  But enough about my ways... let's take
one of yours.

> Can you please explain me how the following statements are thread safe
> assuming that 'thread_vector' protects its operations:

> thread_vector<int> global_vector; // global so another thread can
> access it

>   void monitor() {
>      while (1)
>        if (global_vector.size() > 0 && global_vector[0] != 0)
>          break;
>      std::cout << "global_vector[0] != 0\n";
>    }

>  Here is another function which is running in a separate thread:

>   void process() {
>      while (1)
>        if (global_vector.size() > 0) {
>          int first = global_vector[global_vector.size() - 1];
>          global_vector.pop_back();
>    }

This is a great example... the && itself becomes the source of this
problem since a readlock on both size() and operator[]
is useless since it gives up the lock in between the two.  I'll make a
comment about this in just a moment.

>  Do you think a program having your "thread safe" containers running
>  these two function is thread safe? Well, hopefully you are only
>  programming things which will not cause harm to living things...

please don't assume that a theoretical discussion (or, in this case, a
"wishful thinking" discussion) is reflective of what I churn
out for a living.  You made a false assertion, then judged me based on
that assertion, silly.  To set the record strait, I
brainwash chimpanzees for urban counterserveillance.  It's a living.

>  Thanks for filling me in on the use of 'char_traits': Having
>  implemented the IOStreams library which makes heavy use of character
>  traits I'm well aware of the traits approach and, yes, it is handy to
>  do certain things.

Hey, glad I could help.  Please don't be offended if I overexplain
things to you... this isn't just for your edification, but for mine and
for the onlookers'.  I could be blowin' smoke... likewise, not everyone
here is an author of a book nor have they all implemented their own
IOStreams libraries.

> Allocators are not intended for this use but it looks as if you can
> hijack this mechanism for this purpose in a portable fashion! That is,
> the thread safe allocator can be provided by a third party library and
> the implementation is only required to deal with their internal thread
> safety which is a reasonable requirement and does not make the user
> dependent on whatever interfaces the impelmenter chooses.

now hang on a second... what you JUST proposed was what I was
suggesting in the first message... write your own
allocator.  I've done this.  It's just that allocator did not go far
enough to do what I would "LIKE" it to do (whether that is .
But I went one further and said that I want locking on a coarser grain
"if possible".  And it is possible... adaptors.  I was
simply hoping for something a tad more portable because, as I said,
forwarding all of the functions is a serious pain in the
butt... especially if I can write a traits object that provides the
before and after functions...

> It is tempting to use a traits class for thread
> safety but: Look closer and you will find that there is no character
> traits object! There is a character traits class with a bunch of type
> definitions and a bunch of static functions but no object. This is
> very different from something like the allocator class for which
> there are indeed objects! ... and to associate a lock with a
> container it is useful to have an object where the lock object can
> be stored. Traits don't have such a place.

Fine (groan)... no soup for you.  Take a journey to the fantastic world
of make-believe where, in fact, there is a parameter
to a collection template that is another class object which defines at
least 4 functions (lockread, unlockread, lockwrite,
unlockwrite).  If it ends up making an object that it needs to use for
locking then good for it... it has crossed over from a
no-overhead traits object to an overhead traits object.

And if "traits" is what is causing the confusion, by all means, give me
another word to use.

and to hopefully get something out of this... how about this for a
running opinion of container locks:

------------------------------------------------------
If you are going to lock a container, it may not be enough to just
create mutual exclusion within the container itself.  What is
needed is the cooperation of all things that may modify and examine the
container.   This includes iterators, algorithms, and
even programmers... the third inclusion which might make the entire
concept of thread-safe container unattainable.
------------------------------------------------------


> > Hmmm... perhaps the construct to which I was referring is
> > unfamiliar.
> No, it is not and I went down the same road until I realized that I'm
> walking into the wrong direction: It looks like the easier path but it
> has serious pitfalls and is looming users into a false feeling of
> security.

I have no doubt that you are right.  But still, life goes on and we
find ways to make our programs thread-safe.  The question remains...
how much protection can we guarantee, and at what point is it no longer
possible to guarantee protection (after all, if there are an enumerable
number of functions to simple avoid, then we avoid them, content that
we CAN write thread safe code (or at least assign our implementors to
do it) without an advanced degree in thread-safe-ology).



Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> I wouldn't be.  Mr. Kuehl has written an implementation of the
> <iostream> classes, so he's very much familiar with the traits idiom.
> Why he chose to use namespaces instead of traits is anyone's guess,
> but I do know he understands traits.>

With the exception of a handful of people on these discussion boards, I
recognize few names.  Heck, I have to check the top of the message to
remind me of mine.  Of course, I do know people who have written an
implementation of a stack, but I'll be a shucked oyster if they are an
authority on stacks... :-)  Also, "Mr. Kuehl" is more than capable of
laying out his credentials for me and has already done so.

> I'm not sure why you mention exception safety here.  Different topic
> all together.>

when discussing changes to the standard library, exception safety is
always topical since exception safety is one of the prime concerns
surrounding the standard library.  Heck, it may turn out that a traits
object (not necessarily for the purposes of thread safety, mind you)
DOES compromise exception safety...  At least put the possibility down
on your checklist.

> I'm not sure that a collection_traits object would ever be useful.  In
> any case, you missed Mr. Kuehl's point, since such a trait object is
> next to useless here.  This is too low of a granularity for thread
> synchronization.

I'm not sure I have missed his point, but read the response I gave to
him and see if you still believe that.  I don't want a thread sync
discussion to degenerate into things the implementation "might do"
wrong and then using that as a reason not to investigate the limits of
what we CAN do right...  I have a strong opinion of what I would "LIKE"
to be true, and I have ideas about how to pursue that (even a closet
full of half-cocked ideas), and I have very strong opinions that end up
biting me on the butt.  But every time I hit a wall I reassess and try
again.

> constructs.  No, what's needed is an object level lock.  You apply the
> lock before your first access to the object and after the last access
> to the object (don't misread what I'm saying here... you'll want to
> unlock ASAP, but not until the last access that's a part of
> the "transaction" you're attempting on the object).  Unfortunately,
> such locks can't be automated within the object itself, but it's still
> essential that you don't move locks too far down in the code.>

So the question seems to be... how far is too far.  And, for the
purposes of a thread-safe STL... is there ANYWAY AT ALL to provide this
automatically, and if not, then what are the BOUNDARY conditions of
what CAN be protected.

For instance:  back() may indeed be invalid if someone sneaks a pop_back
() in between your empty() and your back().  However, this can be
mitigated by a back() that throws an exception.  This removes the space
between empty() and back(), bringing the operation closer to being
atomic.  We may still be far from perfect, but we are closer than we
were two sentences ago...

> Locks can be secured using a RAII mechanism to insure unlocks.  Beyond
> this, threads add little to the concern of exception safety that I can
> see.  The "state of the object" in the face of an exception will be
> the same wehter the code is executed in a seperate thread or not.

ok... RAII... good thing to know.  <scribbles note>.  And as I was
thinking about it... front() and back() become very problematic as they
may disappear after the lock has been released but before the
reference is used.


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,

this has become a fairly long article... Thus, let me point out, that
the really interesting part, namely an idea how a thread safe container
might be created, comes at the end. This idea occured to me after
writing
most of the article and I think what I wrote before is still reasonable.

In article <8fa2g5$5ve$1@nnrp1.deja.com>,
  Michael Hays <icarus_rising@yahoo.com> wrote:

This discussion has moved a fair bit towards kind of personal attacks
and
I want to get away from this again. I think support for thread safety in
the standard library is important and thus I would prefer to solve the
technical problems rather than getting bogged down in a flamewar until
the moderators cut it down.

To bring this back to a technical level, I think we should synchronize
our views of the problem and discuss on this level. So I will start out
to state the problem and then answer the original article with my view
of the problem made clear.

To make a class useful in a threaded environment, several things have
to be synchronized to avoid corruption of invariants due to different
threads modifying the same entities:

- Operations on an entity have to prevent that global resource, ie.
  resources shared with another entity which might be used
simultaneously,
  are corrupted due to simultaneous access from multiple entites. For
  example, the memory allocation mechanism, be it an allocator or
  new/delete, can only be accessed by one thread at a time.

- Care has to be taken that only one thread changes an entity at a time
  to prevent the entities internal corruption. While a thread changes an
  object, no thread shall be allowed to use non-mutating operations,
too,
  because the results could be inconsistent. However, multiple threads
  might be allowed to run non-mutanting operations simultaneously.

- It has to be possible to group multiple operations on an entity into
  some sort of a transaction during which only one thread can modify the
  entity to allow reading the entities state (eg. a containers size)
  and taking actions depending on this state (eg. reading the last
  element in a container).

Note, that this discussion assumes that objects are constructed in a
thread safe manner without any thread protection. This clearly hold
for object constructed on the heap or on the stack unless during
construction of the objects another thread is spawn to which the
object is known. This is, however, not made with any standard objects
(or at least, a standard library should not do it unless it takes care
to prevent corruption). Whether thread safe construction can be assumed
for statically constructed objects, ie. objects with static linkage like
eg. global objects, is a questionable.  However, a simple requirement
imposed by the library can guarantee this, too: An application is not
allowed to create a thread accessing one of the libraries global objects
prior to entering 'main()' at which time all objects with static linkage
are constructed.

The first requirement is completely local to the entity and should be
of no concern to the entities user. For the purpose of the standard
library, there are only very few global resources used internally by the
library and an implementation for a threaded environment should protect
them. Those I can remembers are:

- The memory pool maintained by 'operator new()' and family and
'malloc()'
  and family. The standard allocator works on top of these functions and
  if these functions are defined in a thread safe fashion, there is no
  need to modify the allocator. Note, that all of the operations in this
  catagory share a common property which allows to make them thread safe
  for themselves without help of eg. the user: There is just one call
  which does the whole operation. There is no need (nor a way) to first
  gain information and then perform the operation or to perform multiple
  operations depending on the internal data structure not being mutated
  in between these calls. If another thread chooses to access the memory
  pool between to calls, this does not cause any problem!

- The 'xalloc()' and the 'sync_with_stdio()' methods in 'std::ios_base'.
  The call to 'xalloc()' also provides a form a transaction in itself
and
  there is not much to say about it. 'sync_with_stdio()' is more
critical
  because it might affect the behavior of writing to one of the standard
  stream objects if it is called from a different thread. It is not
  critical, though, because the requirements on it are basically that it
  is called prior to any I/O operation. Thus, a thread already writing
to
  one of the standard streams while 'sync_with_stdio()' is called, is
  flawed anyway. Probably it would be possible to include this call into
  a locking mechanism for the standard stream objects.

- The global 'std::locale' object which is used whenever an
'std::locale'
  object is used with a default constructor which is relatively
frequent,
  although you rarely see locales. For example, a 'std::locale' object
is
  default constructed whenever a stream is constructed (actually, if the
  stream buffer is constructed, too, there are two 'std::locale' objects
  default constructed). Still, this resource can be protected easily
  underneath because, again, multiple calls to the corresponding methods
  do not depend on the underlying resource remaining unchanged, that is,
  there is no need for some kind of transaction.

This discussion does not include all global resources in the C standard
library although I think that these global resources also share the
property of causing no problems if used by multiple threads if the
access
functions prevent resource internal corruption. Thus, I don't think
that there is any need to worry about protection of global resources
because the obvious approach to protect them is leave the protection
to themselves, ie. putting the burdon the library implementor. My
understanding is that any library implementor targetting multi-threaded
systems already does this (that is, the only implementation I'm aware of
that does have code for protection of global resources at least
optionally
built-in is mine; ... and this will probably be changed relatively soon
because I think this is all a library implementor needs to do for thread
safety - but see below...).

Preventing entity internal corruption due to simultaneaous can be done
by
functions called on entering and leaving a function, basically what is
done in IOStreams with the 'sentry' objects: When entering an inserter
or
an extractor, a 'sentry' object is constructed which prepares the stream
for the operation at construction and does cleanup on destruction. Using
an object for this has the advantage that the function called on
function
exit has not be present in every single execution path which might leave
the function and also the cleanup is executed even if the function is
left due to an exception being thrown.

Note, that I explicitly said that this *can* be done to prevent internal
corruption. This is, however, not the only option! Another option how to
prevent internal corruption is much easier to implement: Simply making
simultaneous use of the same object undefined behavior! Wow, this option
sucks rocks! Putting the whole burdon on the poor user of the object!

Hang on! The poor user has to carry this burdon anyway and this is where
the third requirement mentioned above comes in, that is the second and
the third requirement are not at all independent and can be used
together
to form a rather effective approach to thread safety:

Typical uses of objects are "transaction like" in the following sense:

- The program only behaves consistent if data read from an entity does
  not change until a certain sequence of operation is completely
  performed. For example, to read the last element of a 'std::vector'
  - the 'std::vector's size has to be read resulting in an index n
  - the 'std::vector's n-th element has to be read
  These three (!) requests to the 'std::vector' (reading the
  size, obtaining a reference to the n-th object, and reading the
  referenced object) behave only consistent if the 'std::vector' is not
  resized between these three operations. Corresponding problems occure
  for algorithms processing all elements of one or even more sequences
  like eg. 'std::copy()'.

- The program only behaves consistent if multiple mutations to an
  entity are performed before the corresponding invariant is restored
  again. Here the destination of 'std::copy()' fits in as an example:
  If we are copying a container to another one, the whole consistence
  gets messed up if an element is removed by another thread between
  two copies.

Basically, concerning the standard containers these are not usable in a
thread safe fashion without grouping multiple operations into some form
of transaction. Here "transaction" basically only refers to exclusion
of concurrent changes to the entities. Data base transactions also have
features like "atomacy" which means that either the whole thing is
successful or nothing. This is not required for thread safety at all
- what is, however, required is that each thread leaves a consistent
state but this is not specific to threads: This alway has to be the
case, independent from threads. Back from the detour on transactions:
To access a containers element, you first have to get a handle to the
object and then you can use the object. The only container operations
which behave differently are some of the functions inserting elements
into the container - but write-only containers are rarely that useful.

As a consequence, the typical scenario of user code using a container
looks somewhat like this:

  {
    readlock lock(cont);
    // read data from the container 'cont'
  }

or

  {
    writelock lock(cont);
    // read and modify the container 'cont'
  }

Basically, the braces delimit the scope of a "transaction" and the lock
objects prevent accesses from other threads. How the locks associate a
common mutex (or whatever) to synchronize operations on the container is
basically irrelevant for the general discussion. For the standard C++
library I think that the allocator object associated with a container
is a good an portable place to put the lock in (well, I'm not yet sure
what has to with the allocator object eg. on assigning containers:
if the allocator object is to be copied, too, this would cause real
problems with the approach of putting the lock into the allocator).

Now back to the discussion of the entities internal integrity: If the
entities are only accessed by one thread at a time due to thread safety
considerations of the entities user, what is the point of protecting
the members again? It only slows down multi-threaded code (for single
threaded code it would be possible to always turn the locking code into
nops) and complicates the library interface and implementation. There is
no benefit with respect to thread safety! None - nada - keiner - zip!

For the standard containers, the user of the container has to protect
the user code against damages due to other threads mutating the
container
or the container is only known to one thread and not a problem to thread
safety in the first place. This protection is sufficient for the
container
integrity wihtout additional protection within the container.

That does not say that functions optionally called on entry and exit of
methods could not be useful for other purposes than thread safety, eg.
debugging code to verify that the objects are indeed properly locked.
This is "nice to have" but not essential, though. Well, people coming
from a different background might disagree and pretend that verifying
assertions is absolutely necessary (any Eiffel -> C++ converts
listening? :-)

Basically, what an implementation of the standard library has to provide
for thread safety is the following:

- Proper protection of all global resources against simultaneous uses
  which would result in violation of the internal consistency. This
  protection is completely done underneath and invisible to the user. It
  basically comes in the form of a guarantee which say that the standard
  library is implemented thread safe.

- A way to associate the synchronization objects, eg. mutex locks (yes,
  I know that the objects called mutexes with MFC are actually very
  different and what I want is a "critical section"; however, the
  naming I'm used to calls a "critical section" the section of code to
  be protected and a "mutex" the way how to achieve this protection -
  these names have not to match class names in an actual implementation)
  with entities to be protected. Since we are talking about fitting the
  thread safety mechanism onto the current standard library, I can only
  see the allocator object to be hijacked for this purpose. An
alternative
  would be wrappers for the entities adding access to a lock object.

- A clear documentation which entities have to be protected against
  simultaneous accesses. For example, there is no need to protect locale
  objects or their facets: These are immutable anyway and they can very
  well maintain their internal integrity on their own (when merging
  facets some reference counts have to be protected during construction
  and destruction of locales).

>From these requirements derives my intention to control the thread
safety
of the standard library by two namespaces: The entities requiring
internal
protection would be reimplemented in the namespace for the multi-thread
implementation, the rest would be just dragged over. Basically, in some
configuration file the choice would then be reduce to this:

  #if defined(_IS_MULTI_THREADED)
    namespace std = _Std_multi_threaded;
  #else
    namespace std = _Std_single_threaded;
  #endif

... and the implementation of both alternatives would not be obfuscated
by conditional compilation.

I hope I have provided a clear and technical correct description of what
the problem - and basically the only viable approach to its solution I
can see - is. I hope it is reasonable complete and I'm not missing some
serious point (if there is such a problem, I would really appreciated
being pointed at it). If there are other approaches how to solve the
*whole* problem, not just entity internal consistency, I would be
interested in these, too.

> > However, the result of making the standard library thread safe are
in
> > no case "thread safe containers" because there is no such thing in
the
> > first place!
>
> My original idea for the container_attributes was to emulate an old
old
> idea of ":before" and ":after" methods which were
> implicitly called for the user at the beginning and end of a method
> (not ctor's or dtor's) to allow the locking and unlocking of
> resources  (of course, for the container_traits, I would have to fit
> into the standard collections calls to
> "readbefore/readafter" and "writebefore/writeafter" which would call
> those functions as defined in the traits object.

I'm not objecting ":before" and ":after" methods in general and if you
can make a good point what they are useful and how a resonable interface
should look like, I wouldn't mind to fit them into my implementation.
What I'm saying, however, is that these methods do not help you with
thread safety because you are applying locks at the wrong level of
granularity and you are actually even accessing unprotected data, unless
you are protecting this otherwise:

  cont[i] = 17;

The execution of 'operator[]()' is protected and it will return a
reference which is safe until the ":after" method is called. Afterwards,
the reference might go away or another thread might suffer from partial
reads of the i-th element of the container: There is no lock when the
[built-in] 'operator=()' is executed. Although the container protects
its internal integrity, this does not help you anything with respect to
thread safety. The only help I can imagine from a ":before" method is
an assertion that the proper lock (read vs. write) is indeed hold.

> Heck... even the routines in algorithms could make use of these.

Basically, this is a move into the right direction: Get away from
individual entities to do their internal locking and consider
transactions
for locking (although my understanding is that you want ":before" and
":after" methods for algorithms for whatever purpose - not only
locking).
Using the standard algorithms for locking purposes would, however, imply
a major change to typical standard library implementations: You would
have
to be able to infer the container to be locked from an iterator unless
you
would settle for element level locking which is, in general,
insufficient
because another thread might eg. erase the element from a container.
Well,
the container could check object locks before erasing them...

> Remember though that the default function for these before and
> after calls is an empty inlined function, which translates to a "pay
> for what you use" kinda of feature.  This is an attribute of a
> few languages outside of C++ and it was for this exact purpose
> (resource locking) that they seemed so useful.  I really
> wanted to emulate this behavior in the containers... (heck, I think
> this was a feature Stroustrup was trying to get into the
> language... at least according to his D&E book). And besides, it
really
> isn't JUST for the readbefore/readafter, but for
> other things as well (I won't get into it here though... we'll keep
the
> thread topical)

Having user defined functions called at whatever condition seems to be
reasonable would, of course, add a lot of new possibilities. However,
it does not help you with thread safety for the standard containers
which
is what I'm saying the whole time. If you want user defined functions to
be called at whatever condition seems to be reasonable, say so! With a
reasonable application I would consider adding it to my implementation
(not with high priority, though...). Thread safety is no such
application.

> > Can you please explain me how the following statements are thread
safe
> > assuming that 'thread_vector' protects its operations:
>
> > thread_vector<int> global_vector; // global so another thread can
> > access it
>
> >   void monitor() {
> >      while (1)
> >        if (global_vector.size() > 0 && global_vector[0] != 0)
> >          break;
> >      std::cout << "global_vector[0] != 0\n";
> >    }
>
> >  Here is another function which is running in a separate thread:
>
> >   void process() {
> >      while (1)
> >        if (global_vector.size() > 0) {
> >          int first = global_vector[global_vector.size() - 1];
> >          global_vector.pop_back();
> >    }
>
> This is a great example... the && itself becomes the source of this
> problem since a readlock on both size() and operator[]
> is useless since it gives up the lock in between the two.

Cool! What am I discussing for all the time? If this is so obvious, why
are you asking for 'size()' and 'operator[]()' locking anything? You
need
to determine the size of the object in some way before you can access
them
(if you just know the size, there is no problem with threading and no
need to lock anything, again). To rely on the size, reading the size and
the access have to go into the same transaction. My whole point is that
you cannot get this transaction from fitting locking into the container
because the container cannot tell when the transaction will end without
the user's help.

> I'll make a comment about this in just a moment.

Unless the following paragraph is the comment, I have missed it...

> >  Do you think a program having your "thread safe" containers running
> >  these two function is thread safe? Well, hopefully you are only
> >  programming things which will not cause harm to living things...
>
> please don't assume that a theoretical discussion (or, in this case, a
> "wishful thinking" discussion) is reflective of what I churn
> out for a living.  You made a false assertion, then judged me based on
> that assertion, silly.  To set the record strait, I
> brainwash chimpanzees for urban counterserveillance.  It's a living.

Either it is my non-native English or the [unintentional] ommision of
"if assertions are not met due to a false assumption of thread safety"
and probably also a restriction to "unintended harm" which caused you
to assume I'm making any assumption about what you are doing.

> > Allocators are not intended for this use but it looks as if you can
> > hijack this mechanism for this purpose in a portable fashion! That
is,
> > the thread safe allocator can be provided by a third party library
and
> > the implementation is only required to deal with their internal
thread
> > safety which is a reasonable requirement and does not make the user
> > dependent on whatever interfaces the impelmenter chooses.
>
> now hang on a second... what you JUST proposed was what I was
> suggesting in the first message... write your own allocator.

I might be wrong but I'm pretty sure this is quite different: What I
understood is that you want to write an allocator to create a thread
safe container which protects its internal consistency (at least this
is what I'm assuming due to your mentioning of ":before" and ":after"
methods or its equivalents). What I'm proposing is to use the allocator
for holding the synchronization object and potentially also for
protection
of resources shared between containers. I'm not proposing at all to
change the container to protect its internal data! The allocators are
just a place where there synchronization object is to be placed.

>  I've done this.  It's just that allocator did not go far
> enough to do what I would "LIKE" it to do (whether that is .
> But I went one further and said that I want locking on a coarser grain
> "if possible".  And it is possible... adaptors.  I was
> simply hoping for something a tad more portable because, as I said,
> forwarding all of the functions is a serious pain in the
> butt... especially if I can write a traits object that provides the
> before and after functions...

... and I had though that I had explained at great length that your
courser grain is *far* too fine grained to aid with thread safety... :-(

> and to hopefully get something out of this... how about this for a
> running opinion of container locks:
>
> ------------------------------------------------------
> If you are going to lock a container, it may not be enough to just
> create mutual exclusion within the container itself.  What is
> needed is the cooperation of all things that may modify and examine
the
> container.   This includes iterators, algorithms, and
> even programmers... the third inclusion which might make the entire
> concept of thread-safe container unattainable.
> ------------------------------------------------------

OK. I can agree with this one. However, after the above discussion I
think
it is safe to change it to become

  ------------------------------------------------------
  What is needed for thread safe access to containers is the cooperation
  of all things that may modify and examine the container. Basically
  this means that the programmer has to wrap up groups of container
  accesses some kind of transaction preventing simultaneous access from
  other threads while one group is active - there is no such thing as
  a container handling thread safety for the programmer (at least not
  with the standard C++ library interface to containers).
  ------------------------------------------------------

This statement might not what is desired but I prefer facing the
problems rather than pretending they are not there until it is too late
to face them. Also, it requires less changes to the standard C++ library
implementation which means less work for me ;-)

Hm... Thread safety without user interaction being the goal, here is
an idea: ":before" and ":after" methods are definitely not sufficient
because the results returned from methods are not reliable when received
by the caller. Thus, just simply adding a few calls to lock data does
not do the trick but there may be way rewriting the containers.

Basically the idea is this: As an effect of calling a container method
the container becomes locked automatically until no result obtained from
the container is used anymore. Whether this works out to be reasonable
I have no idea but lets persue this. Here is an excerpt of the the
'std::vector<T>' declaration I have in mind:

  template <typename T, typename Alloc>
  class vector<T> {
  public:
    struct reference {
      reference(lock& l, T& e): lck(l), elm(e) { l.acquire(); }
      reference(reference const& r): lck(r.lck), elm(r.elm) {
        l.acquire(); }
      ~reference() { lck.release(); }
      operator T const& () const { return elm; }
      reference& operator= (T const& t) { elm = t; }
    private:
      lock& lck;
      T&    elm;
    };
    struct size_type {
      size_type(lock& l, size_t s): lck(l), sz(s) { l.acquire(); }
      size_type(size_type const& st): lck(l.lck), sz(l.sz) {
        l.acquire(); }
      ~size_type() { lck.release(); }
      operator size_t() const { return sz; }
    private:
      lock&     lck;
      size_type sz;
    };

    size_type size() const { return size_type(lck, end - beg); }
    reference operator[](size_type const& s) {
      return reference(lck, beg[s]); }
    // ...

  private:
    T*    beg;
    T*    end;
    lock& lck;
  };

With these definition, it would be possible to obtain the size and hold
it until the container accessed. While holding the size, the container
would locked. Here is a sample use during which would be thread safe:

  int x;
  cont.size() > 0 && x = cont[cont.size() - 1];

The first call to 'cont.size()' receives a temporary object which
is dstructed at the end of the full expression, thereby defining a
transaction for the duration of the full expression. A longer
transaction can be obtained by using a variable to hold the size, eg:

  {
    std::vector<T>::size_type sz = cont.size(); // transaction start
    int x = cont[sz - 1];
  } // transaction end

Of course, this approach also causes problems:

- Failing to release objects returned from the container, eg. because
  passing them around, would leave locked containers.

- Due to the use of proxies, the container requirements as currently
  stated in the standard, do no longer hold. Maybe, this could become
  another argument to change the container requirements.

- It is easy to fail locking the container:

    { int sz = cont.size(); int x = cont[sz - 1]; }

- It is easy to unintentionally create dead-locks when using multiple
  container because it is not at all visible that containers are locked.

- ... (probably there are also other implications).

This approach requires a fairly different implementation of the standard
containers and the implementation has to be created in such a way to
allow this. However, since an intrusive approach using a traits or an
allocator class does not do the right thing, it might be a suitable
option. ... and, just to contradict what I have said above, maybe a
thread safe container is indeed possible...
--
<mailto:dietmar.kuehl@claas-solutions.de>
homepage: <http://www.informatik.uni-konstanz.de/~kuehl>


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <39182EE8.174600CD@physik.tu-muenchen.de>,
  Christopher Eltschka <celtschk@physik.tu-muenchen.de> wrote:
> It doesn't relief you from doing synchronisation yourself - but
> it helps for synchronizing those parts which the user isn't
> even aware that it is shared (think ref counted strings, f.ex.).

Ref-counting is a different animal all together.  This will need
internal synchronization, since it's shared *between* objects.  This is
no different than protecting global data, as Mr. Keuhl pointed out.
What was suggested was a lock used during inserts, etc, of the
container.  This is too fine grained and simply adds overhead when not
needed for the majority of uses.  It's much better to use an external
lock in this case.

> I think a traits class could be quite useful; not only with
> synchronisation - f.ex. do you want vector<bool> to be packed
> (as in the standard) or unpacked (as in the original STL)?

This is something all together different again.  I'm not sure it's
worth the overhead and complexity, but that's definately open for
debate and thought.

> >  It will add tremendous speed costs while addressing
> > only a very small subset of uses of the object.
>
> Since the standard traits class would have empty inline
> lock/unlock, the performance hit would be close to zero.
> Only if a (non-standard) syncronisation container_traits
> is given to the container, it will cost any time for that.

And when we give it a trait that locks/unlocks for real it adds this
overhead for 100% of the useage, while only 2% needs the lock since the
other 98% uses an external lock for the reasons I pointed out.  This is
the performance cost I was addressing.

> >  For instance, imagine
> > trying to use std::copy to copy items from one container to another.
> > If the locks were left at the level you've specified with
> > container_traits then seperate threads could add/remove/etc items
> > between each insertion within the copy algorithm, resulting in
> > something very much unexpected.
>
> If your program does this, yopur program is broken.
> But without thread safety, it could happen that two
> containers make concurrent calls to the same allocator,
> and therefore f.ex. both get the same memory back.

I think you missed the point.  Of course you need locks, but the locks
must be external since it's required around a set of calls on the
object.

--
William E. Kempf
Software Engineer, MS Windows Programmer


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> And when we give it a trait that locks/unlocks for real it adds this
> overhead for 100% of the useage, while only 2% needs the lock since
the
> other 98% uses an external lock for the reasons I pointed out.  This
is
> the performance cost I was addressing.

I have reservations about THIS particular point.  If 98% of the people
do NOT want the locks, then those people don't need to use the locks.
The solution would be, of course, to seperate those features that
increase overhead and make them optional for those 2% who DO want it.
I haven't seen any comments to the contrary

(on this thread anyway! ;-) )


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> This discussion has moved a fair bit towards kind of personal attacks
> and I want to get away from this again.

Amen brutha!  And before we get into this, I've read through your
message already and I really like where this is going.

I'm still mulling over your last message, so I will only pick out the
things that I see so far.

> - Care has to be taken that only one thread changes an entity at a
time
>  to prevent the entities internal corruption. While a thread changes
an
>  object, no thread shall be allowed to use non-mutating operations,
>  too,  because the results could be inconsistent. However, multiple
threads
>  might be allowed to run non-mutanting operations simultaneously.

Definitely.  I don't know about your implementation, but looking
through mine, I see no indication in any algorithm that tells whether
it is mutating or not.  It would seem that the iterator being passed in
could be constant, EXCEPT for the fact that the iterator itself has to
change in order to move through the collection.  Is there an in between
road that promises that although an iterator might change, it will not
assign to the dereferenced data?  Without such a convention, algorithms
require a bit mor familiarity (fortunately, I have a handy-dandy
reference manual for the EXISTING algorithms)

> eg. global objects, is a questionable.  However, a simple requirement
> imposed by the library can guarantee this, too: An application is not
> allowed to create a thread accessing one of the libraries global
objects
> prior to entering 'main()' at which time all objects with static
linkage
> are constructed.

That's kind of odd.  Is there a way to tell that you have entered main
() without making the programmer set a flag?  Some sort of global that
launches a singleton builder sounds like a solution, albeit a slow,
bloated solution (bloated meaning that it might "turn on" certain
global objects that may only conditionally get used.

> Preventing entity internal corruption due to simultaneaous can be done
> by
> functions called on entering and leaving a function, basically what is
> done in IOStreams with the 'sentry' objects: When entering an inserter
> or
> an extractor, a 'sentry' object is constructed which prepares the
stream
> for the operation at construction and does cleanup on destruction.

This is where I fall apart.  I purchased "Standard C++ IOSreams &
Locals" by Langer & Kreft last week (through the internet, so I'm still
waiting for it), so I'll certainly bone up on this sort of thing with
all due speed...  ;-)

> Typical uses of objects are "transaction like" in the following sense:

We were tossing the idea around in the office and table-lock/record-
lock came up an awful lot.  It REALLY looks like it falls into the
"crawling program" you mentioned earlier, but it did seem logical that
the reference you got from the iterator created a lock on at LEAST
the data being pointed to until the reference was released (a reference
counting kinda reference... don't hit me though, I know it isn't a well-
formed idea).  The concept was that you COULD lock the whole container
up, but it was more reasonable to lock portions of the container, and
to differentiate between read locks and write locks.  But I'll hold
off... you say something way down in the end of your message that
really gets exciting.

> - Having user defined functions called at whatever condition seems to
be
> reasonable would, of course, add a lot of new possibilities. However,
> it does not help you with thread safety for the standard containers
> which

yeah... I'm gettin' the drift.

> is what I'm saying the whole time. If you want user defined functions
to
> be called at whatever condition seems to be reasonable, say so!

So!  When all you have is a hammer, everything looks like a nail.  I
already had the idea in my head for other things and just extended it
to one more thing... all to grand comedic effect.


> is what I'm assuming due to your mentioning of ":before" and ":after"
> methods or its equivalents). What I'm proposing is to use the
allocator
> for holding the synchronization object and potentially also for
> protection

you are right... my thoughts on this subject have been revamped several
times since my original post.

>    struct reference {
>     reference(lock& l, T& e): lck(l), elm(e) { l.acquire(); }
>      reference(reference const& r): lck(r.lck), elm(r.elm) {
>        l.acquire(); }
>       <SNIKT>

This whole section is very, VERY cool stuff...   I did something
similar to propogate certain special commands through operator[] in a
map-of-map-of-map-of-.... directory structure  (sometimes I wanted to
create "directories" as I moved deeper into the structure, sometimes I
wanted it to throw early... all depended on a reference object bubbled
out at each function call).   This is kind of a smart pointer that
gives back more smart pointers (smart references?)  Anyway... I'm off
to compile this example and play around with it...



Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michael Hays wrote:

[...]

> Definitely.  I don't know about your implementation, but looking
> through mine, I see no indication in any algorithm that tells whether
> it is mutating or not.  It would seem that the iterator being passed in
> could be constant, EXCEPT for the fact that the iterator itself has to
> change in order to move through the collection.  Is there an in between
> road that promises that although an iterator might change, it will not
> assign to the dereferenced data?

Yes: Use container::const_iterator. It's there for exactly
that purpose.

[...]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <8fe96a$psb$1@nnrp1.deja.com>,
  Michael Hays <icarus_rising@yahoo.com> wrote:
>
> > And when we give it a trait that locks/unlocks for real it adds this
> > overhead for 100% of the useage, while only 2% needs the lock since
> the
> > other 98% uses an external lock for the reasons I pointed out.  This
> is
> > the performance cost I was addressing.
>
> I have reservations about THIS particular point.  If 98% of the people
> do NOT want the locks, then those people don't need to use the locks.
> The solution would be, of course, to seperate those features that
> increase overhead and make them optional for those 2% who DO want it.
> I haven't seen any comments to the contrary

You misread what I wrote.  Read the quote above carefully.  Here's an
example:

std::copy(vt1.begin(), vt1.end(), std::back_inserter(vt2));

In order to make this call thread safe we _MUST_ use an external lock.
There's no way around this.  So, we get (psuedo code, since c++ doesn't
have thread primitives).

lock(vt1);
std::copy(vt1.begin(), vt1.end(); std::back_inserter(vt2));
unlock(vt1);

98% of the cases (like most statistics found on the net this is made up
on the spot, but I'll bet good money that this figure is at best
conservative) require an external lock such as this.  Now every access
into the container in this example is also attempting to do a lock (and
locks are expensive).  So, if vt1 had 1000 elements we've done (at
least) 1001 locks here, when we could have done 1 lock.  The
granularity is too fine here.  Only in rare cases will an external lock
not still be needed, while the internal lock has made a HUGE impact on
our performance for all cases.

So, even if the internal lock were optional, turning it on would be a
mistake for the vast majority of situations regardless of whether or
not you need thread synchronization to the object.

Remember, even a statement as simple as this:

vt1[0] = 2;

would require an external lock.  How many people would realize this?
You're safer to require the external lock all of the time so that users
won't do something like the above with out one.

--
William E. Kempf
Software Engineer, MS Windows Programmer


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <8fe8pe$pm7$1@nnrp1.deja.com>,
  Michael Hays <icarus_rising@yahoo.com> wrote:
> >    struct reference {
> >     reference(lock& l, T& e): lck(l), elm(e) { l.acquire(); }
> >      reference(reference const& r): lck(r.lck), elm(r.elm) {
> >        l.acquire(); }
> >       <SNIKT>
>
> This whole section is very, VERY cool stuff...   I did something
> similar to propogate certain special commands through operator[] in a
> map-of-map-of-map-of-.... directory structure  (sometimes I wanted to
> create "directories" as I moved deeper into the structure, sometimes I
> wanted it to throw early... all depended on a reference object bubbled
> out at each function call).   This is kind of a smart pointer that
> gives back more smart pointers (smart references?)  Anyway... I'm off
> to compile this example and play around with it...

This is the standard RAII mechanism I mentioned a few days ago.  This
is done frequently by C++ programmers in their thread code.  However,
the lock in question still must remain an external lock for all of the
reasons we've given you.  Let's assume that we have some primitive
mutex object with lock and unlock members.  The following is an example
of what one might do (pseudo code, and with some things I would *NOT*
recommend doing in real code, such as inheriting from std::vector).

template <typename T>
class synchronize
{
public:
   synchronize(T* obj) : _obj(obj) { _obj->lock(); }
   ~synchronize() { _obj->unlock(); }
private:
   T* _obj;
};

class safe_int_vect : public std::vector<int>
{
public:
   void lock() { _mutex->lock(); }
   void unlock() { _mutex->unlock(); }
private:
   mutex _mutex;
};

Now we can write code like this:

{
   safe_int_vect vt;
   synchronize synch(&vt);
   vt.push_back(1);
   vt[0] = 10;
}

Notice that I've still left the lock external?  However, the thread
synchronization has been simplified to look like something similar to
what you have in Java.

--
William E. Kempf
Software Engineer, MS Windows Programmer


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,
In article <8fhscg$r3i$1@nnrp1.deja.com>,
  sirwillard@my-deja.com wrote:
> This is the standard RAII mechanism I mentioned a few days ago.  This
> is done frequently by C++ programmers in their thread code.  However,
> the lock in question still must remain an external lock for all of the
> reasons we've given you.

Note, that the approach to locking I have outlined in this thread
without using explicit locks actually also just "externalizes" the
locks by bundling the lock with the objects used to access the
container. That is, the external locks are still there but are implicit
in the returned objects. Having the locks being just implicit can, of
course, cause severe problems if the mechanisms are not used properly.

> However, the thread
> synchronization has been simplified to look like something similar to
> what you have in Java.

... and the semantics have been improved to provide control at a
reasonable level while the Java 'synchronized' approach only provides
this control if you define lots of classes and methods.
--
<mailto:dietmar.kuehl@claas-solutions.de>
homepage: <http://www.informatik.uni-konstanz.de/~kuehl>


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <8fp8aj$gs5$1@nnrp1.deja.com>,
  Dietmar Kuehl <dietmar.kuehl@claas-solutions.de> wrote:
> Hi,
> In article <8fhscg$r3i$1@nnrp1.deja.com>,
>   sirwillard@my-deja.com wrote:
> > This is the standard RAII mechanism I mentioned a few days ago.
This
> > is done frequently by C++ programmers in their thread code.
However,
> > the lock in question still must remain an external lock for all of
the
> > reasons we've given you.
>
> Note, that the approach to locking I have outlined in this thread
> without using explicit locks actually also just "externalizes" the
> locks by bundling the lock with the objects used to access the
> container. That is, the external locks are still there but are
implicit
> in the returned objects. Having the locks being just implicit can, of
> course, cause severe problems if the mechanisms are not used properly.

As you pointed out, however, this approach won't be compatible with the
standard, which prevents the return of proxy objects.  The same thing
can be (somewhat) achieved by using a wrapper instead of a returned
proxy.  Many attempts have been done on this scheme, most revolving
around a "smart pointer" that manages the locks.  This scheme, however,
requires a very large amount of knowledge on what exactly the wrapper
will do in order to avoid many pitfalls ranging from prematurely
releasing the lock to holding the lock too long.  It's honestly much
easier (and so usually much safer) to use an external lock with a RAII
mechanism.  This approach also has the added benefit that it's as
trivial to implement as it is to use.  KISS principle in action here.

> > However, the thread
> > synchronization has been simplified to look like something similar
to
> > what you have in Java.
>
> ... and the semantics have been improved to provide control at a
> reasonable level while the Java 'synchronized' approach only provides
> this control if you define lots of classes and methods.

I don't follow this.  I'm not an expert on Java, let alone on Java
threading issues, but it seems to me that this approach and the
Java "synchronize" key word should be identical (except that the Java
keyword is built in).  After all, you can use "synchronize" in Java to
protect either a method or an object.  Seems to be the same thing
here.  What am I missing?

--
William E. Kempf
Software Engineer, MS Windows Programmer


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,
In article <8f57tg$p8e$1@nnrp1.deja.com>,
  Michael Hays <icarus_rising@yahoo.com> wrote:
> HOWEVER... it sure would have been nice to have a sequence_traits
> member of the template to allow the programmer the ability to override
> the behavior of the insert/deletes.  (After all, char_traits is
> provided for std::string).  Allocator is pretty good, but if you
> redefine this action, then certain things that get run after calls to
> the allocator function can sort of work at odds with what you might
> want to do -- SPECIFICALLY, create a thread-safe container.

Creating a thread safe library is a all or nothing thing: Either you
are protecting all entities or your thread safety would be dwarfed.
Also, thread safety means different things to different people and I
think the only reasonable form of thread safety for the C++ standard
library is the lowest form of thread safety: All global resources used
by the library are protected but the objects themselves are not. That
is, you can use different objects simultanously from different threads
but one object only from one thread. The reason is simply that the
granularity of object specific protection is at the wrong level and far
too expensive for a reasonable application. Instead, an objects user
can easily lock individual objects explicitly at the right level. Have
a look at <http://www.sgi.com/Technology/STL/thread_safety.html> for a
more detailed and precise description.

That said, I think that it would be reasonable to have two separate
implementations of the standard C++ library, one being thread safe (in
the above outlined sence) and one not being thread safe. Well, actually
there are more variations (eg. a version doing bounds checking). I'm
experimenting a little bit with using different namespaces for this
feature.
--
<mailto:dietmar.kuehl@claas-solutions.de>
homepage: <http://www.informatik.uni-konstanz.de/~kuehl>


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

> Creating a thread safe library is a all or nothing thing: Either you
> are protecting all entities or your thread safety would be dwarfed.
> Also, thread safety means different things to different people and I
> think the only reasonable form of thread safety for the C++ standard
> library is the lowest form of thread safety: All global resources used
> by the library are protected but the objects themselves are not.

Hmmm... perhaps the construct to which I was referring is unfamiliar.
After reading the comment about putting different types of collections
into different namespaces, I'm rather sure of it.

First, I am not asking for the standard to change to support thread
safety.  Not at all.  I stand by the standard's support of exception
safety and its efficiency.

Second, take a look at the std::basic_char definition.  One of the
template parameters is another template called char_traits.  Take a
look at the definition for char_traits.  A user wishing to expand the
usability of the std::string functions (for example) could change the
underlying way in which a string works by providing a char_traits
object (and overriding the lt (less than), equal, length, etc).  An
example I remember from Herb Sutter's book, "Exceptional C++" shows how
to create a case-insensitive string class WITHOUT overriding
std::string along with every one of its members... In addition, said
programmer could pat himself on the back when he goes to write a case-
insensitive ostream and istream class only to find out that, waa-hoo,
char_traits are used in those as well.

This same technique could be applied to a "collection_traits" object.
In fact... it ALREADY partially exists inside the Allocator class.
However, if there were hooks into the insert and delete functions, then
a designer could arbitrarily assign more complicated activity to a
container as his/her project might require, WITHOUT bring in a whole
new library of classes for EVERY collection that he/she wanted to
mutate.  In other words -- write the thread safety locks for insert and
delete for a vector, using ITS collection_traits object, then reuse
that collection_traits object inside map, deque, ... whatever...

The alternative is to encapsulate the collection totally and write a
thread-safe wrapper.  Currently, this is how I have to do it...
however, because I loathe writing this sort of stuff repeatedly, I use
a threadsafe_adapter which takes a collection template and a collection
traits parameter and screws thread safety into the mix... The sad fact
is that I have to look through all of the standard collections and
override any and all member functions that might modify the collection
whether they be specific to map, vector, or common...

This also bring to light one glaring problem... you DO, in fact, gain
thread safety, but at the expense of adding a lot of exception handling
overhead to release the locks on the collection if an exception is
thrown.  Not doing so reduces the exception guarantee to "weak" or
potentially "none".  I have this crazy suspicion that if there *WERE* a
collection_traits object in the standard, they wouldn't be able to give
the "strong" exception safety we've come to expect... (FYI - "strong" =
the object is still intact after the exception.  "weak" = the object
could dies but it won't leak resources after an exception.)


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <8f76im$uua$1@nnrp1.deja.com>,
  Michael Hays <icarus_rising@yahoo.com> wrote:
>
> > Creating a thread safe library is a all or nothing thing: Either you
> > are protecting all entities or your thread safety would be dwarfed.
> > Also, thread safety means different things to different people and I
> > think the only reasonable form of thread safety for the C++ standard
> > library is the lowest form of thread safety: All global resources
used
> > by the library are protected but the objects themselves are not.
>
> Hmmm... perhaps the construct to which I was referring is unfamiliar.
> After reading the comment about putting different types of collections
> into different namespaces, I'm rather sure of it.

I wouldn't be.  Mr. Kuehl has written an implementation of the
<iostream> classes, so he's very much familiar with the traits idiom.
Why he chose to use namespaces instead of traits is anyone's guess, but
I do know he understands traits.

> First, I am not asking for the standard to change to support thread
> safety.  Not at all.  I stand by the standard's support of exception
> safety and its efficiency.

I'm not sure why you mention exception safety here.  Different topic
all together.

> Second, take a look at the std::basic_char definition.  One of the
> template parameters is another template called char_traits.  Take a
> look at the definition for char_traits.  A user wishing to expand the
> usability of the std::string functions (for example) could change the
> underlying way in which a string works by providing a char_traits
> object (and overriding the lt (less than), equal, length, etc).  An
> example I remember from Herb Sutter's book, "Exceptional C++" shows
how
> to create a case-insensitive string class WITHOUT overriding
> std::string along with every one of its members... In addition, said
> programmer could pat himself on the back when he goes to write a case-
> insensitive ostream and istream class only to find out that, waa-hoo,
> char_traits are used in those as well.
>
> This same technique could be applied to a "collection_traits" object.
> In fact... it ALREADY partially exists inside the Allocator class.
> However, if there were hooks into the insert and delete functions,
then
> a designer could arbitrarily assign more complicated activity to a
> container as his/her project might require, WITHOUT bring in a whole
> new library of classes for EVERY collection that he/she wanted to
> mutate.  In other words -- write the thread safety locks for insert
and
> delete for a vector, using ITS collection_traits object, then reuse
> that collection_traits object inside map, deque, ... whatever...

I'm not sure that a collection_traits object would ever be useful.  In
any case, you missed Mr. Kuehl's point, since such a trait object is
next to useless here.  This is too low of a granularity for thread
synchronization.  It will add tremendous speed costs while addressing
only a very small subset of uses of the object.  For instance, imagine
trying to use std::copy to copy items from one container to another.
If the locks were left at the level you've specified with
container_traits then seperate threads could add/remove/etc items
between each insertion within the copy algorithm, resulting in
something very much unexpected.  Worse still, it's possible that things
could even lead to a deadlock with this level of granularity on some
constructs.  No, what's needed is an object level lock.  You apply the
lock before your first access to the object and after the last access
to the object (don't misread what I'm saying here... you'll want to
unlock ASAP, but not until the last access that's a part of
the "transaction" you're attempting on the object).  Unfortunately,
such locks can't be automated within the object itself, but it's still
essential that you don't move locks too far down in the code.

> The alternative is to encapsulate the collection totally and write a
> thread-safe wrapper.  Currently, this is how I have to do it...
> however, because I loathe writing this sort of stuff repeatedly, I use
> a threadsafe_adapter which takes a collection template and a
collection
> traits parameter and screws thread safety into the mix... The sad fact
> is that I have to look through all of the standard collections and
> override any and all member functions that might modify the collection
> whether they be specific to map, vector, or common...
>
> This also bring to light one glaring problem... you DO, in fact, gain
> thread safety, but at the expense of adding a lot of exception
handling
> overhead to release the locks on the collection if an exception is
> thrown.  Not doing so reduces the exception guarantee to "weak" or
> potentially "none".  I have this crazy suspicion that if there *WERE*
a
> collection_traits object in the standard, they wouldn't be able to
give
> the "strong" exception safety we've come to expect... (FYI - "strong"
=
> the object is still intact after the exception.  "weak" = the object
> could dies but it won't leak resources after an exception.)

Locks can be secured using a RAII mechanism to insure unlocks.  Beyond
this, threads add little to the concern of exception safety that I can
see.  The "state of the object" in the face of an exception will be the
same wehter the code is executed in a seperate thread or not.

--
William E. Kempf
Software Engineer, MS Windows Programmer


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Does the C++ standard say anything about the thread-safety of STL?

Not so much in having fully synchronized methods on all the containers,
presumably that is too much overhead for most applications.  But, is
there any guarantee that two separate threads can create and use, say,
separate vector<int> without stomping on each other.  Although I haven't
verified this myself, a friend of mine said he ran into problems with
the STL containers memory allocators (on g++).  Presumably the memory
allocators had some shared structures/methods that were not reentrant.
Even though the vectors themselves were created independently, they
still had implicit dependencies on each other.

Is this a g++ bug, or is g++ doing what it's supposed to and it's the
standard that makes no promises about thread safety?

thanks,
Steve

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Thu, 4 May 2000 05:55:19 CST, Steve Hardt <hardts@best.com> wrote
in comp.std.c++:

> Does the C++ standard say anything about the thread-safety of STL?

Actually it does not.  The C++ standard does not support multiple
threads of execution in any way, shape, or form.

> Not so much in having fully synchronized methods on all the containers,
> presumably that is too much overhead for most applications.  But, is
> there any guarantee that two separate threads can create and use, say,
> separate vector<int> without stomping on each other.  Although I haven't
> verified this myself, a friend of mine said he ran into problems with
> the STL containers memory allocators (on g++).  Presumably the memory
> allocators had some shared structures/methods that were not reentrant.
> Even though the vectors themselves were created independently, they
> still had implicit dependencies on each other.
>
> Is this a g++ bug, or is g++ doing what it's supposed to and it's the
> standard that makes no promises about thread safety?
>
> thanks,
> Steve

Since the language itself does not define or support threads, whatever
a compiler does or does not do, based on whatever services the
underlying operating system provides, is whatever it is.  It is
strictly a quality of implementation issue.

However, consider this:

Operating systems generally provide relatively raw threading services,
with no inherent protection against the sort of problem you mention.
They also provide one or more type of synchronization and/or exclusion
mechanism such as mutex, semaphore, etc.  This leaves the choice up to
the programmer.

Many uses of threads will not have a problem, and the programmer will
not need to use these mechanisms and thus save the run-time overhead.
It is up to the programmer to recognize the cases when they are
needed, and use them accordingly.

If a compiler or its library automatically applied these mechanisms in
every single function in the threaded version of its library where it
might be needed, the programmer would be robbed of the choice and have
to accept the overhead on all the cases where it was not needed.  Not
only would all programs that used multiple threads be larger and
slower, they might even slow down the overall performance of the OS
and other applications.

Besides this would be very much against the "spirit of C", which C++
has inherited in proper object-oriented fashion.  Remember, the
language does not even add the overhead of checking array subscripts
to your code.

Jack Klein
--
Home: http://jackklein.home.att.net

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I understand and agree that STL cannot necessarily make itself thread
safe while STILL maintaining its efficiency for those who run in a
single-threaded environment (strangely enough, in the implementation
*I* use, all associative containers have guards around the
insert/deletes, but all the regular sequences do not).

HOWEVER... it sure would have been nice to have a sequence_traits
member of the template to allow the programmer the ability to override
the behavior of the insert/deletes.  (After all, char_traits is
provided for std::string).  Allocator is pretty good, but if you
redefine this action, then certain things that get run after calls to
the allocator function can sort of work at odds with what you might
want to do -- SPECIFICALLY, create a thread-safe container.


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]