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.

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

Some more little changes, I have added counters, and I have used the faster Xorshift:

http://codepad.org/hIFPgSTd

Bye,
bearophile

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.

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));
    }

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

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.

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?

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.

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