NAME

VERSION

DESCRIPTION

This module implements an ordered hash featuring tombstone deletion, inspired by Hash::Ordered. An ordered hash is very much like a normal hash but with key insertion order preserved.

It provides "splice", sorting, plus extra capabilities for use with MCE::Shared::Minidb. Tombstone deletion is further optimized to not impact "store", "push", "unshift", and "merge". Tombstones are purged in-place for lesser memory consumption. In addition, "pop" and "shift" run optimally when an index is present. The optimization also applies to forward and reverse deletes. The end result is achieving a new level of performance, for a pure-Perl ordered hash implementation.

SYNOPSIS

 # non-shared or local construction for use by a single process

 use MCE::Shared::Ordhash;

 my $oh = MCE::Shared::Ordhash->new( @pairs );

 # construction for sharing with other threads and processes

 use MCE::Shared;

 my $oh = MCE::Shared->ordhash( @pairs );

 # hash-like dereferencing

 my $val = $oh->{$key};
 $oh->{$key} = $val;

 %{$oh} = ();

 # OO interface

 if ( !defined ( $val = $oh->get("some_key") ) ) {
    $val = $oh->set( some_key => "some_value" );
 }

 $val   = $oh->set( $key, $val );
 $ret   = $oh->setnx( $key, $val );         # set only if the key exists
 $val   = $oh->get( $key );
 $val   = $oh->delete( $key );              # del is an alias for delete
 $bool  = $oh->exists( $key );
 void   = $oh->clear();
 $len   = $oh->len();                       # scalar keys %{ $oh }
 $len   = $oh->len( $key );                 # length $oh->{ $key }
 @pair  = $oh->pop();
 $len   = $oh->push( @pairs );
 @pair  = $oh->shift();
 $len   = $oh->unshift( @pairs );
 %pairs = $oh->splice( $offset, $length, @pairs );

 $oh2   = $oh->clone( @keys );              # @keys is optional
 $oh3   = $oh->flush( @keys );
 $iter  = $oh->iterator( @keys );           # ($key, $val) = $iter->()
 @keys  = $oh->keys( @keys );
 %pairs = $oh->pairs( @keys );
 @vals  = $oh->values( @keys );             # vals is an alias for values

 $len   = $oh->assign( $key/$val pairs );   # equivalent to ->clear, ->mset
 $cnt   = $oh->mdel( @keys );
 @vals  = $oh->mget( @keys );
 $bool  = $oh->mexists( @keys );            # true if all keys exists
 $len   = $oh->mset( $key/$val pairs );     # merge is an alias for mset

 @vals  = $oh->sort();                      # by val $a <=> $b default
 @vals  = $oh->sort( "desc" );              # by val $b <=> $a
 @vals  = $oh->sort( "alpha" );             # by val $a cmp $b
 @vals  = $oh->sort( "alpha desc" );        # by val $b cmp $a

 @vals  = $oh->sort( "key" );               # by key $a <=> $b
 @vals  = $oh->sort( "key desc" );          # by key $b <=> $a
 @vals  = $oh->sort( "key alpha" );         # by key $a cmp $b
 @vals  = $oh->sort( "key alpha desc" );    # by key $b cmp $a

 # included, sugar methods without having to call set/get explicitly

 $len   = $oh->append( $key, $string );     #   $val .= $string
 $val   = $oh->decr( $key );                # --$val
 $val   = $oh->decrby( $key, $number );     #   $val -= $number
 $val   = $oh->getdecr( $key );             #   $val--
 $val   = $oh->getincr( $key );             #   $val++
 $val   = $oh->incr( $key );                # ++$val
 $val   = $oh->incrby( $key, $number );     #   $val += $number
 $old   = $oh->getset( $key, $new );        #   $o = $v, $v = $n, $o

 # pipeline, provides atomicity for shared objects, MCE::Shared v1.09+

 @vals  = $oh->pipeline(                    # ( "a_a", "b_b", "c_c" )
    [ "set", foo => "a_a" ],
    [ "set", bar => "b_b" ],
    [ "set", baz => "c_c" ],
    [ "mget", qw/ foo bar baz / ]
 );

