Re: D const enables multi-reader synchronization
Tomek Sowiński j...@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.
Re: D const enables multi-reader synchronization
On Tue, 15 Jun 2010 14:47:08 -0400, Jérôme M. Berger jeber...@free.fr wrote: Robert Jacques wrote: On Mon, 14 Jun 2010 15:17:57 -0400, Tomek Sowiński j...@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.
Re: D const enables multi-reader synchronization
Robert Jacques wrote: On Mon, 14 Jun 2010 15:17:57 -0400, Tomek Sowiński j...@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 -- mailto:jeber...@free.fr http://jeberger.free.fr Jabber: jeber...@jabber.fr signature.asc Description: OpenPGP digital signature
Re: D const enables multi-reader synchronization
Brad Roberts wrote:
On Mon, 14 Jun 2010, Tomek Sowi?ski wrote:
Dnia 14-06-2010 o 21:27:24 Brad Roberts bra...@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
Re: D const enables multi-reader synchronization
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
D const enables multi-reader synchronization
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
Re: D const enables multi-reader synchronization
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
Re: D const enables multi-reader synchronization
Dnia 14-06-2010 o 21:27:24 Brad Roberts bra...@slice-2.puremagic.com
napisał(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 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).
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.
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.
Probably. It's difficult to find info on threading in D2, so it's hard to
imagine how a library implementation could look like.
Tomek
Re: D const enables multi-reader synchronization
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. 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 -- mailto:jeber...@free.fr http://jeberger.free.fr Jabber: jeber...@jabber.fr signature.asc Description: OpenPGP digital signature
Re: D const enables multi-reader synchronization
On Mon, 14 Jun 2010 15:17:57 -0400, Tomek Sowiński j...@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.
Re: D const enables multi-reader synchronization
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).
