www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - D const enables multi-reader synchronization

reply =?iso-8859-2?B?VG9tZWsgU293afFza2k=?= <just ask.me> writes:
This is a continuation of a recent thread "Synchronized const methods" on  
D.learn.

Currently only one thread at a time can execute a synchronized method. But  
think about D's const -- it's deep, so if a method is const, it can't  
possibly mutate its object. So many synchronized const method calls could  
safely look-but-not-touch the same object at the same time.

The chain of questions that stems from the above is:
1. Is letting many readers in on an object really safe? Know any  
multi-threading quirk that would make sh*t hit the fan?
2. If answer to 1. is yes, would there be room in the current  
implementation of synchronized keyword for a readers-writer lock?
3. If answer to 2. is yes, how do we tackle write-starvation? In a  
read-mostly scenario the mutating thread may be held up forever.

More on readers-writer lock:
http://en.wikipedia.org/wiki/Readers-writer_lock


Tomek
Jun 14 2010
next sibling parent reply Brad Roberts <braddr slice-2.puremagic.com> writes:
On Mon, 14 Jun 2010, Tomek Sowi?ski wrote:


 This is a continuation of a recent thread "Synchronized const methods" on
 D.learn.
 
 Currently only one thread at a time can execute a synchronized method. But
 think about D's const -- it's deep, so if a method is const, it can't possibly
 mutate its object. So many synchronized const method calls could safely
 look-but-not-touch the same object at the same time.
 
 The chain of questions that stems from the above is:
 1. Is letting many readers in on an object really safe? Know any
 multi-threading quirk that would make sh*t hit the fan?
 2. If answer to 1. is yes, would there be room in the current implementation
 of synchronized keyword for a readers-writer lock?
 3. If answer to 2. is yes, how do we tackle write-starvation? In a read-mostly
 scenario the mutating thread may be held up forever.
 
 More on readers-writer lock:
 http://en.wikipedia.org/wiki/Readers-writer_lock
 
 
 Tomek


Const methods only prevent mutating 'this'.  You can still call functions 
that mutate other state (via globals or passed in arguments).

Additionally, I'm also a little concerned about the implications to 
application performance.  Add one method that's non-const and suddenly the 
app performs somewhat differently and it's hard to tell why.

It's an interesting idea, and still worth exploring, but my inclinations 
are that this should be explicitly setup rather than done behind the 
scenes.

Later,
Brad
Jun 14 2010
parent reply =?iso-8859-2?B?VG9tZWsgU293afFza2k=?= <just ask.me> writes:
Dnia 14-06-2010 o 21:27:24 Brad Roberts <braddr slice-2.puremagic.com>  =

napisa=B3(a):


 On Mon, 14 Jun 2010, Tomek Sowi?ski wrote:


 This is a continuation of a recent thread "Synchronized const methods=




"  =


 on
 D.learn.

 Currently only one thread at a time can execute a synchronized method=




.  =


 But
 think about D's const -- it's deep, so if a method is const, it can't=




  =


 possibly
 mutate its object. So many synchronized const method calls could safe=




ly

 look-but-not-touch the same object at the same time.

 The chain of questions that stems from the above is:
 1. Is letting many readers in on an object really safe? Know any
 multi-threading quirk that would make sh*t hit the fan?
 2. If answer to 1. is yes, would there be room in the current  =





 implementation
 of synchronized keyword for a readers-writer lock?
 3. If answer to 2. is yes, how do we tackle write-starvation? In a  =





 read-mostly
 scenario the mutating thread may be held up forever.

 More on readers-writer lock:
 http://en.wikipedia.org/wiki/Readers-writer_lock


 Tomek


 Const methods only prevent mutating 'this'. You can still call functio=


ns

 that mutate other state (via globals or passed in arguments).


But synchronized on a method also protects only 'this', no?. Currently y=
ou  =

can have:

class A { ... }