For normal hash behavior, the TIE interface is supported.

 # non-shared or local construction for use by a single process

 use MCE::Shared::Ordhash;

 tie my %oh, "MCE::Shared::Ordhash", @pairs;
 tie my %oh, "MCE::Shared::Ordhash";

 # construction for sharing with other threads and processes
 # the ordered option is needed to know to use MCE::Shared::Ordhash

 use MCE::Shared;

 tie my %oh, "MCE::Shared", { ordered => 1 }, @pairs;
 tie my %oh, "MCE::Shared", ordered => 1;

 # usage

 my $val;

 if ( !defined ( $val = $oh{some_key} ) ) {
    $val = $oh{some_key} = "some_value";
 }

 $oh{some_key} = 0;

 tied(%oh)->incrby("some_key", 20);
 tied(%oh)->incrby(some_key => 20);

SYNTAX for QUERY STRING

 o Basic demonstration

   @keys = $oh->keys( "query string given here" );
   @keys = $oh->keys( "val =~ /pattern/" );

 o Supported operators: =~ !~ eq ne lt le gt ge == != < <= > >=
 o Multiple expressions delimited by :AND or :OR, mixed case allowed

   "key eq 'some key' :or (val > 5 :and val < 9)"
   "key eq some key :or (val > 5 :and val < 9)"
   "key =~ /pattern/i :And val =~ /pattern/i"
   "val eq foo baz :OR key !~ /pattern/i"

   * key matches on keys in the hash
   * likewise, val matches on values

 o Quoting is optional inside the string

   "key =~ /pattern/i :AND val eq 'foo bar'"   # val eq "foo bar"
   "key =~ /pattern/i :AND val eq foo bar"     # val eq "foo bar"

Examples.

 # search capability key/val: =~ !~ eq ne lt le gt ge == != < <= > >=
 # key/val means to match against actual key/val respectively

 @keys  = $oh->keys( "key eq 'some key' :or (val > 5 :and val < 9)" );
 @keys  = $oh->keys( "key eq some key :or (val > 5 :and val < 9)" );

 @keys  = $oh->keys( "key =~ /$pattern/i" );
 @keys  = $oh->keys( "key !~ /$pattern/i" );
 @keys  = $oh->keys( "val =~ /$pattern/i" );
 @keys  = $oh->keys( "val !~ /$pattern/i" );

 %pairs = $oh->pairs( "key == $number" );
 %pairs = $oh->pairs( "key != $number :and val > 100" );
 %pairs = $oh->pairs( "key <  $number :or key > $number" );
 %pairs = $oh->pairs( "val <= $number" );
 %pairs = $oh->pairs( "val >  $number" );
 %pairs = $oh->pairs( "val >= $number" );

 @vals  = $oh->vals( "key eq $string" );
 @vals  = $oh->vals( "key ne $string with space" );
 @vals  = $oh->vals( "key lt $string :or val =~ /$pat1|$pat2/" );
 @vals  = $oh->vals( "val le $string :and val eq 'foo bar'" );
 @vals  = $oh->vals( "val le $string :and val eq foo bar" );
 @vals  = $oh->vals( "val gt $string" );
 @vals  = $oh->vals( "val ge $string" );

