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 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 =?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=


 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=

 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=

 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
prev sibling next sibling parent =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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

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
next sibling parent =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

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

 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 i=

 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 =

 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
prev sibling 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 parent reply Sean Kelly <sean invisibleduck.org> writes:
Tomek Sowiski 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