shared class K {
     synchronized void fun(A a) const {
         // mutate a
     }
}

If you call fun on two instances of K, each in a different thread, but  =

pass them the same instance of A, you'll get a data race anyway. You cou=
ld  =

make fun's arguments const, but still there's shared globals.


 Additionally, I'm also a little concerned about the implications to
 application performance.  Add one method that's non-const and suddenly=


  =


 the
 app performs somewhat differently and it's hard to tell why.

 It's an interesting idea, and still worth exploring, but my inclinatio=


ns

 are that this should be explicitly setup rather than done behind the
 scenes.


Probably. It's difficult to find info on threading in D2, so it's hard t=
o  =

imagine how a library implementation could look like.


Tomek
Jun 14 2010
parent reply Brad Roberts <braddr slice-2.puremagic.com> writes:
On Mon, 14 Jun 2010, Tomek Sowi?ski wrote:


 Dnia 14-06-2010 o 21:27:24 Brad Roberts <braddr slice-2.puremagic.com>
 napisa?(a):
 

 Const methods only prevent mutating 'this'. You can still call functions
 that mutate other state (via globals or passed in arguments).


 
 But synchronized on a method also protects only 'this', no?. Currently you can
 have:
 
 class A { ... }
 
 shared class K {
    synchronized void fun(A a) const {
        // mutate a
    }
 }
 
 If you call fun on two instances of K, each in a different thread, but pass
 them the same instance of A, you'll get a data race anyway. You could make
 fun's arguments const, but still there's shared globals.


The lock is per-object but the lock protects all of the code inside the 
block, not just the parts that hang off the this reference.

You're code describes the case I'm talking about.  If the mutations to A 
are all inside the K::fun code, and your proposal happens, then code that 
runs safely changes to code that runs unsafely.

I'm not saying it's a good idea to structure code that way, but the 
language rules need to consider all angles, not just the used correctly or 
best practices uses.
Jun 14 2010
parent Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Brad Roberts wrote:


 On Mon, 14 Jun 2010, Tomek Sowi?ski wrote:
 

 Dnia 14-06-2010 o 21:27:24 Brad Roberts <braddr slice-2.puremagic.com>
 napisa?(a):
 

 Const methods only prevent mutating 'this'. You can still call
 functions that mutate other state (via globals or passed in arguments).


 
 But synchronized on a method also protects only 'this', no?. Currently
 you can have:
 
 class A { ... }
 
 shared class K {
    synchronized void fun(A a) const {
        // mutate a
    }
 }
 
 If you call fun on two instances of K, each in a different thread, but
 pass them the same instance of A, you'll get a data race anyway. You
 could make fun's arguments const, but still there's shared globals.


 
 The lock is per-object but the lock protects all of the code inside the
 block, not just the parts that hang off the this reference.
 
 You're code describes the case I'm talking about.  If the mutations to A
 are all inside the K::fun code, and your proposal happens, then code that
 runs safely changes to code that runs unsafely.
 
 I'm not saying it's a good idea to structure code that way, but the
 language rules need to consider all angles, not just the used correctly or
 best practices uses.


Hm, not sure if we understand each other. Perhaps a full example:

import std.stdio;
import core.thread;

class A { int a; }

shared class K {
    A a;
    synchronized void fun(A a) const {
        foreach (i; 0..3) {
            writeln(Thread.getThis().name, ": I saw ", a.a, ", changed to ", 
++a.a);
            Thread.sleep(1_000_000);
        }
    }
}

class Thr : Thread {
    A a;

    this(A a, string name) {
        super(&run);
        this.a = a;
        this.name = name;
    }

    void run() {
        auto k = new K;
        k.fun(a);
    }
}

void main() {
    A a = new A;
    (new Thr(a, "T1")).start();
    (new Thr(a, "T2")).start();
}

