Re: Please disprove this Double-Checked Locking "fix"

On Apr 26, 9:58 am, jl_p...@hotmail.com wrote:


[Snipped discussion of double checked locking]


I'm sorry for being so gruff in the following (not really), but it's
evident that you have not even fully read the paper which you cited,
the only paper, and that is highly irritating.

Look, follow this, and understand just how royally screwed your
approach is. Given the initial conditions:
  int x = 0;
  int y = 0;
Thread 1 executing:
  x = 1;
  y = 2;
And threads 2-5 executing the following all concurrently with threads
1-5:
  cout << x << ' ' << y << endl;
On non-obscure hardware and compilers, that can print /on a single
execution/, all 4 combinations:
  00
  02
  10
  12
Repeat, /on a single execution/. Different threads can see some writes
done by different threads in different orders! Thread 2 could see the
write to x without seeing the write to y, and thread 3 can see the
write to y without seeing the write to x.

Technically, the standard guarantees even worse - undefined behavior,
but the above is an example that /really happens/ on /real/ hardware
and /real/ compilers. This is largely due to hardware "reorderings",
but let me quote the paper for the relevant bit:

[quote]
Nothing you do can alter the fundamental problem: you need to be able
to specify a constraint on instruction ordering, and your language
gives you no way to do it.
[/quote]

To emphasize, it might be the compiler reordering it, it might be the
hardware reordering it, and it could even be some new kind of thing
which hasn't been invented yet! In practice the compiler writers and
hardware makers give guarantees for C++03 which mean that your code is
fundamentally broken. There is no standard or given guarantee of any
kind that any code written without proper synchronization will work.
None. Your code, give it to any compiler writer, and they will say
"won't work", which means while it might incidentally work today, but
tomorrow they might put in a new optimization (software or hardware),
and your code breaks. **This is the fundamental problem which you
cannot dodge!!**

Here's how you can break your code. Note again the general problem
that there are no guarantees that could even make it work, so I want
you to focus on the above basic problem, and do not spend too much
time on this, but I present it completeness. For example:

    Singleton* Singleton::instance() {
      if (pInstance == 0) {
        Lock lock;
        if (pInstance == 0) {
          Singleton* temp = new Singleton; // initialize to temp
          secondLock.lock();
          pInstance = temp; // assign temp to pInstance
          secondLock.unlock();
        }
      }
      return pInstance;
    }

A sufficiently smart compiler is allowed to move things from before a
lock to after the lock, and from after an unlock to before a lock. It
can transform the above to:

    Singleton* Singleton::instance() {
      if (pInstance == 0) {
        Lock lock;
        if (pInstance == 0) {
          secondLock.lock();
          Singleton* temp = new Singleton; // initialize to temp
          pInstance = temp; // assign temp to pInstance
          secondLock.unlock();
        }
      }
      return pInstance;
    }

And once we get that, it's trivial to change it to:

    Singleton* Singleton::instance() {
      if (pInstance == 0) {
        Lock lock;
        if (pInstance == 0) {
          secondLock.lock();
          pInstance = new Singleton;
          secondLock.unlock();
        }
      }
      return pInstance;
    }

Which means we're back to screwed for the reasons known to you. I
didn't even need to resort to the wonderful DEC Alpha and its split
cache, but I could have.

You need to reread the paper which you cited. Here's the link again
for your benefit.
http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf
And pay attention this time.