www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Atomic updates

reply "qznc" <qznc go.to> writes:
I implemented a D2 version of an open Rosetta problem.

Problem: http://rosettacode.org/wiki/Atomic_updates

Code: http://dpaste.dzfl.pl/e6615a53

Any comments or improvements?

I actually implemented a more scalable version than most of the 
other languages used, by using a lock per item instead of a 
single lock for the whole array.
Jan 21 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
qznc:

 Code: http://dpaste.dzfl.pl/e6615a53

 Any comments or improvements?
I have reformatted your code a little, according to the style used in all other D entries of RosettaCode: http://codepad.org/ceDyQ8lE The usage of a sink for toString() isn't common, but it's OK. I suggest to add something to make it stop after 20 seconds or so (I run all the rosettacode entries every so often to test them, so I prefer them to not go on forever. Some entries are required to produce infinite loops, but I think this time it's not necessary).
 I actually implemented a more scalable version than most of the 
 other languages used, by using a lock per item instead of a 
 single lock for the whole array.
Then I suggest you to add this comment before the entry. Bye, bearophile
Jan 21 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Some more little changes, I have added counters, and I have used 
the faster Xorshift:

http://codepad.org/hIFPgSTd

Bye,
bearophile
Jan 21 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Monday, 21 January 2013 at 21:16:58 UTC, bearophile wrote:
 Some more little changes, I have added counters, and I have 
 used the faster Xorshift:

 http://codepad.org/hIFPgSTd

 Bye,
 bearophile
I wouldn't mind seeing some "scope" in there. Keeps things safe. After all, those locks can throw exceptions... (can't they? I'm no mutex expert). Anyways, something like this: public void transfer(in uint from, in uint to, in TBucketValue amount) { auto low = min(from, to); auto high = max(from, to); buckets[low].mtx.lock(); scope(exit) buckets[low].mtx.unlock(); buckets[high].mtx.lock(); scope(exit) buckets[high].mtx.unlock(); immutable realAmount = min(buckets[from].value, amount); buckets[from].value -= realAmount; buckets[to ].value += realAmount; } void toString(in void delegate(const(char)[]) sink) { TBucketValue sum = 0; sink("("); size_t i; scope(exit) foreach (ref b; buckets[0 .. i]) { b.mtx.unlock().collectException(); } foreach (ref b; buckets) { b.mtx.lock(); ++i; sum += b.value; sink(text(b.value)); sink(" "); } sink(") "); sink(text(sum)); }
Jan 21 2013
prev sibling next sibling parent reply "qznc" <qznc go.to> writes:
On Monday, 21 January 2013 at 20:35:16 UTC, bearophile wrote:
 qznc:

 Code: http://dpaste.dzfl.pl/e6615a53

 Any comments or improvements?
I have reformatted your code a little, according to the style used in all other D entries of RosettaCode: http://codepad.org/ceDyQ8lE The usage of a sink for toString() isn't common, but it's OK. I suggest to add something to make it stop after 20 seconds or so (I run all the rosettacode entries every so often to test them, so I prefer them to not go on forever. Some entries are required to produce infinite loops, but I think this time it's not necessary).
Thanks for the feedback. I made another iteration on your changes. http://codepad.org/9xB58cbE * Since display is not performance critical, relying on AA.toString for formatting is nicer. * I'm not sure about "alias value this" in Bucket. It shows off a nice feature, but might be confusing for Rosetta visitors, due to its subtle effects. * A running variable to stop execution after some time.
Jan 21 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
qznc:

 I made another iteration on your changes.

 http://codepad.org/9xB58cbE
I suggest to put your code on Rosettacode now, and then we'll do the changes there... As you see in other answers, both me and monarch_dodra have other ideas for improvements. Bye, bearophile
Jan 21 2013
parent reply "qznc" <qznc go.to> writes:
On Tuesday, 22 January 2013 at 00:10:22 UTC, bearophile wrote:
 I suggest to put your code on Rosettacode now, and then we'll 
 do the changes there... As you see in other answers, both me 
 and monarch_dodra have other ideas for improvements.
