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?".

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

> 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

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

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.

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.

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

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

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

> 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