«

"Joshua Maurice" <> wrote in message
news:2736a5f6-59eb-434e-b21b-...
[...]

> DCL is the most common application I see of this flawed reasoning. The
> heart of DCL is that one relies on investigating the possible
> interleavings of source code "instructions" to see if it will work
> out. IMHO, as soon as you modify DCL to be correct in C or C++, it is
> no longer DCL.

What modifications of the DCL algorithm itself are needed in order to get it
to work in C/C++? I don't have to modify the actual algorithm in order to
get it to work in C/C++. I only have to implement the algorithm using highly
non-portable methods.




> You have fundamentally changed the basis of your belief
> of its correctness when you add in proper synchronization. No longer
> are you doing a single check outside of all synchronization,
> the hallmark of DCL. It only superficially resembles DCL.

Unless I am misunderstanding you, I have to disagree here. The algorithm
needs proper synchronization on the fast-path and on the slow-path. On the
fast-path it needs a data-dependant load memory barrier, and on the slow
path it needs the mutex along with release semantics. There is no "single
check outside of all synchronization". AFAICT, that's a misunderstanding on
how the algorithm actually works. Skipping the mutex acquisition/release is
the only thing that DCL actually optimizes. Just because you can skip a call
to the mutex (e.g., fast-path) does not mean that you're somehow "outside of
all synchronization".




> Now, arguably, your post Jerry and mine is merely a definition over
> terms. I hope I've generated more light than heat, but I don't think
> it will be useful to get into a discussion of whether DCL is by
> definition broken or merely usually incorrectly implemented. Define it
> however you want. I still think that DCL by definition is incorrect in
> C and C++, and modifications to make it correct render it no longer
> DCL.

DCL is DCL. Even if I implement it in pure ASM, I still cannot get away from
using proper synchronization. If I implement DCL in C/C++ using
platform/compiler specific guarantees, well, it's still DCL, not something
different.

"Joshua Maurice" <> wrote in message
news:a6221b91-add3-4629-b955-...
On Sep 10, 11:43 am, "Chris M. Thomasson" <n...@spam.invalid> wrote:
> > "Joshua Maurice" <joshuamaur...@gmail.com> wrote in message
> > > PPS: All windows standard mutexes have runtime init, so you cannot do
> > > either of these approaches without significant modifications, or
> > > without rolling your own mutex built on some of the atomic primitives
> > > like test and swap. See:
> > >http://www.ddj.com/cpp/199203083?pgno=7
> > > for a good discussion on how to do this.
> > > Alternatively, use a namespace scope variable to force construction
> > > before main (or before dlopen returns for static init of a dll) to
> > > "guarantee" correctness as demonstrated in countless posts in this
> > > thread.
> >
> > Windows has everything one needs in order to create a 100% correct DCL
> > pattern. The following code will work with Windows, modulo bugs of
> > course
> > because I just hacked it together:

> [snip probably correct impl]

> I should probably just shut up and take my losses. I am still right
> that there is no mutex on windows without runtime init, but your
> workaround, which Boost also uses to do boost_once IIRC, is quite
> good.

Ahhh. I forgot that Boost does something like that. It works, but it's kind
of "hackish"...

;^)




> I forget which versions, but windows also have their own native
> version of pthread_once, so you could also use that.

It's on Windows Vista and higher.




> Also, as you
> mentioned, volatile would work, for whichever VS versions and
> platforms make it into barriers.

Yes.