Ok, posted it. http://rosettacode.org/wiki/Atomic_updates#D I incorporated some of your and monarch_dodra's suggestions.
Jan 22 2013
parent reply "cal" <callumenator gmail.com> writes:
On Tuesday, 22 January 2013 at 08:12:03 UTC, qznc wrote:
 On Tuesday, 22 January 2013 at 00:10:22 UTC, bearophile wrote:
 I suggest to put your code on Rosettacode now, and then we'll 
 do the changes there... As you see in other answers, both me 
 and monarch_dodra have other ideas for improvements.
Ok, posted it. http://rosettacode.org/wiki/Atomic_updates#D I incorporated some of your and monarch_dodra's suggestions.
Just curious: in the transfer function, why do you lock/unlock the lower bucket number first? Why does the order matter?
Jan 22 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 22 January 2013 at 09:26:25 UTC, cal wrote:
 On Tuesday, 22 January 2013 at 08:12:03 UTC, qznc wrote:
 On Tuesday, 22 January 2013 at 00:10:22 UTC, bearophile wrote:
 I suggest to put your code on Rosettacode now, and then we'll 
 do the changes there... As you see in other answers, both me 
 and monarch_dodra have other ideas for improvements.
Ok, posted it. http://rosettacode.org/wiki/Atomic_updates#D I incorporated some of your and monarch_dodra's suggestions.
Just curious: in the transfer function, why do you lock/unlock the lower bucket number first? Why does the order matter?
Avoids deadlock. imagine 2 threads: a: from 2 to 5. b: from 5 to 2. If both threads acquire their first lock, then you have a dead lock, and your program is basically dead. By always locking low first, you avoid the deadlock in a rather simple but elegant way.
Jan 22 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
I have modified a little the code on RosettaCode (no changes in 
the logic).

monarch_dodra:

 Avoids deadlock.

 imagine 2 threads:
 a: from 2 to 5.
 b: from 5 to 2.

 If both threads acquire their first lock, then you have a dead 
 lock, and your program is basically dead.

 By always locking low first, you avoid the deadlock in a rather 
 simple but elegant way.
The Go language has four different solutions, one of them is: http://rosettacode.org/wiki/Atomic_updates#Lock-free From the site:
 This version uses no locking for the phase where the
 two clients are updating the buckets. Instead it
 watches for collisions and retries as needed.
