Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Hash reference searching

by seggy (Initiate)
on Dec 07, 2009 at 17:12 UTC ( [id://811562]=perlquestion: print w/replies, xml ) Need Help??

seggy has asked for the wisdom of the Perl Monks concerning the following question:

Hello perlmonks, this is my first post so I hope I am posting on the correct forum section. So it seems that when executing an "exists" call on a hash reference (to check whether the corresponding value exists) the amount of time needed to complete the call is significantly higher compared to the same operation performed on a normal hash (not a hash reference). Is this behavior expected? Please check the following simple code highlighting what I described.
#!/usr/bin/perl -w use strict; use warnings; use Time::Local; my $range = 100000; my $ITERS = 30000; my (%HASH, $HASH_REF); for(my $iter = 1; $iter <= $ITERS; $iter++){ my $random_number = int(rand($range)); $HASH{$random_number} = 1; $HASH_REF->{$random_number} = 1; } my $TIME = time; for(my $iter = 1; $iter <= $ITERS; $iter++){ my $random_number = int(rand($range)); if( exists $HASH{$random_number} ){;} } my $ctime = time; my $exec_time = $ctime - $TIME; print 'Hash search :'."$exec_time\n"; $TIME = time; for(my $iter = 1; $iter <= $ITERS; $iter++){ my $random_number = int(rand($range)); if( exists {%{$HASH_REF}}->{$random_number} ){;} } $ctime = time; $exec_time = $ctime - $TIME; print 'Hashref search :'."$exec_time\n";

Replies are listed 'Best First'.
Re: Hash reference searching
by kyle (Abbot) on Dec 07, 2009 at 17:18 UTC

    This is a lot worse than it could be: exists {%{$HASH_REF}}->{$random_number}.

    What that does is dereference the hash %{$HASH_REF} in the context of creating another hash reference { ... }, which is then checked. On every iteration, you copy the whole referenced hash into a new hash reference and then destroy it.

    Write it this way instead: exists $HASH_REF->{$random_number}

    Update: If I were testing this, I'd probably use Benchmark like so:

    use Benchmark qw( cmpthese ); use List::Util qw( shuffle ); my $range = 100000; my $ITERS = 30000; my (%HASH, $HASH_REF); for(my $iter = 1; $iter <= $ITERS; $iter++){ my $random_number = int(rand($range)); $HASH{$random_number} = 1; $HASH_REF->{$random_number} = 1; } my @rand = map { int rand $range } 1 .. $ITERS; my @hits = shuffle keys %HASH; my @miss = grep { ! exists $HASH{$_} } 0 .. $range; cmpthese( -2, { hash_r => sub { map { exists $HASH{$_} } @rand }, ref_r => sub { map { exists $HASH_REF->{$_} } @rand }, hash_h => sub { map { exists $HASH{$_} } @hits }, ref_h => sub { map { exists $HASH_REF->{$_} } @hits }, hash_m => sub { map { exists $HASH{$_} } @miss }, ref_m => sub { map { exists $HASH_REF->{$_} } @miss }, } ); __END__ Rate ref_m hash_m ref_r ref_h hash_r hash_h ref_m 57.8/s -- -10% -56% -58% -59% -61% hash_m 64.2/s 11% -- -51% -54% -54% -56% ref_r 131/s 127% 105% -- -5% -6% -11% ref_h 139/s 140% 117% 6% -- -0% -6% hash_r 140/s 141% 117% 6% 0% -- -5% hash_h 147/s 155% 130% 12% 6% 6% --

    This way I test the difference between hits and misses as well as the random chance test you have. From this, it appears that the difference between exists finding or not finding something is a lot bigger than the difference between operating on a hash or a reference to a hash. In fact, I'd say the differences between hashes and references is so small as to be within the margin of error (which I usually think of as 5–10% with Benchmark).

    Update 2: Oops! Bad test. I was feeding in far more misses than hits. I should have said:

    my @rand = ( map { int rand $range } 1 .. $ITERS )[0 .. $ITERS/2]; my @hits = ( shuffle keys %HASH )[0 .. $ITERS/2]; my @miss = ( grep { ! exists $HASH{$_} } 0 .. $range )[0 .. $ITERS/2];

    Then the results are:

    Rate ref_h hash_h ref_r ref_m hash_r hash_m ref_h 229/s -- -10% -13% -18% -22% -30% hash_h 254/s 11% -- -3% -9% -14% -22% ref_r 263/s 15% 3% -- -6% -11% -19% ref_m 279/s 22% 10% 6% -- -5% -14% hash_r 295/s 29% 16% 12% 6% -- -10% hash_m 326/s 42% 28% 24% 17% 11% --

    Just the opposite of before. Misses are faster than hits. Hashes are faster than references, but not by much.

    I might also note: performance testing is hard.

      A test expression like
          map { exists $HASH{$_} } @rand
      seems to include a lot of superfluous temporary list construction and destruction redundant overhead extraneous activity.

      My approach would be simpler (please forgive a bit of slapdashery):

      >perl -wMstrict -le "use Benchmark qw(cmpthese); my %HASH; my $not_key = 'not_key'; $HASH{ rand() } = 1; compare(); $HASH{ rand() } = 1 for 0 .. 30_000; compare(); sub compare { print '------------------'; print 'hash keys/buckets: ' . %HASH; my ($is_key) = each %HASH; ! exists $HASH{$not_key} or die qq{$not_key should not exist}; exists $HASH{$is_key} or die qq{$is_key should exist}; print qq{test keys '$is_key' and '$not_key' seem ok}; my $HR = \%HASH; cmpthese(-2, { hash_hit => sub { exists $HASH{$is_key} }, hash_miss => sub { exists $HASH{$not_key} }, href_hit => sub { exists $HR->{$is_key} }, href_miss => sub { exists $HR->{$not_key} }, }); } " ------------------ hash keys/buckets: 1/8 test keys '0.408477783203125' and 'not_key' seem ok Rate hash_miss href_miss href_hit hash_hit hash_miss 3305141/s -- -6% -22% -42% href_miss 3520236/s 7% -- -16% -39% href_hit 4215045/s 28% 20% -- -27% hash_hit 5746274/s 74% 63% 36% -- ------------------ hash keys/buckets: 14778/32768 test keys '0.091217041015625' and 'not_key' seem ok Rate href_miss href_hit hash_miss hash_hit href_miss 3392515/s -- -18% -21% -36% href_hit 4126900/s 22% -- -3% -23% hash_miss 4272362/s 26% 4% -- -20% hash_hit 5329295/s 57% 29% 25% --

      Hashes still seem faster than references, but hits seem faster than misses. Overall differences are still not compelling.

      Update: The results above support the notion that hash key lookup (e.g., with exists) is O(1), so the idea of direct or indirect hash lookup being 'faster' might not have much meaning even if the timing differences were more significant.

Re: Hash reference searching
by Gangabass (Vicar) on Dec 07, 2009 at 17:20 UTC

    The right way for hash ref is:

    if( exists $HASH_REF->{$random_number} ){;}

    Also use Benchmark; for such tasks.

Re: Hash reference searching
by JadeNB (Chaplain) on Dec 07, 2009 at 17:25 UTC

    I find your hashref-checking code quite strange—you are de-referencing (%{$HASH_REF}) a hashref ($HASH_REF), then treating the de-reference as a hash-ref itself ({%{$HASH_REF}}->{$random_number})—which I wouldn't expect to run at all. (UPDATE: kyle explained what I was too sleepy to notice—the extra pair of braces is re-creating a hashref from the de-referenced hashref, and you're then de-referencing it again before checking for existence.) Anyway, it does run, and I also observe a significant slow-down in the second loop, whatever it's doing.

    Since I don't know what the second loop is doing, there could be lots of reasons, but one obvious candidate is that indirection has a cost, and all that de-referencing doesn't come for free. Changing the second loop to

    my %HASH_DEREF = %$HASH_REF; for(...){ my $random_number = ...; 1 if exists $HASH_DEREF{$random_number}; }
    gives a running time nearly identical to the first.

Re: Hash reference searching
by Anonymous Monk on Dec 08, 2009 at 00:21 UTC
    I reckon since you have $HASH{$random_number} and $HASH_REF->{$random_number} both values defined then you be better off checking using the defined and not the exists function...

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://811562]
Approved by JadeNB
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (8)
As of 2024-04-18 10:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found