API DOCUMENTATION

 # non-shared or local construction for use by a single process

 use MCE::Shared::Ordhash;

 $oh = MCE::Shared::Ordhash->new( @pairs );
 $oh = MCE::Shared::Ordhash->new( );

 # construction for sharing with other threads and processes

 use MCE::Shared;

 $oh = MCE::Shared->ordhash( @pairs );
 $oh = MCE::Shared->ordhash( );

 $len = $oh->assign( "key1" => "val1", "key2" => "val2" );  # 2
 $len = %{$oh} = ( "key1" => "val1", "key2" => "val2" );    # 4

 $oh->clear;
 %{$oh} = ();

 $oh2 = $oh->clone( "key1", "key2" );
 $oh2 = $oh->clone;

 $val = $oh->delete( "some_key" );
 $val = delete $oh->{ "some_key" };

 if ( $oh->exists( "some_key" ) ) { ... }
 if ( exists $oh->{ "some_key" } ) { ... }

 $val = $oh->get( "some_key" );
 $val = $oh->{ "some_key" };

 $iter = $oh->iterator;
 $iter = $oh->iterator( "key1", "key2" );

 while ( my ( $key, $val ) = $iter->() ) {
    ...
 }

 $iter = $oh->iterator( "val eq some_value" );
 $iter = $oh->iterator( "key eq some_key :AND val =~ /sun|moon|air|wind/" );
 $iter = $oh->iterator( "val eq sun :OR val eq moon :OR val eq foo" );
 $iter = $oh->iterator( "key =~ /$pattern/" );

 while ( my ( $key, $val ) = $iter->() ) {
    ...
 }

 @keys = $oh->keys( "key1", "key2" );

 @keys = $oh->keys;     # faster
 @keys = keys %{$oh};   # involves TIE overhead

 $len  = $oh->keys;     # ditto
 $len  = keys %{$oh};

 @keys = $oh->keys( "val eq some_value" );
 @keys = $oh->keys( "key eq some_key :AND val =~ /sun|moon|air|wind/" );
 @keys = $oh->keys( "val eq sun :OR val eq moon :OR val eq foo" );
 $len  = $oh->keys( "key =~ /$pattern/" );

 $size = $oh->len;
 $len  = $oh->len( "key1" );
 $len  = length $oh->{ "key1" };

 $cnt = $oh->mdel( "key1", "key2" );

 if ( $oh->mexists( "key1", "key2" ) ) { ... }

 ( $val1, $val2 ) = $oh->mget( "key1", "key2" );

 $len = $oh->mset( "key1" => "val1", "key2" => "val2" );

 @pairs = $oh->pairs( "key1", "key2" );

 @pairs = $oh->pairs;
 $len   = $oh->pairs;

 @pairs = $oh->pairs( "val eq some_value" );
 @pairs = $oh->pairs( "key eq some_key :AND val =~ /sun|moon|air|wind/" );
 @pairs = $oh->pairs( "val eq sun :OR val eq moon :OR val eq foo" );
 $len   = $oh->pairs( "key =~ /$pattern/" );

 @vals = $oh->pipeline(                     # ( "a_a", "b_b", "c_c" )
    [ "set", foo => "a_a" ],
    [ "set", bar => "b_b" ],
    [ "set", baz => "c_c" ],
    [ "mget", qw/ foo bar baz / ]
 );

 $len = $oh->pipeline(                      # 3, same as $oh->len
    [ "set", foo => "i_i" ],
    [ "set", bar => "j_j" ],
    [ "set", baz => "k_k" ],
    [ "len" ]
 );

 $oh->pipeline(
    [ "set", foo => "m_m" ],
    [ "set", bar => "n_n" ],
    [ "set", baz => "o_o" ]
 );

 @vals = $oh->pipeline_ex(                  # ( "a_a", "b_b", "c_c" )
    [ "set", foo => "a_a" ],
    [ "set", bar => "b_b" ],
    [ "set", baz => "c_c" ]
 );

 ( $key, $val ) = $oh->pop;

 $val = $oh->pop;

 $oh->purge;

 $len = $oh->push( "key1", "val1", "key2", "val2" );

 $val = $oh->set( "key", "value" );
 $val = $oh->{ "key" } = "value";

 $ret = $oh->setnx( "key", "value" );

 ( $key, $val ) = $oh->shift;

 $val = $oh->shift;

 @keys = $oh->sort( "BY val" );

 $oh->sort();

 @keys = $oh->sort( "BY key ALPHA" );

 $oh->sort( "BY val ALPHA" );

 @keys = $oh->sort( "BY val DESC ALPHA" );

 $oh->sort( "BY key DESC ALPHA" );

 @pairs = $oh->splice( 20, 2, @pairs );
 @pairs = $oh->splice( 20, 2 );
 @pairs = $oh->splice( 20 );

 $len = $oh->unshift( "key1", "val1", "key2", "val2" );

 @vals = $oh->values( "key1", "key2" );

 @vals = $oh->values;     # faster
 @vals = values %{$oh};   # involves TIE overhead

 $len  = $oh->values;     # ditto
 $len  = values %{$oh};

 @vals = $oh->values( "val eq some_value" );
 @vals = $oh->values( "key eq some_key :AND val =~ /sun|moon|air|wind/" );
 @vals = $oh->values( "val eq sun :OR val eq moon :OR val eq foo" );
 $len  = $oh->values( "key =~ /$pattern/" );

SUGAR METHODS

The API resembles a subset of the Redis primitives <http://redis.io/commands#strings> with key representing the hash key.

 $len = $oh->append( $key, "foo" );

 $num = $oh->decr( $key );

 $num = $oh->decrby( $key, 2 );

 $old = $oh->getdecr( $key );

 $old = $oh->getincr( $key );

 $old = $oh->getset( $key, "baz" );

 $num = $oh->incr( $key );

 $num = $oh->incrby( $key, 2 );