func (bl *lfList) transfer(b1, b2, a int, ux int) { if b1 == b2 { return } bl.RLock() for { t := int32(a) v1 := atomic.LoadInt32(&bl.b[b1]) if t > v1 { t = v1 } if atomic.CompareAndSwapInt32(&bl.b[b1], v1, v1-t) { atomic.AddInt32(&bl.b[b2], t) break } // else retry } bl.tc[ux]++ bl.RUnlock() runtime.Gosched() } Bye, bearophile
Jan 22 2013
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 22 January 2013 at 10:27:58 UTC, bearophile wrote:
 I have modified a little the code on RosettaCode (no changes in 
 the logic).

 monarch_dodra:

 Avoids deadlock.

 imagine 2 threads:
 a: from 2 to 5.
 b: from 5 to 2.

 If both threads acquire their first lock, then you have a dead 
 lock, and your program is basically dead.

 By always locking low first, you avoid the deadlock in a 
 rather simple but elegant way.
The Go language has four different solutions, one of them is: http://rosettacode.org/wiki/Atomic_updates#Lock-free [SNIP] Bye, bearophile
That's a good point, and I'm sure we could also have a version of D that could also do it that way. D has attomic swap operations too, AFAIK. But I was really just answering the original question of "if you need 2 locks, why do it that way?".
Jan 22 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:

 That's a good point, and I'm sure we could also have a version 
 of D that could also do it that way.
Someone is willing to create that second version for RosettaCode? I have modified a bit the second and third Go versions on Rosettacode, now there are 20 buckets and it shows the print every 1 second (like the D version currently present on Rosettacode). I have compiled the Go code with the latest go1.0.3 (that is a fast compiler, but I think it doesn't produce a very efficient binary). The outputs: Go atomic2b: sum ---updates--- mean buckets 1000 825883 825883 1651766 [96 19 7 45 119 35 67 4 45 19 106 51 19 69 8 102 34 47 56 52] 1000 754038 754037 1579920 [27 92 16 9 17 34 74 26 69 20 110 120 38 16 93 10 131 8 34 56] 1000 815841 815842 1597174 [27 10 46 54 32 19 55 87 125 87 46 29 70 57 37 2 14 151 2 50] 1000 748939 748938 1572350 [78 52 82 64 12 6 15 36 13 103 52 21 12 55 58 137 100 69 16 19] 1000 748836 748837 1557414 [78 79 29 114 13 12 131 105 22 20 68 77 40 19 68 30 36 57 1 1] 1000 751092 751092 1548209 [23 17 35 106 58 74 40 141 35 124 3 46 32 46 0 47 32 37 57 47] 1000 747933 747933 1540732 [43 32 31 32 29 36 41 46 37 51 46 1 48 263 37 61 51 61 43 11] Go atomic3b sum ---updates--- mean buckets 1000 1098238 1098238 2196476 [93 22 4 122 48 20 52 37 50 73 13 22 85 103 93 22 2 13 86 40] 1000 907417 907417 2005655 [36 57 36 134 6 48 21 134 47 76 18 65 22 18 61 92 67 15 23 24] 1000 814198 814197 1879901 [21 51 56 37 55 36 22 50 106 0 99 6 59 107 55 21 40 67 65 47] 1000 725805 725805 1772828 [32 5 105 39 123 17 46 23 25 38 24 104 109 51 87 32 13 1 39 87] 1000 793476 793476 1735653 [65 24 63 62 88 59 57 99 27 47 25 70 30 4 31 0 57 89 24 79] 1000 837247 837247 1725460 [23 28 95 35 31 37 105 40 15 13 46 53 36 17 36 134 50 76 94 36] 1000 991714 991714 1762312 [20 86 116 42 32 52 59 11 55 49 41 102 82 59 17 7 7 28 31 104] 1000 838766 838767 1751715 [18 29 15 17 31 140 12 42 52 90 53 136 57 42 31 73 31 44 43 44] 1000 764370 764370 1726940 [64 5 78 77 127 90 43 14 46 0 46 70 63 20 42 57 3 20 58 77] D version (-O -release -inline -noboundscheck): n. randomize, n. equalize, buckets, buckets sum: 409363 2 [47, 0, 70, 77, 9, 0, 70, 36, 130, 24, 53, 64, 52, 17, 56, 65, 116, 65, 17, 40] 1008 2318049 2265054 [51, 51, 51, 51, 51, 51, 51, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 40] 1008 2063793 2447437 [9, 0, 196, 76, 0, 2, 60, 36, 23, 40, 17, 44, 0, 29, 156, 16, 147, 76, 41, 40] 1008 2010050 2579035 [51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 50, 51, 40] 1008 2180213 2151695 [152, 130, 12, 46, 6, 5, 10, 0, 0, 130, 109, 11, 73, 39, 15, 72, 0, 60, 98, 40] 1008 1930470 2646068 [50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 40] 1008 1967369 2650625 [64, 17, 16, 260, 29, 50, 94, 128, 65, 24, 49, 30, 42, 0, 35, 9, 28, 15, 13, 40] 1008 To compile the second Go version you need: import ( "fmt" "math/rand" "time" "sync" "runtime" ) ... func main() { // Create a concrete object implementing the bucketList interface. bl := newRwList(20, originalTotal, nUpdaters) And for the third: import ( "fmt" "math/rand" "time" "sync" "runtime" "sync/atomic" ) ... func main() { // Create a concrete object implementing the bucketList interface. bl := newLfList(20, originalTotal, nUpdaters) Bye, bearophile
Jan 22 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
 I have modified a bit the second and third Go versions on 
 Rosettacode,
The changes on the Go versions are only on my local copies of the code. Bye, bearophile
Jan 22 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
I have tried to scope the Mutex, but the D code gets a little 
slower, I don't know why:


5,6d5
< import std.typecons: scoped;
< import std.traits: ReturnType;
19,22c17,19
<         ReturnType!(scoped!Mutex) mtx;
<         alias this = value;
<     }
<     // pragma(msg, Bucket.sizeof); // 52 bytes
---
         Mutex mtx;
         alias this = value;
     }
31c28 < b = Bucket(uniform(0, 100), scoped!Mutex()); ---
             b = Bucket(uniform(0, 100), new Mutex());
35c32 < return buckets[index].value; ---
         return buckets[index];
70,76c67,68 < //sink(text(buckets)); < sink("["); < foreach (ref b; buckets) { < sink(text(b.value)); < sink(" "); < } < sink("] "); ---
         sink(text(buckets));
         sink(" ");
(And as you see the "alias this" of Bucket partially stops working). Bye, bearophile
Jan 22 2013
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
monarch_dodra:

 D has attomic swap operations too, AFAIK.
In core.atomic I think there is what's needed, cas and atomicOp: https://github.com/D-Programming-Language/druntime/blob/master/src/core/atomic.d Do you know why the site doesn't show the ddocs here? http://dlang.org/phobos/core_atomic.html Bye, bearophile
Jan 22 2013
next sibling parent reply Martin Drasar <drasar ics.muni.cz> writes:
On 22.1.2013 16:00, bearophile wrote:
 Do you know why the site doesn't show the ddocs here?
 http://dlang.org/phobos/core_atomic.html
Wild guess, but couldn't it be because the ddoc documentation is inside version(CoreDdoc) and not processed? Martin
Jan 22 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Martin Drasar:

 Wild guess, but couldn't it be because the ddoc documentation 
 is inside
 version(CoreDdoc) and not processed?
The question then becomes why is that version(CoreDdoc) used :-) Bye, bearophile
Jan 22 2013
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
 In core.atomic I think there is what's needed, cas and atomicOp:
I know what a cas is, but I don't have experience on this kind of coding. First try at a translation (doesn't work yet, and the global lock on buckets is missing still): import core.atomic: atomicLoad, atomicOp, cas; ... public void transfer(in size_t from, in size_t to, TBucketValue amount) { if (from == to) // Needed? return; buckets.RLock(); while (true) { auto v1 = atomicLoad(buckets[from].value); if (amount > v1) amount = v1; if (cas(&buckets[from].value, v1, v1 - amount)) { atomicOp!"+="(buckets[to].value, amount); break; } // Else retry. } buckets.RUnlock(); transfersCount++; } Bye, bearophile
Jan 22 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Second try at a translation of the third Go version. It seems to 
work correctly (comments welcome), but it seems slower:

http://codepad.org/y1LnjLl0

Bye,
bearophile
Jan 22 2013
prev sibling parent reply "qznc" <qznc go.to> writes:
On Tuesday, 22 January 2013 at 10:27:58 UTC, bearophile wrote:
 The Go language has four different solutions, one of them is:
 http://rosettacode.org/wiki/Atomic_updates#Lock-free


 From the site:

 This version uses no locking for the phase where the
 two clients are updating the buckets. Instead it
 watches for collisions and retries as needed.
func (bl *lfList) transfer(b1, b2, a int, ux int) { if b1 == b2 { return } bl.RLock() for { t := int32(a) v1 := atomic.LoadInt32(&bl.b[b1]) if t > v1 { t = v1 } if atomic.CompareAndSwapInt32(&bl.b[b1], v1, v1-t) { atomic.AddInt32(&bl.b[b2], t) break } // else retry } bl.tc[ux]++ bl.RUnlock() runtime.Gosched() }
Is that solution actually correct? If I am not mistaken, the buckets are in an inconsistent state between CompareAndSwapInt32 and AddInt32.
Jan 22 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 22 January 2013 at 14:10:14 UTC, qznc wrote:
 On Tuesday, 22 January 2013 at 10:27:58 UTC, bearophile wrote:
 The Go language has four different solutions, one of them is:
 http://rosettacode.org/wiki/Atomic_updates#Lock-free


 From the site:

 This version uses no locking for the phase where the
 two clients are updating the buckets. Instead it
 watches for collisions and retries as needed.
func (bl *lfList) transfer(b1, b2, a int, ux int) { if b1 == b2 { return } bl.RLock() for { t := int32(a) v1 := atomic.LoadInt32(&bl.b[b1]) if t > v1 { t = v1 } if atomic.CompareAndSwapInt32(&bl.b[b1], v1, v1-t) { atomic.AddInt32(&bl.b[b2], t) break } // else retry } bl.tc[ux]++ bl.RUnlock() runtime.Gosched() }
Is that solution actually correct? If I am not mistaken, the buckets are in an inconsistent state between CompareAndSwapInt32 and AddInt32.
So? buckets[from] -= realAmount; //Inconsistent state here buckets[to ] += realAmount; The bottom line is that there *has* to be a point in time where the state is inconsistent. Your job is to make sure this inconsistency does not overlap and corrupt the overall state.
Jan 22 2013
prev sibling parent reply "cal" <callumenator gmail.com> writes:
On Tuesday, 22 January 2013 at 09:47:25 UTC, monarch_dodra wrote:
 Avoids deadlock.

 imagine 2 threads:
 a: from 2 to 5.
 b: from 5 to 2.

 If both threads acquire their first lock, then you have a dead 
 lock, and your program is basically dead.

 By always locking low first, you avoid the deadlock in a rather 
 simple but elegant way.
Ah neat. And what about the case from = to? Why doesn' that deadlock in this code? (Concurrency is rather new to me)
Jan 22 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 22 January 2013 at 18:10:27 UTC, cal wrote:
 On Tuesday, 22 January 2013 at 09:47:25 UTC, monarch_dodra 
 wrote:
 Avoids deadlock.

 imagine 2 threads:
 a: from 2 to 5.
 b: from 5 to 2.

 If both threads acquire their first lock, then you have a dead 
 lock, and your program is basically dead.

 By always locking low first, you avoid the deadlock in a 
 rather simple but elegant way.
Ah neat. And what about the case from = to? Why doesn' that deadlock in this code? (Concurrency is rather new to me)
Because a single thread may acquire the same lock more than once. At which point, it will increment the lock counter. The lock is released when the counter reaches zero. This allows having easy "nested" logic, where a function does not have to worry if the caller function already has a lock.
Jan 22 2013
prev sibling parent reply "ixid" <nuaccount gmail.com> writes:
On Monday, 21 January 2013 at 20:35:16 UTC, bearophile wrote:
 qznc:

 Code: http://dpaste.dzfl.pl/e6615a53

 Any comments or improvements?
I have reformatted your code a little, according to the style used in all other D entries of RosettaCode: http://codepad.org/ceDyQ8lE The usage of a sink for toString() isn't common, but it's OK. I suggest to add something to make it stop after 20 seconds or so (I run all the rosettacode entries every so often to test them, so I prefer them to not go on forever. Some entries are required to produce infinite loops, but I think this time it's not necessary).
 I actually implemented a more scalable version than most of 
 the other languages used, by using a lock per item instead of 
 a single lock for the whole array.
Then I suggest you to add this comment before the entry. Bye, bearophile
I note you always seem to use "in" in your functions and on reddit seemed to imply that this was the idiomatic way of using D yet I recall Jonathan M Davies posting that using "in" was a bad idea.
Jan 22 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
ixid:

 I note you always seem to use "in" in your functions and on 
 reddit seemed to imply that this was the idiomatic way of using 
 D yet I recall Jonathan M Davies posting that using "in" was a 
 bad idea.
I think "in" is supposed to be(come) idiomatic, because it's short, and it's supposed to combine two attributes that you usually want, const and scope. On the other hand scope for arguments is not implemented yet (and Walter doesn't show lot of interest in implementing it, I don't know why. Few days ago Hara has said he wants to try to implement scope. But it's a lot of work, so I don't know if and when he will be done). So if you annotate something with scope, and you let the reference escape, the code now compiles, but later will break. Breaking the D code on Rosettacode is acceptable, because that site is like a wide variety of tiny test programs. So using "in" in Rosettacode is good. But if you are writing a largish D2 project, then Jonathan is right, it's better to not use "in" and scope arguments, unless you want to fix ton of future errors. Bye, bearophile
Jan 22 2013