Re: Atomic updates
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.
Re: Atomic updates
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?
Re: Atomic updates
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.
Re: Atomic updates
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?.
Re: Atomic updates
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
Re: Atomic updates
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
Re: Atomic updates
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
Re: Atomic updates
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.
Re: Atomic updates
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.
Re: Atomic updates
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
Re: Atomic updates
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
Re: Atomic updates
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
Re: Atomic updates
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)
Re: Atomic updates
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.
Re: Atomic updates
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.
Re: Atomic updates
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
Re: Atomic updates
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
Re: Atomic updates
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));
}
Re: Atomic updates
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