Compiled with DMD 2.045 it outputs:
T2: I saw 0, changed to 1
T1: I saw 1, changed to 2
T2: I saw 2, changed to 3
T1: I saw 3, changed to 4
T2: I saw 4, changed to 5
T1: I saw 5, changed to 6

So the 2 sync'ed calls are mutating its parameter at the same time, already 
without my proposal.

Anyway, language-level implementation probably doesn't make sense. As Sean 
said, it's too much machinery and too many options to devise a standard that 
would make everybody happy.


Tomek
Jun 15 2010
prev sibling next sibling parent =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Tomek Sowi=C5=84ski wrote:

 3. If answer to 2. is yes, how do we tackle write-starvation? In a
 read-mostly scenario the mutating thread may be held up forever.
=20


	I'd say that as soon as someone requests the write lock, nobody can
get the read lock anymore. Then when the current readers release the
lock, the writer gets it. So you can have the following sequence of
events:

1. R1 requests the read lock and gets it;
2. R2 requests the read lock and gets it;
3. W1 requests the write lock and waits;
4. R3 requests the read lock and waits;
5. R4 requests the read lock and waits;
6. R1 and R2 release the lock, W1 gets it;
7. W2 requests the write lock and waits;
8. W1 releases the lock, R3 and R4 get it (since they requested the
lock before W2);
9. R5 requests the read lock and waits (since W2 is already waiting
for the write lock);
10. R3 and R4 release the lock, W2 gets it;
11. W2 releases the lock, R5 gets it.

	Of course, this is not optimal: it is conceivable that R3 could
have gotten the lock, done whatever it had to do and released the
lock before R1 and R2. However, I believe it is the best compromise:
it still allowed R1 and R2 to access the object simultaneously,
while at the same time ensuring that write starvation cannot occur.

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
Jun 14 2010
prev sibling next sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 14 Jun 2010 15:17:57 -0400, Tomek Sowiński <just ask.me> wrote:

 This is a continuation of a recent thread "Synchronized const methods"  
 on D.learn.

 Currently only one thread at a time can execute a synchronized method.  
 But think about D's const -- it's deep, so if a method is const, it  
 can't possibly mutate its object. So many synchronized const method  
 calls could safely look-but-not-touch the same object at the same time.

 The chain of questions that stems from the above is:
 1. Is letting many readers in on an object really safe? Know any  
 multi-threading quirk that would make sh*t hit the fan?
 2. If answer to 1. is yes, would there be room in the current  
 implementation of synchronized keyword for a readers-writer lock?
 3. If answer to 2. is yes, how do we tackle write-starvation? In a  
 read-mostly scenario the mutating thread may be held up forever.

 More on readers-writer lock:
 http://en.wikipedia.org/wiki/Readers-writer_lock


 Tomek


This has been suggested before and has been rejected. The major issue is  
that CREW (concurrent-read exclusive-write) locks are known to be not  
composite and therefore its trivial to write code which results in a  
deterministic dead-lock. The problem lies in that the const method can  
have access to a non-const reference to its object via method arguments  
and/or globals. Thus, a read-lock can be obtained first and then later a  
write lock is attempted. Since the first read lock will never be released,  
the write lock can never be taken and a deadlock occurs.
Jun 14 2010
parent reply =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Robert Jacques wrote:

 On Mon, 14 Jun 2010 15:17:57 -0400, Tomek Sowi=C5=84ski <just ask.me> w=


rote:

 This is a continuation of a recent thread "Synchronized const methods"=





 on D.learn.

 Currently only one thread at a time can execute a synchronized method.=





 But think about D's const -- it's deep, so if a method is const, it
 can't possibly mutate its object. So many synchronized const method
 calls could safely look-but-not-touch the same object at the same time=




