MCE::Shared::Ordhash - An ordered hash class featuring tombstone deletion
This document describes MCE::Shared::Ordhash version 1.699_013
# non-shared use MCE::Shared::Ordhash; my $oh = MCE::Shared::Ordhash->new( @pairs ); # shared use MCE::Shared; my $oh = MCE::Shared->ordhash( @pairs ); # oo interface $val = $oh->set( $key, $val ); $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 $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 # search capability key/val { =~ !~ eq ne lt le gt ge == != < <= > >= } # key/val means to match against actual key/val respectively # do not add quotes inside the string unless intended literally # do not mix :AND(s) and :OR(s) together @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->values( "key eq $string" ); @vals = $oh->values( "key ne $string with space" ); @vals = $oh->values( "key lt $string :OR val =~ /$pat1|$pat2/" ); @vals = $oh->values( "val le $string :AND val eq foo bar" ); @vals = $oh->values( "val gt $string" ); @vals = $oh->values( "val ge $string" ); # 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
This module implements an ordered hash featuring tombstone deletion, inspired by the Hash::Ordered module. An ordered hash means the key insertion order is 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.
splice
store
push
unshift
merge
pop
shift
The end result is achieving a new level of performance, for a pure-Perl ordered hash implementation.
Several methods in MCE::Shared::Ordhash take a query string for an argument. The format of the string is quoteless. Therefore, any quotes inside the string is treated literally.
MCE::Shared::Ordhash
o Basic demonstration: @keys = $oh->keys( "val =~ /pattern/" ); o Supported operators: =~ !~ eq ne lt le gt ge == != < <= > >= o Multiple expressions are delimited by :AND or :OR. "key =~ /pattern/i :AND val =~ /pattern/i" "key =~ /pattern/i :AND val eq foo bar" # val eq "foo bar" "val eq foo baz :OR key !~ /pattern/i" * key matches on keys in the hash * val matches on values
The modifiers :AND and :OR may be mixed case. e.g. :And
:AND
:OR
:And
Mixing :AND and :OR in the query is not supported.
This module involves TIE when accessing the object via hash-like behavior. Both non-shared and shared instances are impacted if doing so. Although likely fast enough for many use cases, use the OO interface if better performance is desired.
Constructs a new object, with an optional list of key-value pairs.
# non-shared use MCE::Shared::Ordhash; $oh = MCE::Shared::Ordhash->new( @pairs ); $oh = MCE::Shared::Ordhash->new( ); # shared use MCE::Shared; $oh = MCE::Shared->ordhash( @pairs ); $oh = MCE::Shared->ordhash( );
Removes all key-value pairs from the hash.
$oh->clear; %{$oh} = ();
Creates a shallow copy, a MCE::Shared::Ordhash object. It returns an exact copy if no arguments are given. Otherwise, the object includes only the given keys in the same order. Keys that do not exist in the hash will have the undef value.
undef
$oh2 = $oh->clone( "key1", "key2" ); $oh2 = $oh->clone;
Deletes and returns the value by given key or undef if the key does not exists in the hash.
$val = $oh->delete( "some_key" ); $val = delete $oh->{ "some_key" };
del is an alias for delete.
del
delete
Determines if a key exists in the hash.
if ( $oh->exists( "some_key" ) ) { ... } if ( exists $oh->{ "some_key" } ) { ... }
Same as clone. Though, clears all existing items before returning.
clone
Gets the value of a hash key or undef if the key does not exists.
$val = $oh->get( "some_key" ); $val = $oh->{ "some_key" };
Returns a code reference for iterating a list of key-value pairs stored in the hash when no arguments are given. Otherwise, returns a code reference for iterating the given keys in the same order. Keys that do not exist will have the undef value.
The list of keys to return is set when the closure is constructed. Later keys added to the hash are not included. Subsequently, the undef value is returned for deleted keys.
$iter = $oh->iterator; $iter = $oh->iterator( "key1", "key2" ); while ( my ( $key, $val ) = $iter->() ) { ... }
Returns a code reference for iterating a list of key-value pairs that match the given criteria. It returns an empty list if the search found nothing. The syntax for the query string is described above.
query string
$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->() ) { ... }
Returns hash keys in the same insertion order when no arguments are given. Otherwise, returns the given keys in the same order. Keys that do not exist will have the undef value. In scalar context, returns the size of the hash.
@keys = $oh->keys; @keys = $oh->keys( "key1", "key2" ); $len = $oh->keys;
Returns only keys that match the given criteria. It returns an empty list if the search found nothing. The syntax for the query string is described above. In scalar context, returns the size of the resulting list.
@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/" );
Returns the size of the hash when no arguments are given. For the given key, returns the length of the value stored at key or the undef value if the key does not exists.
$size = $oh->len; $len = $oh->len( "key1" ); $len = length $oh->{ "key1" };
Deletes one or more keys in the hash and returns the number of keys deleted. A given key which does not exist in the hash is not counted.
$cnt = $oh->mdel( "key1", "key2" );
Returns a true value if all given keys exists in the hash. A false value is returned otherwise.
if ( $oh->mexists( "key1", "key2" ) ) { ... }
Gets the values of all given keys. It returns undef for keys which do not exists in the hash.
( $val1, $val2 ) = $oh->mget( "key1", "key2" );
Sets multiple key-value pairs in a hash and returns the number of keys stored in the hash.
$len = $oh->mset( "key1" => "val1", "key2" => "val2" );
merge is an alias for mset.
mset
Returns key-value pairs in the same insertion order when no arguments are given. Otherwise, returns key-value pairs for the given keys in the same order. Keys that do not exist will have the undef value. In scalar context, returns the size of the hash.
@pairs = $oh->pairs; @pairs = $oh->pairs( "key1", "key2" ); $len = $oh->pairs;
Returns only key-value pairs that match the given criteria. It returns an empty list if the search found nothing. The syntax for the query string is described above. In scalar context, returns the size of the resulting list.
@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/" );
Removes and returns the last key-value pair or value in scalar context of the ordered hash. If there are no keys in the hash, returns the undefined value.
( $key, $val ) = $oh->pop; $val = $oh->shift;
A utility method for purging any *tombstones* in the keys array. It also resets a couple counters internally. Call this method before serializing to a file, which is the case in MCE::Shared::Minidb.
MCE::Shared::Minidb
$oh->purge;
Appends one or multiple key-value pairs to the tail of the ordered hash and returns the new length. Any keys already existing in the hash are re-inserted with the new values.
$len = $oh->push( "key1", "val1", "key2", "val2" );
Sets the value of the given hash key and returns its new value.
$val = $oh->set( "key", "value" ); $val = $oh->{ "key" } = "value";
Removes and returns the first key-value pair or value in scalar context of the ordered hash. If there are no keys in the hash, returns the undefined value.
( $key, $val ) = $oh->shift; $val = $oh->shift;
Returns sorted keys in list context, leaving the elements intact. In void context, sorts the hash in-place. By default, sorting is numeric and applied to values when no arguments are given.
@keys = $oh->sort( "BY val" ); $oh->sort();
If the keys or values contain string values and you want to sort them lexicographically, specify the ALPHA modifier.
ALPHA
@keys = $oh->sort( "BY key ALPHA" ); $oh->sort( "BY val ALPHA" );
The default is ASC for sorting the hash from small to large. In order to sort the hash from large to small, specify the DESC modifier.
ASC
DESC
@keys = $oh->sort( "BY val DESC ALPHA" ); $oh->sort( "BY key DESC ALPHA" );
Removes the key-value pairs designated by offset and length from the ordered hash, and replaces them with key-value pairs, if any. The behavior is similar to the Perl splice function.
offset
length
key-value pairs
@pairs = $oh->splice( 20, 2, @pairs ); @pairs = $oh->splice( 20, 2 ); @pairs = $oh->splice( 20 );
Prepends one or multiple key-value pairs to the head of the ordered hash and returns the new length. Any keys already existing in the hash are re-inserted with the new values.
$len = $oh->unshift( "key1", "val1", "key2", "val2" );
Returns hash values in the same insertion order when no arguments are given. Otherwise, returns values for the given keys in the same order. Keys that do not exist will have the undef value. In scalar context, returns the size of the hash.
@vals = $oh->values; @vals = $oh->values( "key1", "key2" ); $len = $oh->values;
Returns only values that match the given criteria. It returns an empty list if the search found nothing. The syntax for the query string is described above. In scalar context, returns the size of the resulting list.
@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/" );
vals is an alias for values.
vals
values
This module is equipped with sugar methods to not have to call set and get explicitly. The API resembles a subset of the Redis primitives http://redis.io/commands#strings with key representing the hash key.
set
get
Appends a value to a key and returns its new length.
$len = $oh->append( $key, "foo" );
Decrements the value of a key by one and returns its new value.
$num = $oh->decr( $key );
Decrements the value of a key by the given number and returns its new value.
$num = $oh->decrby( $key, 2 );
Decrements the value of a key by one and returns its old value.
$old = $oh->getdecr( $key );
Increments the value of a key by one and returns its old value.
$old = $oh->getincr( $key );
Sets the value of a key and returns its old value.
$old = $oh->getset( $key, "baz" );
Increments the value of a key by one and returns its new value.
$num = $oh->incr( $key );
Increments the value of a key by the given number and returns its new value.
$num = $oh->incrby( $key, 2 );
Many thanks to David Golden for Hash::Ordered. This implementation is inspired by Hash::Ordered v0.009.
I wanted an ordered hash implementation for use with MCE::Shared without any side effects. For example, linear scans, slow deletes, or excessive memory consumption. The closest module on CPAN to pass in this regard is Hash::Ordered by David Golden.
MCE::Shared has only one shared-manager process which is by design. Therefore, refactored 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 various 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>.
MCE::Hobo-
use MCE::Shared::Ordhash; use List::Util 'shuffle'; use Time::HiRes 'time'; srand 1618; 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. Result for MCE::Shared::Hash is included for seeing how much longer a given ordered hash implementation takes in comparison.
for ( shuffle $oh->keys ) { $oh->delete($_) } 0.362 secs. 55 MB MCE::Shared::Hash; unordered hash 0.626 secs. 126 MB Tie::Hash::Indexed; (XS) ordered hash 0.720 secs. 74 MB MCE::Shared::Ordhash; ordered hash ** 1.032 secs. 74 MB Hash::Ordered; ordered hash 1.756 secs. 161 MB Tie::LLHash; ordered hash > 42 mins. 79 MB Tie::IxHash; ordered hash (stopped)
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.332 secs. 55 MB MCE::Shared::Hash; unordered hash 0.447 secs. 67 MB MCE::Shared::Ordhash; ordered hash ** 0.503 secs. 126 MB Tie::Hash::Indexed; (XS) ordered hash 0.802 secs. 74 MB Hash::Ordered; ordered hash 1.337 secs. 161 MB Tie::LLHash; ordered hash > 42 mins. 79 MB Tie::IxHash; ordered hash (stopped)
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. Basically, key setting and deletion is through the OO interface for fair comparison.
my $oh = Hash::Ordered->new(); $oh->set($_,$_); $oh->keys; $oh->delete($_); my $oh = tie my %hash, 'Tie::Hash::Indexed'; $oh->STORE($_,$_); keys %hash; $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
Tie::Hash::Indexed
Tie::IxHash
Tie::LLHash
MCE, MCE::Core, MCE::Shared
Mario E. Roy, <marioeroy AT gmail DOT com>
To install MCE, copy and paste the appropriate command in to your terminal.
cpanm
cpanm MCE
CPAN shell
perl -MCPAN -e shell install MCE
For more information on module installation, please visit the detailed CPAN module installation guide.