On 10 Set, 23:35, James Kanze <james.ka...@gmail.com> wrote:
> On Sep 10, 1:46 pm, Francesco <entul...@gmail.com> wrote:
>
> > On 10 Set, 13:04, James Kanze <james.ka...@gmail.com> wrote:
>
> * * *[...]
>
> > Uh, well, I've read your code but I didn't think about the
> > fact that ourInstance had to be initialized before being
> > compared to NULL - in other words, I missed to catch the
> > subtlety.
>
> You missed the fact that the function used to initialize the
> variable uses the previous value of the variable.
>
> In fact, it's a clever trick, with both the positive and
> negative implications of "clever". * The suggestion else thread
> of using a separate boolean variable to accomplish this achieves
> exactly the same results, and is doubtlessly more readable.
>
> > Can I rely on this default, hidden initialization for static
> > members of any type?
>
> For any variable. *The standard describes the initialization of
> objects with static lifetime as occuring in three phases: zero
> initialization, static initialization and dynamic
> initialization. *In practice, there's no way to distinguish the
> first two, since both occur before any code you write is
> executed. *(In practice, on most systems, the first two are done
> by the system, when the program is loaded, either by copying an
> image from disk or by zapping the block containing the variables
> with 0's. *This only works, of course, on systems where null
> pointers and 0.0 are represented by all 0 bits, but that's the
> vast majority of the systems today.`)
>
> > Something like this:
> > -------
> > class A {
> > * static int data;
> > * public:
> > * * static int get_data();
> > };
> > int A::data = get_data();
> > int A::get_data() {
> > * if (data == 0) data = 42;
> > * return data;
> > }
> > -------
> > Is the above guaranteed to work for any type?
> > (using the appropriate value on the rhs of ==, I mean)
>
> Or using 0. *Yes. *For class types, it applies recursively,
> until you reach a basic type which can be "zero initialized".
> The one exception is references, since by definition, a
> reference can't be zero initialized.

Good, now seems that I got it. Thanks for the further explanation
James.

Cheers,
Francesco

In article <2736a5f6-59eb-434e-b21b-968b735a8e91
@u16g2000pru.googlegroups.com>, says...
>
> On Sep 10, 4:07*pm, Jerry Coffin <jerryvcof...@yahoo.com> wrote:

[ ... ]

> > That paper followed shortly after he realized that this just
> > wasn't so. The tone of the paper is unfortunate though -- it
> > comes off as basically saying there's a problem with double-
> > checked locking, which really isn't the case at all. The problem
> > is that C++ (up through the 2003 standard) simply lacks memory
> > barriers.
>
> Sorry what? There's something which resembling threading guarantees in
> C++03?

No, "lacks" would mean "does not have", and almost any kind of
threading guarantee requires some kind of memory barrier.

[ ... ]

> The problem is that most people I talk to at my work, they have
> certain notions of how threading works. One of these notions is that
> one can reason about threading by considering all possible
> interleavings of instructions (which, of course, is incorrect). Sadly,
> most of my colleagues still don't "get it". The proto-typical example
> I use: "Suppose a thread does a write A and a write B in source code.
> Physically after that processor core does both load instructions,
> another thread may see write A and not write B, another thread may see
> write B and not see write A, another thread may see both, and another
> thread may see neither." If one was incorrectly taught threading,
> which is the case I think for most university graduates nowadays, it
> is very hard to break your old habits and understand how threading
> really works.

I think the problem is really somewhat more fundamental: with
threading, it's almost pointless to try to figure out every scenario
that _could_ happen. Instead, you have to think strictly in terms of
what you've _made_ happen, and assume something wrong will happen
unless you've prevented it.

[ ... ]

> IMHO, as soon as you modify DCL to be correct in C or C++, it is
> no longer DCL. You have fundamentally changed the basis of your belief
> of its correctness when you add in proper synchronization.

I can't agree. Just for an obvious example, see page 12 of the paper
you cited, which gives (most of) an implementation of the DCLP using
memory barriers to ensure correctness. Note, in particular, that it's
essentially identical to the original (incorrect) code other than the
addition of two memory barriers (added only as comments, since the
current version of C++ doesn't include them).

With C++ 0x, we'll have acquire and release memory barriers, and
we'll be able to implement exactly that code -- and I can't see any
way you can reasonably call it anything other than a DCL -- it still
has the double-check and locking, just with memory barriers inserted
to ensure that it actually works.

> No longer
> are you doing a single check outside of all synchronization, the
> hallmark of DCL. It only superficially resembles DCL.

I'd say the hallmark of DCL is obvious from the name: double-checked
locking. As long as you still do double-checked locking, insertion of
memory barriers doesn't change the fact that you're still doing
double-checked locking, and therefore implementing the double-checked
locking pattern.

--
Later,
Jerry.

On Sep 11, 1:07 am, Jerry Coffin <jerryvcof...@yahoo.com> wrote:
> In article <aac0ea5e-c259-4177-9781-d94931593069
> @j9g2000prh.googlegroups.com>, joshuamaur...@gmail.com says...

> [ ... ]
> > Firstly and most importantly, you're using double checked
> > locking, which is broken in effectively all C++
> > implementations. Don't do that. Please read, continue to
> > re-read if you don't get it, this excellent paper:
> >http://www.aristeia.com/Papers/DDJ_J...04_revised.pdf

> This is a decent paper, but it should be kept in context. Up
> until shortly before he (helped) write that paper, Andrei
> seems to have thought that the 'volatile' keyword was
> sufficient to give assurances necessary for multithreading (in
> essence that reading or writing a volatile variable acted as a
> memory barrier).

I seem to recall that it was a couple of years before the paper
in question. Andrei did (naively) propose a means of achieving
thread safety using volatile. In fact, his solution worked, but
not for the reasons he thought---his solution actually only used
the fact that volatile is part of the type system. In the
following discussions, however, he quickly realized (and openly
admitted) that his understanding wasn't complete; since then
(and before writing the paper in question), he completed it.
The paper was also thoroughly reviewed before publication, to
ensure accuracy.

> That paper followed shortly after he realized that this just
> wasn't so. The tone of the paper is unfortunate though -- it
> comes off as basically saying there's a problem with
> double-checked locking, which really isn't the case at all.

This depends on how you defined double checked locking. There
is a definite problem in the code presented by Vlissides in his
original article, and that is what most people understand by
double checked locking. IIRC, the paper in question does make
it clear that double checked locking can be made to work using
assembler (at least on most platforms) or perhaps some
additional, system specific requests (other than just mutexes),
and while I don't think the paper mentions it, it can also be
made to work using thread local storage. In practice, it's
generally not worth it, since the additional assembler generally
does more or less what the outer mutex (which you're trying to
avoid) does, and costs about the same in run time.

> The problem is that C++ (up through the 2003 standard) simply
> lacks memory barriers. Double-checked locking is one example
> of code that _needs_ a memory barrier to work correctly -- but
> it's only one example of many.

It can be made to work with thread local storage as well,
without memory barriers.

[...]
> The real problem was never with the DCLP itself, but with
> attempting to do multi-threaded programming without the tools
> necessary for the job.

Yes. The "problem" with DCLP is in fact just a symptom of a
larger problem, of people not understanding what is and is not
guaranteed (and to a lesser degree, of people not really
understanding the costs---acquiring a non-contested mutex is
really very, very cheap, and usually not worth trying to avoid).

--
James Kanze

"James Kanze" <> wrote in message
news:edee09a7-fbc2-41fd-84b4-...
[...]

>> The problem is that C++ (up through the 2003 standard) simply
>> lacks memory barriers. Double-checked locking is one example
>> of code that _needs_ a memory barrier to work correctly -- but
>> it's only one example of many.
>
> It can be made to work with thread local storage as well,
> without memory barriers.

Indeed; something along the lines of:

<pseudo-code typed in newsreader>
__________________________________________________ _________________
template<typename T, unsigned T_id = 0>
struct non_destroying_singleton
{
static T& instance()
{
__thread T* l_instance = NULL;

if (! l_instance)
{
static T* g_instance = NULL;

static pthread_mutex_t g_mutex = PTHREAD_MUTEX_INITIALIZER;

lock_guard lock(g_mutex);

if (! (l_instance = g_instance))
{
l_instance = g_instance = new T();
}
}

return *l_instance;
}
};
__________________________________________________ _________________




No memory barriers required! Yeah!

;^)


[...]

In article <edee09a7-fbc2-41fd-84b4-
>,
says...

[ ... using a memory barrier ]

> In practice, it's
> generally not worth it, since the additional assembler generally
> does more or less what the outer mutex (which you're trying to
> avoid) does, and costs about the same in run time.

I have to disagree with both of these. First, a memory barrier is
quite a bit different from a mutex. Consider (for example) a store
fence. It simply says that stores from all previous instructions must
complete before any stores from subsequent instructions (and a read
barrier does the same, but for reads). It's basically equivalent to a
sequence point, but for real hardware instead of a conceptual model.

As far as cost goes: a mutex normally uses kernel data, so virtually
every operation requires a switch from user mode to kernel mode and
back. The cost for that will (of course) vary between systems, but is
almost always fairly high (figure a few thousand CPU cycles as a
reasonable minimum).

A memory barrier will typically just prevent combining a subsequent
write with a previous one. As long as there's room in the write queue
for both pieces of data, there's no cost at all. In the (normally
rare) case that the CPU's write queue is full, a subsequent write has
to wait for a previous write to complete to create an empty spot in
the write queue. Even in this worst case, it's generally going to be
around an order of magnitude faster than a switch to kernel mode and
back.

> > The problem is that C++ (up through the 2003 standard) simply
> > lacks memory barriers. Double-checked locking is one example
> > of code that _needs_ a memory barrier to work correctly -- but
> > it's only one example of many.
>
> It can be made to work with thread local storage as well,
> without memory barriers.

Well, yes -- poorly stated on my part. It requires _some_ sort of
explicit support for threading that's missing from the current and
previous versions of C++, but memory barriers aren't the only
possible one.

[ ... ]

> Yes. The "problem" with DCLP is in fact just a symptom of a
> larger problem, of people not understanding what is and is not
> guaranteed (and to a lesser degree, of people not really
> understanding the costs---acquiring a non-contested mutex is
> really very, very cheap, and usually not worth trying to avoid).

At least under Windows, this does not fit my experience. Of course,
Windows has its own cure (sort of) for the problem -- rather than
using a mutex (with its switch to/from kernel mode) you'd usually use
a critical section instead. Entering a critical section that's not in
use really is very fast.

Then again, a critical section basically is itself just a double-
checked lock (including the necessary memory barriers). They have two
big limitations: first, unlike a normal mutex, they only work between
threads in a single process. Second, they can be quite slow when/if
there's a great deal of contention for the critical section.

--
Later,
Jerry.

On Sep 8, 5:39 pm, James Kanze <james.ka...@gmail.com> wrote:
> Not knowing the requirements, it's hard to say. My usual
> implementation is:
>
> class Data
> {
> private:
> static Data* ourInstance ;
> Data() {}
> ~Data() {}
>
> public:
> static Data& instance() ;
> // ...
> } ;
>
> Data* Data:: ourInstance = &instance() ;
>
> Data&
> Data::instance()
> {
> if ( ourInstance == NULL ) {
> ourInstance = new Data ;
> }
> return *ourInstance ;
> }
>
> This solves the threading issues (for the most part), and avoids
> any order of destruction issues, by not destructing the object.

I think it's worth noting that the implementation above always
instantiates Data even if it is never used by another part of
the program. ie the above is not the "lazy" instantiation of
the original implementation.

KHD

On Sep 12, 4:01*pm, Jerry Coffin <jerryvcof...@yahoo.com> wrote:
> In article <edee09a7-fbc2-41fd-84b4-
> dcdae859b...@a21g2000yqc.googlegroups.com>, james.ka...@gmail.com
> says...
> > Yes. *The "problem" with DCLP is in fact just a symptom of a
> > larger problem, of people not understanding what is and is not
> > guaranteed (and to a lesser degree, of people not really
> > understanding the costs---acquiring a non-contested mutex is
> > really very, very cheap, and usually not worth trying to avoid).
>
> At least under Windows, this does not fit my experience. Of course,
> Windows has its own cure (sort of) for the problem -- rather than
> using a mutex (with its switch to/from kernel mode) you'd usually use
> a critical section instead. Entering a critical section that's not in
> use really is very fast.
>
> Then again, a critical section basically is itself just a double-
> checked lock (including the necessary memory barriers). They have two
> big limitations: first, unlike a normal mutex, they only work between
> threads in a single process. Second, they can be quite slow when/if
> there's a great deal of contention for the critical section.

Well, with contention, how slow would a CriticalSection be compared to
a WIN32 Mutex object? I would presume about the same, and with that
assumption, I would say one should use CriticalSections as your mutex
implementation on windows unless you actually need the extra
functionality, like locking the same object across processes, which in
my experience is quite rare.

In article <cb280907-a612-4a13-baa8-01688c959868
@z3g2000prd.googlegroups.com>, says...

[ ... ]

> Well, with contention, how slow would a CriticalSection be compared
> to a WIN32 Mutex object? I would presume about the same, and with
> that assumption, I would say one should use CriticalSections as
> your mutex implementation on windows unless you actually need the
> extra functionality, like locking the same object across processes,
> which in my experience is quite rare.

We're getting off topic, so I won't try to get into a lot of detail,
but with sufficient contention, a critical section can become
_substantially_ slower than direct use of a mutex.

A couple of years ago (or so) there was a thread about this on
comp.os.ms-windows.programmer.win32. IIRC, somebody eventually posted
an improved version that didn't suffer nearly as bad of a slowdown.
Unfortunately, given the degree to which Google has broken searching
on the newsgroup archive, I can't tell you exactly where to get that.

--
Later,
Jerry.