=2E

 The chain of questions that stems from the above is:
 1. Is letting many readers in on an object really safe? Know any
 multi-threading quirk that would make sh*t hit the fan?
 2. If answer to 1. is yes, would there be room in the current
 implementation of synchronized keyword for a readers-writer lock?
 3. If answer to 2. is yes, how do we tackle write-starvation? In a
 read-mostly scenario the mutating thread may be held up forever.

 More on readers-writer lock:
 http://en.wikipedia.org/wiki/Readers-writer_lock


 Tomek


=20
 This has been suggested before and has been rejected. The major issue i=


s

 that CREW (concurrent-read exclusive-write) locks are known to be not
 composite and therefore its trivial to write code which results in a
 deterministic dead-lock. The problem lies in that the const method can
 have access to a non-const reference to its object via method arguments=



 and/or globals. Thus, a read-lock can be obtained first and then later =


a

 write lock is attempted. Since the first read lock will never be
 released, the write lock can never be taken and a deadlock occurs.


	Unless the write lock can be acquired when the only thread holding
the read lock is the same as the one wanting the write lock.
Something similar is already done for the "standard" lock used by
synchronized methods (otherwise, a synchronized method would be
unable to call another synchronized method without deadlocking).

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
Jun 15 2010
parent "Robert Jacques" <sandford jhu.edu> writes:
On Tue, 15 Jun 2010 14:47:08 -0400, Jérôme M. Berger <jeberger free.fr>  
wrote:


 Robert Jacques wrote:

 On Mon, 14 Jun 2010 15:17:57 -0400, Tomek Sowiński <just ask.me> wrote:

 This is a continuation of a recent thread "Synchronized const methods"
 on D.learn.

 Currently only one thread at a time can execute a synchronized method.
 But think about D's const -- it's deep, so if a method is const, it
 can't possibly mutate its object. So many synchronized const method
 calls could safely look-but-not-touch the same object at the same time.

 The chain of questions that stems from the above is:
 1. Is letting many readers in on an object really safe? Know any
 multi-threading quirk that would make sh*t hit the fan?
 2. If answer to 1. is yes, would there be room in the current
 implementation of synchronized keyword for a readers-writer lock?
 3. If answer to 2. is yes, how do we tackle write-starvation? In a
 read-mostly scenario the mutating thread may be held up forever.

 More on readers-writer lock:
 http://en.wikipedia.org/wiki/Readers-writer_lock


 Tomek


 This has been suggested before and has been rejected. The major issue is
 that CREW (concurrent-read exclusive-write) locks are known to be not
 composite and therefore its trivial to write code which results in a
 deterministic dead-lock. The problem lies in that the const method can
 have access to a non-const reference to its object via method arguments
 and/or globals. Thus, a read-lock can be obtained first and then later a
 write lock is attempted. Since the first read lock will never be
 released, the write lock can never be taken and a deadlock occurs.


 	Unless the write lock can be acquired when the only thread holding
 the read lock is the same as the one wanting the write lock.
 Something similar is already done for the "standard" lock used by
 synchronized methods (otherwise, a synchronized method would be
 unable to call another synchronized method without deadlocking).

 		Jerome


Correct in theory, wrong in practice. There's an elegant way of storing  
this information at zero cost in the case of simple locks; there's no  
equivalent for CREW locks.
Jun 16 2010
prev sibling next sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
Tomek Sowiñski Wrote:


 This is a continuation of a recent thread "Synchronized const methods" on  
 D.learn.
 
 Currently only one thread at a time can execute a synchronized method. But  
 think about D's const -- it's deep, so if a method is const, it can't  
 possibly mutate its object. So many synchronized const method calls could  
 safely look-but-not-touch the same object at the same time.


It's an interesting idea but I'd recommend against it for a few reasons:

1. Acquiring, using, and releasing a reader lock is actually more expensive
than a plain old mutex so it isn't a good idea to use one just because you can.
 A ReadWriteMutex is really for addressing convoying problems on containers.

