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