CREDITS

MOTIVATION

MCE::Shared has only one shared-manager process which is by design. Therefore, re-factored tombstone deletion with extras for lesser impact to the rest of the library. This module differs in personality from Hash::Ordered mainly for compatibility with the other classes included with MCE::Shared.

The following simulates a usage pattern inside MCE::Hobo involving random key deletion. For example, an application joining a list of Hobos provided by "MCE::Hobo->list_joinable".

 use MCE::Shared::Ordhash;
 use List::Util 'shuffle';
 use Time::HiRes 'time';

 srand 0;

 my $oh = MCE::Shared::Ordhash->new();
 my $num_keys = 200000;
 my $start = time();

 $oh->set($_,$_) for 1 .. $num_keys;

 for ( shuffle $oh->keys ) {
    $oh->delete($_);
 }

 printf "duration: %7.03f secs\n", time() - $start;

Both the runtime and memory consumption are captured for the demonstration. Results are included for MCE::Shared::Hash (unordered hash) for comparison.

 for ( shuffle $oh->keys ) { $oh->delete($_) }

 0.378 secs.  35 MB  MCE::Shared::Hash (unordered)
 0.437 secs.  49 MB  Tie::Hash::Indexed (XS)
 0.743 secs.  54 MB  MCE::Shared::Ordhash
 1.028 secs.  60 MB  Hash::Ordered
 1.752 secs. 112 MB  Tie::LLHash
  > 42 mins.  66 MB  Tie::IxHash

Using the same demonstration above, another usage pattern inside MCE::Hobo involves orderly hash-key deletion. For example, waiting for and joining all Hobos provided by "MCE::Hobo->list".

 for ( $oh->keys ) { $oh->delete($_) }

 0.353 secs.  35 MB  MCE::Shared::Hash (unordered)
 0.349 secs.  49 MB  Tie::Hash::Indexed (XS)
 0.452 secs.  41 MB  MCE::Shared::Ordhash
 0.735 secs.  54 MB  Hash::Ordered
 1.338 secs. 112 MB  Tie::LLHash
  > 42 mins.  66 MB  Tie::IxHash

No matter if orderly or randomly, even backwards, hash-key deletion in "MCE::Shared::Ordhash" performs reasonably well. The following provides the construction used for the modules mentioned.

 my $oh = Hash::Ordered->new();
    $oh->set($_,$_);   $oh->keys;  $oh->delete($_);

 my $oh = Tie::Hash::Indexed->new();
    $oh->set($_,$_);   $oh->keys;  $oh->delete($_);

 my $oh = Tie::IxHash->new();
    $oh->STORE($_,$_); $oh->Keys;  $oh->DELETE($_);

 my $oh = tie my %hash, 'Tie::LLHash';
    $oh->last($_,$_);  keys %hash; $oh->DELETE($_);

Hash::Ordered is supported for use with MCE::Shared. This includes on-demand hash-like dereferencing, similarly to "hash" and "ordhash".

 use feature 'say';

 use MCE::Hobo;
 use MCE::Shared;
 use Hash::Ordered; # 0.010 or later

 my $ha = MCE::Shared->hash();    # shared MCE::Shared::Hash
 my $oh = MCE::Shared->ordhash(); # shared MCE::Shared::Ordhash

 my $ho = MCE::Shared->share( Hash::Ordered->new() );

 sub parallel_task {
    my ($id) = @_;

    # OO interface
    if ($id == 1) {
       $ha->set("$id", "foo");
       $oh->set("$id", "foo");
       $ho->set("$id", "foo");
    }
    # hash-like dereferencing
    elsif ($id == 2) {
       $ha->{"$id"} = "baz";
       $oh->{"$id"} = "baz";
       $ho->{"$id"} = "baz";
    }

    return;
 }

 MCE::Hobo->create("parallel_task", $_) for 1..2;
 MCE::Hobo->waitall;

 say $ha->{"1"};     # foo
 say $oh->{"1"};
 say $ho->{"1"};

 say $ha->get("2");  # baz
 say $oh->get("2");
 say $ho->get("2");

SEE ALSO

• Hash::Ordered
• Tie::Hash::Indexed
• Tie::IxHash
• Tie::LLHash

INDEX

AUTHOR