2. The typical implementation of a ReadWriteMutex doesn't permit recursive
up/downgrades from reader to writer and such.  It's technically possible to do
this, but doing so requires a lot more machinery and consequently trades away
even more performance.

That said, if you're inclined to experiment there's a ReadWriteMutex in
core.sync.rwmutex (which you already may know).
Jun 14 2010
parent reply Tomek =?UTF-8?B?U293acWEc2tp?= <just ask.me> writes:
Sean Kelly wrote:


 Tomek Sowi�ski Wrote:
 

 This is a continuation of a recent thread "Synchronized const methods" on
 D.learn.
 
 Currently only one thread at a time can execute a synchronized method.
 But think about D's const -- it's deep, so if a method is const, it can't
 possibly mutate its object. So many synchronized const method calls could
 safely look-but-not-touch the same object at the same time.


 
 It's an interesting idea but I'd recommend against it for a few reasons:
 
 1. Acquiring, using, and releasing a reader lock is actually more
 expensive than a plain old mutex so it isn't a good idea to use one just
 because you can.  A ReadWriteMutex is really for addressing convoying
 problems on containers.
 
 2. The typical implementation of a ReadWriteMutex doesn't permit recursive
 up/downgrades from reader to writer and such.  It's technically possible
 to do this, but doing so requires a lot more machinery and consequently
 trades away even more performance.


That shed some light, thanks.
 

 That said, if you're inclined to experiment there's a ReadWriteMutex in
 core.sync.rwmutex (which you already may know).


I didn't know it even existed:) The library reference seems a bit broken. 
Some core modules are camouflaged as std.* (e.g. std.thread, std.gc is 
core.memory for some reason), core.sync is not even listed.

http://www.digitalmars.com/d/2.0/phobos/phobos.html


Tomek
Jun 15 2010
parent Sean Kelly <sean invisibleduck.org> writes:
Tomek Sowiński <just ask.me> wrote:

 Sean Kelly wrote:
 

 Tomek Sowi�ski Wrote:
 

 This is a continuation of a recent thread "Synchronized const
 methods" on
 D.learn.
 
 Currently only one thread at a time can execute a synchronized
 method.
 But think about D's const -- it's deep, so if a method is const, it
 can't
 possibly mutate its object. So many synchronized const method calls
 could
 safely look-but-not-touch the same object at the same time.


 
 It's an interesting idea but I'd recommend against it for a few
 reasons:
 
 1. Acquiring, using, and releasing a reader lock is actually more
 expensive than a plain old mutex so it isn't a good idea to use one
 just
 because you can.  A ReadWriteMutex is really for addressing convoying
 problems on containers.
 
 2. The typical implementation of a ReadWriteMutex doesn't permit
 recursive
 up/downgrades from reader to writer and such.  It's technically
 possible
 to do this, but doing so requires a lot more machinery and
 consequently
 trades away even more performance.


 
 That shed some light, thanks.
  

 That said, if you're inclined to experiment there's a ReadWriteMutex
 in
 core.sync.rwmutex (which you already may know).


 
 I didn't know it even existed:) The library reference seems a bit
 broken. 
 Some core modules are camouflaged as std.* (e.g. std.thread, std.gc is
 
 core.memory for some reason), core.sync is not even listed.
 
 http://www.digitalmars.com/d/2.0/phobos/phobos.html


The Phobos wrappers exist for backwards compatibility, I suppose it's
high time they were removed. I really need to see about bundling the
druntime docs with the Phobos docs.
Jun 17 2010
prev sibling parent Sean Kelly <sean invisibleduck.org> writes:
Tomek Sowiñski Wrote:

 3. If answer to 2. is yes, how do we tackle write-starvation? In a  
 read-mostly scenario the mutating thread may be held up forever.


The implementation in core.sync.rwmutex can be set to favor readers or writers.
 So you can choose the method most appropriate to your use case.  I imagine
something more balanced would be possible as well, but I didn't want to get too
fancy.
Jun 14 2010