Re: Does "preallocating hash improve performance"? Or "using a hash slice"?

[dave_the_m]

So, are my tests flawed

Kinda. Your benchmarks are dominated by the time taken to generate @a and 'map log @a'. If these are precomputed you can start to see a big improvement with slicing and a smaller improvement with pre-sizing.

use strict;
use warnings;
use Benchmark qw/ cmpthese /;;

for my $count ( 100, 1_000, 10_000, 100_000 ) {
    my @a = map { log } 2 .. $count;
    my @b = map log @a;
    cmpthese( -5, {
        1 => sub {
            my %h;
            keys %h = @a;
            $h{ $_ } = log for @a;
            return \%h
        },
        2 => sub {
            my %h;
            $h{ $_ } = log for @a;
            return \%h
        },
        3 => sub {
            my %h;
            keys %h = @a;
            @h{ @a } = @b;
            return \%h
        },
        4 => sub {
            my %h;
            @h{ @a } = @b;
            return \%h
        },
    })
}

$ perl5240o ~/tmp/x.pl 
     Rate    2    1    4    3
2 14381/s   --  -1% -25% -26%
1 14516/s   1%   -- -24% -26%
4 19198/s  33%  32%   --  -2%
3 19510/s  36%  34%   2%   --
    Rate    2    1    4    3
2 1427/s   --  -4% -25% -29%
1 1480/s   4%   -- -22% -26%
4 1895/s  33%  28%   --  -5%
3 2004/s  40%  35%   6%   --
   Rate    2    1    4    3
2 131/s   --  -6% -22% -29%
1 140/s   6%   -- -17% -25%
4 168/s  28%  20%   --  -9%
3 185/s  41%  33%  10%   --
    Rate    2    1    4    3
2 6.50/s   --  -6% -12% -18%
1 6.94/s   7%   --  -6% -12%
4 7.39/s  14%   6%   --  -7%
3 7.91/s  22%  14%   7%   --
$

Dave.

[vr]

I see, thank you everyone for answers. With these changes I'm getting same 2-1-4-3 consistent (and expected) sequence, though with less than 10% total difference, on older computer. Hashes of 100_000 keys were largest in linked article, but I understand that influence of preallocating was not its subject.

[Eily]

++ for correcting the benchmark (I actually wouldn't have guessed that log could weight so much on the result).

There are still two issues with your benchmark though. First, you forgot the comma in @b = map log @a;, which is parsed as @b = map(log(@a)) where an empty @b is obtained. I have no idea why this is not a syntax error though. Second, the for-loops variant do not use the precomputed values, but compute the logarithm on each iteration.

With this benchmark:

use strict;
use warnings;
use Benchmark qw/ cmpthese /;;

for my $count ( 100, 1_000, 10_000, 100_000 ) {
    my @array = map { log } 2 .. $count;
    print "-" x 10, "\nWith $count elements\n";
    cmpthese( -5, {
        1 => sub {
            my %h;
            keys %h = @array;
            $h{ $_ } = $_ for @array;
            return \%h
        },
        2 => sub {
            my %h;
            $h{ $_ } = $_ for @array;
            return \%h
        },
        3 => sub {
            my %h;
            keys %h = @array;
            @h{ @array } = @array;
            return \%h
        },
        4 => sub {
            my %h;
            @h{ @array } = @array;
            return \%h
        },
    });
}
__DATA__
----------
With 100 elements
    Rate   2   3   1   4
2 6956/s  -- -2% -3% -5%
3 7103/s  2%  -- -1% -3%
1 7162/s  3%  1%  -- -2%
4 7321/s  5%  3%  2%  --
----------
With 1000 elements
   Rate   2   4   1   3
2 621/s  -- -3% -4% -7%
4 638/s  3%  -- -1% -4%
1 644/s  4%  1%  -- -4%
3 668/s  7%  5%  4%  --
----------
With 10000 elements
    Rate   2   4   3   1
2 62.1/s  -- -0% -3% -4%
4 62.3/s  0%  -- -3% -3%
3 63.9/s  3%  3%  -- -1%
1 64.5/s  4%  3%  1%  --
----------
With 100000 elements
    Rate   2   4   1   3
2 4.75/s  -- -3% -6% -7%
4 4.89/s  3%  -- -3% -4%
1 5.03/s  6%  3%  -- -1%
3 5.08/s  7%  4%  1%  --

We can see that in this case, slicing is just a little faster than iterating. Your benchmark did answer vr's question though: slicing does not seem to include the preallocation optimization.

[ikegami]

slicing does not seem to include the preallocation optimization

I don't know how you can say given that the test shows no benefit from pre-allocating^[1].

But the reason the test shows no benefit from pre-allocating because the test is still flawed.

Lexical variables aren't freed when they go out of scope; they are kept around for use the next time the scope is entered. That means the hash is effectively pre-allocated for all tests!^[2].

$ perl -MDevel::Peek -e'
   sub x {
      my %h;
      Dump(%h, 0);
      keys(%h) = 100;
      Dump(%h, 0);
   }

   x() for 1..3;
' 2>&1 | grep MAX
  MAX = 7
  MAX = 127
  MAX = 127  <-- Preallocated even before C<< keys(%h) = 100; >>!
  MAX = 127
  MAX = 127  <-- Preallocated even before C<< keys(%h) = 100; >>!
  MAX = 127

Adding undef %h; should provide better results.

$ perl -MDevel::Peek -e'
   sub x {
      my %h;
      Dump(%h, 0);
      keys(%h) = 100;
      Dump(%h, 0);
      undef %h;
   }

   x() for 1..3;
' 2>&1 | grep MAX
  MAX = 7
  MAX = 127
  MAX = 7
  MAX = 127
  MAX = 7
  MAX = 127

---

1. The number are far too small to be meaningful, and one would expect the difference to grow as the hash size increases. (1 vs 2: 3%, 4%, 4%, 6%; 3 vs 4: -3%, 5%, 3%, 4%)
2. Well, except on the first pass of a given size of a given test.

[ikegami]

On second thought, a fresh hash is created on scope exit because a reference to the hash is returned.

$ perl -MDevel::Peek -e'
   sub x {
      my %h;
      Dump(%h, 0);
      keys(%h) = 100;
      Dump(%h, 0);
      return \%h;
   }

   x() for 1..3;
' 2>&1 | grep MAX
  MAX = 7
  MAX = 127
  MAX = 7
  MAX = 127
  MAX = 7
  MAX = 127

So all we have is a test that shows that @h{ @array } = @array; is faster than $h{ $_ } = $_ for @array;, but doesn't conclusively show any benefit from pre-allocating.