in reply to Re^3: Avoid Locking Entire Hashes
in thread Avoid Locking Entire Hashes

Thanks! Fascinating solution except that I think it is not thread-safe.. 


TIMESTEP 0:

    Say, $h{$k} points to v1 
    Thread T0: Holding lock on v1
    Thread T1: Waiting on Lock on v1 

TIMESTEP 1:

    T0 changes $h{$k} = \$v2, releases lock on $v1

TIMESTAMP 2: (Thread T2 makes an entrance)

    Thread T2: Acquires Lock on v2, proceeds
    Thread T1: Acquires Lock on v1, proceeds
    <Race-around condition>

[download]

Replies are listed 'Best First'.
Re^4: Avoid Locking Entire Hashes
by BrowserUk (Patriarch) on Jun 15, 2011 at 08:09 UTC

    I've tried everything I can think of to provoke this 'race condition', but I've yet to see it manifest itself in real code:

    #! perl -slw
use strict;
use Data::Dump qw[ pp ];
use Time::HiRes qw[ time ];
use List::Util qw[ shuffle ];
use threads;
use threads::shared;

our $START //= 'aaa';
our $END   //= 'zzz';

my %hash :shared = map{ my $n :shared = 0; $_ => \$n } $START .. $END;

my $start = time;
$_->join for map{
    async{
        my @order;
        {
            lock %hash;
            @order = shuffle keys %hash;
        }
        for ( @order ) {
            lock ${ $hash{ $_ } };
            ++${ $hash{ $_ } };
        }
    }
} 1 .. 40;

printf "Lock scalar ref took %.3f seconds\n", time() - $start;

my @fails = grep $$_ != 40, values %hash;
warn @fails . " fails\n" if @fails;

__END__
C:\test>909437-2
Lock scalar ref took 42.807 seconds

    [download]

    By all means show me how?

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
Re^4: Avoid Locking Entire Hashes
by BrowserUk (Patriarch) on Jun 15, 2011 at 04:22 UTC

    Neither it seems is ikegami's original suggestion:

    #! perl -slw
use strict;
use Data::Dump qw[ pp ];
use Time::HiRes qw[ time ];
use List::Util qw[ shuffle ];
use threads;
use threads::shared;

our $START //= 'aaa';
our $END   //= 'zzz';

my %sems :shared = map{ my $n :shared = 0; $_ => \$n } $START .. $END;
my %hash :shared = map{ $_ => 0 } $START .. $END;

my $start = time;
$_->join for map{
    async{
        my @order = shuffle keys %hash;
        for ( @order ) {
            lock ${ $sems{ $_ } };
            ++$hash{ $_ };
        }
    }
} 1 .. 4;

printf "Lock scalar ref took %.3f seconds\n", time() - $start;

my @fails = grep $_ != 4, values %hash;

warn @fails . " fails\n" if @fails;

__END__
C:\test>909437-3
Lock scalar ref took 2.937 seconds
2840 fails

    [download]
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]

      Neither it seems is ikegami's original suggestion:

      We knew that two days ago, so we fixed it two days ago.

[reply]

        The modified version is broken also. As demonstrated by the attached code.

        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

In Section Seekers of Perl Wisdom